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.
Les calculatrices sont interdites
Préambule: Les trois parties qui composent ce sujet sont indépendantes et peuvent être traitées par les candidats dans un ordre quelconque.
Pour les candidats ayant utilisé le langage CaML dans le cadre des enseignements d'informatique, la partie III (Algorithmique et programmation en CaML) se situe en page 6.
Pour les candidats ayant utilisé le langage PASCAL dans le cadre des enseignements d'informatique, la partie III (Algorithmique et programmation en PASCAL) se situe en page 13.
Partie I : Logique et calcul des propositions
Vous participez à un concours de mathématiques comportant une partie de raisonnement logique. Plusieurs orateurs font des déclarations et vous devez répondre à des questions en vous appuyant sur des informations déduites de ces déclarations. La règle suivante s'applique : «Les orateurs sont de trois natures : les véridiques, les menteurs et les changeants. Les véridiques disent toujours la vérité, les menteurs mentent toujours, et les changeants disent en alternance une vérité et un mensonge (c'est-à-dire, soit une vérité, puis un mensonge, puis une vérité, etc. ; soit un mensonge, puis une vérité, puis un mensonge, etc.). Pendant tout le concours, les orateurs ne peuvent pas changer de nature. » Les épreuves comportent deux phases :
Les différents orateurs font plusieurs déclarations dont l'analyse permet de déterminer la nature de chaque orateur (véridique, menteur, changeant commençant par dire la vérité, ou changeant commençant par dire un mensonge).
Les orateurs font une seconde série de déclarations. Puis, vous devez répondre à des questions en exploitant les informations contenues dans ces déclarations.
Question I. 1 Dans la première phase, quel est le nombre minimum de déclarations que doit faire chaque orateur pour qu'il soit possible de déterminer sa nature? Justifier votre réponse.
Question I. 2 Soit un orateur qui fait une suite de déclarations . Proposer des formules du calcul des propositions et qui permettent de caractériser la nature de (respectivement véridique, menteur, changeant commençant par dire la vérité, ou changeant commençant par dire un mensonge).
Vous participez à une première épreuve avec un orateur qui fait les déclarations suivantes :
J'aime le rouge mais pas le bleu.
Soit j'aime le rouge, soit j'aime le vert.
Si j'aime le rouge et le vert, alors j'aime le bleu.
Nous noterons et les variables propositionnelles associées au fait que l'orateur aime le rouge, le vert ou le bleu.
Nous noterons et les formules propositionnelles associées aux déclarations de .
Question I. 3 Représenter les déclarations de l'orateur sous la forme de formules du calcul des propositions et dépendant des variables et .
Question I. 4 Appliquer les formules permettant de caractériser la nature des orateurs et que vous avez proposées pour la question I. 2 pour l'orateur dépendant des variables , et .
Question I. 5 En utilisant le calcul des propositions (résolution avec les tables de vérité), déterminer la nature de l'orateur . Quelles sont les couleurs qu'aime ?
Vous participez à une seconde épreuve avec trois orateurs et . Vous avez déterminé dans la première phase avec succès que est un menteur, que est un véridique et que est un changeant sans savoir s'il doit dire la vérité ou un mensonge pour sa déclaration suivante. Ceux-ci font les déclarations : : Le losange est visible. : Le cercle n'est visible que si le losange est visible. : Le triangle n'est pas visible. : Soit le cercle est visible, soit le triangle est visible.
Nous noterons et les formules propositionnelles associées aux déclarations des orateurs et dans cette première épreuve.
Nous noterons et les variables propositionnelles associées au fait que le cercle, le losange ou le triangle soit visible.
Question I. 6 Représenter les déclarations des orateurs sous la forme de formules du calcul des propositions et dépendant des variables , et .
Question I.7 Représenter les informations sur la nature des orateurs sous la forme d'une formule du calcul des propositions dépendant des variables et .
Question I. 8 En utilisant le calcul des propositions (résolution avec les formules de De Morgan), déterminer quelle est (ou quelles sont) la (ou les) figure(s) visible(s) ainsi que la nature exacte de I l'orateur changeant.
Partie II : Automates et langages
Le but de cet exercice est l'étude des propriétés de l'opération de composition de deux automates.
1 Automate fini complet déterministe
Pour simplifier les preuves, nous nous limiterons au cas des automates finis complets déterministes. Les résultats étudiés s'étendent au cadre des automates finis complets quelconques.
1.1 Représentation d'un automate fini complet déterministe
Déf. II. 1 (Automate fini complet déterministe) Soit l'alphabet (un ensemble de symboles), soit le symbole représentant le mot vide ( ), soit l'ensemble contenant et les mots composés de séquences de symboles de (donc ); un automate fini complet déterministe sur est un quintuplet composé de :
un ensemble fini d'états : ;
un état initial : ;
un ensemble d'états terminaux : ;
une fonction totale de transition confondue avec son graphe : .
Pour une transition donnée, nous appelons o l'origine de la transition, e l'étiquette de la transition et la destination de la transition.
1.2 Représentation graphique d'un automate
Les automates peuvent être représentés par un schéma suivant les conventions :
les valeurs de la fonction totale de transition sont représentées par un graphe orienté dont les nœuds sont les états et les arêtes sont les transitions;
un état initial est entouré d'un cercle (i);
un état terminal est entouré d'un double cercle (t);
un état qui est à la fois initial et terminal est entouré d'un triple cercle (it);
une arête étiquetée par le symbole va de l'état à l'état si et seulement si .
Exemple II. 1 L'automate avec :
est représenté par le graphe suivant :
Exemple II. 2 L'automate avec :
est représenté par le graphe suivant :
1.3 Langage reconnu par un automate fini complet déterministe
Soit l'extension de à définie par :
Soit un alphabet, un langage sur est un sous-ensemble de .
Le langage sur reconnu par un automate fini complet déterministe est :
Notons que certains états et transitions ne sont pas utiles dans la description d'un langage car ils ne permettent pas d'aller d'un état initial à un état terminal.
Exemple II. 3 Le sous-automate de (exemple II.1) composé des états et transitions utiles est représenté par le graphe suivant :
Exemple II. 4 Le sous-automate de (exemple II.2) composé des états et transitions utiles est représenté par le graphe suivant :
Question II. 1 Donner, sans les justifier, deux expressions régulières ou ensemblistes représentant les langages sur reconnus par les automates de l'exemple II. 1 et de l'exemple II.2.
Soit l'opération interne sur les automates finis complets déterministes définie par :
Déf. II. 2 (Composition d'automates finis complets déterministes) Soient et deux automates finis complets déterministes, l'automate qui résulte de la composition de et est défini par :
Question II. 2 En considérant les exemples II. 1 et II.2, construire le graphe représentant l'automate (seuls les états et les transitions utiles devront être construits).
Question II. 3 Caractériser le langage reconnu par par une expression régulière ou ensembliste.
2.2 Propriétés
Question II. 4 Montrer que : si et sont des automates finis complets déterministes alors est un automate fini complet déterministe.
Question II. 5 Montrer que :
Question II. 6 Soient et des automates finis complets déterministes, montrer que :
Question II. 7 Quelle relation liant les langages reconnus par les automates et peut-on en déduire?
Partie III : Algorithmique et programmation en CaML
Cette partie doit être traitée par les étudiants qui ont utilisé le langage CaML dans le cadre des enseignements d'informatique. Les fonctions écrites devront être récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (c'est-à-dire for, while, ...) ni de références.
1 Séquence croissante d'entiers
1.1 Définition
Déf. III. 1 (séquence d'entiers) Une séquence de taille de valeurs entières avec est notée . Sa taille est notée .
Déf. III. 2 (séquence croissante d'entiers) Une séquence d'entiers est croissante si et seulement si:
Une séquence d'entiers est représentée par le type sequence dont la définition est :
type sequence == int list;
Nous supposons prédéfinie la fonction length : sequence -> int telle que l'appel (length ) sur une séquence d'entiers renvoie la valeur entière . Son calcul se termine quelle que soit la valeur de son paramètre.
1.2 Ajout d'une valeur dans une séquence croissante d'entiers
Question III. 1 Écrire en CaML une fonction ajout Sequence de type :
int -> sequence -> sequence
telle que l'appel (ajoutSequence v s) sur une séquence d'entiers s croissante renvoie une séquence d'entiers croissante contenant les mêmes valeurs que la séquence ainsi que l'entier . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question III. 2 Calculer une estimation de la complexité de la fonction ajoutSequence en fonction du nombre d'éléments de la séquence d'entiers s. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
1.3 Scission d'une séquence croissante d'entiers
Question III. 3 Écrire en CaML une fonction scissionSequence de type :
sequence -> (sequence * int * sequence)
telle que l'appel (scissionSequence s) sur une séquence croissante d'entiers de taille impaire strictement positive renvoie un triplet ( ) contenant deux séquences croissantes d'entiers s 1 et s 2 où s 1 est le préfixe de s de taille n , s 2 est le suffixe de s de taille n et v est le -ième entier de (c'est-à-dire que @( )). Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2 Arbre binaire de recherche d'entiers
L'objectif de cet exercice est d'étudier une implantation d'un arbre binaire de recherche et l'opération d'élimination d'une valeur dans un arbre binaire de recherche.
2.1 Arbre binaire d'entiers
Déf. III. 3 (arbre binaire d'entiers) Un arbre binaire d'entiers est une structure qui peut, soit être vide (notée ), soit être un nœud qui contient une étiquette entière (notée ), un sous-arbre gauche (noté ) et un sous-arbre droit (noté ) qui sont tous deux des arbres binaires d'entiers. L'ensemble des étiquettes de tous les nœuds de l'arbre est noté .
Exemple III. 1 (arbre binaire d'entiers) Voici deux exemples d'arbres binaires étiquetés par des entiers (les sous-arbres vides qui sont les fils gauche ou droit des nœuds ne sont pas représentés) :
2.2 Profondeur d'un arbre
Déf. III. 4 (profondeur d'un arbre) Les branches d'un arbre relient la racine aux sous-arbres vides. La profondeur d'un arbre est égale au nombre de liaisons entre les nœuds de la branche la plus longue. Nous la noterons . Nous associerons la profondeur -1 à l'arbre vide .
Exemple III. 2 (profondeurs) Les profondeurs des deux arbres binaires de l'exemple III. 1 sont respectivement 3 et 2 .
2.3 Arbre binaire de recherche d'entiers
Déf. III. 5 (arbre binaire de recherche) Un arbre binaire de recherche est un arbre binaire d'entiers dont:
les fils de la racine sont des arbres binaires de recherche;
les étiquettes de tous les nœuds composant le fils gauche de la racine sont inférieures ou égales à l'étiquette de la racine;
les étiquettes de tous les nœuds composant le fils droit de la racine sont strictement supérieures à l'étiquette de la racine.
Ces contraintes s'expriment sous la forme :
Exemple III. 3 (arbres binaires de recherche) Le premier arbre de l'exemple III. 1 est un arbre binaire de recherche.
Un arbre binaire d'entiers est représenté par le type arbre dont la définition est :
type arbre =
| Vide
| Noeud of arbre * int * arbre;;
Dans l'appel Noeud ( ), les paramètres et fd sont respectivement le fils gauche, l'étiquette et le fils droit de la racine de l'arbre créé.
est alors associée au deuxième arbre binaire représenté graphiquement dans l'exemple III.1.
Soit le programme en langage CaML :
let rec eliminer v a =
let rec aux a =
match a with
| Noeud(g,v,Vide) -> (v,g)
| Noeud(g,v,d) ->
let (vr,ar) = (aux d) in
(vr,(Noeud(g,v,ar))) in
match a with
| Vide -> Vide
| Noeud(g,vp,d) ->
if (vp = v)
then
(let rg = (eliminer v g) in
(if (rg = Vide)
then d
else
let (vm,gp) = aux rg
in Noeud(gp,vm,d)))
else
if (v < vp)
then
Noeud((eliminer v g),vp,d)
else
Noeud(g,vp,(eliminer v d));;
Soit la constante exemple définie et initialisée par :
let exemple =
Noeud(Noeud(Noeud(Vide,1,Vide),2,Vide),2,Noeud(Vide,3,Vide));;
Question III. 4 Détailler les étapes du calcul de (eliminer 2 exemple) en précisant pour chaque appel aux fonctions eliminer et aux, les valeurs des paramètres et résultats.
Question III. 5 Soient les arbres binaires d'entiers a et , soit l'entier , tels que (eliminer a), montrer que:
Question III. 6 Montrer que le calcul des fonctions aux et el iminer se termine quelles que soient les valeurs de leurs paramètres respectant le type des fonctions.
Question III. 7 Donner des exemples de valeurs du paramètre a de la fonction el iminer qui correspondent aux meilleur et pire cas en nombre d'appels récursifs des fonctions aux et eliminer effectués.
Question III. 8 Calculer une estimation de la complexité dans le meilleur et le pire cas de la fonction el iminer en fonction du nombre de valeurs dans l'arbre donné en paramètre. Cette estimation ne prendra en compte que le nombre d'appels récursifs des fonctions aux et el iminer effectués.
3 Problème : Structure de données B-Arbre d'entiers
La création de branches dans un arbre binaire de recherche est effectuée au niveau des feuilles lors de l'ajout de nouvelles valeurs sans possibilité de réorganisation de la structure de l'arbre si les valeurs sont mal réparties. Ceci peut conduire à la construction d'arbres fortement déséquilibrés. De plus, un nœud est nécessaire pour chaque valeur contenue dans l'arbre, ce qui conduit à une structure peu compacte qui demande un grand nombre d'accès en lecture à des positions différentes. Ces accès sont très coûteux lorsque l'arbre est stocké sur un disque pour implanter une base de données par exemple. Pour réduire ces deux défauts, la structure de B-Arbre associe un nombre de valeurs plus important au niveau de chaque nœud, et exploite un algorithme plus complexe lors de l'ajout d'une valeur qui permet d'équilibrer partiellement la structure.
L'objectif de ce problème est l'étude d'une implantation particulière de la structure de B-Arbre en utilisant une liste de couples (étiquette, sous-arbre) pour les nœuds de l'arbre et une liste d'étiquettes pour les feuilles de l'arbre.
3.1 Définitions
Un B-Arbre de nombres entiers est une extension d'un arbre binaire de recherche de nombres entiers telle qu'un nœud peut contenir plusieurs étiquettes et plusieurs sous-arbres. Les étiquettes et les sousarbres sont alternés dans les nœuds de manière à ce que chaque étiquette ait un sous-arbre à sa gauche et un sous-arbre à sa droite. Les étiquettes contenues dans le sous-arbre gauche sont inférieures ou égales à et les étiquettes contenues dans le sous-arbre droit sont supérieures à .
Déf. III. 6 (B-Arbre d'ordre de nombres entiers) Soit un nombre entier strictement positif, un B-Arbre d'ordre de nombres entiers est une structure qui peut être :
soit une feuille qui contient une séquence croissante notée de taille d'étiquettes entières telle que . Le nombre est appelé rang de la feuille;
soit un nœud qui contient une séquence croissante également notée de taille d'étiquettes entières et une séquence de taille de sous-arbres possédant la même structure de B-Arbre d'ordre de nombres entiers telle que . Le nombre est appelé rang du nœud.
Pour toute feuille et pour tout nœud qui ne sont pas à la racine de l'arbre, le rang vérifie également . L'ensemble des feuilles de l'arbre est noté . L'ensemble des nœuds de l'arbre est noté . L'ensemble des étiquettes entières d'un arbre est noté . Les étiquettes des nœuds d'un B-Arbre vérifient la contrainte suivante :
Déf. III. 7 (feuille et nœud complet) Un nœud ou une feuille de rang d'un B-Arbre d'ordre est complet si et seulement si .
Exemple III. 5 (B-Arbre d'ordre 2 d'entiers) Voici un exemple de B-Arbre d'ordre 2 d'entiers (les feuilles sont indiquées par une double barre horizontale) :
Un B-Arbre d'entiers est représenté par la constante entière ordre et les types bArbre, paire et freres dont la définition est :
let ordre = 2;;
type bArbre =
| Feuille of sequence
| Noeud of bArbre * freres
and paire == int * bArbre
and freres == paire list;;
Dans l'appel Noeud ( ), les paramètres p et n sont respectivement le premier fils le plus à gauche , et la séquence croissante des paires d'étiquettes et de fils droit de la racine de l'arbre composé du nœud ainsi créé. Dans l'appel Feuille(s), le paramètre est la séquence croissante des étiquettes de la racine de l'arbre composé de la feuille ainsi créée. Un arbre vide correspond à une feuille dont la séquence d'étiquettes est vide.
est alors associée au B-Arbre d'ordre 2 représenté graphiquement dans l'exemple III. 5.
3.2 Test de complétude dans un B-Arbre
Question III. 9 Écrire en CaML une fonction estComplet de type bArbre -> boolean telle que l'appel (estComplet a) renvoie la valeur true si le nœud, ou la feuille, situé à la racine de a est complet et la valeur false sinon.
3.3 Calcul du nombre de valeurs dans un B-Arbre
Question III. 10 Écrire en CaML une fonction taille de type bArbre -> int telle que l'appel (taille a) renvoie le nombre d'étiquettes entières contenues dans le B-Arbre a, c'est-à-dire le cardinal de . L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
3.4 Recherche d'une étiquette dans un B-Arbre
Question III. 11 Écrire en CaML une fonction recherche de type :
int -> bArbre -> boolean
telle que l'appel (recherche v a) sur un B-Arbre a renvoie la valeur true si et la valeur false sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
3.5 Scission d'un B-Arbre
La scission est l'opération qui permet d'augmenter la taille d'une branche dans un B-Arbre lors de l'ajout d'une étiquette.
Question III. 12 Écrire en CaML une fonction scissionBArbre de type :
bArbre -> (bArbre * int * bArbre)
telle que l'appel (scissionBArbre a) sur un B-Arbre d'ordre dont la racine est complète renvoie un triplet (a1, ) contenant deux -Arbres d'ordre a1 et a2 où a1 est le préfixe de a de rang (contient les premiers fils et étiquettes de a), a2 est le suffixe de a de rang (contient les derniers fils et étiquettes de a) et est la -ième étiquette de a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
3.6 Ajout d'une valeur dans un B-Arbre d'entiers
L'ajout d'une valeur dans un B-Arbre consiste à parcourir l'arbre de la racine vers la feuille qui devra contenir la valeur en suivant le même algorithme que pour rechercher une valeur. Lors de ce parcours de la racine vers la feuille cible, les nœuds complets traversés, et la feuille destination si elle est complète, doivent être scindés. Lors de la scission d'un élément, celui-ci est remplacé par un nœud contenant une seule étiquette, la valeur obtenue par scission, et les deux sous-arbres produits par la scission. Après chaque scission, le parcours se poursuit dans le sous-arbre conduisant à la feuille cible. L'algorithme se conclut par l'insertion de la valeur dans la feuille destination.
Question III. 13 Détailler les étapes de l'ajout de la valeur 3 dans le B-Arbre de l'exemple III. 5 en précisant toutes les étapes et les B-Arbres intermédiaires.
Question III. 14 Montrer que cet algorithme se termine quelles que soient les valeurs de ses paramètres.
Question III. 15 Montrer que cet algorithme d'ajout d'une valeur dans un B-Arbre préserve la structure de B-Arbre d'ordre n, c'est-à-dire que si le paramètre est un B-Arbre d'ordre alors le résultat est un -Arbre d'ordre .
Question III. 16 Écrire en CaML une fonction ajouter de type int -> bArbre -> bArbre telle que l'appel (ajouter a) sur un -Arbre d'entiers a renvoie un -Arbre d'entiers contenant la valeur v et les mêmes valeurs que l'arbre a. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Partie III : Algorithmique et programmation en PASCAL
Cette partie doit être traitée par les étudiants qui ont utilisé le langage PASCAL dans le cadre des enseignements d'informatique. Les fonctions écrites devront être récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (c'est-à-dire for, while, repeat,...).
1 Séquence croissante d'entiers
1.1 Définition
Déf. III. 1 (séquence d'entiers) Une séquence de taille de valeurs entières avec est notée . Sa taille est notée .
Déf. III. 2 (séquence croissante d'entiers) Une séquence d'entiers est croissante si et seulement si:
Une séquence d'entiers est représentée par le type SEQUENCE. Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
Vide est une constante de valeur NIL qui représente une séquence vide;
FUNCTION S_Inserer(e:INTEGER;s:SEQUENCE):SEQUENCE; renvoie une séquence d'entiers composée d'un premier entier e et du reste de la séquence contenu dans ;
FUNCTION S_Tete(s:SEQUENCE) : INTEGER; renvoie le premier entier de la séquence . Cette séquence ne doit pas être vide;
FUNCTION S_Queue(s:SEQUENCE) : SEQUENCE ; renvoie le reste de la séquence privée de son premier entier. Cette séquence ne doit pas être vide;
FUNCTION S_Juxtaposer(s1,s2:SEQUENCE): SEQUENCE; renvoie une séquence composée des éléments de la séquence dans le même ordre que dans suivis des éléments de la séquence s 2 dans le même ordre que dans s 2 ;
FUNCTION S_Taille(s:SEQUENCE): INTEGER; renvoie la valeur entière .
1.2 Ajout d'une valeur dans une séquence croissante d'entiers
Question III. 1 Écrire en PASCAL une fonction :
ajoutSequence (v:INTEGER; s: SEQUENCE ) : SEQUENCE;
telle que l'appel ajoutSequence( ) sur une séquence d'entiers s croissante renvoie une séquence d'entiers croissante contenant les mêmes valeurs que la séquence ainsi que l'entier . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question III. 2 Calculer une estimation de la complexité de la fonction ajoutSequence en fonction du nombre d'éléments de la séquence d'entiers s . Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
1.3 Scission d'une séquence croissante d'entiers
Un triplet contenant une valeur entière et deux séquences d'entiers est représenté par le type de base S_TRIPLET.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
FUNCTION TS_Creer(s1:SEQUENCE;v:INTEGERS;s2:SEQUENCE):S_TRIPLET; renvoie un triplet dont les éléments sont les séquences d'entiers et et la valeur entière ,
FUNCTION TS_Préfixe(t:S_TRIPLET) : SEQUENCE; renvoie la première séquence de ,
FUNCTION TS_Valeur( ) : INTEGER; renvoie la valeur entière de ,
FUNCTION TS_Suffixe(t:S_TRIPLET) : SEQUENCE; renvoie la seconde séquence de .
Question III. 3 Écrire en PASCAL une fonction :
scissionSequence(s:SEQUENCE):S_TRIPLET;
telle que l'appel scissionSequence(s) sur une séquence croissante d'entiers de taille impaire strictement positive renvoie un triplet TS_Creer ( ) contenant deux séquences croissantes d'entiers et où est le préfixe de de taille est le suffixe de de taille et est le -ième entier de (c'est-à-dire que S_Juxtaposer ( Inserer )). Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2 Arbre binaire de recherche d'entiers
L'objectif de cet exercice est d'étudier une implantation d'un arbre binaire de recherche et l'opération d'élimination d'une valeur dans un arbre binaire de recherche.
2.1 Arbre binaire d'entiers
Déf. III. 3 (arbre binaire d'entiers) Un arbre binaire d'entiers est une structure qui peut, soit être vide (notée ), soit être un nœud qui contient une étiquette entière (notée ), un sous-arbre gauche (noté ) et un sous-arbre droit (noté ) qui sont tous deux des arbres binaires d'entiers. L'ensemble des étiquettes de tous les nœuds de l'arbre est noté .
Exemple III. 1 (arbre binaire d'entiers) Voici deux exemples d'arbres binaires étiquetés par des entiers (les sous-arbres vides qui sont les fils gauche ou droit des nœuds ne sont pas représentés) :
2.2 Profondeur d'un arbre
Déf. III. 4 (profondeur d'un arbre) Les branches d'un arbre relient la racine aux sous-arbres vides. La profondeur d'un arbre est égale au nombre de liaisons entre les nœuds de la branche la plus longue. Nous la noterons . Nous associerons la profondeur -1 à l'arbre vide .
Exemple III. 2 (profondeurs) Les profondeurs des deux arbres binaires de l'exemple III. 1 sont respectivement 3 et 2 .
2.3 Arbre binaire de recherche d'entiers
Déf. III. 5 (arbre binaire de recherche) Un arbre binaire de recherche est un arbre binaire d'entiers dont:
les fils de la racine sont des arbres binaires de recherche;
les étiquettes de tous les nœuds composant le fils gauche de la racine sont inférieures ou égales à l'étiquette de la racine;
les étiquettes de tous les nœuds composant le fils droit de la racine sont strictement supérieures à l'étiquette de la racine.
Ces contraintes s'expriment sous la forme :
Exemple III. 3 (arbres binaires de recherche) Le premier arbre de l'exemple III. 1 est un arbre binaire de recherche.
Un arbre binaire d'entiers est représenté par le type de base ARBRE.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
Vide est une constante de valeur NIL qui représente un arbre vide;
FUNCTION Noeud(fg:ARBRE;v:INTEGER;fd:ARBRE) : ARBRE; est une fonction qui renvoie un arbre dont le fils gauche, l'étiquette et le fils droit de la racine sont respectivement et fd;
FUNCTION Gauche (a:ARBRE) : ARBRE; est une fonction qui renvoie le fils gauche de la racine de l'arbre a. Cet arbre ne doit pas être vide;
FUNCTION Etiquette (a: ARBRE) : INTEGER ; est une fonction qui renvoie l'étiquette de la racine de l'arbre a. Cet arbre ne doit pas être vide;
FUNCTION Droit (a: ARBRE) : ARBRE; est une fonction qui renvoie le fils droit de la racine de l'arbre a. Cet arbre ne doit pas être vide.
est alors associée au deuxième arbre binaire représenté graphiquement dans l'exemple III.1.
Un couple contenant un entier et un arbre binaire d'entiers est représenté par le type COUPLE. Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
FUNCTION C_Creer(e:INTEGER;a:ARBRE) : COUPLE; renvoie un couple contenant l'entier e et l'arbre a;
FUNCTION C_Premier (c:COUPLE) : INTEGER; renvoie l'entier contenu dans le couple c ;
FUNCTION C_Second(c:COUPLE): ARBRE; renvoie l'arbre contenu dans le couple c .
Soit le programme en langage PASCAL :
FUNCTION eliminer(v : INTEGER;a:ARBRE):ARBRE;
FUNCTION aux(a :ARBRE):COUPLE;
VAR
rg, g,d : ARBRE;
e : INTEGER;
BEGIN
IF (a <> Vide) THEN BEGIN
g := Gauche(a);
d := Droite(a);
e := Valeur(a);
IF (d = Vide) THEN
aux := Couple(v,g)
ELSE BEGIN
r := aux(d);
vr := Premier(r);
gr := Second(r);
aux := Couple(vr,Noeud(gr,v,d))
END
END
END; { aux }
BEGIN
IF (a = Vide) THEN
eliminer := Vide
ELSE BEGIN
g := Gauche(a);
d := Droite(a);
vp := Valeur(a);
IF (vp = v) THEN
rg := eliminer(v,g);
IF (rg = Vide) THEN
extraire := d
ELSE BEGIN
r := aux(rg);
vr := Premier(r);
gr := Second(r);
eliminer := Noeud(gr,vr,d)
END
ELSE
IF (v < vp) THEN
eliminer := Noeud(eliminer(v,g),vp,d)
ELSE
eliminer := Noeud(g,vp,eliminer(v,d))
END
END; { eliminer }
Soit la constante exemple définie et initialisée par :
Question III. 4 Détailler les étapes du calcul de eliminer ( 2, exemple ) en précisant pour chaque appel aux fonctions el iminer et aux, la valeur du paramètre et du résultat.
Question III. 5 Soient les arbres binaires d'entiers a et , soit l'entier , tels que eliminer(v, a), montrer que:
Question III. 6 Montrer que le calcul des fonctions aux et el iminer se termine quelles que soient les valeurs de leurs paramètres respectant le type des fonctions.
Question III. 7 Donner des exemples de valeurs du paramètre a de la fonction el iminer qui correspondent aux meilleur et pire cas en nombre d'appels récursifs des fonctions aux et el iminer effectués.
Question III. 8 Calculer une estimation de la complexité dans le meilleur et le pire cas de la fonction eliminer en fonction du nombre de valeurs dans l'arbre donné en paramètre. Cette estimation ne prendra en compte que le nombre d'appels récursifs des fonctions aux et el iminer effectués.
3 Problème : Structure de données B-Arbre d'entiers
La création de branches dans un arbre binaire de recherche est effectuée au niveau des feuilles lors de l'ajout de nouvelles valeurs sans possibilité de réorganisation de la structure de l'arbre si les valeurs sont mal réparties. Ceci peut conduire à la construction d'arbres fortement déséquilibrés. De plus, un nœud est nécessaire pour chaque valeur contenue dans l'arbre, ce qui conduit à une structure peu compacte qui demande un grand nombre d'accès en lecture à des positions différentes. Ces accès sont très coûteux lorsque l'arbre est stocké sur un disque pour implanter une base de données par exemple. Pour réduire ces deux défauts, la structure de B-Arbre associe un nombre de valeurs plus important au niveau de chaque nœud, et exploite un algorithme plus complexe lors de l'ajout d'une valeur qui permet d'équilibrer partiellement la structure.
L'objectif de ce problème est l'étude d'une implantation particulière de la structure de B-Arbre en utilisant une liste de couples (étiquette, sous-arbre) pour les nœuds de l'arbre et une liste d'étiquettes pour les feuilles de l'arbre.
3.1 Définitions
Un B-Arbre de nombres entiers est une extension d'un arbre binaire de recherche de nombres entiers telle qu'un nœud peut contenir plusieurs étiquettes et plusieurs sous-arbres. Les étiquettes et les sousarbres sont alternés dans les nœuds de manière à ce que chaque étiquette ait un sous-arbre à sa gauche et un sous-arbre à sa droite. Les étiquettes contenues dans le sous-arbre gauche sont inférieures ou égales à et les étiquettes contenues dans le sous-arbre droit sont supérieures à .
Déf. III. 6 (B-Arbre d'ordre de nombres entiers) Soit un nombre entier strictement positif, un B-Arbre d'ordre de nombres entiers est une structure qui peut être :
soit une feuille qui contient une séquence croissante notée de taille d'étiquettes entières telle que . Le nombre est appelé rang de la feuille;
soit un nœud qui contient une séquence croissante également notée de taille d'étiquettes entières et une séquence de taille de sous-arbres possédant la même structure de B -Arbre d'ordre de nombres entiers telle que . Le nombre est appelé rang du nœud.
Pour toute feuille et pour tout nœud qui ne sont pas à la racine de l'arbre, le rang vérifie également . L'ensemble des feuilles de l'arbre est noté . L'ensemble des nœuds de l'arbre est noté . L'ensemble des étiquettes entières d'un arbre est noté . Les étiquettes des nœuds d'un B-Arbre vérifient la contrainte suivante :
Déf. III. 7 (feuille et nœud complet) Un nœud ou une feuille de rang d'un B-Arbre d'ordre est complet si et seulement si .
Exemple III. 5 (B-Arbre d'ordre 2 d'entiers) Voici un exemple de B-Arbre d'ordre 2 d'entiers (les feuilles sont indiquées par une double barre horizontale) :
Un B-Arbre d'entiers est représenté par la constante entière ordre et le type BARBRE. Une paire d'étiquette entière et de B-Arbre est représentée par le type PAIRE. Une séquence de paires d'étiquettes entières et de B-Arbres d'entiers est représentée par le type FRERES.
CONST ordre : INTEGER = 2;
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
Vide est une constante de valeur NIL qui représente une séquence d'étiquettes entières et de BArbres vide;
FUNCTION Noeud(p:BARBRE;n:FRERES) :BARBRE; est une fonction qui renvoie un nœud d'arbre dont le fils gauche, et la séquence croissante des paires d'étiquettes entières et de fils droits de la racine sont respectivement et ;
FUNCTION Feuille(f:SEQUENCE):BARBRE; est une fonction qui renvoie une feuille d'arbre dont les étiquettes sont contenues dans la séquence croissante d'entiers f ;
FUNCTION Premier (a:BARBRE) : BARBRE; est une fonction qui renvoie le fils gauche de la racine de l'arbre a. La racine de cet arbre ne doit pas être une feuille;
FUNCTION Freres (a: BARBRE) : FRERES; est une fonction qui renvoie l'étiquette de la racine de l'arbre a. La racine de cet arbre ne doit pas être une feuille;
FUNCTION Etiquettes (a:ARBRE) : SEQUENCE; est une fonction qui renvoie la séquence d'étiquettes entières de la racine de l'arbre a. La racine de cet arbre ne doit pas être un nœud;
FUNCTION F_Inserer(p:PAIRE;s:FRERES) :FRERES; renvoie une séquence d'entiers composée d'un premier entier e et du reste de la séquence contenu dans ;
FUNCTION F_Tete(s:FRERES) : PAIRE; renvoie la première paire de la séquence . Cette séquence ne doit pas être vide;
FUNCTION F_Queue(s:FRERES) : FRERES; renvoie le reste de la séquence privée de sa première paire. Cette séquence ne doit pas être vide;
FUNCTION F_Juxtaposer(s1,s2:FRERES) : FRERES; renvoie une séquence composée des éléments de la séquence dans le même ordre que dans suivis des éléments de la séquence s2 dans le même ordre que dans s2;
FUNCTION P_Creer(e:INTEGER, a:BARBRE):PAIRE; renvoie une paire contenant l'étiquette entière e et le B-Arbre a;
FUNCTION P_Etiquette(p:PAIRE) : INTEGER; renvoie l'étiquette contenue dans la paire p;
FUNCTION P_Arbre ( p : PAIRE) : BARBRE; renvoie le B-Arbre d'entiers contenu dans la paire p.
est alors associée au B-Arbre d'ordre 2 représenté graphiquement dans l'exemple III.5.
3.2 Test de complétude dans un B-Arbre
Question III. 9 Écrire en PASCAL une fonction est Complet (a : BARBRE) : BOOLEAN; telle que l'appel estComplet (a) renvoie la valeur true si le nœud, ou la feuille, situé à la racine de a est complet et la valeur false sinon.
3.3 Calcul du nombre de valeurs dans un B-Arbre
Question III. 10 Écrire en PASCAL une fonction taille (a : BARBRE) : INTEGER ; telle que l'appel taille (a) renvoie le nombre d'étiquettes entières contenues dans le B-Arbre a, c'est-à-dire le cardinal de . L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
3.4 Recherche d'une étiquette dans un B-Arbre
Question III. 11 Écrire en PASCAL une fonction :
recherche(v:INTEGER;a:bArbre):BOOLEAN
telle que l'appel recherche ( v , a) sur un B-Arbre a renvoie la valeur TRUE si et la valeur FALSE sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
3.5 Scission d'un B-Arbre
La scission est l'opération qui permet d'augmenter la taille d'une branche dans un B-Arbre lors de l'ajout d'une étiquette.
Un triplet contenant une valeur entière et deux B-Arbre d'entiers est représenté par le type de base A_TRIPLET.
Nous supposons prédéfinies les constantes et les fonctions suivantes dont le calcul se termine quelles que soient les valeurs de leurs paramètres. Elles pourront éventuellement être utilisées dans les réponses aux questions :
FUNCTION TA_Creer(a1:BARBRE;v:INTEGERS;a2:BARBRE):A_TRIPLET; renvoie un triplet dont les éléments sont les B-Arbres d'entiers a1 et a2 et la valeur entière v ,
FUNCTION TA_Préfixe( : A_TRIPLET) : BARBRE; renvoie le premier B-Arbre de ,
FUNCTION TA_Valeur( t : A_TRIPLET) : INTEGER; renvoie la valeur entière de t ,
FUNCTION TA_Suffixe( : A_TRIPLET) : BARBRE; renvoie le second B-Arbre de .
Question III. 12 Écrire en PASCAL unefonction scissionBArbre (a:BARBRE) : A_TRIPLET; telle que l'appel scissionBARBRE (a) sur un B-Arbre d'ordre dont la racine est complète renvoie un triplet TA_Creer (a1, v, a2) contenant deux B-Arbres d'ordre a1 et a2 telles que a1 est le préfixe de a de taille (contient les premiers fils et étiquettes de a), a2 est le suffixe de a de taille (contient les derniers fils et étiquettes de a) et est la -ième étiquette de a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
3.6 Ajout d'une valeur dans un B-Arbre d'entiers
L'ajout d'une valeur dans un B-Arbre consiste à parcourir l'arbre de la racine vers la feuille qui devra contenir la valeur en suivant le même algorithme que pour rechercher une valeur. Lors de ce parcours de la racine vers la feuille cible, les nœuds complets traversés, et la feuille destination si elle est complète, doivent être scindés. Lors de la scission d'un élément, celui-ci est remplacé par un nœud contenant une seule étiquette, la valeur obtenue par scission, et les deux sous-arbres produits par la scission. Après chaque scission, le parcours se poursuit dans le sous-arbre conduisant à la feuille cible. L'algorithme se conclut par l'insertion de la valeur dans la feuille destination.
Question III. 13 Détailler les étapes de l'ajout de la valeur 3 dans le B-Arbre de l'exemple III. 5 en précisant toutes les étapes et les B-Arbres intermédiaires.
Question III. 14 Montrer que cet algorithme se termine quelles que soient les valeurs de ses paramètres.
Question III. 15 Montrer que cet algorithme d'ajout d'une valeur dans un B-Arbre préserve la structure de B-Arbre d'ordre n, c'est-à-dire que si le paramètre est un B-Arbre d'ordre alors le résultat est un -Arbre d'ordre .
Question III. 16 Écrire en PASCAL une fonction ajouter (v: INTEGER ; a : BARBRE) : BARBRE ; telle que l'appel ajouter ( ) sur un -Arbre d'ordre n d'entiers a renvoie un -Arbre d'ordre d'entiers contenant la valeur vet les mêmes valeurs que l'arbre a. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Fin de l'énoncé
CCINP Option Informatique MP 2012 - Version Web LaTeX | WikiPrépa | WikiPrépa
