X Informatique MP/PC 2011

Thème de l'épreuve Sur les permutations
Principaux outils utilisés boucle for, boucle while, récursivité

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


ECOLE POLYTECHNIQUE ­ ECOLE NORMALE SUPERIEURE DE CACHAN
ECOLE SUPERIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2011

FILIERE

MP HORS SPECIALITE INFO
FILIERE PC

COMPOSITION D'INFORMATIQUE ­ B ­ (XEC)
(Duree : 2 heures)
L'utilisation des calculatrices n'est pas autorisee pour cette epreuve.
Le langage de programmation choisi par le candidat doit etre specifie en tete 
de la copie.

Sur les permutations

La notion mathematique de permutation formalise la notion intuitive de 
rearrangement d'objets discernables. La permutation est une des notions 
fondamentales de la combinatoire, l'etude
des denombrements et des probabilites discretes. Elle sert par exemple a 
etudier sudoku, Rubik's
cube, etc. Plus generalement, on retrouve la notion de permutation au coeur de 
certaines theories
des mathematiques, comme celle des groupes, des determinants, de la symetrie, 
etc.
Une permutation est une bijection d'un ensemble E dans lui-meme. On ordonne un 
ensemble
E fini de taille n en numerotant ses elements a partir de 1 : x1 , x2 , . . . 
xn . En pratique, puisque
seuls les rearrangements des elements de E nous interessent, on considere 
l'ensemble En des
indices qui sont les entiers de 1 a n, bornes comprises. On represente alors 
simplement une
application f sur En par un tableau t de taille n dont les elements sont des 
indices. Autrement
dit, f (k) est t[k], ou t[k] designe le contenu de la case d'indice k du 
tableau t, et t[k] est lui
meme un indice. On notera que f est une permutation, si et seulement si les 
contenus des cases
de t sont exactement les entiers de En .
Dans tout le probleme, les tableaux sont indices a partir de 1. L'acces a la 
ieme case d'un
tableau t de taille n est note t[i] dans l'enonce, pour i entier compris entre 
1 et n au sens
large. Quel que soit le langage utilise, on suppose que les tableaux peuvent 
etre passes comme
arguments des fonctions et renvoyes comme resultat. En outre, il existe une 
primitive allouer(n)
pour creer un tableau de taille n (le contenu des cases du nouveau tableau ont 
des valeurs
inconnues), et une primitive taille(t) qui renvoie la taille du tableau t. 
Enfin, les booleens vrai
et faux sont utilises dans certaines questions de ce probleme. Bien evidemment, 
le candidat reste
libre d'utiliser les notations propres au langage dans lequel il compose.

1

Partie I. Ordre d'une permutation

Question 1 Ecrire une fonction estPermutation(t) qui prend une application 
(representee par
un tableau d'entiers t) en argument et verifie que t represente bien une 
permutation. Autrement
dit, la fonction renvoie vrai si t represente une permutation et faux sinon.
On suppose desormais, sans avoir a le verifier, que les tableaux d'entiers (de 
taille n) donnes
en arguments aux fonctions a ecrire representent bien des permutations (sur En 
). Dans cet
esprit, on confond par la suite les permutations et les tableaux d'entiers qui 
les representent en
machine. Plus generalement, si l'enonce contraint les arguments des fonctions a 
ecrire, le code
de ces fonction sera ecrit en supposant que ces contraintes sont satisfaites.
Question 2 Ecrire une fonction composer(t,u) qui prend deux permutations sur En 
en arguments et renvoie la composee t  u de t et de u. On rappelle que la 
composee f  g de deux
applications est definie comme associant f (g(x)) a x.
Question 3 Ecrire une fonction inverser(t) qui prend une permutation t en 
argument et renvoie
la permutation inverse t-1 . On rappelle que l'application inverse f -1 d'une 
bijection est definie
comme associant x a f (x).
La notation tk designe t composee k fois, -- la definition est correcte en 
raison de l'associativite de la composition. On definit l'ordre d'une 
permutation t comme le plus petit entier k
non nul tel que tk est l'identite.
Question 4 Donner un exemple de permutation d'ordre 1 et un exemple de 
permutation
d'ordre n.
Question 5 En utilisant la fonction composer, ecrire une fonction ordre(t) qui 
renvoie l'ordre
de la permutation t.

Partie II. Manipuler les permutations

La periode d'un indice i pour la permutation t est definie comme le plus petit 
entier k non nul
tel que tk (i) = i.
Question 6 Ecrire une fonction periode(t,i) qui prend en arguments une 
permutation t et un
indice i et qui renvoie la periode de i pour t.
L'orbite de i pour la permutation t est l'ensemble des indices j tels qu'il 
existe k avec
tk (i) = j.
Question 7 Ecrire une fonction estDansOrbite(t,i,j) qui prend en arguments une 
permutation t
et deux indices, et qui renvoie vrai si j est dans l'orbite de i et faux sinon.

2

Une transposition est une permutation qui echange deux elements distincts et 
laisse les autres
inchanges.
Question 8 Ecrire une fonction estTransposition(t) qui prend une permutation t 
en argument
et renvoie vrai si t est une transposition et faux sinon.
Un cycle (simple) est une permutation dont exactement une des orbites est de 
taille strictement superieure a un. Toutes les autres orbites, s'il y en a, 
sont reduites a des singletons.
Question 9 Ecrire une fonction estCycle(t) qui prend une permutation t en 
argument et renvoie
vrai si t est un cycle et faux sinon.

Partie III. Operations efficaces sur les permutations

On commence par ecrire une fonction qui calcule les periodes de tous les 
elements de En et
qui soit la plus efficace possible.
Question 10 Ecrire une fonction periodes(t) qui renvoie le tableau p des 
periodes. C'est-a-dire
que p[i] est la periode de l'indice i pour la permutation t. On impose un cout 
lineaire, c'est-a-dire
que la fonction periodes effectue au plus C · n operations avec C constant et n 
taille de t.
On envisage ensuite le calcul efficace de l'iteree tk . On remarque en effet 
que tk (i) est egal a
ou r est le reste de la division euclidienne de k par la periode de i.

tr (i),

Question 11 Ecrire une fonction itererEfficace(t,k) (k  0) qui calcule l'iteree 
tk en utilisant
le tableau des periodes. On rappelle que t0 est l'identite. Si besoin est, les 
candidats pourront
utliser la primitive reste(a,b) qui renvoie le reste de la division euclidienne 
de a par b (a  0,
b > 0).
La fonction ordre de la question 5 n'est pas tres efficace. En effet, elle 
procede a de l'ordre de
o compositions depermutations, ou o est l'ordre de la permutation passee en 
argument. Or, o
est de l'ordre de n n dans le cas le pire. On peut ameliorer considerablement 
le calcul de l'ordre
en constatant que l'ordre d'une permutation est le plus petit commun multiple 
des periodes des
elements.
Question 12 Donner un exemple de permutation dont l'ordre excede strictement la 
taille.
Question 13 Ecrire une fonction pgcd(a,b) qui prend en arguments deux entiers 
strictement
positifs a et b, et renvoie le plus grand diviseur commun de a et b. On impose 
un calcul efficace
selon l'algorithme d'Euclide qui repose sur l'identite pgcd(a,b) = pgcd(b,r), 
avec r reste de la
division euclidienne de a par b.
Question 14 Ecrire une fonction ppcm(a,b) qui prend en arguments deux entiers 
strictement positifs a et b, et renvoie le plus petit commun multiple de a et 
b. On utilisera l'identite
ppcm(a,b) = (a × b)/pgdc(a,b).

3

Question 15 Ecrire une fonction ordreEfficace(t) qui calcule l'ordre de la 
permutation t selon
la methode efficace. On cherchera a minimer le nombre d'appels a ppcm effectues.

4

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP/PC 2011 -- Corrigé
Ce corrigé est proposé par Arnaud Borde (École polytechnique) ; il a été relu
par Céline Chevalier (Enseignant-chercheur à l'université) et Guillaume Batog 
(ENS
Cachan).

Cette épreuve est commune aux filières PC et MP option sciences de l'ingénieur.
Elle ne compte que pour l'admission.
Le sujet propose l'étude des permutations de En = [[ 1 ; n ]] et de 
quelques-unes
de leurs propriétés : ordre, période et orbite. Il est divisé en trois parties 
de tailles et
difficultés équivalentes, à l'exception des questions 9 et 10 qui demandent 
davantage
de réflexion.
· La première partie s'attache à définir les permutations, les composer, les 
inverser, et enfin à définir l'ordre d'une permutation.
· La deuxième introduit les notions de période et d'orbite. Elle exploite les 
cas
particuliers importants que sont les transpositions et les cycles.
· La troisième partie utilise les propriétés mathématiques des permutations pour
construire un algorithme efficace de calcul de l'ordre d'une permutation.
La plupart des questions demandent d'écrire du code. Dans ce corrigé, ce dernier
a été rédigé en Maple car il s'agit du langage le plus utilisé en prépa, même 
s'il
est plus destiné au calcul formel qu'à la programmation. D'autres langages, 
comme
C++, Caml, Pascal, Java et Python, sont autorisés pour cette épreuve. Les 
fonctions
demandées n'utilisant que la syntaxe de base de Maple, vous pourrez sans 
difficulté
les réécrire dans le langage que vous préférez.
C'est un sujet plus austère que les années précédentes, mais il reste à la 
portée
d'un élève ayant un peu préparé cette épreuve, qui est spécifique à l'X. 
L'énoncé dans
son ensemble est clair et les questions sont toutes bien détaillées. Comme 
souvent,
il était judicieux de lire l'énoncé dans son ensemble afin de repérer les 
questions qui
pouvaient rapporter facilement des points.
Rédiger du code sur papier demande un soin particulier. Il est rare de produire
une procédure juste dès le premier jet : un brouillon s'impose donc pour éviter 
de
multiples ratures et rajouts. De même, afin de faciliter le travail du 
correcteur, il est
important de l'indenter et de l'espacer afin d'en dégager la structure (quelles 
sont les
parties qui le composent, à quelles boucles appartiennent les instructions). Il 
ne faut
pas non plus hésiter à insérer des commentaires (avec # sous Maple) et à 
expliquer
les grandes lignes de sa démarche.

Indications
I. Ordre d'une permutation
1 Chercher les deux conditions sous lesquelles un tableau ne représente pas une
permutation.
2 Retranscrire dans le code la formule de l'énoncé pour chaque indice du 
tableau.
3 Par définition, t-1 [t[i]] = i pour tout i  En .
4 Penser aux permutations circulaires.
5 Écrire une fonction auxiliaire qui teste si une permutation est l'identité.

II. Manipuler les permutations
6 Calculer successivement tk [i] pour k = 1, 2, . . . sans utiliser la fonction 
composer.
7 S'inspirer du code de la fonction periode pour parcourir l'orbite.
8 Une transposition est une permutation qui diffère de l'identité en exactement
deux indices.
9 Vérifier que tous les indices i tel que t[i] 6= i appartiennent bien à la 
même orbite.

III. Opérations efficaces sur les permutations
10 Pour obtenir un coût linéaire, remarquer que la somme des tailles des 
orbites vaut
la taille de la permutation.
11 Traiter chaque élément de t séparément.
12 Composer par exemple deux permutations de taille 5 et d'ordres respectifs 2 
et 3.
15 Utiliser ppcm(a, b, c) = ppcm(a, ppcm(b, c)).

Afin de rester proche du sujet tout en ayant des codes fonctionnels
sous Maple, le code des deux primitives proposées par l'énoncé (allouer
et taille) est donné ici. Ces deux fonctions font appel aux fonctions Array
et ArrayNumElems de Maple que des élèves de CPGE ne sont pas censés
connaître.
allouer := proc(n)
RETURN( Array(1..n) );
end;
taille := proc(t)
RETURN(ArrayNumElems(t));
end;
Dans ce cas précis, la fonction allouer(n) renvoie un tableau de taille n
dont tous les éléments valent 0. Néanmoins, l'énoncé est ici strictement 
respecté et on suppose dans la suite que le contenu des cases après cette 
allocation est inconnu. De manière plus générale, il est important de veiller à
l'initialisation des variables.
Il est aussi possible d'utiliser la structure de liste de Maple qui donnerait :
allouer := proc(n)
RETURN( [seq(0, i = 1 .. n)] );
end;
taille := proc(t)
RETURN(nops(t));
end;
Ici c'est la commande seq qui permet d'initialiser la liste avec le nombre
d'éléments voulus (des zéros en l'occurence). Et c'est la fonction nops qui
donne le nombre d'éléments dans la liste.
Dans Maple, contrairement aux autres langages de programmation,
les indices de tableaux commencent par défaut à 1 et non à 0. Si vous utilisez
un autre langage, il est préférable de préciser la convention que vous adoptez
pour les indices car le sujet suppose qu'ils débutent à 1. Les rapports du
concours des années précédentes recommandent d'ailleurs de suivre l'énoncé
plutôt que les conventions du langage utilisé, quitte à écrire un code qui
n'est pas compilable/exécutable. L'utilisation de la structure Array permet
de choisir les indices de début et de fin du tableau.
Dans l'ensemble du corrigé, les conventions de Maple pour les variables
booléennes sont utilisées : true pour vrai et false pour faux.

I. Ordre d'une permutation
1 Si t est une permutation, alors par définition (c'est une bijection) on y 
trouve
une et une seule fois chaque entier de [[ 1 ; n ]]. Pour tout indice de t, 
effectuons un
test en deux parties :
· une première où l'on regarde si l'entier appartient bien à En ,
· une seconde où l'on vérifie que l'entier n'est pas déjà apparu.

Dans le code, cela représente une boucle for dans laquelle les deux tests sont
effectués. Pour vérifier que chaque entier apparaît une seule fois, utilisons 
un tableau
de valeurs booléennes present de la même taille que t et initialisé à false. 
Chaque
élément present[i] permet de savoir si l'entier i a déjà été rencontré. Si l'on 
rencontre i alors que present[i] vaut true, alors t n'est pas une permutation 
et le code
renvoie false ; sinon present[t[i]] est mis à jour à true. Si on sort de la 
boucle
for sans retourner false, alors le tableau t est constitué de n entiers deux à 
deux
distincts appartenant à En , de cardinal n. Ainsi, t représente bien une 
permutation
de En et le code renvoie true.
estPermutation := proc(t)
local compte, tailleT, i;
tailleT := taille(t);
present := allouer(tailleT);
for i from 1 to tailleT do
present[i] := false;
od;
# vérifie qu'on ne dépasse pas les bornes
# et que de chaque entier est présent au plus une fois
for i from 1 to tailleT do
if t[i] < 1 or t[i] > tailleT then
RETURN(false);
elif present[t[i]] = true then
RETURN(false);
else
present[t[i]] := true
fi;
od;
RETURN(true);
end;
C'est ici la fonction RETURN qui permet d'arrêter la procédure et de renvoyer 
la valeur false. Par défaut Maple renvoie la dernière valeur calculée,
néanmoins il est plus prudent d'expliciter la valeur retournée avec un RETURN.
L'énoncé simplifie grandement la suite en indiquant que les arguments
satisfont les contraintes imposées. Ainsi, il est inutile d'alourdir le code 
avec
quantité de tests vérifiant par exemple que les tableaux donnés en arguments
représentent bien des permutations ou qu'ils ont la même taille lorsqu'on va
vouloir les comparer ou les composer.
2 Appliquons la formule de l'énoncé mot pour mot : il s'agit de calculer 
t[u[i]] pour
chaque i. On réalise cela grâce à une boucle for qui permet de parcourir tous 
les
entiers de En . Les résultats sont stockés dans un tableau composee qui est 
retourné
à la fin de la procédure.
composer := proc(t, u)
local composee, tailleT, i;
tailleT := taille(t);
composee := allouer(tailleT);