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