Informatique 2 - Page principale - Environnement de développement - Syntaxe de Oz |
Cette séance est consacrée aux enregistrements et aux structures de données qu'ils permettent de construire, notamment les arbres. Rappelons qu'un enregistrement est composé d'une étiquette (atome) et d'un certain nombre de champs. Chaque champ est identifié par un nom (atome ou nombre).
Opération | Description | Complexité temporelle |
---|---|---|
etiquette(nom1:X1 ... nomn:Xn) |
crée un enregistrement | Θ(n) |
R.N |
renvoie le champ N de l'enregistrement R |
Θ(1) |
{Label R} |
renvoie l'étiquette de l'enregistrement R |
Θ(1) |
{Width T} |
renvoie le nombre de champs de l'enregistrement R |
Θ(1) |
{Arity R} |
renvoie la liste des noms de champs de l'enregistrement R |
Θ(1) |
Enregistrements. Considérez l'enregistrement suivant. Il représente la carte des menus d'un restaurant.
Carte = carte(menu(entree: 'salade verte aux lardons' plat: 'steak frites' prix: 10) menu(entree: 'salade de crevettes grises' plat: 'saumon fume et pommes de terre' prix: 12) menu(plat: 'choucroute garnie' prix: 9))En utilisant la variable
Carte
, répondez aux questions
suivantes.
Carte
correspond-il ?N1
personnes commandent le premier menu,
N2
personnes le second et N3
personnes le
troisième. Quel prix vont-ils payer au total ?Listes, tuples, enregistrements. Voici un ensemble d'enregistrements. Pour chacune, indiquez s'il s'agit d'une liste, d'un tuple ou d'un enregistrement. Etant donné qu'une liste est un cas particulier de tuple, et qu'un tuple est un cas particulier d'enregistrement, donnez le type le plus précis.
'|'(a b)
'|'(a '|'(b nil))
'|'(2:nil a)
state(1 a 2)
state(1 3:2 2:a)
tree(v:a T1 T2)
Vous pouvez vérifier vos réponses avec les fonctions IsList
et IsTuple
. {IsList X}
renvoie
true
si X
est une liste,
false
sinon. IsTuple
fonctionne de
manière similaire avec les tuples.
Promenade arboricole.
Considérez la grammaire suivante. Elle définit un type pour des arbres
binaires dont les noeuds contiennent une valeur de type
T
. Un arbre binaire est soit un arbre vide, soit un
noeud contenant une valeur et deux sous-arbres.
<btree T> ::= empty | btree(T left:<btree T> right:<btree T>)
Définissez une fonction Promenade
qui réalise un parcours
en profondeur d'abord d'un arbre. Dans ce type de parcours,
le sous-arbre gauche d'un noeud est parcouru entièrement avant son
sous-arbre droit. L'appel {Promenade BT}
renvoie la
liste des valeurs des noeuds visités dans l'arbre BT
. Le
noeud racine d'un arbre est toujours visitée avant ses sous-arbres.
%% affiche [42 26 54 18 37 11] {Browse {Promenade btree(42 left: btree(26 left: btree(54 left: empty right: btree(18 left: empty right: empty)) right: empty) right: btree(37 left: btree(11 left: empty right: empty) right: empty))}}
Utilisez cette fonction pour calculer la somme des valeurs d'un arbre binaire contenant des entiers.
Définissez une fonction qui calcule la somme des valeurs d'un arbre en effectuant elle-même un parcours de l'arbre.
Trier une liste avec des arbres. Dans cet exercice, vous allez implémenter une méthode de tri qui utilise des arbres ordonnés. Nous avons vu au cours une implémentation d'arbres ordonnés : orderedtree.oz. Pour trier une liste, on construit un arbre ordonné qui contient toutes les valeurs de la liste, puis les valeurs sont lues dans l'arbre dans l'ordre croissant. On fait l'hypothèse que les éléments de la liste sont distincts.
Pour construire l'arbre ordonné, définissez une fonction
InsertElements
qui prend en argument une liste de valeurs
et un arbre ordonné, et renvoie l'arbre dans lequel on a inséré les
éléments de la liste. Chaque élément de la liste est à la fois clé et
valeur dans l'arbre. L'appel
{InsertElements [42 17 23] tree(key:31 value:31 leaf leaf)}renvoie l'arbre
tree(key:31 value:31 tree(key:17 value:17 leaf tree(key:23 value:23 leaf leaf)) tree(key:42 value:42 leaf leaf))
Ecrivez une fonction Keys
qui prend un arbre ordonné et
renvoie la liste de ses clés en ordre croissant. Si T
est l'arbre renvoyé ci-dessus, alors {Keys T}
renvoie la
liste [17 23 31 42]
.
Définissez maintenant la fonction OrderedTreeSort
, qui
prend une liste en argument et renvoie la liste triée. Cette fonction
utilise bien sûr les deux précédentes.
Construction d'un arbre équilibré.
Considérez des arbres binaires <btree>
définis
par la grammaire ci-dessous. Dans ces arbres, seules les feuilles
contiennent une information.
<btree> ::= leaf(<value>) | tree(<btree> <btree>)
Ecrivez une fonction Infix
qui effectue un parcours
infixe d'un tel arbre. Cette fonction prend un
<btree>
en argument et renvoie une liste
contenant les valeurs des feuilles de l'arbre, lues de gauche à
droite. Par exemple, l'appel de fonction
{Infix tree(leaf(1) tree(tree(tree(leaf(2) tree(leaf(3) leaf(4))) leaf(5)) leaf(6)))}renvoie la valeur
[1 2 3 4 5 6]
.
Ecrivez une fonction IsBalanced
qui prend un
<btree>
en argument et renvoie
true
s'il est équilibré,
false
sinon. Un arbre tree(L R)
est équilibré si ses sous-arbres L
et
R
sont équilibrés, et s'ils ont le même nombre de
feuilles, à une unité près. Un arbre constitué d'une seule feuille
est équilibré.
Aide: Ecrivez d'abord une fonction qui renvoie le nombre de
feuilles d'un <btree>
.
Ecrivez une fonction MakeTree
qui construit un
<btree>
équilibré à partir d'une
liste de valeurs donnée en argument. La liste donnée en argument doit
correspondre à l'appel de Infix
sur l'arbre résultat.
Testez votre fonction avec Infix
et
IsBalanced
pour vérifier que le résultat a bien les
propriétés voulues.
Par exemple, l'appel {MakeTree [1 2 3 4 5 6]}
peut
renvoyer l'arbre
tree(tree(leaf(1) tree(leaf(2) leaf(3))) tree(leaf(4) tree(leaf(5) leaf(6))))
Note 1. Ce n'est pas le seul arbre équilibré possible pour cet exemple. Vous devez définir précisément le choix que vous faites pour construire un arbre équilibré.
Note 2. Vous pouvez utiliser le module Drawer pour visualiser l'arbre construit.
Nous allons maintenant enrichir la structure de données. Dans les
arbres binaires <btreecount>
définis
ci-dessous, chaque sous-arbre contient en plus un entier. Si
T
est un <btreecount>
, alors
T.count
donne le nombre de feuilles dans cet arbre.
<btreecount> ::= leaf(<value> count:1) | tree(<btreecount> <btreecount> count:<int>)
Ecrivez une fonction AddCount
qui convertit un
<btree>
en le
<btreecount>
correspondant.
Ecrivez une fonction MakeTreeCount
, similaire à votre
fonction MakeTree
, mais qui renvoie un
<btreecount>
.
Ecrivez une fonction NthLeaf
qui prend en argument un
<btreecount>
BTC
, ainsi qu'un
entier N
et renvoie la valeur se trouvant dans la
N
-ième feuille de BTC
.
L'appel {NthLeaf {MakeTreeCount L} N}
renvoie la même
valeur que {Nth L N}
. Quel est l'avantage de
NthLeaf
par rapport à Nth
?
En particulier, quel est la complexité temporelle d'un appel à
NthLeaf
?
Le module Drawer permet de visualiser une valeur Oz comme un arbre. Pour l'utiliser,
%% charger le module (une fois) declare [Drawer] = {Module.link ["http://www.info.ucl.ac.be/notes_de_cours/FSAB1402/tools/Drawer.ozf"]} Draw = Drawer.draw %% afficher une valeur {Draw Valeur}