INFORMATIQUE 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 partie, on s’intéresse aux arbres bicolores qui 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 A = 〈 N , n 0, p〉 où :
— N est un ensemble fini dont les éléments sont appelés nœuds.
— n 0 est un élément particulier de N appelé racine.
— p est une fonction, nommée père, de N – { n 0 } dans N ayant la propriété
suivante :
∀n ∈ N – { n 0 }, ∃ x ∈ IN∗
x
p (n) = n 0
x 0
On rappelle que p désigne p o … o p ; p désigne la fonction identité.






x
Un arbre vide est un arbre dégénéré ayant un ensemble de nœuds vide (il n’a
donc pas de racine).
Dans ce qui suit, on considère un arbre non vide A = 〈 N , n 0, p〉 et les n α sont
des éléments de N .
— Si p(n 1) = n 2 ,on dit que n 2 est le père de n 1 , et que n 1 est un fils de n 2 .
x
— Si p (n 1) = n 2 , on dit que n 2 est un ascendant de n 1 , et que n 1 est un descen-
dant de n 2 .
— Un chemin d’un nœud n a à un nœud n b est une suite de nœuds
( n 1 = n a, n 2, …, n k = n b ) tel que ∀i ∈ [ 1…k – 1 ] , n i = p(n i + 1) .

— Si ∀n ∈ N – { n 0 }, p(n) ≠ n 1 , on dit que n 1 est une feuille. Dans le cas contraire,

on dit que n 1 est un nœud interne.

Concours Centrale-Supélec 2000 1/14

INFORMATIQUE Filière MP

Filière MP

 
— Soit Fn =  ( n ∈ N – { n 0 } ) p(n) = n 1  . F n1 est l’ensemble des fils de n 1 . On
1
 
appelle degré de n 1 le cardinal de F n1 et degré maximal de l’arbre le plus grand
des degrés des nœuds.
 x 
— Soit Nn 1
= n ∈ N ∃ x ∈ IN, p (n) = n 1  .
 

Si p n1 est la restriction de p à N n1 , alors 〈 N n1, n 1, p n1〉 est un arbre, dit sous-

arbre de A de racine n 1 .
x
— La profondeur d’un nœud n est l’entier x ∈ IN tel que p (n) = n 0 . La hauteur
d’un arbre est la profondeur maximale de ses nœuds.
— Un arbre ordonné est un arbre auquel on adjoint à chaque nœud un ordre to-
tal sur ses fils.
— Un arbre n-aire est un arbre ordonné dont chaque nœud 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 nœud.
Un arbre étiqueté est un quintuplet A = 〈 N , n 0, p, ε, e〉 où :
— N , n 0 et p sont définis comme ci-dessus.
— ε est un ensemble.
— e est une fonction de N dans ε .
Un arbre binaire étiqueté A est noté A = ( i, A g, A d ) . C’est l’arbre dont la ra-
cine a pour étiquette i ∈ ε , et pour sous-arbre gauche (respectivement sous-ar-
bre droit) A g (respectivement A d ).
Un arbre binaire de recherche est un arbre binaire étiqueté, tel qu’il existe un
ordre total sur ε , et tel que si n est un nœud, A d et A g ses sous-arbres droit
et gauche (éventuellement des arbres vides) alors :
— ∀n g ∈ A g, e(n g) ≤ e(n) .
— ∀n d ∈ A d, e(n d) ≥ e(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

INFORMATIQUE Filière MP

I.A.2) Représentation
— Dans toute la partie algorithmique, on considère des arbres binaires étique-
tés, et ε est l’ensemble des entiers ZZ .
— Langage CAML : on n’utilisera pas ici la représentation classique d’un arbre
sous forme de produit, car on souhaite pouvoir modifier un nœud 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 ;
and ArbreBinaire =
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 a).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 = ˆNoeud ;
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 :
FUNCTION echange_gauche_droit (a : ArbreBinaire) : Arbre-
Binaire ;
VAR
temp : ArbreBinaire ;
BEGIN
IF (est_vide (a)) THEN
echange_gauche_droit := a
ELSE
BEGIN
temp := aˆ.gauche;
aˆ.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

INFORMATIQUE Filière MP
I.B.1) Rotation gauche
L’arbre obtenu en appliquant une rotation gauche à l’arbre
( i 1 , A g1, ( i 2, A g2, A d2 ) ) est l’arbre ( i 2 , ( i 1, A g1, A g2 ), A d2 ) .

i1 i2
Rotation gauche
i2 i1
A g1 A d2

A g2 A d2 A g1 A g2
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 A est un arbre binaire de recherche, alors
rotation_gauche ( A ) 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.
Écrire 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 A = ( i, A g, A d ) un arbre binaire. La rotation gauche_droite de A est
l’arbre :
rotation_droite ( i , rotation_gauche ( A g ) , A d )
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 A 0 suivant :
4

2 6

1 3 5 7

Concours Centrale-Supélec 2000 5/14

INFORMATIQUE Filière MP
La rotation droite-gauche de A = ( i, A g, A d ) est, s’il est défini, l’arbre :
rotation_gauche ( i , A g , rotation_droite ( A d ) )
c) Écrire la fonction rotation_droite_gauche.
d) Dessiner le résultat obtenu après application de l’opération de rotation droi-
te-gauche à l’arbre A 0 défini en b).
I.C - Arbres bicolores
Un arbre bicolore est un arbre binaire de recherche dont les nœuds 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 nœud 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 vides. 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élec 2000 6/14

INFORMATIQUE Filière MP
- En PASCAL, un arbre bicolore sera représenté ainsi :
TYPE
TCouleur = (Blanc,Noir);
ArbreBinaire = ˆNoeud;
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 nœud est soit blanc, soit noir.
(A-2) Une feuille est noire.
(A-3) La racine est noire.
(A-4) Le père d’un nœud blanc est noir.
(A-5) Tous les chemins partant d’un nœud donné et se terminant à une feuille
contiennent le même nombre de nœuds noirs (sans prendre en compte le nœud
de départ)
On nomme hauteur noire d’un nœud n appartenant à un arbre bicolore (on la
note hn(n) ) le nombre de nœuds noirs sur les chemins partant de ce nœud 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.
I.C.2) Hauteur d’un arbre bicolore
a) Montrer qu’un sous-arbre de racine n d’un arbre bicolore contient au moins
hn ( n )
2 – 1 nœuds internes.
b) Montrer qu’un arbre bicolore comportant l nœuds internes a une hauteur au
plus égale à 2log 2(l + 1) .
c) Que peut-on dire de l’ordre de grandeur de la complexité de la recherche d’un
élément dans un arbre bicolore ?
I.C.3) Insertion dans un arbre bicolore
Pour insérer un nouveau nœud 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

INFORMATIQUE Filière MP
priété. L’algorithme utilisé est itératif, donc si au départ, le nœud 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 n 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 f d et f g les deux fils de n , p son
père, q son grand père, f son frère et o son oncle) :
q = p( p(n)) q = p( p(n))

p = p(n) o p = p(n) o

n f n
f

fg fd fg fd

Cas n°1 Cas n°2

q = p( p(n)) q = p( p(n))

o p = p(n) p = p(n)
o

n f f n

fg fd fg fd

Cas n°3 Cas n°4

On suppose qu’au départ, tous les nœuds respectent la propriété A-5 des arbres
bicolores et que seuls n et p violent la condition (A-4).
c) Que peut-on dire de la couleur du frère f de n ?

Concours Centrale-Supélec 2000 8/14

INFORMATIQUE Filière MP
On va modifier l’arbre afin de retrouver un arbre bicolore. Deux familles de mo-
difications sont possibles, selon la couleur de o . On suppose tout d’abord que
l’oncle o de n est blanc. Dans le cas n°1, on effectue la transformation suivante :

q = p( p(n)) q = p( p(n))

p = p(n) o o
p = p(n)

n f f
n

fg fd
fg fd
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 o 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( p(n)) p

p = p(n) o
n q
n f
fg fd f o

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 nœuds p, q, n 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.
l) Dessiner et nommer la transformation à effectuer dans le cas n°4.

Concours Centrale-Supélec 2000 9/14

INFORMATIQUE 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 = <fun>
- En PASCAL, la fonction est déclarée ainsi :
FUNCTION inserer_arbre_binaire (a : ArbreBinaire;
val : INTEGER) : ArbreBinaire;
m) Écrire 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.

TSVP

Concours Centrale-Supélec 2000 10/14

INFORMATIQUE 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 = {e 1, …,e n} .
Une propriété p des éléments de E est un sous ensemble de E .
On dira que e ∈ E vérifie la propriété p quand 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 P = { p 1, p 2, … , p k} 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 ∨ , ∧ ,¬ (ou, et, non)
et les opérateurs temporels O (juste après), (désormais), ◊ (finalement), ℑ
(jusqu’à).
Si p est une propriété, et si φ et ψ sont des formules de logique temporelle :
-p
- (φ ∧ ψ)
- (φ ∨ ψ)
- ( ¬φ )
- (O φ)
- ( φℑψ )
- ◊ (φ)
- (φ)
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 φ ∧ ψ au lieu de ( φ ∧ ψ ) , et
( φ ∧ ψ ) au lieu de ( ( φ ∧ ψ ) ) .
On utilisera aussi le connecteur → , φ → ψ étant l’abréviation de ( ¬φ ) ∨ ψ .

Concours Centrale-Supélec 2000 11/14

INFORMATIQUE Filière MP
Soit n un entier strictement positif et σ = ( σ 0, σ 1, …, σ n – 1 ) une suite finie d’élé-
ments de E . Par définition, la longueur de la suite σ et n et est notée σ .
Soit σ une suite non vide, et i un entier naturel.
On définit la relation "la suite σ satisfait la formule de logique temporelle
φ au rang i ", ce qui sera noté (σ,i) = φ par induction sur la composition des for-
mules par les règles suivantes :
(R-1) (σ,i) = p si et seulement si i < σ et σ i vérifie la propriété p ;
(R-2) (σ,i) = ( φ ∨ ψ ) si et seulement si (σ,i) = φ ou (σ,i) = ψ ;
(R-3) (σ,i) = ( φ ∧ ψ ) si et seulement si (σ,i) = φ et (σ,i) = ψ ;
(R-4) (σ,i) = ( ¬φ ) si et seulement si i < σ et ( σ, i ) ne satisfait pas φ ;
(R-5) (σ,i) = ( O φ ) si et seulement si (σ,i + 1) = φ ;
(R-6) (σ,i) = ( φ ) si et seulement si pour tout j tel que i ≤ j < σ , (σ, j) = φ ;
(R-7) (σ,i) = ( ◊ φ) si et seulement s’il existe j tel que i ≤ j < σ et (σ, j) = φ ;
(R-8) (σ,i) = ( φℑψ ) si et seulement s’il existe j tel que i ≤ j < σ et (σ, j) = ψ et
pour tout k tel que i ≤ k < j , (σ,k) = φ .

On notera σ = φ , le fait que (σ,0) = φ . On notera (σ,i) = φ quand σ ne satisfait pas

la formule φ au rang i .

Exemples :
E = {e 0, e 1, e 2,e 3}, p = {e 1,e 3} ,
σ = (e 1, e 1, e 3,e 3, e 2, e 3, e 3, e 0, e 2, e 2, e 0) ,
σ = p, ( σ ,2 ) = p, ( σ, 4 ) = p, ( σ, 15 ) = p ,
( σ, 23 ) = V , ( σ, 6 ) = V ,
( σ, 2 ) = p ∧ Op ,
(σ,1) = ¬p ,
( σ, 2 ) = ◊ ¬p .

On dit que φ a comme conséquence ψ , ce qu’on note φ ⇒ ψ si seulement si pour

tout E , tout ensemble P de propriétés sur E , toute suite σ et tout i , si (σ,i) = φ ,
alors (σ,i) = ψ
Exemple : φ ⇒ ◊ φ .
On dit que φ et ψ sont équivalentes si φ ⇒ ψ et ψ ⇒ φ , on notera cela φ ⇔ ψ .

Concours Centrale-Supélec 2000 12/14

INFORMATIQUE Filière MP
II.B - Satisfaction de formules
II.B.1) Pour l’ensemble E = { e 0, e 1, e 2 } , les propriétés p = { e 0, e 1 } et
q = { e 0, e 2 } , et la suite σ = (e 1, e 1, e 1,e 2, e 1, e 1, e 0, e 0) , les formules suivantes sont-
elles satisfaites ?
• (σ,4) = p
• (σ,2) = O ( q )
• (σ,1) = ◊ ( p )
• (σ,1) = pℑq

II.B.2) Soit p une propriété. Quelle sont les suites σ vérifiant σ = ( O p ) ?

II.B.3) Donner une formule Dern telle que (σ,i) = Dern si et seulement si σ i
est le dernier élément de la suite, c’est-à-dire si i = σ – 1 . Dern 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 σ = Pair si et seulement si la propriété p est
vérifiée pour tous les éléments σ 2*i tel que 0 ≤ 2*i < σ et seulement ceux-là.
II.B.5) Les équivalences suivantes sont-elles satisfaites ?
• ◊φ⇔ ◊ φ
• ◊φ⇔ ◊ ◊φ
• ( φ) ∨ ( ψ) ⇔ (φ ∨ ψ)
• ( ◊ φ) ∧ ( ψ ) ⇔ ◊ ( φ ∧ ψ )
• ( ◊ φ) ∧ ( ψ ) ⇔ ( ◊ φ ∧ ψ)
• ( φℑψ )ℑψ ⇔ φℑψ
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 ℑ
et de V , plus précisément, que pour toute formule φ où apparaît ◊ , il existe
une formule ψ équivalente où n’apparaît pas ◊ , mais où apparaîssent ℑ et V .
II.B.7) Montrer que toute formule de logique temporelle est équivalente à une
formule où n’apparaissent comme opérateurs temporels que O et ℑ .
II.C - Rappels de définitions et de notations sur les automates finis.
Un automate fini non déterministe A = (E,e 0, F, A, δ) est défini ainsi :
- E est l’ensemble (fini) des états ;
- e 0 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 ;
- δ est une application de E × A dans P ( E ) , appelée fonction de
transition.

Concours Centrale-Supélec 2000 13/14

INFORMATIQUE Filière MP

Soit u = u 0 u 1 …u n – 1 un mot de A∗ :
- Une suite d’états s = s 0 s 1 …s n est compatible pour u quand s 0 = e 0 ,
et s i + 1 ∈ δ ( s i, u i ) , pour tout i tel que 0 ≤ i ≤ n – 1 .
- Une suite compatible est acceptante quand elle se termine par un état
final.
- Un mot u est accepté par A s’il existe une suite acceptante pour u .
- Le langage accepté (on dit aussi reconnu) par l’automate A est l’en-
semble des mots acceptés par A .
Pour chaque a ∈ A , on définit la propriété p a = { a } , c’est-à-dire que pour a' ∈ A ,
a' vérifie la propriété p a si et seulement si a' = a . On aura donc : pour le mot
u = u 0 u 1 …u n – 1 , (u,i) = p a si et seulement si i ≤ n – 1 et u i = a .
Dans cette partie, on verra sur des exemples les liens entre la logique temporelle
et les automates finis.
On se contentera d’une justification sommaire des automates et des formules de-
mandés.
II.C.1) Soit L le langage défini par l’expression régulière :
L = { a, b, c }∗ ⋅ a ⋅ { b, c }∗ ⋅ bc ⋅ { b, c }∗
Donner un automate non déterministe reconnaissant ce langage et donner une
formule de logique temporelle φ basée sur { p a, p b, p c} , telle que σ = φ si et seu-
lement si σ ∈ L .
II.C.2) Soit l’ensemble A = {a,b, c} . On pose P = { p a, p b, p c} .
Pour chacun des langages L i ( 1 ≤ i ≤ 3 ) suivants, donner une expression ration-
nelle e i décrivant L i , puis un automate fini A i reconnaissant L i :

L 1 = {σ ∈ A* σ = ( p a → O p b )}

L 2 = {σ ∈ A* σ = ( p a → O p b )}

L 3 = {σ ∈ A* σ = ◊( ( p a → O p b ) )}

••• FIN •••

Concours Centrale-Supélec 2000 14/14