Scribd
Importer
5 vues2 pages

Programmation avancée en Oz : TP M2

Ce document contient les instructions pour trois exercices sur la programmation logique et par contraintes avancée en Oz. Les exercices portent sur l'écriture de fonctions pour trouver la valeur maximale d'une liste, construire un arbre binaire de recherche à partir d'une liste de paires clé-valeur, et supprimer une paire d'un tel arbre.

Transféré par

حمادوش عبد اللطيف
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
5 vues2 pages

Programmation avancée en Oz : TP M2

Ce document contient les instructions pour trois exercices sur la programmation logique et par contraintes avancée en Oz. Les exercices portent sur l'écriture de fonctions pour trouver la valeur maximale d'une liste, construire un arbre binaire de recherche à partir d'une liste de paires clé-valeur, et supprimer une paire d'un tel arbre.

Transféré par

حمادوش عبد اللطيف
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

M2 Master Informatique Fondamentale et Appliquée 2021/2022

Programmation logique et par contraintes avancée Feuille de TP n◦ 1

Premiers pas en Oz

Exercice 1
Écrire en Oz une procdure Maxlist à deux arguments telle que {Maxlist L R}, où L est une liste
d’entiers non-négatifs, lie R à la valeur maximale de L (0 si la liste L est vide).

Exercice 2
La fonction suivante pour la mise à jour d’une pair (clef, valeur) dans un arbre binaire recherche
a été montrée en cours :
% i n s e r t i o n o f a new p a i r ( key , v a l u e ) i n t o a b i n a r y s e a r c h t r e e
declare
fun { F u n I n s e r t Key Value TreeIn }
case TreeIn
of n i l then t r e e ( Key Value n i l n i l )
[ ] t r e e (K1 V1 T1 T2) then
i f Key == K1 then t r e e ( Key Value T1 T2)
e l s e i f Key < K1 then
t r e e (K1 V1 { F u n I n s e r t Key Value T1} T2)
else
t r e e (K1 V1 T1 { F u n I n s e r t Key Value T2} )
end
end
end
Vous trouverez ce fichier également sur le site web.

1. Écrire une fonction qui, quand son premier argument est une liste de paires (clef,valeur),
renvoye un arbre binaire de recherche qui contient toutes ces paires.

2. Écrire une fonction qui, quand son premier argument est un arbre binaire de recherche et
son deuxième argument une clef, renvoye la valeur stockée dans l’arbre pour cette clef.

3. Écrire une fonction qui, quand son premier argument est un arbre binaire de recherche et
son deuxième argument une clef, lie son troisième argument à l’arbre sans la paire avec la
clef donnée.

1
Exercice 3 (Optionnel)
Écrire la fonction de tri rapide d’une liste (quicksort) en Oz. La fonction prendra comme
argument la liste à trier, et renvoie la liste triée.
Programmez l’algorithme de quicksort en utilisant les listes :

• une liste de longueur 0 ou 1 est déjà triée

• pour trier une liste d’au moins deux éléments on utilise le premier élément de liste comme
pivot. La liste est partagée en deux sous-listes, une contenant les éléments strictement
plus petits que le pivot, et l’autre les éléments qui sont égaux ou plus grands que le pivot.
Puis on trie récursivement ces deux liste, et on recombine les résultats obtenus.

Indication : Il y a un constructeur de paires qui est notée #. Par exemple, 1#2 est la paire
des valeurs 1 et 2. Vous pouvez facilement décomposer une paire p par une construction comme
l o c a l L e f t#Right = p in . . . end

Vous aimerez peut-être aussi