X Informatique MP/PC 2013

ECOLE POLYTECHNIQUE -- ECOLE NORMALE SUPÉRIEURE DE CACHAN

ECOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2013 FILIÈRE MP HORS SPECIALITE INFO
FILIÈRE PC

COMPOSITION D'INFORMATIQUE -- B -- (XEC)

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

***

Points fixes de fonctions à domaine fini

Dans ce problème, on s'intéresse aux points fixes des fonctions f: E --> E, où 
E 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 E et les propriétés de f.

On suppose par la suite un entier strictement positif n > 0 fixé et rangé dans 
une constante
globale de même nom, et on pose En : {O, . . . ,n -- 1}. On représente une 
fonction f: En --> En
par un tableau t de taille n, autrement dit f(oe) =t [x] pour tout a: = O, . . 
. ,n -- 1. Ainsi la
fonction f0 qui a a: E E... associe 255 + 1 modulo 10 est--elle représentée par 
le tableau

l1l3l5l7l9lll3l5l7l9l_
thl 't... tl2l tl3l tl4l tl5l tl6l tl7l tl8l tl9l

Les tableaux sont indexés a partir de 0 et la notation t[i] est utilisée dans 
les questions pour
désigner l'élément d'indice 75 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 n (le contenu des cases du nouveau tableau est a 
priori quelconque).
On suppose les entiers machines signés, et on suppose que les entiers --n, --n 
+ 1, . . . ,n -- 1, n
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 a 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 a 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 p1, . . . ,pk est défini 
comme le nombre
d'opérations (accès en lecture ou écriture a une case d'un tableau ou a une 
variable, appel a
une des primitives données dans l'énoncé) exécutées par proc pour ces 
paramètres; on note
T(proc, n) le temps de calcul maximal pris sur tous les paramètres possibles 
pour n fixé. On
dit que proc s'exécute en temps linéaire si il existe des réels or, 5 > 0 et un 
entier N 2 0 tels
que 04.71 £ T(proc,n) $ 5.71 pour tout n 2 N. De même, on dit que proc 
s'exécute en temps
logarithmique si il existe des réels or, 5 > 0 et un entier N 2 0 tels que 
alogn £ T(proc, n) S
filogn pour tout n 2 N.

Partie I. Recherche de point fixe : cas général
On rappelle que a: est un point fine de la fonction f si et seulement si f (a:) 
= 517.

Question 1 Écrire une procédure admet_point_fîxe (t) qui prend en argument un 
tableau
t de taille n et renvoie vrai si la fonction f : En --> En représentée par t 
admet un point fixe,
faux sinon. Par exemple, admet_point_fîxe devra renvoyer vrai pour le tableau 
donné en
introduction, puisque 9 est un point fixe de la fonction fo qui a a: associe 
2513 + 1 modulo 10.

Question 2 Écrire une procédure nb_points_fixes(t) qui prend en argument un 
tableau t
de taille n et renvoie le nombre de points fixes de la fonction f : En --> En 
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 fo.

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

fkï En _' En
sa ... f>...>.
--\,_/
kfois

Question 3 Écrire une procédure itere (t,x,k) qui prend en premier argument un 
tableau
t de taille n représentant une fonction f : E,, --> E... en deuxième et 
troisième arguments des
entiers a:, 16 de E... et renvoie fk(aî).

Question 4 Écrire une procédure nb_points_fixes_iteres (t ,k) qui prend en 
premier argu--
ment un tableau t de taille n représentant une fonction f: E,, --> E... en 
deuxième argument un

entier 16 2 O, et renvoie le nombre de points fixes de f k .

Un élément ?: EUR En est dit attracteur principal de f : En --> En si et 
seulement si ?: est un
point fixe de f, et pour tout a: E E... il existe un entier 16 2 0 tel que 
fk(OE) : 75.

Afin d'illustrer cette notion, on pourra vérifier que la fonction f1 
représentée par le tableau

ci--dessous admet 2 comme attracteur principal.

l5l5l2l2l0l2l2l
t[0] t[1] t[2] t[3] t[4] t[5] t[6]

En revanche, on notera que la fonction fo donnée en introduction n'admet pas 
d'attracteur
principal, puisque fâ"(0) # 9 quel que soit l'entier k 2 0.

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

On suppose aux questions 6 et 7 que f admet un attracteur principal. Le temps 
de convergence
de f en a: EUR En est le plus petit entier le 2 0 tel que f ""(a:) soit un 
point fixe de f. Pour la fonction
f1 ci--dessus, le temps de convergence en 4 est égal a 3. En effet, f1(4) : O, 
fÎ(4) : 5, fÎ(4) : 2,
et 2 est un point fixe de fl. On note tc(f, a:) le temps de convergence de f en 
517.

Question 6 Écrire une procédure temps_de_convergence (t , x) qui prend en 
premier argument
un tableau t de taille n représentant une fonction f : En --> En qui admet un 
attracteur principal,
en deuxième argument un entier a: de E... et renvoie le temps de convergence de 
f en a:. On pourra
admettre que tc(f, a:) vaut 0 si a: est un point fixe de f, et 1 + tc(f, f(a7)) 
si 56 n'est pas un point
fixe de f.

Question 7 Écrire une procédure temps_de_convergence_max(t) qui prend en 
argument un
tableau t de taille n représentant une fonction f : En --> En qui admet un 
attracteur principal,

et renvoie _ rÛnax 1tc( f, 75). On impose un temps de calcul linéaire en la 
taille n du tableau. A
Z: ...'ÏL--

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.

Partie II. Recherche efficace de points fixes

rToute procédure point-fixe (t) retournant un point fixe d'une fonction 
arbitraire est de
complexité au mieux linéaire en n. On s'intéresse maintenant a 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.

Premier cas.

Le premier cas que nous considérons est celui d'une fonction croissante de En 
dans En. On
rappelle qu'une fonction f : En --> En est croissante si et seulement si pour 
tous a:,y EUR En tels

que a? £ % f(â?) £ f(y)-
On admet qu'une fonction croissante de En dans En admet toujours un point fixe.

À titre d'exemple, la fonction dont le tableau et le graphe sont donnés 
ci--dessous est crois--
sante. Elle a deux points fixes, a savoir les entiers 5 et 7.

Question 8 Écrire une procédure est_croissante (t) qui prend en argument un 
tableau t de
taille n et renvoie vrai si la fonction représentée par t est croissante, faux 
sinon. On impose un
temps de calcul linéaire en la taille n 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
n représentant une fonction croissante f : E, --> E... et retourne un entier a: 
EUR En tel que f (a:) = a:.
On impose un temps de calcul logarithmique en la taille n 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 a chaque itération de boucle. Justifier que 
le temps de calcul
est logarithmique en la taille n du tableau.

Deuxième cas.

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

a? 5 y implique f (a?) 5 f (y)-

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

On dit qu'un élément m de E est un plus petit élément de E au sens de 5 si et 
seulement si,
pour tout a: E E, m 5 a:. On admet que pour tout ensemble fini E, muni d'une 
relation d'ordre
5 et qui admet un plus petit élément m au sens de 5, pour toute fonction 
croissante f : E --> E
au sens de 5, il existe un entier 16 2 0 tel que fk(m) est un point fixe de f 
dans E.

Question 11 Soit E un ensemble fini quelconque muni d'une relation d'ordre 5 et 
admettant
un plus petit élément m au sens de 5. Soit f: E --> E une fonction croissante 
au sens de j, et
soit 16 2 0 un entier tel que fk(m) soit un point fixe de f dans E. Démontrer 
que fk(m) est en

fait le plus petit point fixe de f au sens de j, autrement dit que pour tout 
autre point fixe a: de
f dans E, on a fk(m) 5 517.

Nous nous intéressons maintenant a un choix particulier d'ordre 5, appelé ordre 
de divisibilîte'
et noté \. Précisément, on note a \ b la relation d'ordre "& divise b" sur les 
entiers positifs, vraie
si et seulement s'il existe un entier c 2 0 tel que ca : (9. Ainsi, l'ensemble 
E... ordonné par
divisibilité peut se représenter graphiquement comme suit.

/\\
\

îÀî . .
\1%

D'après la définition donnée précédemment, une fonction f: E,... --> En 
croissante au sens de
l'ordre de divisibilîte' est une fonction telle que pour tous a:, y dans E... 
si a: l y, alors f (a:) \ f (y)
Par exemple, la fonction représentée par le tableau ci--dessous est croissante 
au sens de l'ordre
de divisibilité.

l0l2l4l6l4l8l0l2l0lôl_
thl tlll t12l tlBl tl4l tl5l tlôl tl7l tl8l tl9l

On remarque que, par la question 11, toute fonction de E,... dans En 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 a: 2 1 et y 2 1 est le plus grand 
entier non nul
qui divise a: et y. On étend cette définition a des entiers naturels 
quelconques, en convenant de
définir le pgcd d'un entier a: 2 0 et de 0 comme valant 517.

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

Question 13 Écrire une procédure pgcd_points_fîxes (t) qui prend en argument un 
tableau
t de taille n représentant une fonction de E,... dans E... croissante au sens 
de la divisibilité, et
renvoie le pgcd de ses points fixes. On impose un temps de calcul logarithmique 
en la taille n 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 n du tableau.