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
Preambule : 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
Lors d'une séance d'un jeu informatique dérivé de la mythologie grecque, vous êtes accompagné par un couple de Sphinx. Ces créatures posent des énigmes logiques pour vous aider à progresser dans le jeu. Les énigmes suivent une règle que les Sphinx respectent scrupuleusement. Lorsque les Sphinx énoncent cette règle, ils disent toujours la vérité. Le premier Sphinx qui vous accompagne a énoncé la règle suivante :
«Dans les énigmes, je peux soit dire la vérité, soit mentir. Mais, pour une énigme donnée, la première et la dernière de mes affirmations seront de la même nature (soit vérité, soit mensonge); et toutes les autres affirmations seront de la nature opposée à ces deux là (mensonge, respectivement vérité, si les premières et dernières sont des vérités, respectivement des mensonges) ».
Le second Sphinx a énoncé la règle suivante : «Je suivrais la même règle que mon compagnon».
Question I. 1 Considérons que l'un des Sphinx fait une suite de déclarations dans une même énigme, proposer une formule du calcul des propositions qui représente la règle qu'il respecte.
Vous vous retrouvez face à trois escaliers, l'un à gauche, l'autre à droite et le dernier au milieu entre les deux autres.
Le premier Sphinx énonce les affirmations suivantes :
l'escalier de gauche est sûr,
l'escalier du milieu est sûr ou celui de droite n'est pas sûr.
Le second Sphinx énonce les affirmations suivantes :
ni l'escalier de gauche, ni celui du milieu ne sont sûrs,
si les escaliers de gauche ou de droite sont sûrs, alors l'escalier du milieu est sûr.
Nous noterons et les variables propositionnelles associées au fait que les escaliers de gauche, du milieu et de droite sont sûrs.
Nous noterons et , respectivement et , les formules propositionnelles associées aux déclarations du premier Sphinx, respectivement du second Sphinx.
Question I. 2 Représenter les déclarations des deux Sphinx sous la forme de formules du calcul des propositions et dépendant des variables et .
Question I. 3 Appliquer la règle respectée par les Sphinx que vous avez proposée pour la question I.1. Nous noterons , respectivement , la formule du calcul des propositions dépendant des variables et , respectivement et , qui correspond au respect de la règle par le premier Sphinx, respectivement le second Sphinx, dans cette énigme. Nous noterons la formule du calcul des propositions dépendant des variables et qui décrit le respect global des règles par les deux Sphinx dans cette énigme.
Question I. 4 En utilisant le calcul des propositions (résolution avec les tables de vérité), déterminer quel est (ou quels sont) le (ou les) escalier(s) qui est (ou sont) sûr(s) ? Vous indiquerez explicitement les résultats intermédiaires correspondant aux formules et .
Vous vous retrouvez plus tard face à trois portes de couleurs rouge, verte et bleu.
Seul le premier Sphinx s'exprime et énonce les affirmations suivantes :
la porte rouge n'est pas sûre ou la porte verte est sûre,
si les portes rouge et verte sont sûres alors la porte bleue n'est pas sûre,
la porte verte n'est pas sûre mais la porte bleue est sûre.
Nous noterons et les formules propositionnelles associées aux déclarations du premier Sphinx.
Nous noterons et les variables propositionnelles associées au fait que les portes rouge, verte et bleue sont sûres.
Question I.5 Représenter les déclarations du Sphinx sous la forme de formules du calcul des propositions et dépendant des variables et .
Question I. 6 Appliquer la règle respectée par le premier Sphinx que vous avez proposée pour la question I.1. Nous noterons , la formule du calcul des propositions dépendant des variables et qui correspond au respect de la règle par le premier Sphinx dans cette énigme.
Question I. 7 En utilisant le calcul des propositions (résolution avec les formules de De Morgan), déterminer quelle est (ou quelles sont) la (ou les) porte(s) qui est (ou sont) sûre(s).
Partie II : automates et langages
Le but de cet exercice est l'étude des propriétés des opérations de dérivation à gauche et à droite d'un automate fini selon un mot .
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 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é :
d'un ensemble fini d'états : ;
d'un état initial : ;
d'un ensemble d'états terminaux : ;
d'une fonction totale de transition confondue avec son graphe : .
Pour une transition donnée, nous appelons l'origine de la transition, 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 ;
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 :
1.3 Langage reconnu par un automate fini 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 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 de l'état initial à un état terminal.
Exemple II. 2 Le sous-automate de (exemple II.1) composé des états et transitions utiles est représenté par le graphe suivant :
Question II. 1 Donner, sans la justifier, une expression régulière ou ensembliste représentant le langage sur reconnu par l'automate de l'exemple II.1.
2 Opérations de dérivation
2.1 Définitions
Soient les opérations internes sur les automates finis complets déterministes définies par :
Déf. II. 2 (Dérivées selon un mot) Soient un automate fini complet déterministe et , les automates (dérivation à gauche selon ) et (dérivation à droite selon sont définis par :
Question II. 2 En considérant l'exemple II.1, construire les automates a. . et (seuls les états et les transitions utiles, c'est-à-dire accessibles depuis les états initiaux, devront être construits).
Question II. 3 Caractériser les langages reconnus par et , par une expression régulière ou ensembliste.
2.2 Propriétés
Question II. 4 Montrer que : si est un automate fini complet déterministe et si est un mot, alors et sont des automates finis complets déterministes.
Question II. 5 Montrer que :
Question II. 6 Soit un automate fini complet déterministe, montrer que :
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 Exercice : le tri rapide
L'objectif de cet exercice est d'étudier une implantation particulière d'un algorithme de tri d'une séquence d'entiers et d'en proposer une évolution pour améliorer ses performances dans le pire cas.
Déf. III. 1 Une séquence de taille de valeurs avec est notée . Sa taille est notée . Une même valeur peut figurer plusieurs fois dans , nous noterons le cardinal de dans , c'est-à-dire le nombre de fois que figure dans avec :
Le type entiers représente une séquence d'entiers. Le type triplet représente un triplet contenant une première séquence d'entiers située à gauche du triplet, puis un entier situé au milieu du triplet et enfin une seconde séquence d'entiers située à droite du triplet. Les définitions de ces types sont :
type entiers == int list;;
type triplet == entiers * int * entiers;;
Soit le programme en langage CaML :
let rec eclater e l =
match l with
| [] -> ([], e, [])
| t::q ->
let (g, v, d) = (eclater e q) in
if (t <= v) then
(t::g, v, d)
else
(g, v, t::d);;
let rec trier l =
match l with
| [] -> []
| t::q ->
let (g, v, d) = (eclater t q) in
((trier g)@(v::(trier d)));;
Soit la constante exemple définie et initialisée par :
let exemple = [ 3; 1; 4; 2];;
Question III. 1 Détailler les étapes du calcul de (trier exemple) en précisant pour chaque appel aux fonctions eclater et trier, la valeur du paramètre et du résultat.
Déf. III. 2 (Symbole de Kronecker) Soient deux valeurs et , le symbole de Kronecker est une fonction égale à la valeur 1 si et sont égales et à la valeur 0 sinon.
Question III. 2 Soient les entiers e et v , soient les séquences d'entiers de taille , de taille et de taille , telles que (eclater e p), montrer que:
(a)
(b)
(c)
(d)
(e)
(f)
Question III. 3 Soit la séquence de taille , soit la séquence telle que (trier ), montrer que:
(a)
(b)
(c)
Question III. 4 Montrer que le calcul des fonctions eclater et trier se termine quelles que soient les valeurs de leurs paramètres respectant le type des fonctions.
Question III. 5 Donner des exemples de valeurs du paramètre s de la fonction trier qui correspondent aux meilleur et pire cas en nombre d'appels récursifs effectués.
Montrer que la complexité dans les meilleur et pire cas de la fonction trier en fonction du nombre de valeurs dans les séquences données en paramètre sont respectivement de et . Cette estimation ne prend en compte que le nombre d'appels récursifs effectués.
La complexité dans le pire cas de la fonction trier peut être ramenée à celle du meilleur cas par une modification simple de la fonction eclater.
Question III. 6 Ecrire une nouvelle version de la fonction eclater telle que la complexité dans le pire cas de la fonction trier soit égale à sa complexité dans le meilleur cas.
Question III. 7 Prouver que cette nouvelle version de la fonction eclater satisfait les propriétés énoncées dans la question III.2.
2 Problème : représentation de dictionnaire avec des arbres Patricia
L'utilisation de dictionnaires joue un rôle prépondérant dans l'analyse automatique d'informations en langage naturel. Il est donc essentiel de pouvoir exploiter ceux-ci efficacement dans des programmes, c'est-à-dire de pouvoir tester rapidement si un mot fait partie d'un dictionnaire, tout en minimisant l'occupation en mémoire de la représentation informatique du dictionnaire.
L'objectif de ce problème est l'étude des arbres Patricia (Practical Algorithm To Retrieve Information Coded In Alphanumeric ce qui signifie algorithme pratique pour retrouver des informations codées par des caractères alphanumériques) introduit par D . Morisson et G . Gwehenberger pour réduire la taille des arbres lexicographiques qui permettent un test d'appartenance rapide.
2.1 Préliminaires : mots et séquence de mots
Un dictionnaire contient une séquence de mots composés de caractères.
Déf. III. 3 (Mot) Un mot est une séquence de taille de caractères avec . Il est noté . Sa taille est notée .
Un mot est représenté par le type mot dont la définition est :
type mot == char list;;
Nous supposons prédéfinie la fonction length : mot -> int telle que l'appel (length m ) sur un mot m renvoie la valeur entière . Son calcul se termine quelle que soit la valeur de son paramètre.
Exemple III. 1 L'expression suivante :
[ `f`; `a`; `c`; `e` ]
est alors associée au mot face.
Déf. III. 4 (Séquence de mots) Une séquence de taille de mots avec est notée . Sa taille est notée .
Une séquence de mots est représentée par le type mots dont la définition est :
type mots == mot list;;
Nous supposons prédéfinie la fonction length : mots -> int telle que l'appel (length s ) sur la séquence s renvoie la valeur entière . Son calcul se termine quelle que soit la valeur de son paramètre.
La structure des arbres Patricia impose de distinguer et classer les mots par leur premier caractère.
Question III. 8 Ecrire en CaML une fonction dist inguer de type mot -> mot -> bool telle que l'appel (distinguer m1 m2) sur deux mots m1 et m2 renvoie la valeur true si m1 et m2 ne sont pas vides et si le premier caractère de est strictement plus petit que le premier caractère de m2 et la valeur false sinon.
2.1.2 Ajout d'un préfixe dans une séquence de mots
L'extraction de l'ensemble des mots représentés par un arbre Patricia repose sur l'ajout d'un préfixe à l'ensemble des mots représentés par les sous-arbres de chaque noeud.
Question III. 9 Ecrire en CaML une fonction prefixer de type mot mots mots telle que l'appel (prefixer ) sur un mot et une séquence de mots renvoie une séquence de mots contenant les mêmes mots que s préfixés par le mot m. L'algorithme utilisé ne devra parcourir qu'une seule fois la séquence s. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question III. 10 Calculer une estimation de la complexité de la fonction prefixer en fonction du nombre d'éléments de la séquence de mots s. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.2 Arbres lexicographiques et Arbres Patricia
Les arbres lexicographiques sont des arbres -aires utilisés pour représenter des dictionnaires et, plus généralement, des ensembles de mots. Les liens entre deux noeuds consécutifs dans l'arbre, c'est-àdire entre un noeud père et un noeud fils, sont étiquetés par un caractère. La séquence des caractères qui étiquettent les liens le long d'un chemin de la racine de l'arbre jusqu'à un noeud forme donc un mot. Un noeud peut être terminal si le mot qui conduit de la racine à ce noeud est un mot du dictionnaire, ou non-terminal si ce mot n'est qu'un préfixe d'un mot du dictionnaire.
Exemple III. 3 (Arbre lexicographique) Voici un exemple d'arbre lexicographique représentant le dictionnaire contenant les mots : as, fa,fable, facile et la. Les noeuds terminaux, respectivement non terminaux, sont de couleur noire, respectivement blanche :
Dans les arbres Patricia, les liens entre noeuds sont étiquetés par des mots au lieu de caractères. Les chemins entre deux noeuds ne contenant aucun branchement sont alors remplacés par un lien unique étiqueté par le mot composé des caractères étiquetant le chemin complet dans l'arbre lexicographique contenant également ce mot.
Exemple III. 4 (Arbre Patricia) Voici un exemple d'arbre Patricia représentant le même dictionnaire que l'exemple III.3. Les noeuds terminaux, respectivement non terminaux, sont de couleur noire, respectivement blanche :
Déf. III. 5 (Arbre Patricia) Un arbre Patricia est composé de noeuds qui peuvent être terminaux ou non-terminaux. L'ensemble des noeuds de l'arbre Patricia est noté , l'ensemble des noeuds terminaux est noté . La racine de l'arbre Patricia est un noeud. Chaque noeud est composé d'une séquence éventuellement vide de fils notée avec et d'une séquence éventuellement vide de étiquettes associées notée qui sont des mots. Un arbre Patricia est valide si et seulement si :
un noeud qui ne possède pas de fils est terminal ;
le noeud situé à la racine de l'arbre est non terminal sauf s'il ne possède aucun fils;
les étiquettes de chaque noeud doivent être distinctes et ordonnées de manière croissante selon la relation définie dans la question III.8.
Question III. 11 Exprimer le fait qu'un arbre Patricia a est valide sous la forme d'une propriété . Nous noterons la relation définie dans la question III.8.
Un arbre Patricia est représenté par le type patricia et le type auxiliaire fils. Le type fils représente la séquence des fils et étiquettes associées d'un noeud, c'est-à-dire une liste de paires contenant un élément de type mot et un élément de type patricia. Les définitions en CaML de ces types sont :
type patricia Noeud of bool * fils
and fils == (mot * patricia) list; ;
Dans l'appel Noeud(fin, fils), les paramètres fin et fils sont respectivement un drapeau booléen qui indique si le noeud est terminal, ou non terminal et la liste des fils et étiquettes associées de ce noeud de l'arbre. Chaque élément de cette liste est une paire contenant d'une part le mot qui étiquette le lien entre le noeud et son fils, et d'autre part le fils.
Exemple III. 5 L'expression suivante :
let mot_as = [`a`; `s`] in
let mot_fa = [`f`; 'a'] in
let mot_ble = [`b`; `l`; `e`] in
let mot_c = [`c'] in
let mot_e = [`e`] in
let mot_ile = [`i`; `l`; `e`] in
let mot_la = [`l`; `a`] in
Noeud(false,
[
( mot_as, Noeud(true, []))
;
( mot_fa,
Noeud (true,
[
( mot_ble, Noeud(true, []))
;
( mot_c,
Noeud(false,
[
( mot_e, Noeud(true, []))
;
( mot_ile, Noeud(true, []))
]))
]))
;
( mot_la, Noeud(true, []))
])
est alors associée à l'arbre Patricia représenté graphiquement dans l'exemple III. 4 (page 10).
2.2.1 Création d'un arbre Patricia
Question III. 12 Ecrire en CaML une fonction creer de type mot -> patricia telle que l'appel (creer m) sur un mot renvoie un arbre Patricia valide contenant uniquement le mot .
2.2.2 Calcul du nombre de mots contenus dans un arbre Patricia
Question III. 13 Ecrire en CaML une fonction compter de type patricia -> int telle que l'appel (compter a) sur un arbre Patricia valide a renvoie le nombre de mots contenus dans 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.
2.2.3 Extraction des mots contenus dans un arbre Patricia
Question III. 14 Ecrire en CaML une fonction extrairede type patricia -> mots telle que l'appel (extraire a) sur un arbre Patricia valide a renvoie une séquence de mots contenant les mêmes mots 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.
2.2.4 Validation d'un arbre Patricia
Question III. 15 Ecrire en CaML une fonction valider de type patricia -> bool telle que l'appel (valider a) sur un arbre Patricia a renvoie la valeur true si l'arbre Patricia a est valide, c'est-à-dire si VAP(a) 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.
2.2.5 Test d'appartenance d'un mot à un arbre Patricia
Question III. 16 Ecrire en CaML une fonction accepterde type mot -> patricia -> bool telle que l'appel (accepter a) sur un mot et un arbre Patricia valide a renvoie la valeur true si l'arbre a contient le mot met 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.
2.2.6 Ajout d'un mot dans un arbre Patricia
Question III. 17 Détailler les étapes de l'ajout des mots facteur, lampe et lame dans l'arbre Patricia de l'exemple III. 4 en précisant toutes les étapes et les arbres intermédiaires.
Question III. 18 Ecrire en CaML une fonction ajouter de type mot -> patricia -> patricia telle que l'appel (ajouter a) sur un mot et un arbre Patricia valide a renvoie un arbre Patricia valide contenant le mot et les mêmes mots 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.
2.2.7 Fusion de deux arbres Patricia
Question III. 19 Ecrire en CaML une fonction fusionner de type patricia -> patricia -> patriciatelle que l'appel (fusionner a1 a2) sur deux arbres Patricia valides a1 et a2 renvoie un arbre Patricia valide contenant exactement les mots contenus dans les arbres a1 et a2. L'algorithme utilisé ne devra parcourir qu'une seule fois les arbres a1 et a2. 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 Exercice : le tri rapide
L'objectif de cet exercice est d'étudier une implantation particulière d'un algorithme de tri d'une séquence d'entiers et d'en proposer une évolution pour améliorer ses performances dans le pire cas.
Déf. III. 1 Une séquence de taille de valeurs avec est notée . Sa taille est notée . Une même valeur peut figurer plusieurs fois dans , nous noterons le cardinal de dans , c'est-à-dire le nombre de fois que figure dans avec :
Le type ENTIERS représente une séquence d'entiers. 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 d'entiers;
FUNCTION E_Inserer (e:INTEGER; : ENTIERS) : ENTIERS; renvoie une séquence d'entiers composée d'un premier entier e et du reste de la séquence contenu dans ;
FUNCTION E_Tete ( ENTIERS) : INTEGER; renvoie le premier entier de la séquence . Cette séquence ne doit pas être vide;
FUNCTION E_Queue (s:ENTIERS) : ENTIERS; renvoie le reste de la séquence privée de son premier entier. Cette séquence ne doit pas être vide;
FUNCTION E_Juxtaposer(s1,s2:ENTIERS):ENTIERS; renvoie une séquence composée des éléments de la séquence dans le même ordre que dans puis des éléments de la séquence dans le même ordre que dans .
Le type TRIPLET représente un triplet contenant une première séquence d'entiers située à gauche du triplet puis un entier situé au milieu du triplet et enfin une seconde séquence d'entiers située à droite du 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 T_Creer ( ENTIERS; INTEGER; ENTIERS) : TRIPLET; renvoie un triplet contenant la séquence d'entiers , puis la valeur entière et enfin la séquence d'entiers ;
FUNCTION T_Gauche(t:TRIPLET):ENTIERS; renvoie la séquence d'entiers située à gauche du triplet ;
FUNCTION T_Valeur (t:TRIPLET) :INTEGER; renvoie la valeur entière située au milieu du triplet ;
FUNCTION T_Droite(t:TRIPLET):ENTIERS; renvoie la séquence d'entiers située à droite du triplet .
Soit le programme en langage PASCAL :
FUNCTION eclater(e:INTEGER; s:ENTIERS):TRIPLET;
VAR t, v : INTEGER; g, d : ENTIERS;
BEGIN
IF (s = Vide) THEN
eclater := T_Creer( Vide, e, Vide)
ELSE BEGIN
t := E_Tete( s);
q := E_Queue( s);
r := eclater( e, q);
g := T_Gauche( r);
d := T_Droite( r);
v := Valeur( r);
IF (t <= v) THEN
eclater := T_Creer( E_Inserer( t, g), v, d)
ELSE
eclater := T_Creer( g, v, E_Inserer( t, d))
END
END;
FUNCTION trier(s:ENTIERS):ENTIERS;
VAR q, g, rg, d, rd : ENTIERS; t, v : INTEGER; r : TRIPLET;
BEGIN
IF (s = Vide) THEN
trier := Vide
ELSE BEGIN
t := E_Tete( s);
q := E_Queue( s);
r := eclater( t, q);
g := T_Gauche( r);
v := T_Valeur( r);
d := T_Droite( r);
rg := trier( g);
rd := trier( d);
trier := E_Juxtaposer( rg, E_Inserer( v, rd))
END
END;
Soit la constante exemple définie et initialisée par:
CONST exemple : ENTIERS
= E_Inserer ( 3, E_Inserer ( 1, E_Inserer ( 4, E_Inserer(2, Vide))));
Question III. 1 Détailler les étapes du calcul de trier (exemple) en précisant pour chaque appel aux fonctions eclater et trier, la valeur du paramètre et du résultat.
Déf. III. 2 (Symbole de Kronecker) Soient deux valeurs et , le symbole de Kronecker est une fonction égale à la valeur 1 si et sont égales et à la valeur 0 sinon.
Question III. 2 Soient les entiers e et v , la séquence d'entiers de taille , soient les séquences d'entiers de taille et de taille , soit le triplet , tel que Gauche et , monter que:
(a)
(b)
(c)
(d)
(e)
(f)
Question III. 3 Soit la séquence de taille , soit la séquence telle que trier , montrer que:
(a)
(b)
(c)
Question III. 4 Montrer que le calcul des fonctions eclater et trier se termine quelles que soient les valeurs de leurs paramètres respectant le type des fonctions.
Question III. 5 Donner des exemples de valeurs du paramètre s de la fonction trier qui correspondent aux meilleur et pire cas en nombre d'appels récursifs effectués.
Montrer que la complexité dans les meilleur et pire cas de la fonction trier en fonction du nombre de valeurs dans les séquences données en paramètre sont respectivement de et . Cette estimation ne prend en compte que le nombre d'appels récursifs effectués.
La complexité dans le pire cas de la fonction trier peut être ramenée à celle du meilleur cas par une modification simple de la fonction eclater.
Question III. 6 Ecrire une nouvelle version de la fonction eclater telle que la complexité dans le pire cas de la fonction trier soit égale à sa complexité dans le meilleur cas.
Question III. 7 Prouver que cette nouvelle version de la fonction eclater satisfait les propriétés énoncées dans la question III.2.
2 Problème : représentation de dictionnaire avec des arbres Patricia
L'utilisation de dictionnaires joue un rôle prépondérant dans l'analyse automatique d'informations en langage naturel. Il est donc essentiel de pouvoir exploiter ceux-ci efficacement dans des programmes, c'est-à-dire de pouvoir tester rapidement si un mot fait partie d'un dictionnaire, tout en minimisant l'occupation en mémoire de la représentation informatique du dictionnaire.
L'objectif de ce problème est l'étude des arbres Patricia (Practical Algorithm To Retrieve Information Coded In Alphanumeric ce qui signifie algorithme pratique pour retrouver des informations codées par des caractères alphanumériques) introduit par D . Morisson et G . Gwehenberger pour réduire la taille des arbres lexicographiques qui permettent un test d'appartenance rapide.
2.1 Préliminaires : mots et séquence de mots
Un dictionnaire contient une séquence de mots composés de caractères.
Déf. III. 3 (Mot) Un mot est une séquence de taille de caractères avec . Il est noté . Sa taille est notée .
Un mot est représenté par le type MOT. 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 mot vide ;
FUNCTION M_Inserer ( c : CHARACTER; m : MOT) : MOT; renvoie un mot composé d'un premier caractère suivi des caractères du mot dans le même ordre que dans ;
FUNCTION M_Tete (m:MOT) : CHARACTER; renvoie le premier caractère du mot m. Ce mot ne doit pas être vide;
FUNCTION M_Queue (m:MOT) : MOT; renvoie le suffixe du mot m privé de son premier caractère. Ce mot ne doit pas être vide;
FUNCTION M_Juxtaposer (m1,m2:MOT) : MOT; renvoie un mot composé des caractères du mot dans le même ordre que dans puis des caractères du mot dans le même ordre que dans m2 ;
FUNCTION M_Taille(m:MOT):INTEGER; renvoie la valeur entière .
Exemple III. 1 L'expression suivante :
M_Inserer ('f', M_Inserer ('a', M_Inserer( ' c', M_Inserer( 'e', Vide))))
est alors associée au mot face.
Déf. III. 4 (Séquence de mots) Une séquence de taille de mots avec est notée . Sa taille est notée .
Une séquence de mots est représentée par le type MOTS. 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 de mots vide ;
FUNCTION S_Inserer(m:MOT;s:MOTS):MOTS; renvoie une séquence composée d'un premier mot m suivi des mots de la séquence de mots s dans le même ordre que dans s ;
FUNCTION S_Tete (s:MOTS) : MOT; renvoie le premier mot de la séquence de mots s . Cette séquence ne doit pas être vide;
FUNCTION S_Queue(s:MOTS):MOTS; renvoie le reste de la séquence de mots privée de son premier mot. Cette séquence ne doit pas être vide;
FUNCTION S_Juxtaposer (s1,s2:MOTS) :MOTS; renvoie une séquence de mots composée des mots de la séquence de mots dans le même ordre que dans puis des mots de la séquence de mots dans le même ordre que dans ;
FUNCTION S_Taille(s:MOTS):INTEGER; renvoie la valeur entière | .
est alors associée à la séquence de mots , face, .
2.1.1 Distinction de deux mots
La structure des arbres Patricia impose de distinguer et classer les mots par leur premier caractère.
Question III. 8 Ecrire en PASCAL une fonction distinguer (m1,m2:MOT) : BOOLEAN; telle que l'appel distinguer ( ) sur deux mots et renvoie la valeur true si et ne sont pas vides et si le premier caractère de m1 est strictement plus petit que le premier caractère de m2 et la valeur false sinon.
2.1.2 Ajout d'un préfixe dans une séquence de mots
L'extraction de l'ensemble des mots représentés par un arbre Patricia repose sur l'ajout d'un préfixe à l'ensemble des mots représentés par les sous-arbres de chaque noeud.
Question III. 9 Ecrire en PASCAL une fonction prefixer(m:MOT;s:MOTS) :MOTS; telle que l'appel prefixer( ) sur un mot et une séquence de mots renvoie une séquence de mots contenant les mêmes mots que s préfixés par le mot . L'algorithme utilisé ne devra parcourir qu'une seule fois la séquence s. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Question III. 10 Calculer une estimation de la complexité de la fonction prefixer en fonction du nombre d'éléments de la séquence de mots s. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.
2.2 Arbres lexicographiques et Arbres Patricia
Les arbres lexicographiques sont des arbres -aires utilisés pour représenter des dictionnaires et, plus généralement, des ensembles de mots. Les liens entre deux noeuds consécutifs dans l'arbre, c'est-àdire entre un noeud père et un noeud fils, sont étiquetés par un caractère. La séquence des caractères qui étiquettent les liens le long d'un chemin de la racine de l'arbre jusqu'à un noeud forme donc un mot. Un noeud peut être terminal si le mot qui conduit de la racine à ce noeud est un mot du dictionnaire, ou non-terminal si ce mot n'est qu'un préfixe d'un mot du dictionnaire.
Exemple III. 3 (Arbre lexicographique) Voici un exemple d'arbre lexicographique représentant le dictionnaire contenant les mots : as, fa,fable, facile et la. Les noeuds terminaux, respectivement non terminaux, sont de couleur noire, respectivement blanche :
Dans les arbres Patricia, les liens entre noeuds sont étiquetés par des mots au lieu de caractères. Les chemins entre deux noeuds ne contenant aucun branchement sont alors remplacés par un lien unique étiqueté par le mot composé des caractères étiquetant le chemin complet dans l'arbre lexicographique contenant également ce mot.
Exemple III. 4 (Arbre Patricia) Voici un exemple d'arbre Patricia représentant le même dictionnaire que l'exemple III.3. Les noeuds terminaux, respectivement non terminaux, sont de couleur noire, respectivement blanche :
Déf. III. 5 (Arbre Patricia) Un arbre Patricia est composé de noeuds qui peuvent être terminaux ou non-terminaux. L'ensemble des noeuds de l'arbre Patricia est noté , l'ensemble des noeuds terminaux est noté . La racine de l'arbre Patricia est un noeud. Chaque noeud est composé d'une séquence éventuellement vide de fils notée avec et d'une séquence éventuellement vide de étiquettes associées notée qui sont des mots. Un arbre Patricia est valide si et seulement si :
un noeud qui ne possède pas de fils est terminal ;
le noeud situé à la racine de l'arbre est non terminal sauf s'il ne possède aucun fils;
les étiquettes de chaque noeud doivent être distinctes et ordonnées de manière croissante selon la relation définie dans la question III.8.
Question III. 11 Exprimer le fait qu'un arbre Patricia a est valide sous la forme d'une propriété . Nous noterons la relation définie dans la question III.8.
Un arbre Patricia est représenté par le type de base PATRICIA. La séquence des fils et étiquettes associées d'un noeud est représentée par le type de base FILS. Une paire composée d'un fils et de l'étiquette associée est représentée par le type de base PAIRE.
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 P_Creer(mot:MOT;fils:PATRICIA):PAIRE; renvoie une paire contenant l'étiquette mot et l'arbre Patricia fils;
FUNCTION P_Etiquette(p:PAIRE):MOT; renvoie l'étiquette contenue dans la paire ;
FUNCTION P_Arbre( p : PAIRE): PATRICIA; renvoie l'arbre contenu dans la paire p ;
FUNCTION F_Inserer(p:PAIRE;s:FILS):FILS; renvoie une séquence de fils composée d'un premier fils et du reste de la séquence contenu dans ;
FUNCTION F_Tete(s:FILS):PAIRE; renvoie le premier fils de la séquence . Cette séquence ne doit pas être vide ;
FUNCTION F_Queue(s:FILS):FILS; renvoie le reste de la séquence privée du premier fils. Cette séquence ne doit pas être vide;
FUNCTION F_Juxtaposer (s1,s2:FILS) :FILS; renvoie une séquence composée des éléments de la séquence dans le même ordre que dans puis des éléments de la séquence dans le même ordre que dans s2;
FUNCTION Noeud(fin:BOOLEAN;fils:FILS):PATRICIA; est une fonction qui renvoie un arbre Patricia dont le noeud situé à la racine est terminal si fin prend la valeur FALSE et non terminal sinon et dont les fils et leurs étiquettes associées sont contenus dans la séquence fils;
FUNCTION EstTerminal (a:PATRICIA) : BOOLEAN; est une fonction qui renvoie la valeur TRUE si le noeud situé à la racine de l'arbre a est terminal et la valeur FALSE sinon;
FUNCTION Fils(a:PATRICIA) :FILS; est une fonction qui renvoie la séquence des fils et étiquettes associées de la racine de l'arbre Patricia a.
Exemple III. 5 Le programme suivant :
VAR exemple : PATRICIA;
CONST
mot_as : MOT = M_Inserer( ' a', M_Inserer( 's', Vide));
mot_fa : MOT = M_Inserer('f', M_Inserer('a', Vide));
mot_ble : MOT =
M_Inserer( 'b', M_Inserer( 'l', M_Inserer( 'e', Vide)));
mot_c : MOT = M_Inserer( ' c', Vide);
mot_e : MOT = M_Inserer( 'e', Vide);
mot_ile : MOT =
M_Inserer( 'i', M_Inserer( 'l', M_Inserer( 'e', Vide)));
mot_la : MOT = M_Inserer( 'l', M_Inserer('a', Vide));
BEGIN
exemple := Noeud(false,
F_Inserer(
P_Creer( mot_as, Noeud(true, Vide))
F_Inserer(
P_Creer( mot_fa,
Noeud(true,
F_Inserer(
P_Creer( mot_ble, Noeud(true, Vide))
F_Inserer(
P_Creer( mot_c,
Noeud(false,
F_Inserer(
P_Creer( mot_e, Noeud(true, Vide)),
F_Inserer(
P_Creer( mot_ile, Noeud(true, Vide)),
Vide)))),
Vide)))),
F_Inserer(
R_Creer( mot_la, Noeud(true, Vide)),
Vide))))
END
affecte à la variable exemple l'arbre Patricia représenté graphiquement dans l'exemple III. 4 (page 18).
2.2.1 Création d'un arbre Patricia
Question III. 12 Ecrire en PASCAL une fonction creer ( ) : PATRICIA; telle que l'appel creer ( ) sur un mot renvoie un arbre Patricia valide contenant uniquement le mot .
2.2.2 Calcul du nombre de mots contenus dans un arbre Patricia
Question III. 13 Ecrire en PASCAL une fonction compter (a:PATRICIA) : INTEGER; telle que l'appel compter (a) sur un arbre Patricia valide a renvoie le nombre de mots contenus dans 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.
2.2.3 Extraction des mots contenus dans un arbre Patricia
Question III. 14 Ecrire en PASCAL une fonction extraire(a:PATRICIA) : MOTS; telle que l'appel extraire(a) sur un arbre Patricia valide a renvoie une séquence de mots contenant les mêmes mots 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.
2.2.4 Validation d'un arbre Patricia
Question III. 15 Ecrire en PASCAL une fonction valider (a:PATRICIA) : BOOLEAN; telle que l'appel valider (a) sur un arbre Patricia a renvoie la valeur TRUE si l'arbre Patricia a est valide, c'est-à-dire si V AP (a) 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.
2.2.5 Test d'appartenance d'un mot à un arbre Patricia
Question III. 16 Ecrire en PASCAL une fonction accepter (m:MOT; a :PATRICIA) : BOOLEAN; telle que l'appel accepter ( ) sur un mot et un arbre Patricia valide a renvoie la valeur TRUE si l'arbre a contient le mot 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.
2.2.6 Ajout d'un mot dans un arbre Patricia
Question III. 17 Détailler les étapes de l'ajout des mots facteur, lampe et lame dans l'arbre Patricia de l'exemple III. 4 en précisant toutes les étapes et les arbres intermédiaires.
Question III. 18 Ecrire en PASCAL une fonction a jouter (m:MOT; a : PATRICIA) : PATRICIA; telle que l'appel a jouter ( ) sur un mot et un arbre Patricia valide a renvoie un arbre Patricia valide contenant le mot met les mêmes mots 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.
2.2.7 Fusion de deux arbres Patricia
Question III. 19 Ecrire en PASCAL une fonction fusionner (a1,a2: PATRICIA) : PATRICIA; telle que l'appel fusionner (a1,a2) sur deux arbres Patricia valides a1 et a2 renvoie un arbre Patricia valide contenant exactement les mots contenus dans les arbres a1 et a2. L'algorithme utilisé ne devra parcourir qu'une seule fois les arbres a1 et a2. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Fin de l'énoncé
CCINP Option Informatique MP 2013 - Version Web LaTeX | WikiPrépa | WikiPrépa
