CCINP Informatique optionnelle MP 2022

SESSION 2022

GP

CONCOURS
COMMUN
INP

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH

ÉPREUVE SPÉCIFIQUE - FILIÈRE MP

INFORMATIQUE

Durée : 4 heures

N.B. : le candidat attachera la plus grande importance à la clarté, à la 
précision et à la concision de la rédaction.
Si un candidat est amené à repérer ce qui peut lui sembler être une erreur 
d'énoncé, il le signalera sur sa copie
et devra poursuivre sa composition en expliquant les raisons des initiatives 
qu'il a été amené à prendre.

RAPPEL DES CONSIGNES

-_ Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la 
rédaction de votre composition ; d'autres
couleurs, excepté le vert, peuvent être utilisées, mais exclusivement pour les 
schémas et la mise en
évidence des résultats.

-< _ Ne pas utiliser de correcteur. *_ Écrire le mot FIN à la fin de votre composition. Les calculatrices sont interdites. Le sujet est composé de trois parties, toutes indépendantes. 1/8 Partie | - Automates L'objectif de cette partie est de proposer quelques éléments autour d'un automate, dit augmenté, construit autour d'un automate fini non déterministe et d'un sous-ensemble d'états. Définition 1 (Automate fini non déterministe) Un automate fini non déterministe est un quintuplet À = (Q, x, I, 6, F) avec : - Q un ensemble fini non vide d'états, de cardinal |Q]; - > un alphabet;
- IC Q l'ensemble des états initiaux ;
- 06: O XXE -- P(Q) une fonction de transition : sig e Q et a EUR X, 6(q, a) 
désigne l'ensemble des états
g de Q tels qu'il existe une transition étiquetée par a de q vers g;
- FC Q l'ensemble des états finaux.

Définition 2 (Automate augmenté)
Soient A = (Q, >, 1,6, F) un automate fini non déterministe et O EUR Q un 
sous-ensemble d'états de Q. On
appelle automate augmenté par O la paire (A, O), que l'on notera par la suite 5.

La notion de calcul est la même entre A et 4, : un calcul dans est une séquence 
d'états g1---q,
de © telle qu'il existe toujours au moins une transition entre deux états 
successifs de cette séquence.
Le mot construit par concaténation des étiquettes de chacune des transitions 
est alors reconnu par
l'automate.

L'ensemble O introduit la notion de calcul réussi au seuil s.

Définition 3 (Calcul réussi au seuil s)
Soit À, un automate augmenté. Un calcul passant par les états g; EUR Q, i EUR 
[0, n]] est dit réussi au seuil
s EUR N Si :

l) gel;
Il) qer;
il) pour tout : >Otelquei+s 0 est un arbre enraciné dans lequel les fils 
de chaque noeud sont
ordonnés. Il est défini récursivement comme suit :

I) ao=Cr,[]1) est constitué d'un noeud unique, la racine ;

il) pour ke N, soit a;=Cr, [to,---f, 11) Un arbre non vide. a; est un arbre 
binomial d'ordre k si :
- t,_1 eSt un arbre binomial d'ordre (k -- 1);
- (r,[t,-::f%-21) est un arbre binomial d'ordre (k -- 1);
- la racine de r,_, a une valeur supérieure ou égale à r.

La figure 3 donne un exemple d'arbre binomial d'ordre 3. Les valeurs dans 
l'arbre sont des entiers.

Figure 3 - Exemple d'arbre binomial d'ordre 3

Q8. Écrire une fonction Python ArbreBinomial(al,a2) qui construit, à partir de 
deux arbres bino-
miaux ali et a2 d'ordre k -- 1, un arbre binomial a; d'ordre k contenant les 
mêmes valeurs que
celles des arbres a1 et a2. Dans la suite, on note a1@a2 cette opération.

Q9. Montrer par récurrence que la racine d'un arbre binomial d'ordre k a 
exactement k fils.
Q10. En déduire une fonction Python Ordre(a) qui renvoie l'ordre de l'arbre 
binomial a.
Q11. Montrer qu'un arbre binomial a d'ordre k possède 2! noeuds.

Q12. Écrire une fonction récursive Python EstUnArbreBinomial (a) qui renvoie 
True si a est un arbre
binomial, False sinon.

11.2 - Tas binomial

Un tas est une structure de données de type arbre qui permet en particulier de 
retrouver directement
un élément qui doit être traité en priorité.

Définition 7 (Tas binomial)

Soient & > 0etT = {ao,---,a,} Un ensemble d'arbres. T est un tas binomial de 
longueur k + 1 si, pour
tout : EUR [[0, k], a; est soit un arbre vide, soit un arbre binomial d'ordre 
:. Si i = k, a; ne peut, de plus, pas
être vide et a, est donc un arbre binomial d'ordre k.

On note dans la suite [T| le nombre de noeuds d'un tas T.

Q13. Quelle structure Python adopter pour coder un tas ?

Définition 8 (Signature d'un tas)

Soit T = {ao,:-- ,a;} Un tas binomial de longueur k + 1. On appelle signature 
de T la suite s0---s, telle

que pour tout i EUR [0,4], s; = 0 (respectivement s; = 1) si l'arbre a; est 
vide (respectivement n'est pas
vide).

4/8
CCINP Informatique optionnelle MP 2022 -- Énoncé 5

Q14. Soit T un tas binomial de longueur k + 1. En utilisant sa signature, 
calculer |T| et montrer que
2* <|T|< 2"*!. En déduire k en fonction de |T|. Q15. Écrire une fonction Python MinimumTas (T) qui retourne la valeur minimum du tas T. En donner la complexité en fonction de |T|. Les tas se construisent itérativement à partir de données. On est donc amené, pour un tas T, à ajouter un à un des éléments. Soit p un élément que l'on souhaite ajouter à un tas binomial T non vide et déjà construit. L'insertion de la valeur p dans le tas T se fait alors selon l'algorithme 1. Algorithme 1 - Insertion de p dans T. Entrées : un tas T={ao --- as}, Une valeur p Sorties : un tas T augmenté de la valeur p début i 0 Coder p dans un arbre binomial a d'ordre 0 tant que i int 
qui calcule le
PGCD de deux entiers naturels.

Q24. Écrire une fonction récursive OCaml de signature 
fraction:int->int->fraction qui construit
une fraction positive irréductible à partir d'un numérateur n et un 
dénominateur d. La fonction
vérifie que n > 0 et d > 0. Au besoin, elle simplifie la fraction par n A d.

Par la suite, on ne construira des valeurs de type fraction que par 
l'intermédiaire de la fonction fraction,
ce qui permettra de garantir l'invariant de type suivant : "pour toute valeur £ 
: fraction, f.n et f.d
sont premiers entre eux".

Q25. Soient deux noeuds k/l et n/d de l'arbre ayant des fils gauches (ou 
droits) identiques. Montrer
qu alors k=netl = d.

Q26. Soient N un noeud et k EUR N. Montrer que le noeud provenant d'une suite 
de k fils gauches de N
N ,
est le noeud DEN Donner sans démonstration le noeud provenant d'une suite de & 
fils droits
de N.

On définit alors une suite (v;);:v, avec vo = 0, puis en effectuant un parcours 
en largeur, de gauche à
droite, de l'arbre de Calkin-Wilf pour définir les termes de la suite.

Q27. Donner les huit premiers termes de la suite (v;);ew.

6/8
Q28. Soient n,d EUR N° premiers entre eux. Montrer par récurrence sur n + d que 
toute fraction n/d
apparaît dans l'arbre.

Q29. Montrer qu'aucune fraction n'apparaît deux fois dans l'arbre.

Q30. Déduire des questions précédentes que la suite (v;);.\ est une bijection 
de N dans Q*.

La suite (v;);.N permet donc d'affirmer que Q" est dénombrable. Nous allons 
utiliser (v;);«\X pour déter-

miner, dans l'énumération des fractions produite par cette suite, la position 
de n'importe quelle fraction

positive n/d. En d'autres termes, étant donnée une fraction positive n/d, on se 
propose de rechercher à

tel que n/d = v;.

Q31. Soit: e N°. Montrer que le fils gauche du noeud de valeur v; a pour valeur 
v:;. Montrer de même
que le fils droit a pour valeur v:;,1.

Pour pouvoir énoncer le i-ième terme dans cette énumération, on introduit alors 
une suite auxiliaire, aux
nombreuses propriétés arithmétiques et liens avec d'autres objets mathématiques.

La suite diatomique de Stern (ou suite de Stern-Brocot) doit son nom à Moritz 
Stern (1807-1894),
élève de Gauss et Achille Brocot (1817-1878), horloger qui s'intéressait aux 
fractions pour la fabrication
d'horloges avec des engrenages comportant peu de dents, donc simples à 
fabriquer.

Définition 11 (Suite diatomique de Stern ou suite de Stern-Brocot)
La suite diatomique de Stern (s;);,\ est définie par so = 0, s, = 1 et pour 
tout i > 1 :

Si -- 1j
S2i+1 -- Si + Six]
Q32. Donner les dix premiers termes de la suite (s;);en.

Q33. Écrire une fonction récursive OCaml de signature stern : int -> int 
permettant de calculer
les termes de cette suite.

Q34. Déduire par récurrence de la Q31 que : Vie N, v = --

Si+1
La suite diatomique de Stern permet d'exprimer le i-ième terme dans 
l'énumération des fractions posi-
tives qui est induite par le parcours en largeur de l'arbre de Calkin-Wilf 
décrit ci-dessus.

Voyons maintenant comment obtenir de manière rapide le successeur d'une 
fraction v; donnée, sans
connaître :, dans cette énumération. Trois cas peuvent se présenter :
- premier cas : les noeuds de valeur v; et v;., Sont à même profondeur k, fils 
d'un même noeud N,
- deuxième cas : le noeud de valeur v; est le dernier noeud à droite à la 
profondeur k,
- troisième cas : les noeuds de valeur v; et v;,, sont à même profondeur k, 
mais ne sont pas fils d'un
même noeud.
1

On pose pour tout x > O, f(x) -- 1+2xl-x

Q35. Montrer que dans le premier cas, v;:1 = f(v;).

Q36. Montrer, en utilisant la Q26, que dans le deuxième cas on a encore v;,; = 
f(v;).

On étudie enfin le dernier cas : les noeuds de valeur v; et v;,, sont sur une 
même profondeur k, mais ne
sont pas les fils d'un même noeud. On va donc passer par la recherche d'un 
ancêtre commun de ces
deux noeuds. Dans la suite, on s'intéressera toujours au premier ancêtre 
commun, c'est-à-dire celui de
profondeur maximale.

En partant de la racine r, il est possible d'atteindre n'importe quel noeud N = 
n/d de l'arbre par une
suite de déplacements vers la gauche (G) ou vers la droite (D). Le chemin de r 
vers N peut donc être
codé par un mot sur l'alphabet {G, D}.

118
Si un déplacement est représenté en OCaml par un type

type direction = G | D

alors un chemin est une liste direction list.

Q37.

Q38.

Q39.

Q40.

Q41.

Écrire une fonction OCaml de signature chemin : fraction -> direction list qui 
calcule le
chemin de la racine à un noeud quelconque de l'arbre. Cette fonction fera appel 
à une fonction
auxiliaire récursive. Ainsi chemin n d calcule la liste des directions à 
prendre pour passer de
r au noeud n/d. On pourra supposer l'existence d'une fonction de signature rev 
: direction
list -> direction list qui renverse une liste.

Écrire une fonction OCaml de signature noeud : direction list -> fraction qui 
détermine le
noeud obtenu en effectuant une série de déplacements depuis la racine. 
Ainsinoeud [D;D;G;D]
renverra un couple d'entiers (n,d) correspondant au noeud de valeur n/d. Cette 
fonction fera
appel à une fonction auxiliaire récursive.

Utiliser les deux fonctions précédentes pour écrire une fonction OCaml ancetre 
de signature
ancetre : fraction -> fraction -> fraction qui détermine le premier ancêtre 
commun
entre deux noeuds. Ainsi ancetre (n,d) (p,q) détermine le premier ancêtre 
commun à n/d
et p/q. Cette fonction pourra utiliser une fonction auxiliaire récursive.

On suppose que le noeud de valeur v,, le premier ancêtre commun des noeuds de 
valeur v; et
V1, eSt à k' niveaux au-dessus d'eux. Donner le chemin entre v, et v; sous la 
forme d'une liste
de direction. Donner de même le chemin entre v, et v;,1.

À partir de l'expression des fils gauche et droit de v', Montrer que l'on a 
encore v;,1 = f(vi).

FIN

8/8

NATIONALE - 221166 - D'après documents fournis

IMPRIMERIE