Centrale Informatique optionnelle MP 2023

Option informatique om)
ON
MP ©
4 heures Calculatrice autorisée ON
Ce sujet comporte quatre parties.

La partie I est totalement indépendante des suivantes et étudie des 
transformations sur des langages.

Les autres parties s'intéressent à des structures de données représentant des 
ensembles d'entiers naturels E
contenus dans [0, N--1], « denses » au sens où |[E| est du même ordre de 
grandeur que N. On cherche à optimiser
le temps d'exécution des opérations de test d'appartenance, d'insertion ou de 
suppression d'un élément, de calcul
du minimum, de calcul de Pélément de E immédiatement supérieur à x (qu'on 
appellera successeur de x dans
E, même si x n'appartient pas à E) ou d'opérations ensemblistes telles que 
l'union.

Dans la partie II, on étudie des structures ordinaires dont on identifie le 
défaut. Dans la partie IIT, on étudie une
structure simple d'arbre complet modélisant des parties de [0,2? -- 1] et dans 
la partie IV, on implémente des
arbres de van Emde Boas qui, sur des parties Æ de [0,27 -- 1], donnent des 
opérations en temps quasi-constant.

I Langages et automates

Dans cette partie, on s'intéresse à des transformations sur des langages 
définis sur un alphabet à deux lettres
X = {a,b}. On note L,|L, la réunion de deux langages L, et L, et EUR le mot 
vide (ou le langage réduit au
mot vide, suivant le contexte). Les automates considérés sont des quadruplets 
(Q, 1, F, À) où Q est l'ensemble
des états de l'automate, 1 l'ensemble de ses états initiaux, F l'ensemble de 
ses états finals et ACQXXXxQ
l'ensemble de ses transitions.

Soit L et K deux langages. On définit le langage noté LE> K par
LE>K = {uv | (u,v,w) EUR (X*)9,uw EUR K,ve L}
Q 1. Déterminer les langages suivants :
a* [> b* (ba)* [> (ab)* a* [> {aPbat | (p,q) E N?,p < a} Q 2. Soit L, K, et K, trois langages. Exprimer à l'aide de LS K,, LS K,, K, et K, les langages suivants : LD (Klk:) LD (K.K2) LD (K) On ne justifiera que la formule portant sur l'étoile de Kleene. Q 3. Montrer que si L et K sont deux langages réguliers, LE> K est régulier.

Q 4. Donner l'exemple d'un langage régulier L et d'un langage non régulier K 
tel que L[> K soit régulier.
On justifiera en détail que le langage K proposé n'est pas régulier.

Q 5. À l'aide d'automates reconnaissant des langages réguliers L et K et 
d'e-transitions, construire un
automate à e-transitions reconnaissant L [> K. On expliquera la construction 
puis on formalisera l'automate
correspondant. Il est inutile de justifier qu'il convient.

On définit sur X* l'application © par :

o(e) =EEUR
Vue X*, Vre X, o(ux) = xu

On note alors pour tout langage L, L le langage défini par :

+00
L = | Jo"(L)
k=0
Q 6. Pour chacun des langages L suivants, déterminer o(L) puis L:
L, = (ab) L; = a*(ba|b)

Q 7. Soit L un langage régulier et 4 = (Q,1I,F, A) un automate le 
reconnaissant. Pour (q,q') EUR Q?, on
note L, y l'ensemble des mots qui étiquettent un chemin de l'état q à l'état q" 
dans 4. Exprimer o(L) à l'aide
de langages L, et du langage X. On portera une attention particulière au cas du 
mot vide et on justifiera la
formule proposée.

1014/2023-03-21 17:57:12 Page 1/5 (cc) BY-NC-SA
Q 8. Montrer que si L est régulier, o(L) est régulier.

Q 9. Montrer que si L n'est pas régulier, o(L) ne l'est pas non plus.

Q 10. Montrer que si L est régulier, L est régulier. Étudier la réciproque.

IT Représentations classiques d'ensembles

Dans cette partie, on implémente des ensembles par des structures connues. On 
note |Æ| le cardinal d'un
ensemble Æ.

IT. À -- Avec une liste triée

Q 11. Dans cette question uniquement, on implémente un ensemble d'entiers 
positifs par la liste de ses

éléments, rangés dans l'ordre croissant. Écrire une fonction succ_list de 
signature int list -> int ->
int prenant en arguments une liste d'entiers distincts dans l'ordre croissant 
et un entier + et renvoyant le
successeur de x dans la liste, c'est-à-dire le plus petit entier strictement 
supérieur à x de la liste (--1 si cela
n'existe pas). Donner sa complexité dans le pire cas.

II.B -- Avec un vecteur trié

Soit N un entier naturel strictement positif, fixé pour toute cette partie. On 
choisit de représenter un ensemble
d'entiers Æ de cardinal n < N par un tableau t de taille N + 1 dont la case d'indice 0 indique le nombre n d'éléments de Æ et les cases d'indices 1 à n contiennent les éléments de Æ rangés dans l'ordre croissant, les autres cases étant non significatives. Par exemple, le tableau [13;2;5;7;9;1;14]] représente l'ensemble à 3 éléments {2,5,7}. Q 12. Pour une telle implémentation d'un ensemble Æ, décrire brièvement des méthodes permettant de réali- ser chacune des opérations ci-dessous (on ne demande pas d'écrire des programmes) et donner leurs complexités dans le pire cas : -- déterminer le maximum de E : -- tester l'appartenance d'un élément x à E : -- ajouter un élément x dans Æ (on suppose la taille du tableau suffisante et que x n'appartient pas à Æ). Q 13. Par une méthode dichotomique, écrire une fonction succ_vect de signature int array -> int ->
int prenant en arguments un tableau t codant un ensemble Æ comme ci-dessus et 
un entier x et renvoyant le
successeur de x dans E (--1 si cela n'existe pas).

Q 14. Calculer la complexité dans le pire cas de la fonction succ_vect en 
fonction de n.

Q 15. Écrire une fonction union_vect de signature int array -> int array -> int 
array prenant en
arguments deux tableaux t_1 et t_2, de taille V, codant deux ensembles Æ;, et 
Æ, et renvoyant le tableau
correspondant à Æ, U E,. On supposera que |E, UE, | < N. II.C -- Avec un arbre binaire de recherche On choisit maintenant de représenter un ensemble d'entiers à l'aide d'un arbre binaire de recherche, les noeuds étant étiquetés par les éléments de Æ. On définit le type type abr = Nil | Noeud of int * abr * abr Pour un tel arbre, pour tout noeud x, les étiquettes de tous les noeuds du sous-arbre gauche de x, s'il y en a, doivent être inférieures à l'étiquette de x et les étiquettes de tous les noeuds du sous-arbre droit de x, s'il y en a, doivent être supérieures à l'étiquette de x. Par exemple, on peut représenter l'ensemble {2,3,5,8,13} par l'arbre figure 1. 3 13 Figure 1 Un arbre binaire de recherche pour l'ensemble {2,3,5,8,13} Q 16. Écrire une fonction min_abr de signature abr -> int prenant en argument 
un arbre binaire de re-
cherche représentant un ensemble E et renvoyant son étiquette minimale (--1 si 
l'ensemble est vide).

Q 17. Ecrire une fonction récursive partitionne_abr de signature abr -> int -> 
(bool * abr * abr)
prenant en arguments un arbre binaire de recherche représentant un ensemble Æ 
et un entier x et renvoyant un

1014/2023-03-21 17:57:12 Page 2/5 (cc) BY-NC-SA
triplet (b, ag, ad) où b vaut true si x appartient à Ë et false sinon, ag est 
un arbre binaire de recherche
codant les éléments de Æ strictement plus petits que x et ad un arbre binaire 
de recherche codant les éléments
de Æ strictement plus grands que x.

Q 18. Écrire une fonction insertion_abr de signature abr -> int -> abr prenant 
en arguments un arbre
binaire de recherche représentant un ensemble Æ et un entier x et renvoyant un 
arbre binaire de recherche
associé à l'ensemble EU {x} et de racine étiquetée par x. Calculer sa 
complexité dans le pire cas en fonction de
l'arbre reçu puis en fonction de Æ.

Q 19. Ecrire une fonction union_abr de signature abr -> abr -> abr prenant en 
arguments deux arbres
binaires de recherche représentant deux ensembles Æ, et FE, et renvoyant un 
arbre binaire de recherche associé
à l'ensemble £, U F,. On expliquera brièvement la méthode choisie.

IIT Représentation par arbres binaires complets

On considère dans cette partie des arbres binaires complets dont les noeuds 
sont étiquetés par des booléens. On
rappelle que la profondeur d'un noeud est égale à la longueur du chemin reliant 
la racine à ce noeud et la hauteur
d'un arbre est la plus grande profondeur de ses feuilles (la racine est donc à 
la profondeur 0). Les noeuds seront
numérotés à partir de la racine qui porte le numéro 1 dans l'ordre d'un 
parcours en largeur (de gauche à droite

à chaque profondeur).
1,
, DS a 3.
NN . : UT

Figure 2 Numérotation des noeuds

Q 20. Dans un arbre binaire complet de hauteur p EUR N, quel numéro peut avoir 
un noeud à la profondeur
k EUR ]0, p] ? Combien le sous-arbre dont la racine a le numéro à a-t-il de 
feuilles ?

Q 21. Dans un arbre binaire complet de hauteur p EUR NN, pour le noeud numéro 
à, donner, en les justifiant, les
numéros de son fils gauche, de son fils droit et de son père.

Informatiquement, un tel arbre complet de hauteur p sera implémenté par un 
tableau de booléens de taille 2PT1,
la case d'indice à EUR [1,2? T1 -- 1] contenant l'étiquette du noeud numéroté 
i. La case d'indice 0 n'est pas utilisée.
On notera que dans tous les programmes de cette partie, on peut avoir accès à 
la valeur 2? via la taille du
tableau.

Soit p EUR N. On choisit de coder un ensemble Æ EUR [0,2P -- 1] par un arbre 
binaire complet de hauteur p selon
les règles suivantes :

-- chaque feuille numérotée 1 est étiquetée par true si et seulement 
sii---2%EUReF;:

-- chaque noeud interne est étiqueté par le « ou logique » des étiquettes de 
ses deux fils.
let ensemble = bool array ;;

Par exemple, l'ensemble {0,1,7} est représenté par l'arbre représenté figure 3.

DS _ a
true true
true false false true
true true false false false false false true

Figure 3 Arbre associé à l'ensemble {0,1,7} pour p = 3

Q 22. Écrire une fonction appartient de signature ensemble -> int -> bool qui 
détermine si un entier
quelconque appartient ou non à un ensemble donné. Calculer sa complexité.

1014/2023-03-21 17:57:12 Page 3/5 (cc) BY-NC-SA
Q 23. Écrire une fonction fabrique de signature int list -> int -> ensemble qui 
prend en arguments
une liste d'entiers positifs distincts £ et une valeur pour 2? et renvoie 
l'arbre associé à l'ensemble Æ dont les
éléments sont ceux de la liste. On supposera que tous les éléments de £ 
appartiennent à [0,27 --1]. Cette fonction
devra s'exécuter en O(2P).

Q 24. Écrire une fonction insere de signature ensemble -> int -> unit qui 
ajoute un entier # à un
ensemble Æ. On suppose 4 compatible avec la valeur de p associée à Æ. Cette 
fonction devra s'exécuter en (1)
dans le meilleur cas.

Q 25. Écrire une fonction supprime de signature ensemble -> int -> unit qui 
retire un entier k d'un
ensemble Æ. On suppose k compatible avec la valeur de p associée à Æ. Calculer 
la complexité de cette fonction
dans le pire cas.

Q 26. Ecrire une fonction minlocal de signature ensemble -> int -> int qui 
cherche l'élément de Æ
minimal parmi ceux codés dans le sous-arbre de racine numérotée à dans l'arbre 
associé à Æ. Si un tel élément
n'existe pas, cette fonction devra renvoyer --1. Calculer la complexité de 
cette fonction en fonction de p et 1.

On veut maintenant écrire une fonction qui calcule le successeur d'un entier + 
dans un ensemble Æ pour une
telle structure. On propose l'algorithme suivant, pour x EUR ]0,2P -- 1]:

-- on part de la case numéro à codant l'entier x dans E ;

-- tant que à n'est pas le noeud le plus à droite à sa profondeur et que la 
case ? + 1 vaut false, on remplace ?
par son père :

-- on renvoie l'élément minimum du sous-arbre de racine 2 + 1 ou --1 si ? était 
totalement à droite.

Q 27.  Prouver l'algorithme décrit ci-dessus.

Q 28. Ecrire une fonction successeur de signature ensemble -> int -> int 
prenant en arguments l'en-
semble Æ et un entier x positif et renvoyant son successeur dans Æ (--1 si cela 
n'existe pas).

Q 29. Montrer que si x EUR E admet bien un successeur dans Æ, il existe une 
constante K° > 0 indépendante
de Æ et p telle que la complexité de successeur e x soit majorée par K (log, 
(successeur(r) -- x) + 2). On
admet que le même type de justification montre que si x est le maximum de Æ, la 
complexité de successeur e
x est majorée par K (log, (2? -- x) +2).

Q 30. En utilisant la fonction successeur, écrire une fonction cardinal de 
signature ensemble -> int
prenant en argument un ensemble et renvoyant son cardinal.

Q 31. Déterminer la complexité de la fonction cardinal en fonction de p et n = 
|E|. On rappelle que la
fonction log, est concave.

Q 32. Quels sont les intérêts et inconvénients d'une telle structure ? Dans 
quels cas peut-elle s'avérer plus
intéressante que des structures connues ?

IV Arbres de van Emde Boas

Soit p un entier positif et N = 2*°. On supposera que tous les entiers 
manipulés restent représentables par
la structure d'entier OCaml ordinaire. On considère le type de structure 
suivant (appelé arbre veb par suite)
implémentant un ensemble Æ d'entiers positifs strictement inférieurs à N :

type veb = {mutable mini : int; mutable maxi : int; table : veb array};;

Les champs mutables d'un arbre veb sont modifiables : par exemple, pour un 
arbre veb noté v, v.mini <- 1 change la valeur du champ v.mini. Le codage d'un ensemble Æ C [0,N -- 1] par un arbre veb dit d'ordre N = 2? suit les règles suivantes : -- Les champs mini et maxi représentent toujours la valeur minimale et maximale de Æ. Ils sont mis arbitrai- rement à --1 si l'ensemble est vide. -- Si N = 2, ie. si l'arbre doit coder une partie de [0,1], le champ table est un tableau vide (4e. [111), les champs mini et maxi suffisant à coder Æ. On veillera à ce que les fonctions demandées traitent correctement ce cas particulier. -- Pour N > 2, on note Ë = E\{min(Æ)} (où min(Æ) désigne le minimum de E). On 
décompose E en
VN = 2% ensembles E, définis par

vke [o, VN -- 1]. Be = {a kVN |xe EN[EVN,(k+1)VN -1]}

le champ table est alors un tableau de VN + 1 arbres veb d'ordre VN :
e pour & EUR [0, VAN -- 1], l'arbre veb stocké dans la case table. (k) code 
l'ensemble E, :

e l'arbre veb stocké dans la case table.(VN) code l'ensemble R = {e ce [0, VN 
-1] | FE, & 0}.

1014/2023-03-21 17:57:12 Page 4/5 (cc) BY-NC-SA
Par exemple, considérons l'arbre veb ex codant l'ensemble E = {2,13,14,15} avec 
p = 2 te. N = 16. On a
E = {13,14,15} puisque min(Æ) = 2 et donc les cinq cases du tableau ex.table 
correspondent respectivement
aux ensembles

Es =Ù EE; =0 E,=0  E3={13--3V16,14--3V16,15--3V16}={1,2,3}  R=1{3}

On obtient la structure représentée figure 4.

ex, N--16 N=4

mini = 2 maxi = 15 table -- --{3}----| mini =3 maxi =3 table = | 1 --
: : \

/ \ LT
ÿ N--2 /
LS mini =-1 maxi =-1 table -- J

()
N--2
mini = -1 maxi =-1l table -- ]
{1,2,3}

mini =-1 maxi =-1 table --

N--2

1-11
Î
Q
() LN mini = -1 maxi =-1 table --

mini = -1 maxi =-1 table -- J

N--2

mini = -1 maxi =-1 table -- |

N--2

mini = 1 maxi = 3 se ELT
mini =-1 maxi =-1 table -- |
1

{0,1}

mini =-1 maxi =-1 table -- J

Ü}

N--2

mini = 0 maxi = 1 table -- |

N--2

mini = 1 maxi = 1 table -- |

Figure 4 L'arbre veb ex associé à l'ensemble {2, 13, 14, 15} avec p = 2

Q 33. On veut coder l'ensemble {0,2,3,5,7,13,14} par un arbre veb d'ordre N = 
16, noté ex_veb. Indiquer
quel ensemble code chaque arbre veb stocké dans ex_veb.table puis préciser 
ex_veb.table. (3).

Q 34. Écrire une fonction creer_veb de signature int -> veb prenant en argument 
un entier p et créant
un arbre veb d'ordre N = 2*° implémentant l'ensemble vide.

Q 35. Résoudre en fonction de q la récurrence C(q) = C(,/g) + O(1) dans le cas 
où g = 2°.
Q 36. Écrire une fonction appartient_veb de signature veb -> int -> bool qui 
teste l'appartenance d'un
entier x quelconque à un ensemble Æ codé par un arbre veb. Calculer sa 
complexité dans le pire cas.

Q 37. Écrire une fonction successeur_veb de signature veb -> int -> int qui 
calcule le successeur d'un
entier æ quelconque dans Æ (--1 s'il n'y en a pas). Calculer sa complexité dans 
le pire cas.

Q 38. Écrire une fonction insertion_veb de signature veb -> int -> unit qui 
insère un entier x dans un
arbre veb. On suppose que x EUR [0, N -- 1]. Cette fonction devra avoir une 
complexité en O(log, (log, (N)).

Q 39. Soit M(N) la totalité de l'espace mémoire nécessaire pour stocker un 
ensemble par un arbre veb d'ordre
N avec N = 2°. Donner la relation de récurrence vérifiée par M(N) puis 
déterminer l'ordre de grandeur de
M(N).

eeoeFrINeee

1014/2023-03-21 17:57:12 Page 5/5 (cc) BY-NC-SA