X Informatique MP/PC 2013

Thème de l'épreuve Points fixes de fonctions à domaine fini
Principaux outils utilisés boucles for, boucles while, structures conditionnelles, récursivité
Mots clefs point fixe, attracteur principal, temps de convergence, fonction croissante, divisibilité, relation d'ordre

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

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP/PC 2013 -- Corrigé
Ce corrigé est proposé par Arnaud Borde (École polytechnique) ; il a été relu 
par
Simon Billouet (ENS Cachan) et Benjamin Monmege (ENS Cachan).

Cette épreuve est commune aux filières PC et MP option sciences de l'ingénieur
et ne compte que pour l'admission. Ce corrigé a été rédigé en Maple car ce 
langage
est 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, Java et Python étaient 
autorisés.
Les fonctions écrites n'utilisant que la syntaxe de base, vous pourrez sans 
difficulté
les réécrire dans le langage de votre choix.
Le sujet propose l'étude des points fixes de fonctions à domaine fini, en se 
basant
sur les ensembles En = {0, . . . , n - 1}. Il est composé de deux parties.
· La première s'intéresse au cas général et aux notions d'attracteur principal 
et
de temps de convergence.
· La seconde examine le cas particulier des fonctions croissantes, d'abord au 
sens
usuel du terme puis généralisé avec une relation d'ordre binaire quelconque. Le
sujet se termine avec l'exemple de la divisibilité en tant que relation d'ordre.
Cette année, quatre questions ne demandent pas d'écrire de code. Deux d'entre
elles (les questions 11 et 12) consistent en des démonstrations de 
mathématiques et
les deux autres demandent de justifier la complexité d'un code.
C'est un sujet plus difficile que les années précédentes ; en particulier, les 
questions demandant d'écrire des algorithmes de complexité logarithmique 
peuvent être
considérées comme hors-programme. En dehors de ces questions, il est à la portée
d'un élève ayant un minimum préparé cette épreuve spécifique à ce concours. Une
bonne maîtrise de la programmation récursive permet de gagner du temps sur un 
certain nombre de questions. L'énoncé dans son ensemble est clair et les 
questions bien
détaillées. On regrettera juste la remarque sur le type de passage par 
paramètre, qui
en plus d'être elle aussi hors-programme, est inutile pour la plupart des 
candidats,
cette distinction n'existant pas en Maple.
Rédiger du code sur papier est un exercice auquel il convient d'accorder un soin
particulier. Un code (sur papier ou sur ordinateur) est très rarement juste dès 
le début : un brouillon s'impose donc pour éviter de multiples ratures et 
rajouts. De même,
afin de faciliter la lecture du code par le 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 à commenter (avec # sous Maple) son code, surtout s'il est long, et à 
expliquer les grandes
lignes de sa démarche.

Indications
Partie I. Recherche de point fixe : cas général
1 On peut s'arrêter dès que l'on rencontre un point fixe.
2 Parcourir le tableau et tenir à jour un compteur.
3 Le code peut être écrit soit avec une boucle for soit de manière récursive.
4 Combiner les codes des questions 2 et 3.
5 Remarquer qu'une fonction qui admet un attracteur principal n'a qu'un seul 
point
fixe et que cet attracteur principal est atteint en au plus n itérations pour 
chaque
entier.
6 Utiliser la formule de récurrence donnée par l'énoncé.
7 Construire récursivement grâce à la formule de l'énoncé un tableau contenant 
tous
les temps de convergence.

Partie II. Recherche efficace de points fixes
8 La condition de croissance d'une fonction f représentée par un tableau t est
donnée par t[i] 6 t[i + 1] pour 0 6 i 6 n - 2.
9 Procéder par dichotomie sur le domaine En en utilisant l'assertion de 
l'énoncé.
10 Un algorithme logarithmique a pour particularité le fait que doubler la 
taille
du tableau rajoute un nombre fixe d'instructions (correspondant à un « tour
de boucle »).
11 Appliquer k fois la croissance de f .
12 Ne pas oublier que 1 divise tous les entiers et en particulier tous les xm .
13 Utiliser le résultat de la démonstration précédente.
14 Regarder comment évolue la suite des itérés de 1 par f .

Dans Maple, contrairement à la plupart des autres langages de programmation, 
les indices de tableaux commencent par défaut à 1 et non à 0. Il est
préférable de préciser la convention que vous adoptez pour les indices car le
sujet suppose qu'ils débutent à 0. 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.
C'est ainsi que ce corrigé a été rédigé.
L'énoncé travaillant beaucoup avec des tableaux, il y a deux opérations
courantes qui reviennent souvent : obtenir la taille d'un tableau et initialiser
un tableau de taille donnée avec une valeur donnée. L'énoncé nous indique
l'existence d'une fonction allouer, qui permet uniquement d'allouer la mémoire 
nécessaire à un tableau de taille n donnée (ce qui est surtout utile dans
d'autres langages que Maple, comme C ou Java). Comme elle ne garantit rien
sur l'initialisation du tableau, une boucle d'initialisation est nécessaire 
après
son appel. Par exemple pour définir un tableau t de taille n rempli de zéros,
on écrit (car les indices d'un tableau de taille n vont de 0 à n - 1) :
t := allouer(n);
for i from 0 to n-1 do
t[i]:=0;
od;
On peut aussi utiliser l'expression [seq(0, i=0..n-1)] pour initialiser un
tableau de taille n. Pour ce corrigé, nous avons choisi la fonction nops()
pour obtenir le nombre d'éléments d'un tableau. Les années précédentes, une
fonction taille était supposée exister, sur le modèle d'allouer.

I. Recherche de point fixe : cas général
1 Il s'agit ici de parcourir le tableau et de retourner vrai dès que l'on 
rencontre un
point fixe. faux est retourné si l'on a parcouru l'ensemble du tableau sans 
trouver de
point fixe. Une boucle for est utilisée pour parcourir le tableau et l'on met à 
profit
le fait qu'une instruction RETURN() arrête immédiatement la procédure.
admet_point_fixe:=proc(t)
local i;
for i from 0 to nops(t)-1 do
# on teste si i est un point fixe
if t[i] = i then
RETURN(vrai);
fi;
od;
# on ne passe ici que si on a parcouru l'ensemble
# du tableau sans trouver de point fixe
RETURN(faux);
end;

2 Cette question est très similaire à la précédente, la différence étant qu'au 
lieu de
retourner vrai lorsque l'on rencontre un point fixe, un compteur pts_fixes, 
initialisé
à 0, est incrémenté.
nb_points_fixes:=proc(t)
local i, pts_fixes;
pts_fixe := 0;
for i from 0 to nops(t)-1 do
if t[i] = i then
pts_fixes := pts_fixes + 1;
fi;
od;
RETURN(pts_fixes);
end;
3 Traitons cette question avec un code récursif. En effet, les fonctions f k 
vérifient
la relation de récurrence : pour tout x  En
f 0 (x) = x

et

k > 1,

f k+1 (x) = f (f k (x))

La première ligne représente la condition d'arrêt du code.
itere := proc(t, x, k)
if k = 0 then
RETURN(x);
else
RETURN(itere(t, t[x], k-1));
fi;
end;
On peut aussi écrire un code itératif en appliquant k fois la fonction f , 
c'està-dire le tableau t, à l'aide d'une boucle for.
itere := proc(t, x, k)
local i, res;
res := x;
for i from 1 to k do
res := t[res];
od;
RETURN(res);
end;
4 Modifions le code de la procédure nb_point_fixes de la question 2 en 
remplaçant
le test t[i] = i par le même test mais sur l'itérée : itere(t, i, k) = i.
nb_points_fixes_iteres:=proc(t, k)
local i, pts_fixes;
pts_fixe := 0;
for i from 0 to nops(t)-1 do
if itere(t, i, k) = i then
pts_fixes := pts_fixes + 1;
fi;
od;
RETURN(pts_fixes);
end;