(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.

Dans ce problème, on s'intéresse aux points fixes des fonctions , où est un ensemble fini. Le calcul effectif et efficace des points fixes de telles fonctions est un problème récurrent en informatique (transformation d'automates, vérification automatique de programmes, algorithmique des graphes, etc), et admet différentes approches selon la structure de et les propriétés de .

On suppose par la suite un entier strictement positif fixé et rangé dans une constante globale de même nom, et on pose . On représente une fonction par un tableau t de taille , autrement dit pour tout . Ainsi la fonction qui à associe modulo 10 est-elle représentée par le tableau

Les tableaux sont indexés à partir de 0 et la notation t est utilisée dans les questions pour désigner l'élément d'indice du tableau t , indépendamment du langage de programmation choisi. Quel que soit le langage utilisé, on suppose qu'il existe une primitive allouer(n) pour créer un tableau d'entiers de taille (le contenu des cases du nouveau tableau est à priori quelconque). On suppose les entiers machines signés, et on suppose que les entiers ne débordent pas de la capacité des entiers machines - en d'autres termes, les entiers machines représentent fidèlement ces entiers. On suppose que les tableaux peuvent être passés en argument - le type de passage de paramètre, par valeur ou par adresse, devra être précisé par le candidat si le comportement du code écrit venait à en dépendre. On note dans l'énoncé vrai et faux les deux valeurs possibles d'un booléen. Le candidat reste libre d'utiliser d'autres notations ou d'autres primitives, pourvu qu'elles existent dans le langage de son choix et qu'elles soient clairement
spécifiées. Enfin, le code écrit devra être sûr (pas d'accès invalide à un tableau, pas de division par zéro, et le programme termine, notamment) pour toutes valeurs des paramètres vérifiant les conditions données dans l'énoncé.

Le temps de calcul d'une procédure proc de paramètres est défini comme le nombre d'opérations (accès en lecture ou écriture à une case d'un tableau ou à une variable, appel à une des primitives données dans l'énoncé) exécutées par proc pour ces paramètres; on note le temps de calcul maximal pris sur tous les paramètres possibles pour fixé. On dit que proc s'exécute en temps linéaire si il existe des réels et un entier tels que pour tout . De même, on dit que proc s'exécute en temps logarithmique si il existe des réels et un entier tels que pour tout .

On rappelle que est un point fixe de la fonction si et seulement si .
Question 1 Écrire une procédure admet_point_fixe(t) qui prend en argument un tableau t de taille et renvoie vrai si la fonction représentée par t admet un point fixe, faux sinon. Par exemple, admet_point_fixe devra renvoyer vrai pour le tableau donné en introduction, puisque 9 est un point fixe de la fonction qui à associe modulo 10 .

Question 2 Écrire une procédure nb_points_fixes(t) qui prend en argument un tableau t de taille et renvoie le nombre de points fixes de la fonction représentée par t. Par exemple, nb_points_fixes devra renvoyer 1 pour le tableau donné en introduction, puisque 9 est le seul point fixe de .

On note l'itérée -ième de , autrement dit

Question 3 Écrire une procédure itere ( ) qui prend en premier argument un tableau t de taille représentant une fonction , en deuxième et troisième arguments des entiers de , et renvoie .

Question 4 Écrire une procédure nb_points_fixes_iteres qui prend en premier argument un tableau t de taille représentant une fonction , en deuxième argument un entier , et renvoie le nombre de points fixes de .

Un élément est dit attracteur principal de si et seulement si est un point fixe de , et pour tout , il existe un entier tel que .

Afin d'illustrer cette notion, on pourra vérifier que la fonction représentée par le tableau
ci-dessous admet 2 comme attracteur principal.

En revanche, on notera que la fonction donnée en introduction n'admet pas d'attracteur principal, puisque quel que soit l'entier .

Question 5 Écrire une procédure admet_attracteur_principal(t) qui prend en argument un tableau t de taille et renvoie vrai si et seulement si la fonction représentée par admet un attracteur principal, faux sinon. On ne requiert pas ici une solution efficace.

On suppose aux questions 6 et 7 que admet un attracteur principal. Le temps de convergence de en est le plus petit entier tel que soit un point fixe de . Pour la fonction ci-dessus, le temps de convergence en 4 est égal à 3 . En effet, , et 2 est un point fixe de . On note le temps de convergence de en .

Question 6 Écrire une procédure temps_de_convergence ( ) qui prend en premier argument un tableau t de taille représentant une fonction qui admet un attracteur principal, en deuxième argument un entier de , et renvoie le temps de convergence de en . On pourra admettre que vaut 0 si est un point fixe de , et si n'est pas un point fixe de .

Question 7 Écrire une procédure temps_de_convergence_max (t) qui prend en argument un tableau t de taille représentant une fonction qui admet un attracteur principal, et renvoie . On impose un temps de calcul linéaire en la taille du tableau. À titre d'indication, on pourra au besoin créer un deuxième tableau, qui servira d'intermédiaire au cours du calcul. On ne demande pas de démonstration du fait que le temps de calcul de la solution proposée est linéaire.

Toute procédure point_fixe(t) retournant un point fixe d'une fonction arbitraire est de complexité au mieux linéaire en . On s'intéresse maintenant à des améliorations possibles de cette complexité lorsque la fonction considérée possède certaines propriétés spécifiques. Nous examinons deux cas.

Le premier cas que nous considérons est celui d'une fonction croissante de dans . On rappelle qu'une fonction est croissante si et seulement si pour tous tels que .

On admet qu'une fonction croissante de dans admet toujours un point fixe.
À titre d'exemple, la fonction dont le tableau et le graphe sont donnés ci-dessous est croissante. Elle a deux points fixes, à savoir les entiers 5 et 7 .

Question 8 Écrire une procédure est_croissante(t) qui prend en argument un tableau t de taille et renvoie vrai si la fonction représentée par est croissante, faux sinon. On impose un temps de calcul linéaire en la taille du tableau. On ne demande pas de démonstration du fait que le temps de calcul de la solution proposée est linéaire.

Question 9 Écrire une procédure point_fixe(t) qui prend en argument un tableau t de taille représentant une fonction croissante , et retourne un entier tel que . On impose un temps de calcul logarithmique en la taille du tableau. On ne demande pas ici de démonstration du fait que le temps de calcul de la solution proposée est logarithmique, ceci étant le sujet de la question suivante.

Question 10 Démontrer que la procédure de la question 9 termine. On rappelle que pour prouver qu'une boucle termine, il suffit d'exhiber un entier positif , fonction des variables du programme, qui décroît strictement à chaque itération de boucle. Justifier que le temps de calcul est logarithmique en la taille du tableau.

On peut généraliser la notion de fonction croissante comme suit. On rappelle qu'une relation binaire sur un ensemble est une relation d'ordre si et seulement si elle est réflexive ( pour tout ), anti-symétrique (pour tous , si et , alors ), et transitive (pour tous , si et , alors ). Soit une relation d'ordre sur . Une fonction est croissante au sens de si et seulement si pour tous , implique .

Ceci généralise la notion de fonction croissante de dans , que l'on retrouve en prenant et la relation d'ordre . On s'intéresse dorénavant à d'autres relations d'ordre sur .

On dit qu'un élément de est un plus petit élément de au sens de si et seulement si, pour tout . On admet que pour tout ensemble fini , muni d'une relation d'ordre et qui admet un plus petit élément au sens de , pour toute fonction croissante au sens de , il existe un entier tel que est un point fixe de dans .

Question 11 Soit un ensemble fini quelconque muni d'une relation d'ordre et admettant un plus petit élément au sens de . Soit une fonction croissante au sens de , et soit un entier tel que soit un point fixe de dans . Démontrer que est en fait le plus petit point fixe de au sens de , autrement dit que pour tout autre point fixe de dans , on a .

Nous nous intéressons maintenant à un choix particulier d'ordre , appelé ordre de divisibilité et noté . Précisément, on note la relation d'ordre " divise " sur les entiers positifs, vraie si et seulement s'il existe un entier tel que . Ainsi, l'ensemble ordonné par divisibilité peut se représenter graphiquement comme suit.

D'après la définition donnée précédemment, une fonction croissante au sens de l'ordre de divisibilité est une fonction telle que pour tous dans , si , alors . Par exemple, la fonction représentée par le tableau ci-dessous est croissante au sens de l'ordre de divisibilité.

On remarque que, par la question 11, toute fonction de dans croissante au sens de l'ordre de divisibilité a un plus petit point fixe au sens de l'ordre de divisibilité.

On rappelle que le pgcd de deux entiers et est le plus grand entier non nul qui divise et . On étend cette définition à des entiers naturels quelconques, en convenant de définir le pgcd d'un entier et de 0 comme valant .

Question 12 Soit une fonction de dans , croissante au sens de l'ordre de divisibilité, et notons les points fixes de dans . Montrer que le plus petit point fixe de au sens de l'ordre de divisibilité est exactement le pgcd de .

Question 13 Écrire une procédure pgcd_points_fixes(t) qui prend en argument un tableau t de taille représentant une fonction de dans , croissante au sens de la divisibilité, et renvoie le pgcd de ses points fixes. On impose un temps de calcul logarithmique en la taille du tableau. On ne demande pas ici de démonstration du fait que le temps de calcul de la solution proposée est logarithmique, ceci étant le sujet de la question qui suit.

Question 14 Justifier que la procédure de la question 13 a un temps de calcul logarithmique en la taille du tableau.