(Durée : 2 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.

La notion mathématique de permutation formalise la notion intuitive de réarrangement d'objets discernables. La permutation est une des notions fondamentales de la combinatoire, l'étude des dénombrements et des probabilités discrètes. Elle sert par exemple à étudier sudoku, Rubik's cube, etc. Plus généralement, on retrouve la notion de permutation au cœur de certaines théories des mathématiques, comme celle des groupes, des déterminants, de la symétrie, etc.

Une permutation est une bijection d'un ensemble dans lui-même. On ordonne un ensemble fini de taille en numérotant ses éléments à partir de . En pratique, puisque seuls les réarrangements des éléments de nous intéressent, on considère l'ensemble des indices qui sont les entiers de 1 à , bornes comprises. On représente alors simplement une application sur par un tableau de taille dont les éléments sont des indices. Autrement dit, est , où désigne le contenu de la case d'indice du tableau , et est lui même un indice. On notera que est une permutation, si et seulement si les contenus des cases de sont exactement les entiers de .

Dans tout le problème, les tableaux sont indicés à partir de 1 . L'accès à la case d'un tableau de taille est noté dans l'énoncé, pour entier compris entre 1 et au sens large. Quel que soit le langage utilisé, on suppose que les tableaux peuvent être passés comme arguments des fonctions et renvoyés comme résultat. En outre, il existe une primitive allouer( ) pour créer un tableau de taille (le contenu des cases du nouveau tableau ont des valeurs inconnues), et une primitive taille( ) qui renvoie la taille du tableau . Enfin, les booléens vrai et faux sont utilisés dans certaines questions de ce problème. Bien évidemment, le candidat reste libre d'utiliser les notations propres au langage dans lequel il compose.

Question 1 Écrire une fonction estPermutation(t) qui prend une application (représentée par un tableau d'entiers ) en argument et vérifie que représente bien une permutation. Autrement dit, la fonction renvoie vrai si représente une permutation et faux sinon.

On suppose désormais, sans avoir à le vérifier, que les tableaux d'entiers (de taille ) donnés en arguments aux fonctions à écrire représentent bien des permutations (sur ). Dans cet esprit, on confond par la suite les permutations et les tableaux d'entiers qui les représentent en machine. Plus généralement, si l'énoncé contraint les arguments des fonctions à écrire, le code de ces fonction sera écrit en supposant que ces contraintes sont satisfaites.

Question 2 Écrire une fonction composer qui prend deux permutations sur en arguments et renvoie la composée de et de . On rappelle que la composée de deux applications est définie comme associant à .

Question 3 Écrire une fonction inverser( ) qui prend une permutation en argument et renvoie la permutation inverse . On rappelle que l'application inverse d'une bijection est définie comme associant à .

La notation désigne composée fois, - la définition est correcte en raison de l'associativité de la composition. On définit l'ordre d'une permutation comme le plus petit entier non nul tel que est l'identité.

Question 4 Donner un exemple de permutation d'ordre 1 et un exemple de permutation d'ordre .

Question 5 En utilisant la fonction composer, écrire une fonction ordre(t) qui renvoie l'ordre de la permutation .

La période d'un indice pour la permutation est définie comme le plus petit entier non nul tel que .

Question 6 Écrire une fonction periode qui prend en arguments une permutation et un indice et qui renvoie la période de pour .

L'orbite de pour la permutation est l'ensemble des indices tels qu'il existe avec .

Question 7 Écrire une fonction estDansOrbite( ) qui prend en arguments une permutation et deux indices, et qui renvoie vrai si est dans l'orbite de et faux sinon.

Une transposition est une permutation qui échange deux éléments distincts et laisse les autres inchangés.

Question 8 Écrire une fonction estTransposition(t) qui prend une permutation en argument et renvoie vrai si est une transposition et faux sinon.

Un cycle (simple) est une permutation dont exactement une des orbites est de taille strictement supérieure à un. Toutes les autres orbites, s'il y en a, sont réduites à des singletons.

Question 9 Écrire une fonction estCycle( ) qui prend une permutation en argument et renvoie vrai si est un cycle et faux sinon.

On commence par écrire une fonction qui calcule les périodes de tous les éléments de et qui soit la plus efficace possible.

Question 10 Écrire une fonction periodes( ) qui renvoie le tableau des périodes. C'est-à-dire que est la période de l'indice pour la permutation . On impose un coût linéaire, c'est-à-dire que la fonction periodes effectue au plus opérations avec constant et taille de .

On envisage ensuite le calcul efficace de l'itérée . On remarque en effet que est égal à , où est le reste de la division euclidienne de par la période de .

Question 11 Écrire une fonction itererEfficace ( ) qui calcule l'itérée en utilisant le tableau des périodes. On rappelle que est l'identité. Si besoin est, les candidats pourront utliser la primitive reste( ) qui renvoie le reste de la division euclidienne de par ( , .

La fonction ordre de la question 5 n'est pas très efficace. En effet, elle procède à de l'ordre de compositions de permutations, où est l'ordre de la permutation passée en argument. Or, est de l'ordre de dans le cas le pire. On peut améliorer considérablement le calcul de l'ordre en constatant que l'ordre d'une permutation est le plus petit commun multiple des périodes des éléments.

Question 12 Donner un exemple de permutation dont l'ordre excède strictement la taille.

Question 13 Écrire une fonction qui prend en arguments deux entiers strictement positifs et , et renvoie le plus grand diviseur commun de et . On impose un calcul efficace selon l'algorithme d'Euclide qui repose sur l'identité , avec reste de la division euclidienne de par .

Question 14 Écrire une fonction qui prend en arguments deux entiers strictement positifs et , et renvoie le plus petit commun multiple de et . On utilisera l'identité .

Question 15 Écrire une fonction ordreEfficace qui calcule l'ordre de la permutation selon la méthode efficace. On cherchera à minimer le nombre d'appels à ppcm effectués.