X Informatique MP/PC 2011

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

Corrigé

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

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(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);