Centrale Informatique MP 2000

INFORMA TIOUE Filière MP

INFORMATIQUE

Note :Toutes les réponses doivent être justifiées.

Note :Vous indiquerez, au début de votre copie, si vous choisissez de rédiger 
vos
programmes en PASCAL ou en CAML.

Partie I - Algorithmique

Dans cette artie on s'intéresse aux arbres bicolores ui sont une classe
?
particulière des arbres binaires de recherche.

I.A - Rappels et Notations
I.A.1) Définitions
Un arbre est un triplet fil : (SM, no, p) où :
-- N est un ensemble fini dont les éléments sont appelés noeuds.
-- n() est un élément particulier de 17\£ appelé racine.
-- p est une fonction, nommée père, de 9\[ -- {no} dans 9\[ ayant la propriété
suivante :
Vn G N --{n0}, Elx & IN* | px(n) : n0
On rappelle que px dés1gne p o o p ; p0 dé51gne la fonction 1dent1té.

x

Un arbre vide est un arbre dégénère ayant un ensemble de noeuds vide (il n'a
donc pas de racine).

Dans ce qui suit, on considère un arbre non vide fll = (9\£, no, p) et les "a 
sont
des éléments de N .

---- Si p(n1) : n2 ,on dit que n2 est le père de n1 , et que n1 est un fils de 
n2.

-- Si px(n1) : n2 , on dit que n2 est un ascendant de n1 , et que n1 est un 
descen-
dant de riz.

-- Un chemin d'un noeud na à un noeud n b est une suite de noeuds
(n1 = na,n2, ...,nk : nb) tel que Vie [l...k-- 1] , ni : p(ni+1) .

--- Si Vn & Û\[ -- {no}, p(n) := n1 ,on dit que n1 est une feuille. Dans le cas 
contraire,
on dit que n1 est un noeud interne.

Concours Centrale-Supélec 2000 1/14

INFORMA TIQUE Filière MP

Fil'ère MP

-- Soit _'Î % = {(n e 9\[ --{n0})lp(n) : nl}. _'Î M est l'ensemble des fils de 
n1 . On
appelle degré de n1 le cardinal de _7: 711 et degré maximal de l'arbre le plus 
grand

des degrés des noeuds.

-- Soit %... : {ne 9\£| 3xEUR lN,px(n)=nl}.

Si p... est la restriction de 10 à 9\£ ... , alors <9\£ .... nl, p,,l> est un 
arbre, dit sous-
arbre de fil de rac1ne n1 .

-- La profondeur d'un noeud n est l'entier x 6 IN tel que px(n) : n0 . La 
hauteur
d'un arbre est la profondeur maximale de ses noeuds.

-- Un arbre ordonné est un arbre auquel on adjoint à chaque noeud un ordre to-
tal sur ses fils.

-- Un arbre n-aire est un arbre ordonné dont chaque noeud a exactement n fils
(certains des fils pouvant être des arbres vides).

-- Un arbre binaire est un arbre 2-aire. On nomme classiquement fils droit et
fils gauche les deux fils de chaque noeud.

Un arbre étiqueté est un quintuplet % : (9\£ , no, p, e, e) où :
-- 9\£ , "o et p sont définis comme ci-dessus.

-- e est un ensemble.

-- e est une fonction de 9\[ dans a.

Un arbre binaire étiqueté fil est noté }7l : (i, 54 g, /'Zld) . C'est l'arbre 
dont la ra-
cine a pour étiquette ie 8, et pour sous-arbre gauche (respectivement sous-ar--
bre droit) ÿlg (respectivement flld).

Un arbre binaire de recherche est un arbre binaire étiqueté, tel qu'il existe un
ordre total sur e , et tel que si n est un noeud, flld et fll g ses sous-arbres 
droit
et gauche (éventuellement des arbres vides) alors :

---- Vnge Âg,e(ng) Se(n) .
-- Vnde fld, e(nd) Ze(n) .

On suppose connu du candidat l'ordre de grandeur de la complexité de l'opéra--
tion de recherche d'un élément dans un arbre binaire de recherche ainsi que le
principe d'insertion d'un élément dans un tel arbre.

Concours Centrale-Supélec 2000 2/14

INFORMA TIQUE Filière MP

I.A.2) Représentation

-- Dans toute la partie algorithmique, on considère des arbres binaires étique-
tés, et e est l'ensemble des entiers Z.

-- Langage CAML : on n'utilisera pas ici la représentation classique d'un arbre
sous forme de produit, car on souhaite pouvoir modifier un noeud sans en créer
un nouveau. On utilisera donc un enregistrement.

- Un arbre binaire étiqueté sera représenté ainsi :
Type Noeud :
mutable etiquette : int ;
mutable gauche : ArbreBinaire ;
mutable droit : ArbreBinaire ;
andereBinaire :
ArbreVide
| Pointeur of Noeud
;;
- Les fonctions suivantes seront utilisées :
let est_vide : function

ArbreVide "> true

| _ --> false
;;
let noeud = function

ArbreVide ----> failwith "arbre vide"

| Pointeur x --> X
;;
- Voici un exemple d'utilisation de ces fonctions : la fonction échan-
geant les fils gauche et droit d'un arbre sera écrite :
let echange_gauche_droit a :
if est_vide a then a
else let temp : (noeud a) .gauche in
(noeud a) .gauche <-- (noeud &) .droit; (noeud a) .droit <-- temp; a " Concours Centrale-Supélec 2000 3/14 INFORMATIQUE Filière MP -- Langage PASCAL - Un arbre binaire étiqueté sera représenté ainsi : TYPE ArbreBinaire = ANoeud ; Noeud = RECORD etiquette : INTEGER gauche, droit : ArbreBinaire END ; - La fonction suivante sera utilisée : FUNCTION est_vide (a : ArbreBinaire) :BOOLEAN ; BEGIN est_vide := (a : NIL); END; - Voici un exemple d'utilisation de cette fonction : la fonction échan- geant les fils gauche et droit d'un arbre sera écrite : F UNCTION echange_gauche_droit (a : ArbreBinaire) : Arbre-- Binaire ; VAR temp : ArbreBinaire ; BEGIN IF (est_vide (a)) THEN echange_gauche_droit := a ELSE BEGIN temp := aA.gauche; aA.gauche := a".droit; a".droit := temp; echange_gauche_droit := a END ; END ; I.B - Rotations Afin de pouvoir modifier la hauteur d'un arbre, on introduit, lorsqu'elles sont possibles, les opérations suivantes : Concours Centrale-Supélec 2000 4/14 INFOHMA TIQUE Filière MP I.B.l) Rotation gauche L'arbre obtenu en appliquant une rotation gauche à l'arbre (i,,flg1,(i2,flg2,ñd2)) est l'arbre (i2, (i,,ÿLgl,ÿlg2),ÿldz) . Rotation gauche a) Écrire la fonction rotation _gauche, recevant un ArbreBinaire comme seul ar-- gument, lui appliquant une rotation gauche, et retournant comme résultat l'ar-- bre modifié. On veillera à n'appliquer la rotation que si celle-ci est possible. Dans le cas contraire, l'arbre non modifié sera alors retourné. b) Montrer que si 54 est un arbre binaire de recherche, alors rotation _gauche (fl) est aussi un arbre binaire de recherche. I.B.2) Rotation droite La rotation droite appliquée à un arbre binaire est l'opération inverse de la ro- tation gauche. Ecrire la fonction rotation_droite, selon les mêmes principes que la fonction rotation_gauche. On fera un dessin au préalable. I.B.3) Doubles Rotations Soit 54 : (i,fllg,ÿld) un arbre binaire. La rotation gauche_droite de fil est l'arbre : rotation_droite (i , rotation _gauche (% g) , /'2ld) a) Écrire la fonction rotation gauche_droite. Là aussi, l'opération ne sera effec- tuée que si elle est possible. b) Dessiner le résultat obtenu après application de l'opération de rotation gau-- che-droite à l'arbre 5710 suivant : fix @ @ 9@ Concours Centrale-Supé/ec 2000 5/14 INFOHMA TIQUE Filière MP La rotation droite-gauche de 54 : (i,/q g,ÿld) est, s'il est défini, l'arbre : rotation _gauche (i , fl g , rotation_droite(f£læ) c) Écrire la fonction rotation_dmite_gauche. d) Dessiner le résultat obtenu après application de l'opération de rotation droi- te-gauche à l'arbre 20 défini en b). I.C - Arbres bicolores Un arbre bicolore est un arbre binaire de recherche dont les noeuds sont colorés d'une couleur parmi deux selon des règles particulières énoncées ci-dessous. Si le rouge et noir sont classiquement utilisés, nous prendrons ici le blanc et noir. On choisira d'autre part de ne pas étiqueter les feuilles. I.C.1) Nouvelle représentation On modifie la représentation des arbres afin d'ajouter l'information de coloriage. On en profite pour ajouter dans un noeud un champ indiquant le père qui sera un arbre vide dans le cas de la racine. Les feuilles, non étiquetées, et qui ont une couleur fixe (voir ci--dessous) seront systématiquement représentées par des ar-- bres VidéS. On supposera que les fonctions de rotation ont été corrigées pour te- nir compte de cette nouvelle représentation. -- En CAML, un arbre binaire bicolore sera représenté ainsi : type Couleur : Blanc | Noir ; ; type Noeud : mutable etiquette : int ; mutable couleur: Couleur; mutable gauche: ArbreBinaire ; mutable droit: ArbreBinaire; mutable pere : ArbreBinaire ; and ArbreBinaire : ArbreVide | Pointeur of Noeud '.. '. Concours Centrale-Supé/ec 2000 6/14 INFORMA TIQUE Filière MP - En PASCAL, un arbre bicolore sera représenté ainsi : TYPE TCouleur : (Blanc,Noir); ArbreBinaire : ANoeud; Noeud : RECORD etiquette : INTEGER ; couleur : TCouleur; gauche, droit, pere: ArbreBinaire END; Un arbre bicolore doit satisfaire aux contraintes suivantes (en plus d'être un ar- bre binaire de recherche) : (A-1) Un noeud est soit blanc, soit noir. (A-2) Une feuille est noire. (A-8) La racine est noire. (A-4) Le père d'un noeud blanc est noir. (A--5) Tous les chemins partant d'un noeud donné et se terminant à une feuille contiennent le même nombre de noeuds noirs (sans prendre en compte le noeud de départ) On nomme hauteur noire d'un noeud n appartenant à un arbre bicolore (on la note hn(n)) le nombre de noeuds noirs sur les chemins partant de ce noeud et aboutissant à une feuille (sans prendre en compte n ). Cette fonction est bien dé- finie grâce à (A-5). On nomme hauteur noire d'un arbre bicolore la hauteur noire de sa racine. 1.0.2) Hauteur d'un arbre bicolore a) Montrer qu'un sous-arbre de racine n d'un arbre bicolore contient au moins h . 2 "("'--1 noeuds 1nternes. b) Montrer qu'un arbre bicolore comportant l noeuds internes a une hauteur au plus égale à 210g2(l + 1) . 0) Que peut-on dire de l'ordre de grandeur de la complexité de la recherche d'un élément dans un arbre bicolore ? 1.0.3) Insertion dans un arbre bicolore Pour insérer un nouveau noeud n dans un arbre bicolore, on commence par l'in- sérer selon l'algorithme d'insertion dans un arbre binaire de recherche (on par-- lera d'insertion initiale), en lui affectant la couleur blanc. L'arbre obtenu ainsi n'est plus forcément bicolore, et il faut le modifier pour lui redonner cette pro- Concours Centrale-Supélec 2000 7/14 INFOHMA T/QUE Fil/ère MP priété. L'algorithme utilisé est itératif, donc si au départ, le noeud courant n a deux fils qui sont des arbres vides, cette propriété n'est plus obligatoirement res- pectée aux itérations suivantes. a) Dans le cas où l'arbre initial est vide, quelle modification faut--il apporter pour que l'arbre résultat soit de nouveau bicolore '? b) Dans le cas d'un arbre non vide, que peut-on dire de l'arbre résultat si le père de n après insertion initiale est noire ? On se place maintenant dans le cas où le père de n après insertion initiale (ou après itération) est blanc. Le père de 71 n'est donc pas la racine, et a lui-même un père qui est noir. Les différents cas possibles sont donc (on note fd et fg les deux fils de n , ;) son père, q son grand père, f son frère et 0 son oncle) : q = p p = p...)

fg

Cas n°1

d) À quelle condition simple l'arbre global obtenu est-il bicolore '?

e) Que faut-il faire si la condition n'est pas vérifiée afin de retrouver un 
arbre
bicolore '?

f) Quelle transformation faut-il effectuer dans les cas n°2, 3 et 4 afin de 
retrou-
ver un arbre bicolore, toujours en supposant que 0 est blanc ?

On suppose maintenant que l'oncle o de n est noir. Dans le cas n°1, on effectue
la transformation suivante :

q = p

fg fd Cas n°1

g) Quelle est cette transformation '?
h) Montrer que l'arbre global obtenu est bicolore.

i) Montrer que dans le cas n°2, si on effectue la même transformation, on ne
peut pas trouver une coloration des noeuds p, q. 71 telle que les contraintes 
(A-4)
et (A-5) soient vérifiées.

j) Dessiner et nommer la transformation à effectuer dans le cas n°2 qui permet-
te de conserver la hauteur noire vue du père du sous-arbre.

k) Dessiner et nommer une transformation à effectuer dans le cas n°3.

1) Dessiner et nommer la transformation à effectuer dans le cas n°4.

Concours Centrale-Supé/ec 2000 9/14

INFORMA TIOUE Filière MP

On suppose écrite la fonction d'insertion dans un arbre binaire de recherche.
Cette fonction retourne l'arbre binaire dont la racine est colorée en blanc et 
est
étiquetée par l'élément qui vient d'être inséré.

-- En CAML, la fonction a le profil suivant :

inserer_arbre_binaire : ArbreBinaire --> int ----> ArbreBinaire : 
- En PASCAL, la fonction est déclarée ainsi :
FUNCTION inserer_arbre_binaire (& : ArbreBinaire;
val : INTEGER) : ArbreBinaire;

m) Ecrire une fonction inserer_arbre_bicolore, ayant le même profil que la
fonction inserer_arbre_binaire, mais réalisant l'insertion dans un arbre bico--
lore.

TS VP

Concours Centrale-Supélec 2000 10/14

INFORMA TIOUE Filière MP

Partie II - Logique et automates

Quand on considère un système (pris au sens large du terme), la logique permet
d'exprimer les propriétés des états du système. La logique temporelle permet

d'exprimer l'évolution de l'état d'un système. Cette évolution est considérée
comme une suite d'états.

II.A - Définitions et notations

On considère un ensemble non vide E : {el, ...,en} .

Une propriété p des éléments de E est un sous ensemble de E .
On dira que e e E vérifie la propriété p quand e e p .

On notera V la propriété satisfaite par tous les éléments de E , c'est à dire 
celle
qui correspond à l'ensemble E .

On notera F la propriété satisfaite par aucun élément de E , c'est à dire celle 
qui
correspond à l'ensemble @ .

Soit ? : {p1,p2, ...,pk} un ensemble de propriétés de E .
L'ensemble des formules de logique temporelle basées sur 'P est définie comme
suit à partir des propriétés, avec les opérateurs booléens v, A ,--. (ou, et, 
non)
et les opérateurs temporels 0 (juste après), [Il (désormais), <> (finalement), 3
(jusqu'à).
Si p est une propriété, et si $ et w sont des formules de logique temporelle :

' P

- ( A w)

' ( V W)

' (n)

' (O 'P)

- (®5W)

' 0 ($)

' Û(d>)

sont des formules de logique temporelle.

Toute formule de logique temporelle est construite à partir des règles précéden-
tes.

Pour simplifier l'écriture des formules, on négligera les parenthèses quand il 
n'y
a pas d'ambiguïté possible. Par exemple, on écrira @ /\ \|J au lieu de (© A 
in), et
El (@ A w) au lieu de D(((b A m)) .

On utilisera aussi le connecteur --> , q> --> w étant l'abréviation de (--. V W) si et seulement si (o,i) |= q; ou (o,i) |=\ll ;

(R-3) (Gi) l= ( A W) si et seulement si (o,i)|= @ et (m') l=W ;

(R-4) (G,i)l= (n'?) si et seulement si i< |6l et (o, i) ne satisfait pas (1) ; (R-5) (o,i)|= (Oo): si et seulement si (o,i+1)|= @ ; (R--6) (o,i)}= (ch) si et seulement si pour tout j tel que is j < |0| , (o,j)|= @) ; (R-7) (o,i)|= (N)) si et seulement s'il existe j tel que is j < lol et (o,j)|=@ ; (R-8) (o,i)|= (©8111) si et seulement s'il existe j tel que is j  D--up

On dit que (1) a comme conséquence w , ce qu'on note @ => w si seulement si pour
tout E , tout ensemble ? de propriétés sur E , toute suite 6 et tout i , si 
(o,i) }= (1) ,
alors (o,i) |=1u

Exemple: Dd>=> <><1>.
On dit que @ et w sont équivalentes si @) => 141 et w => (1) , on notera cela 
«) «=> w .

Concours Centrale-Supélec 2000 12/14

INFORMA TIQUE Filière MP

II.B - Satisfaction de formules

II.B.l) Pour l'ensemble E : {e0,el,ez}, les propriétés p : {e0,e1} et
q : {e0, e2} , et la suite 6 : (e1,e1,e1,e2,el,el,eo, eo) , les formules 
suivantes sont-
elles satisfaites '?

. (614)l= DP

° (6,2)I=O(Dq)
° (5,1)l=0(Dp)
' (0,1)l= p5q

II.B.2) Soit p une propriété. Quelle sont les suites o vérifiant o|=El (Op) ?

II.B.8) Donner une formule Dern telle que (o,i) |= Bern si et seulement si ci
est le dernier élément de la suite, c'est-à-dire si i : lol -- 1 . Bern pourra 
être uti-
lisée par la suite.

II.B.4) Soit p une propriété. Donner, avec justification préalable, une formule
Pair , dépendant de p , telle que o |= Pair si et seulement si la propriété p 
est
vérifiée pour tous les éléments 52*i tel que 0 S 2*i < lol et seulement ceux-là. II.B.5) Les équivalences suivantes sont-elles satisfaites ? [] <> q> «=> <> D @ @ <> <> @
(Û) V (DW) <= Û(4>M(Dw)=> <>(QMEW)
(°OE)A(ÜW)@Û (W)/"V)
(©Sw)5w «=> d>8w

Si oui le démontrer, si non donner un contre exemple.

II.B.6) Montrer que l'opérateur <> peut s'exprimer à l'aide de l'opérateur S
et de V, plus précisément, que pour toute formule (1) où apparaît <> , il existe
une formule w équivalente où n'apparaît pas <> , mais où apparaissent S et V.

II.B.7 ) Montrer que toute formule de logique temporelle est équivalente à une
formule où n'apparaissent comme opérateurs temporels que 0 et S .
II.C - Rappels de définitions et de notations sur les automates finis.
Un automate fini non déterministe fil : (E,eo, F, A, 8) est défini ainsi :
- E est l'ensemble (fini) des états ;
- e() est un élément distingué de E appelé état initial ;
- F est un sous ensemble de E appelé ensemble des états finals ;
- A est l'alphabet d'entrée ;

- 8 est une application de E >Opb)}
L2 : {oeA*lol=Û(Pa-->Opb)l

L3 = {55 A*IG |= <>(lîl(JDOE-->Opb))}

ooo FIN 000

Concours Centrale--Supélec 2000 14/14