Les calculatrices sont interdites.
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.
PrÉambule : Les deux parties qui composent ce sujet sont indépendantes et peuvent être traitées par les candidats dans un ordre quelconque.
Partie I: Automates et langages
Le but de cet exercice est l'étude des propriétés de l'opération d'entrelacement || de deux automates. Cette opération permet de composer deux automates qui doivent lire la même entrée. Elle est utilisée pour la modélisation d'activités concurrentes qui partagent une même ressource.
1 Automate fini
Pour simplifier les preuves, nous nous limiterons au cas des automates finis semi-indéterministes, c'est-à-dire les automates finis non déterministes qui ne contiennent pas de transitions instantanées (ou -transitions). Les résultats étudiés s’étendent au cadre des automates finis quelconques.
1.1 Représentation d'un automate fini
Déf. I. 1 (Automate fini semi-indé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 semi-indéterministe sur est un quintuplet composé de :
Un ensemble fini d'états : ;
Un ensemble d'états initiaux : ;
Un ensemble d'états terminaux : ;
Une relation 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.
Remarquons que est le graphe d'une application de transition dont les valeurs sont définies par :
La notation est plus adaptée que à la formalisation et la construction des preuves dans le cadre des automates indéterministes.
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 relation 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 I. 1 L'automate avec :
est représenté par le graphe suivant :
Exemple I. 2 L'automate avec :
est représenté par le graphe suivant :
1.3 Langage reconnu par un automate fini
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 est :
Question I. 1 Donner sans les justifier deux expressions régulières ou ensemblistes représentant les langages sur reconnus par les automates de l'exemple I. 1 et de l'exemple I.2.
2 Entrelacement de mots et de langages
Soit l'opération sur les mots définie par :
Déf. I. 2 (Entrelacement de mots) Soient et deux mots de , le langage résultant de l'entrelacement de et est défini par :
Question I. 2 Soit l'alphabet , construire explicitement le langage (a.b) (c.d).
3 Entrelacement de langages
Soit l'opération interne sur les langages définie par:
Déf. I. 3 (Entrelacement de langages) Soient et deux langages sur , le langage résultant de l'entrelacement des mots de et est défini par :
4 Entrelacement d'automates
4.1 Définition
Soit l'opération interne sur les automates finis semi-indéterministes définie par :
Déf. I. 4 (Entrelacement d'automates) Soient et deux automates finis semi-indéterministes, l'automate qui résulte de l'entrelacement de et est défini par :
Question I. 3 En considérant les exemples I. 1 et I.2, construire l'automate .
Question I. 4 Caractériser le langage reconnu par , par une expression régulière ou ensembliste.
4.2 Propriétés
Question I. 5 Montrer que : si et sont des automates finis semi-indéterministes alors est un automate fini semi-indéterministe.
Question I. 6 Montrer que :
Question I. 7 Montrer que:
Question I. 8 Montrer que:
Question I. 9 Soient et des automates finis semi-indéterministes, montrer que :
Partie II : 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 (for, while, ...) ni de références.
Format de description d'une fonction : La description d'une fonction, lorsque celle-ci est demandée, c'est-à-dire à la question II.25, doit au moins contenir :
L’objectif général;
Le rôle des paramètres de la fonction;
Les contraintes sur les valeurs des paramètres;
Les caractéristiques du résultat renvoyé par la fonction;
Le rôle des variables locales à la fonction;
Le principe de l'algorithme;
Des arguments de terminaison du calcul pour toutes les valeurs des paramètres qui vérifient les contraintes présentées au point 3.
La structure d'ensemble d'entiers est utilisée dans de nombreux algorithmes (par exemple, pour la déterminisation ou la minimisation d'automates). L'objectif de ce problème est l'étude d'une réalisation particulière de cette structure à base d'arbres binaires de recherche équilibrés nommés arbres AVL (du nom de leurs créateurs Adelson-Velskii et Landis). L’objectif de cette réalisation est d'optimiser à la fois l'occupation mémoire et la durée de recherche d'un élément dans un ensemble.
1 Réalisation à base de listes
La réalisation la plus simple d'un ensemble d'entiers repose sur l'utilisation d'une liste d'entiers qui contient exactement un exemplaire de chaque élément contenu dans l'ensemble.
1.1 Représentation en CaML
Nous ferons l'hypothèse qu'un élément appartenant à un ensemble n'apparaît qu'une seule fois dans la liste représentant cet ensemble.
Un ensemble d'entiers est représenté par le type ensemble équivalent à une liste de int.
type ensemble == int list;;
Le parcours d'un ensemble sera donc effectué de la même manière que celui d'une liste.
Nous allons maintenant définir plusieurs opérations sur les ensembles d'entiers et estimer leur complexité.
1.2 Opérations sur la structure d'ensemble
1.2.1 Insertion dans un ensemble
La première opération est l'insertion d'un entier à un ensemble.
Question II. 1 Écrire en CaML une fonction inserer_ens de type int -> ensemble -> ensemble telle que l'appel (inserer_ens v ) renvoie un ensemble contenant les mêmes éléments que l'ensemble ainsi que l'élément s'il ne figurait pas déjà dans E. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 2 Calculer une estimation de la complexité de la fonction inserer _ens en fonction du nombre d'éléments de l'ensemble E. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
1.2.2 Recherche dans un ensemble
La seconde opération consiste à rechercher un entier dans un ensemble.
Question II. 3 Écrire en CaML une fonction rechercher _ens de type
int -> ensemble -> bool telle que l'appel (rechercher_ens v E) renvoie la valeur true si l'ensemble contient l'entier v et la valeur false sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 4 Donner des exemples de valeurs des paramètres v et E de la fonction
rechercher_ens qui correspondent au meilleur et pire cas en nombre d'appels récursifs effectués.
Calculer une estimation de la complexité dans les meilleur et pire cas de la fonction
rechercher_ens en fonction du nombre d'éléments de l'ensemble E. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2 Réalisation à base d'arbres binaires de recherche
L'utilisation de la structure d'arbre binaire de recherche permet de réduire la complexité en temps de calcul pour les opérations d'insertion et de recherche.
2.1 Arbres binaires d'entiers
Un ensemble d'entiers peut être réalisé par un arbre binaire en utilisant les étiquettes des nœuds pour représenter les éléments contenus dans l'ensemble.
2.1.1 Définition
Déf. II. 1 (Arbre binaire d'entiers) Un arbre binaire d'entiers a 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 a est noté .
Exemple II. 1 (Arbres binaires d'entiers) Voici trois exemples d'arbres binaires étiquetés par des entiers (les sous-arbres vides des nœuds ne sont pas représentés) :
2.1.2 Profondeur d'un arbre
Déf. II. 2 (Profondeur d'un arbre) Les branches d'un arbre relient la racine aux feuilles. La profondeur d'un arbre A est égale au nombre de nœuds de la branche la plus longue. Nous la noterons .
Exemple II. 2 (Profondeurs) Les profondeurs des trois arbres binaires de l'exemple II. 1 sont respectivement 3, 4 et 4.
Question II. 5 Donner une définition de la profondeur d'un arbre a en fonction de et .
Question II. 6 Considérons un arbre binaire d'entiers représentant un ensemble contenant n éléments. Quelle est la forme de l'arbre dont la profondeur est maximale? Quelle est la forme de l'arbre dont la profondeur est minimale? Calculer la profondeur de l'arbre en fonction de dans ces deux cas. Vous justifierez vos réponses.
2.1.3 Déséquilibre d'un arbre
Déf. II. 3 (Déséquilibre d'un nœud dans un arbre binaire) Le déséquilibre (a) d'un nœud a dans un arbre binaire est égal à la différence entre la profondeur de son fils gauche et la profondeur de son fils droit, c'est-à-dire :
Nous considérerons par la suite des arbres binaires dont chaque nœud est décoré par son déséquilibre.
Exemple II. 3 (Arbres binaires d'entiers décorés) Voici les arbres de l'exemple II. 1 décorés par le déséquilibre de chaque nœud :
2.1.4 Représentation des arbres binaires en CaML
Un arbre binaire d'entiers dont les nœuds sont décorés par leurs déséquilibres est représenté par le type CaML :
type arbre = Vide | Noeud of int * arbre * int * arbre;;
Dans l'appel Noeud( ), les paramètres et sont respectivement le déséquilibre, le fils gauche, l'étiquette et le fils droit de la racine de l'arbre créé.
est alors associé au premier arbre binaire représenté graphiquement dans l'exemple II.3.
2.1.5 Profondeur d'un arbre binaire d'entiers
Question II. 7 Écrire en CaML une fonction profondeur de type arbre -> int telle que l'appel (profondeur a) renvoie la profondeur de l'arbre binaire d'entiers a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.1.6 Validation d'un arbre binaire d'entiers décoré
Une première opération consiste à déterminer si les valeurs des déséquilibres des nœuds d'un arbre binaire sont correctes.
Question II. 8 Écrire en CaML une fonction valider decore de type arbre -> bool telle que l'appel (valider_decore A) renvoie la valeur true si l'arbre binaire A est vide ou si l'arbre binaire A n'est pas vide et si les valeurs des déséquilibres des nœuds de l'arbre binaire sont correctes et la valeur false sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 9 Calculer une estimation de la complexité de la fonction valider_decore en fonction du nombre de nœuds de l'arbre A. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.2 Arbres binaires de recherche
Déf. II. 4 (Arbre binaire de recherche) Un arbre binaire de recherche est un arbre binaire d'entiers dont les étiquettes de tous les nœuds composant le fils gauche de la racine sont strictement inférieures à l'étiquette de la racine et les étiquettes de tous les nœuds composant le fils droit de la racine sont strictement supérieures à l'étiquette de la racine. Cette contrainte s'exprime sous la forme :
Exemple II. 5 (Arbres binaires de recherche) Le deuxième et le troisième arbre de l'exemple II. 3 sont des arbres binaires de recherche.
Notons qu'un arbre binaire de recherche ne peut contenir qu'un seul exemplaire d'une valeur donnée.
Nous considérerons par la suite des arbres de recherche dont chaque nœud est décoré par son déséquilibre.
2.2.1 Validation d'un arbre binaire de recherche
Une première opération consiste à déterminer si un arbre binaire d'entiers est un arbre binaire de recherche.
Question II. 10 Écrire en CaML une fonction valider abr de type arbre -> bool telle que l'appel (valider_abr A) renvoie la valeur true si l'arbre binaire d'entiers A est un arbre binaire de recherche et la valeur false sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.2.2 Recherche dans un arbre binaire de recherche
Une deuxième opération consiste à déterminer si un arbre binaire contient une étiquette particulière.
Question II. 11 Écrire en CaML une fonction rechercher abr de type
int -> arbre -> bool telle que l'appel (rechercher_abr v A) renvoie la valeur true si l'un des nœuds de l'arbre binaire de recherche contient l'étiquette et la valeur false sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 12 Donner des exemples de valeurs des paramètres v et A de la fonction rechercher_abr qui correspondent au meilleur et pire cas en nombre d'appels récursifs effectués.
Calculer une estimation de la complexité dans les meilleur et pire cas de la fonction rechercher_abr en fonction de la profondeur de l'arbre . Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.2.3 Insertion dans un arbre binaire de recherche
Une deuxième opération consiste à insérer un élément dans un arbre binaire de recherche en préservant cette structure. Pour cela, l'insertion se fait au niveau des feuilles de l'arbre (ou des nœuds ne contenant qu'un seul fils en lieu et place du fils absent).
Question II. 13 Calculer l'accroissement de la profondeur d'un arbre binaire de recherche a dans lequel l'étiquette est insérée en fonction de , de la relation entre et , de , de ou de .
Question II. 14 Écrire en CaML une fonction inserer_abr de type int -> arbre -> arbre telle que l'appel (inserer_abr A) renvoie un arbre binaire de recherche contenant les mêmes étiquettes que l'arbre binaire de recherche ainsi que l'étiquette v s'il ne la contenait pas déjà. Cette fonction doit également calculer les valeurs des déséquilibres de chaque nœud de l'arbre résultat. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 15 Donner une estimation de la complexité dans les meilleur et pire cas de la fonction inserer_abr en fonction de la profondeur de l'arbre . Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.3 Rotations d'un arbre binaire de recherche
Les rotations sont des transformations d'un arbre binaire de recherche qui sont utilisées pour équilibrer la structure de l'arbre, c'est-à-dire donner une valeur proche à la longueur de chaque branche. Il s'agit donc de réduire le déséquilibre entre les différentes branches qui sont de longueurs différentes.
Déf. II. 5 Rotation simple
Une rotation simple concerne 2 nœuds imbriqués de l'arbre. Un arbre qui ne possède pas la structure adéquate (partie gauche de la règle) ne sera pas transformé.
Déf. II. 6 Rotation double
Une rotation double concerne 3 nœuds imbriqués de l'arbre. Un arbre qui ne possède pas la structure adéquate (partie gauche de la règle) ne sera pas transformé.
Question II. 16 Exprimer les rotations doubles comme des combinaisons de rotations simples.
Question II. 17 Montrer que les rotations ne perturbent pas la structure d'arbre binaire de recherche.
Question II. 18 Pour chaque rotation possible, calculer les nouvelles valeurs des déséquilibres des 2 ou 3 nœuds concernés de l'arbre après la rotation en fonction des valeurs avant la rotation.
2.3.1 Rotation simple de type
Une première opération consiste à effectuer une rotation simple de type dans un arbre binaire de recherche pour équilibrer celui-ci.
Question II. 19 Écrire en CaML une fonction rotationSD de type arbre -> arbre telle que l'appel (rotationSD A) sur un arbre A dont la structure permet l'application d'une rotation simple de type sur la racine renvoie l'arbre binaire de recherche sur lequel une rotation simple de type a été appliquée à la racine.
2.3.2 Rotation simple de type G
Une deuxième opération consiste à effectuer une rotation simple de type dans un arbre binaire de recherche pour équilibrer celui-ci.
Nous supposons prédéfinie la fonction rotationSG de type arbre -> arbre telle que l'appel (rotationSG A) sur un arbre A dont la structure permet l'application d'une rotation simple
de type G à la racine renvoie l'arbre binaire de recherche A sur lequel une rotation simple de type G a été appliquée à la racine. Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
2.3.3 Rotation double de type D
Une troisième opération consiste à effectuer une rotation double de type dans un arbre binaire de recherche pour équilibrer celui-ci.
Question II. 20 Écrire en CaML une fonction rotationDD de type arbre -> arbre telle que l'appel (rotationDD A) sur un arbre dont la structure permet l'application d'une rotation double de type à la racine renvoie l'arbre binaire de recherche sur lequel une rotation double de type a été appliquée à la racine.
2.3.4 Rotation double de type G
Une quatrième opération consiste à effectuer une rotation double de type G dans un arbre binaire de recherche pour équilibrer celui-ci.
Nous supposons prédéfinie la fonction rotationDG de type arbre -> arbre telle que l'appel (rotationDG A) sur un arbre A dont la structure permet l'application d'une rotation double de type G à la racine renvoie l'arbre binaire de recherche A sur lequel une rotation double de type G a été appliquée à la racine. Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
3 Arbres équilibrés
Pour réduire la complexité des opérations d'insertion et de recherche, il est nécessaire que les longueurs de toutes les branches de l'arbre aient des valeurs semblables. L'arbre a alors une structure dite équilibrée.
3.1 Définitions
Déf. II. 7 (Arbres binaires équilibrés) Un arbre binaire est dit équilibré si le déséquilibre de chacun de ses nœuds appartient à . Nous appellerons nœuds déséquilibrés les nœuds dont le déséquilibre n'appartient pas à .
Exemple II. 6 (Arbres binaires équilibrés) Le premier et le troisième arbres de l'exemple II. 3 sont équilibrés. Le deuxième arbre est déséquilibré. Il possède 2 nœuds déséquilibrés qui contiennent les étiquettes 6 et 9 .
3.2 Principe de l'équilibrage
Question II. 21 L'insertion d'une nouvelle étiquette dans un arbre binaire de recherche équilibré peut produire des nœuds déséquilibrés. Donner les différentes formes possibles pour le nœud déséquilibré le plus profond produit lors de l'insertion d'une nouvelle étiquette dans un arbre binaire équilibré en précisant la valeur du déséquilibre de ce nœud.
Question II. 22 Montrer qu'une rotation suffit à rééquilibrer le nœud déséquilibré le plus profond qui est apparu lors de l'insertion d'une nouvelle étiquette dans un arbre binaire équilibré. Donner la rotation qui doit être utilisée pour rééquilibrer ce nœud pour chacune des formes étudiées dans la question précédente.
3.3 Équilibrage d'un nœud
Une première opération consiste à équilibrer les nœuds qui viennent d'être déséquilibrés par l'opération d'insertion.
Question II. 23 Écrire en CaML une fonction equilibrage de type arbre -> arbre telle que l'appel (equilibrage A) avec un arbre binaire de recherche dont la racine est déséquilibrée et dont les fils gauche et droit sont équilibrés renvoie un arbre binaire de recherche équilibré contenant les mêmes étiquettes que .
3.4 Insertion équilibrée
Une seconde opération consiste à insérer une nouvelle étiquette dans un arbre de recherche équilibré en préservant la structure équilibrée de l'arbre.
Question II. 24 Modifier la fonction inserer_abr de type int -> arbre -> arbre écrite en CaML à la question II. 14 telle que si A est un arbre binaire de recherche équilibré alors l'appel (inserer_abr ) renverra un arbre binaire de recherche équilibré.
Question II. 25 Expliquer la fonction inserer abr définie à la question précédente.
3.5 Complexité des opérations dans un arbre équilibré
La complexité calculée aux questions II. 15 et II. 12 pour les opérations d'insertion et de recherche dépend de la profondeur de l'arbre. Pour comparer celle-ci avec celle d'une réalisation à base de liste, il faut estimer la profondeur de l'arbre en fonction du nombre d'éléments contenus dans l'ensemble. Nous avons calculé celle-ci dans le meilleur des cas pour un arbre équilibré à la question II.6. Il faut maintenant évaluer celle-ci dans le pire des cas.
Question II. 26 Quelles sont les formes de l'arbre équilibré a dans le meilleur cas et le pire cas pour l'insertion et la recherche d'une étiquette dans ?
Question II. 27 Soit le nombre de nœuds dans un arbre dans le meilleur des cas, exprimer en fonction de .
Question II. 28 Soit le nombre de nœuds dans un arbre dans le pire des cas, exprimer sous la forme d'une relation de récurrence dépendant de et .
Question II. 29 Soit , résoudre l'équation linéaire à coefficients constants dérivée de la relation de récurrence précédente pour obtenir la valeur de en fonction de .
Question II. 30 Déduire des questions II. 27 et II. 29 un encadrement de la profondeur d'un arbre en fonction du nombre de nœuds qu'il contient. En déduire la complexité des opérations de recherche et d'insertion dans un arbre binaire de recherche équilibré.
Partie II : 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 (for, while, repeat,...).
Format de description d'une fonction : La description d'une fonction, lorsque celle-ci est demandée, c'est-à-dire à la question II.25, doit au moins contenir :
L’objectif général;
Le rôle des paramètres de la fonction;
Les contraintes sur les valeurs des paramètres;
Les caractéristiques du résultat renvoyé par la fonction;
Le rôle des variables locales à la fonction;
Le principe de l'algorithme;
Des arguments de terminaison du calcul pour toutes les valeurs des paramètres qui vérifient les contraintes présentées au point 3.
La structure d'ensemble d'entiers est utilisée dans de nombreux algorithmes (par exemple, pour la déterminisation ou la minimisation d'automates). L'objectif de ce problème est l'étude d'une réalisation particulière de cette structure à base d'arbres binaires de recherche équilibrés nommés arbres AVL (du nom de leurs créateurs Adelson-Velskii et Landis). L’objectif de cette réalisation est d'optimiser à la fois l'occupation mémoire et la durée de recherche d'un élément dans un ensemble.
1 Réalisation à base de listes
La réalisation la plus simple d'un ensemble d'entiers repose sur l'utilisation d'une liste d'entiers qui contient exactement un exemplaire de chaque élément contenu dans l'ensemble.
1.1 Représentation en PASCAL
Nous ferons l'hypothèse qu'un élément appartenant à un ensemble n'apparaît qu'une seule fois dans la liste représentant cet ensemble.
Un ensemble d'entiers est représenté par le type de base ENSEMBLE correspondant à une liste d'entiers.
Le parcours d'un ensemble sera donc effectué de la même manière que celui d'une liste.
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 :
NIL représente la liste vide d'entiers;
FUNCTION LE_Inserer(V:INTEGER;E:ENSEMBLE):ENSEMBLE; renvoie une liste d'entiers composée d'un premier entier et du reste de la liste contenu dans ;
FUNCTION LE_Premier(E:ENSEMBLE):INTEGER; renvoie le premier entier de la liste E. Cette liste ne doit pas être vide;
FUNCTION LE_Reste(E:ENSEMBLE):ENSEMBLE; renvoie le reste de la liste E privée de son premier entier. Cette liste ne doit pas être vide.
Nous allons maintenant définir plusieurs opérations sur les ensembles d'entiers et estimer leur complexité.
1.2 Opérations sur la structure d'ensemble
1.2.1 Insertion dans un ensemble
La première opération est l'insertion d'un entier à un ensemble.
Question II. 1 Écrire en PASCAL une fonction
inserer_ens(v:INTEGER;E:ENSEMBLE):ENSEMBLE; telle que l'appel
inserer_ens( ) renvoie un ensemble contenant les mêmes entiers que l'ensemble ainsi que l'entier v s'il ne figurait pas déjà dans E. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 2 Calculer une estimation de la complexité de la fonction inserer ens en fonction du nombre d'éléments de l'ensemble E. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
1.2.2 Recherche dans un ensemble
La seconde opération consiste à rechercher un entier dans un ensemble.
Question II. 3 Écrire en PASCAL une fonction
rechercher_ens(v:INTEGER;E:ENSEMBLE):BOOLEAN; telle que l'appel
rechercher_ens( ) renvoie la valeur TRUE si l'ensemble contient l'entier v et la valeur FALSE sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 4 Donner des exemples de valeurs des paramètres v et de la fonction
rechercher_ens qui correspondent au meilleur et pire cas en nombre d'appels récursifs effectués.
Calculer une estimation de la complexité dans les meilleur et pire cas de la fonction
rechercher_ens en fonction du nombre d'éléments de l'ensemble E. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2 Réalisation à base d'arbres binaires de recherche
L'utilisation de la structure d'arbre binaire de recherche permet de réduire la complexité en temps de calcul pour les opérations d'insertion et de recherche.
2.1 Arbres binaires d'entiers
Un ensemble d'entiers peut être réalisé par un arbre binaire en utilisant les étiquettes des nœuds pour représenter les éléments contenus dans l'ensemble.
2.1.1 Définition
Déf. II. 1 (Arbre binaire d'entiers) Un arbre binaire d'entiers a est une structure qui peut soit être vide (notée Ø), soit être un nœud qui contient une étiquette entière (notée (a)), 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 a est noté .
Exemple II. 1 (Arbres binaires d'entiers) Voici trois exemples d'arbres binaires étiquetés par des entiers (les sous-arbres vides des nœuds ne sont pas représentés) :
2.1.2 Profondeur d'un arbre
Déf. II. 2 (Profondeur d'un arbre) Les branches d'un arbre relient la racine aux feuilles. La profondeur d'un arbre est égale au nombre de nœuds de la branche la plus longue. Nous la noterons .
Exemple II. 2 (Profondeurs) Les profondeurs des trois arbres binaires de l'exemple II. 1 sont respectivement 3, 4 et 4.
Question II. 5 Donner une définition de la profondeur d'un arbre a en fonction de et .
Question II. 6 Considérons un arbre binaire d'entiers représentant un ensemble contenant n éléments. Quelle est la forme de l'arbre dont la profondeur est maximale? Quelle est la forme de l'arbre dont la profondeur est minimale? Calculer la profondeur de l'arbre en fonction de dans ces deux cas. Vous justifierez vos réponses.
2.1.3 Déséquilibre d'un arbre
Déf. II. 3 (Déséquilibre d'un nœud dans un arbre binaire) Le déséquilibre d'un nœud a dans un arbre binaire est égal à la différence entre la profondeur de son fils gauche et la profondeur de son fils droit, c'est-à-dire :
Nous considérerons par la suite des arbres binaires dont chaque nœud est décoré par son déséquilibre.
Exemple II. 3 (Arbres binaires d'entiers décorés) Voici les arbres de l'exemple II. 1 décorés par le déséquilibre de chaque nœud :
2.1.4 Représentation des arbres binaires en PASCAL
Un arbre binaire d'entiers dont les nœuds sont décorés par leurs déséquilibres 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 ou une liste vide;
FUNCTION Noeud(d:INTEGER;fg:ARBRE;v:INTEGER;fd:ARBRE):ARBRE; est une fonction qui renvoie un arbre dont le déséquilibre, le fils gauche, l’étiquette et le fils droit de la racine sont respectivement et ,
FUNCTION Desequilibre(a:ARBRE):INTEGER; est une fonction qui renvoie le déséquilibre de la racine de l'arbre a;
FUNCTION Gauche(a:ARBRE):ARBRE; est une fonction qui renvoie le fils gauche de la racine de l'arbre a;
FUNCTION Etiquette(a:ARBRE):INTEGER; est une fonction qui renvoie l'étiquette de la racine de l'arbre a;
FUNCTION Droit(a:ARBRE) : ARBRE; est une fonction qui renvoie le fils droit de la racine de l'arbre a.
renvoie le premier arbre binaire d'entiers représenté graphiquement dans l'exemple II.3.
2.1.5 Profondeur d'un arbre binaire d'entiers
Question II. 7 Écrire en PASCAL une fonction profondeur(a:ARBRE) : INTEGER; telle que l'appel profondeur(a) renvoie la profondeur de l'arbre binaire d'entiers a. Cette fonction devra
être récursive ou faire appel à des fonctions auxiliaires récursives.
2.1.6 Validation d'un arbre binaire d'entiers décoré
Une première opération consiste à déterminer si les valeurs des déséquilibres des nœuds d'un arbre binaire sont correctes.
Question II. 8 Écrire en PASCAL une fonction valider_decore(A:ARBRE) : BOOLEAN; telle que l'appel valider_decore( ) renvoie la valeur TRUE si l'arbre binaire est vide ou si l'arbre binaire A n'est pas vide et si les valeurs des déséquilibres des nœuds de l'arbre binaire sont correctes et la valeur FALSE sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 9 Calculer une estimation de la complexité de la fonction valider decore en fonction du nombre de nœuds de l'arbre . Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.2 Arbres binaires de recherche
Déf. II. 4 (Arbre binaire de recherche) Un arbre binaire de recherche est un arbre binaire d'entiers dont les étiquettes de tous les nœuds composant le fils gauche de la racine sont strictement inférieures à l'étiquette de la racine et les étiquettes de tous les nœuds composant le fils droit de la racine sont strictement supérieures à l'étiquette de la racine. Cette contrainte s'exprime sous la forme :
Exemple II. 5 (Arbres binaires de recherche) Le deuxième et le troisième arbre de l'exemple II. 3 sont des arbres binaires de recherche.
Notons qu'un arbre binaire de recherche ne peut contenir qu'un seul exemplaire d'une valeur donnée.
Nous considérerons par la suite des arbres de recherche dont chaque nœud est décoré par son déséquilibre.
2.2.1 Validation d'un arbre binaire de recherche
Une première opération consiste à déterminer si un arbre binaire d'entiers est un arbre binaire de recherche.
Question II. 10 Écrire en PASCAL une fonction valider_abr (A:ARBRE) : BOOLEAN; telle que l'appel valider_abr ( ) renvoie la valeur TRUE si l'arbre binaire d'entiers est un arbre binaire de recherche et la valeur FALSE sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
2.2.2 Recherche dans un arbre binaire de recherche
Une deuxième opération consiste à déterminer si un arbre binaire contient une étiquette particulière.
Question II. 11 Écrire en PASCAL une fonction
rechercher_abr(v:INTEGER;A:ARBRE) :BOOLEAN; telle que l'appel rechercher_abr ( ) renvoie la valeur TRUE si l'un des nœuds de l'arbre binaire de recherche A contient l'étiquette et la valeur FALSE sinon. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 12 Donner des exemples de valeurs des paramètres v et A de la fonction rechercher_abr qui correspondent au meilleur et pire cas en nombre d'appels récursifs effectués.
Calculer une estimation de la complexité dans les meilleur et pire cas de la fonction rechercher_abr en fonction de la profondeur de l'arbre . Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.2.3 Insertion dans un arbre binaire de recherche
Une deuxième opération consiste à insérer un élément dans un arbre binaire de recherche en préservant cette structure. Pour cela, l'insertion se fait au niveau des feuilles de l'arbre (ou des nœuds ne contenant qu'un seul fils en lieu et place du fils absent).
Question II. 13 Calculer l'accroissement de la profondeur d'un arbre binaire de recherche a dans lequel l'étiquette est insérée en fonction de , de la relation entre et , de , de ou de .
Question II. 14 Écrire en PASCAL une fonction
inserer_abr ( : INTEGER; : ARBRE ) : ARBRE; telle que l'appel inserer_abr ( ) renvoie un arbre binaire de recherche contenant les mêmes étiquettes que l'arbre binaire de recherche A ainsi que l'étiquette v s'il ne la contenait pas déjà. Cette fonction doit également calculer les valeurs des déséquilibres de chaque nœud de l'arbre résultat. L'algorithme utilisé ne devra parcourir qu'une seule fois l'arbre. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question II. 15 Donner une estimation de la complexité dans les meilleur et pire cas de la fonction inserer_abr en fonction de la profondeur de l'arbre A. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.3 Rotations d'un arbre binaire de recherche
Les rotations sont des transformations d'un arbre binaire de recherche qui sont utilisées pour équilibrer la structure de l'arbre, c'est-à-dire donner une valeur proche à la longueur de chaque branche. Il s'agit donc de réduire le déséquilibre entre les différentes branches qui sont de longueurs différentes.
Déf. II. 5 Rotation simple
Une rotation simple concerne 2 nœuds imbriqués de l'arbre. Un arbre qui ne possède pas la structure adéquate (partie gauche de la règle) ne sera pas transformé.
Rotation simple de type
Déf. II. 6 Rotation double
Une rotation double concerne 3 nœuds imbriqués de l’arbre. Un arbre qui ne possède pas la structure adéquate (partie gauche de la règle) ne sera pas transformé.
Question II. 16 Exprimer les rotations doubles comme des combinaisons de rotations simples.
Question II. 17 Montrer que les rotations ne perturbent pas la structure d'arbre binaire de recherche.
Question II. 18 Pour chaque rotation possible, calculer les nouvelles valeurs des déséquilibres des 2 ou 3 nœuds concernés de l'arbre après la rotation en fonction des valeurs avant la rotation.
2.3.1 Rotation simple de type
Une première opération consiste à effectuer une rotation simple de type dans un arbre binaire de recherche pour équilibrer celui-ci.
Question II. 19 Écrire en PASCAL une fonction rotationSD (A : ARBRE ) : ARBRE ; telle que l'appel (rotationSD A) sur un arbre dont la structure permet l'application d'une rotation simple de type sur la racine renvoie l'arbre binaire de recherche sur lequel une rotation simple de type D a été appliquée à la racine.
2.3.2 Rotation simple de type G
Une deuxième opération consiste à effectuer une rotation simple de type dans un arbre binaire de recherche pour équilibrer celui-ci.
Nous supposons prédéfinie la fonction rotationSG(A:ARBRE):ARBRE; telle que l'appel (rotationSG A) sur un arbre A dont la structure permet l'application d'une rotation simple de type G à la racine renvoie l'arbre binaire de recherche A sur lequel une rotation simple de type G a été appliquée à la racine. Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
2.3.3 Rotation double de type D
Une troisième opération consiste à effectuer une rotation double de type dans un arbre binaire de recherche pour équilibrer celui-ci.
Question II. 20 Écrire en PASCAL une fonction rotationDD (A : ARBRE ) : ARBRE; telle que l'appel (rotationDD A) sur un arbre dont la structure permet l'application d'une rotation double de type à la racine renvoie l'arbre binaire de recherche sur lequel une rotation double de type a été appliquée à la racine.
2.3.4 Rotation double de type G
Une quatrième opération consiste à effectuer une rotation double de type G dans un arbre binaire de recherche pour équilibrer celui-ci.
Nous supposons prédéfinie la fonction rotationDG(A:ARBRE):ARBRE; telle que l'appel (rotationDG A) sur un arbre A dont la structure permet l'application d'une rotation double de type G à la racine renvoie l'arbre binaire de recherche A sur lequel une rotation double de type G a été appliquée à la racine. Son calcul se termine quelles que soient les valeurs de son paramètre. Elle pourra éventuellement être utilisée dans les réponses aux questions.
3 Arbres équilibrés
Pour réduire la complexité des opérations d'insertion et de recherche, il est nécessaire que les longueurs de toutes les branches de l'arbre aient des valeurs semblables. L'arbre a alors une structure dite équilibrée.
3.1 Définitions
Déf. II. 7 (Arbres binaires équilibrés) Un arbre binaire est dit équilibré si le déséquilibre de chacun de ses nœuds appartient à . Nous appellerons nœuds déséquilibrés les nœuds dont le déséquilibre n'appartient pas à .
Exemple II. 6 (Arbres binaires équilibrés) Le premier et le troisième arbres de l'exemple II. 3 sont équilibrés. Le deuxième arbre est déséquilibré. Il possède 2 nœuds déséquilibrés qui contiennent les étiquettes 6 et 9 .
3.2 Principe de l'équilibrage
Question II. 21 L'insertion d'une nouvelle étiquette dans un arbre binaire de recherche équilibré peut produire des nœuds déséquilibrés. Donner les différentes formes possibles pour le nœud déséquilibré le plus profond produit lors de l'insertion d'une nouvelle étiquette dans un arbre binaire équilibré en précisant la valeur du déséquilibre de ce nœud.
Question II. 22 Montrer qu'une rotation suffit à rééquilibrer le nœud déséquilibré le plus profond qui est apparu lors de l'insertion d'une nouvelle étiquette dans un arbre binaire équilibré. Donner la rotation qui doit être utilisée pour rééquilibrer ce nœud pour chacune des formes étudiées dans la question précédente.
3.3 Équilibrage d'un nœud
Une première opération consiste à équilibrer les nœuds qui viennent d'être déséquilibrés par l'opération d'insertion.
Question II. 23 Écrire en PASCAL une fonction equilibrage(A:ARBRE) :ARBRE; avec un arbre binaire de recherche dont la racine est déséquilibrée et dont tous les nœuds contenus dans les fils gauche et droit de la racine sont équilibrés renvoie un arbre binaire de recherche équilibré contenant les mêmes étiquettes que .
3.4 Insertion équilibrée
Une seconde opération consiste à insérer une nouvelle étiquette dans un arbre de recherche équilibré en préservant la structure équilibrée de l'arbre.
Question II. 24 Modifier la fonction inserer_abr (v:INTEGER;A:ARBRE) : ARBRE écrite en PASCAL à la question II. 14 telle que si A est un arbre binaire de recherche équilibré alors l'appel inserer_abr ( ) renverra un arbre binaire de recherche équilibré.
Question II. 25 Expliquer la fonction inserer_abr définie à la question précédente.
3.5 Complexité des opérations dans un arbre équilibré
La complexité calculée aux questions II. 15 et II. 12 pour les opérations d'insertion et de recherche dépend de la profondeur de l'arbre. Pour comparer celle-ci avec celle d'une réalisation à base de liste, il faut estimer la profondeur de l'arbre en fonction du nombre d'éléments contenus dans l'ensemble. Nous avons calculé celle-ci dans le meilleur des cas pour un arbre équilibré à la question II.6. Il faut maintenant évaluer celle-ci dans le pire des cas.
Question II. 26 Quelles sont les formes de l'arbre équilibré a dans le meilleur cas et le pire cas pour l'insertion et la recherche d'une étiquette dans ?
Question II. 27 Soit le nombre de nœuds dans un arbre dans le meilleur des cas, exprimer en fonction de .
Question II. 28 Soit le nombre de nœuds dans un arbre dans le pire des cas, exprimer sous la forme d'une relation de récurrence dépendant de et .
Question II. 29 Soit , résoudre l'équation linéaire à coefficients constants dérivée de la relation de récurrence précédente pour obtenir la valeur de en fonction de .
Question II. 30 Déduire des questions II. 27 et II. 29 un encadrement de la profondeur d'un arbre en fonction du nombre de nœuds qu'il contient. En déduire la complexité des opérations de recherche et d'insertion dans un arbre binaire de recherche équilibré.
Fin de l'énoncé
CCINP Option Informatique MP 2005 - Version Web LaTeX | WikiPrépa | WikiPrépa
