X Informatique MP/PC 2011

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