Informatique 2 - Page principale - Environnement de développement - Syntaxe de Oz |
L'objectif de cette séance est de manipuler les concepts de complexité temporelle et spatiale, et de les appliquer à des algorithmes particuliers. Les exemples comprennent des fonctions récursives sur des entiers, des listes et des tuples.
A propos des tuples.
Rappelons qu'un tuple de taille n est une valeur de la
forme L(X1 X2 ... Xn)
, où L
est
une étiquette (un atome). Un tuple de taille n occupe
Θ(n) mots mémoire.
Les opérations suivantes sont définies sur les tuples.
Opération | Description | Complexité temporelle |
---|---|---|
atome(X1 ... Xn) |
crée un tuple de taille n | Θ(n) |
{Label T} |
renvoie l'étiquette du tuple T |
Θ(1) |
{Width T} |
renvoie la taille du tuple T |
Θ(1) |
T.N |
renvoie le N -ième élément du tuple T |
Θ(1) |
Code source. L'ensemble du code présenté dans cette séance se trouve dans le fichier seance4.oz.
Vrai ou faux ? Ci-dessous se trouvent des affirmations concernant les classes de fonctions Ω( ), O( ) et Θ( ). Pour chacune, déterminez si elle est vraie ou fausse, et justifiez votre réponse.
Soit un algorithme A avec une complexité temporelle en Θ(1), et P un programme implémentant l'algorithme A. Le temps d'exécution de P sur une machine donnée sera toujours identique, pour plusieurs exécutions de P.
Listes et tuples.
Rappelons que la liste élémentaire X|T
n'est rien
d'autre que le tuple '|'(X T)
.
La fonction Nth
renvoie le N
-ième élément de
la liste L
. Elle a la même fonctionnalité que l'opération
".
" sur les tuples.
fun {Nth L N} if N==1 then L.1 else {Nth L.2 N-1} end endDonnez la complexité temporelle de la fonction
Nth
. En
fonction de quoi l'exprimez-vous ?
Comparez cette complexité avec celle de l'opération ".
" sur
les tuples. Que constatez-vous ?
Décalages de listes.
Dans le calcul des triangles de Pascal vu au cours, la fonction
Pascal
utilise les fonctions auxiliaires
ShiftLeft
et ShiftRight
.
{ShiftLeft L}
insère un zéro au bout de la liste
L
, tandis que {ShiftRight L}
insère un zéro en
tête de la liste L
.
fun {ShiftLeft L} case L of H|T then H|{ShiftLeft T} else [0] end end fun {ShiftRight L} 0|L endQuelles sont les complexités temporelle des fonctions
ShiftLeft
et ShiftRight
?
En fonction de quoi exprimez-vous ces complexités ?
En d'autres mots, quelle est la taille du problème ?
Soyez aussi précis que possible.
Boucles.
Considérez la procédure Turlututu
ci-dessous, qui prend en
argument un tuple T
.
proc {Turlututu T} N={Width T} proc {Loop1 I} proc {Loop2 J} if J=<N then {Browse T.I} {Loop2 J+1} end end in if I=<N then {Loop2 I} {Loop1 I+1} end end in {Loop1 1} end
Décrivez en quelques mots ce que fait la procédure Turlututu
.
Chaque élément du tuple T
est-il visité ?
Certains éléments sont-ils visités plusieurs fois ?
Si l'on appelle Turlututu
avec le tuple t(42 17
23)
, que va-t-elle afficher ?
Loop1
fait appel à la
fonction récursive Loop2
. On parle ici de boucles
imbriquées.
Quelle est la complexité temporelle de la procédure
Turlututu
?
Quelle est la taille du problème ?
Pouvez-vous exprimer la complexité en Θ( ) ?
Création d'une liste. Imaginez que le professeur vous parle d'un algorithme. Vous n'avez pas compris son explication, mais vous avez noté que l'algorithme doit au moins construire une liste de n éléments. Que pouvez-vous dire des complexités temporelle et spatiale de l'algorithme ?
Tri par insertion.
Supposons que l'on veuille trier une liste de n entiers. On peut
utiliser pour cela la méthode du tri par insertion, où l'on
insère un à un les éléments dans une liste déjà triée. La fonction
InsertionSort
ci-dessous implémente cette méthode de tri.
%% insere X dans la liste triee Ys fun {Insert X Ys} case Ys of nil then [X] [] Y|Yr then if X=<Y then X|Ys else Y|{Insert X Yr} end end end %% insere les elements de Xs dans la liste triee Ys fun {InsertList Xs Ys} case Xs of nil then Ys [] X|Xr then {InsertList Xr {Insert X Ys}} end end %% renvoie la liste Xs triee fun {InsertionSort Xs} {InsertList Xs nil} endOn voit que la fonction
InsertList
utilise la liste
temporaire triée Ys
comme un accumulateur.
Quelle est la complexité temporelle de la fonction Insert
?
Existe-t-il des meilleurs cas et des pires cas pour la complexité de
Insert
?
Dans l'affirmative, pouvez-vous donner la complexité en
Θ( ) du meilleur cas ? Et celle du pire cas ?
S'il n'y a pas de meilleur ou pire cas, expliquez pourquoi.
Mêmes questions pour la fonction InsertList
. Soyez
précis quant à la taille du problème. S'il y a des meilleurs et des
pires cas, donnez un exemple de chaque sorte.
Quelles sont les complexités temporelle et spatiale de la fonction
InsertionSort
?
Recherche dichotomique.
Supposez qu'un tuple T
contienne n entiers en ordre
croissant, et que l'on veuille savoir si la valeur X
est
contenue dans T
. L'algorithme naïf, qui consiste à tester
les valeurs du tuple une à une, est implémenté par la fonction suivante.
fun {IsInTuple T X} N={Width T} fun {Loop I} if I>N then false else if T.I==X then true else {Loop I+1} end end end in {Loop 1} end
Cet algorithme a-t-il des meilleurs et des pires cas ? Si oui, donnez un exemple pour chacun, et leur complexité en Θ( ).
Quelle est la complexité moyenne de l'algorithme, si on
suppose que X
et les valeurs du tuple on une distribution
de probabilités uniforme sur un intervalle donné ?
Voici un autre algorithme pour résoudre le problème, appelé
recherche dichotomique. Dans cet algorithme, on considère une
"section" du tuple comprise entre deux indices i et j.
On suppose que si X
est dans le tuple, son indice est
compris entre i et j.
Si i=j, alors X
est dans le tuple si et seulement si
X
est le i-ème élément de T
.
Si i < j, on découpe l'intervalle d'entiers
en deux parties égales (à une unité près) : [i,j] =
[i,k] ∪ [k+1,j].
Ensuite, on compare X
au k-ième élément de
T
. S'il est inférieur ou égal, alors X
doit
se trouver dans le premier intervalle. Sinon, il ne peut se trouver que
dans le second.
Voici une implémentation de cet algorithme.
fun {IsInOrderedTuple T X} %% renvoie true si X est egal a T.K, pour un K tel que I=<K=<J fun {FindBetween I J} if I==J then X==T.I else local K in K=(I+J) div 2 % I=<K<J if X=<T.K then {FindBetween I K} else {FindBetween K+1 J} end end end end in {FindBetween 1 {Width T}} end
Quelle est la complexité de l'algorithme de recherche dichotomique ? Y a-t-il des meilleurs cas ? Si oui, lesquels ?
Mesures expérimentales.
Dans cet exercice, vous allez mesurer les temps d'exécution de
programmes. La fonction MeasureTime
ci-dessous prend en
argument une procédure, l'exécute et renvoie son temps d'exécution en
millisecondes.
fun {MeasureTime P} T0 T1 in T0={Property.get time} {P} T1={Property.get time} (T1.user+T1.system)-(T0.user+T0.system) endL'exemple suivant montre comment utiliser
MeasureTime
pour
mesurer le temps d'exécution de la fonction InsertionSort
.
L'appel de fonction {List.number I J K}
renvoie la
liste des entiers de I
à J
par pas de
K
.
{Browse {MeasureTime proc {$} {Browse {InsertionSort {List.number 1 1000 1}}} end}}
Dans l'exemple, la construction de la liste est-elle également mesurée
par MeasureTime
? Si c'est le cas, modifiez
l'exemple pour que seul le temps d'exécution de
InsertionSort
soit mesuré.
Testez maintenant des listes de tailles différentes. Vérifier
expérimentalement la complexité que vous avez proposé pour la fonction
InsertionSort
. Déterminer également la taille maximale
de la liste pour obtenir le résultat en moins d'une seconde.
Utilisez la fonction MeasureTime
pour comparer les
fonctions IsInTuple
et IsInOrderedTuple
de
l'exercice 7. La fonction Tuple.make
permet de
construire un tuple de variables non initialisées d'une taille donnée.
{Browse {Tuple.make foo 7}} %% affiche foo(_ _ _ _ _ _ _)Utilisez-la pour construire des données de test. N'oubliez pas d'initialiser les éléments du tuple! N'hésitez pas à définir quelques fonctions auxiliaires si vous le jugez utile.
Recherche dichotomique avec des listes.
Prenons l'algorithme de recherche dichotomique ci-dessus et remplaçons
le tuple par une liste. Le code de la fonction
IsInOrderedTuple
doit être adapté. Pour cela, on remplace
T.K
par {Nth T K}
, et {Width
T}
par {Length T}
.
Faites la queue.
La fonctions Tails
définie ci-dessous renvoie la liste des
queues non vides d'une liste L
. Par exemple, {Tails
[a b c]}
renvoie la liste de listes [[a b c] [b c]
[c]]
.
fun {Tails L} case L of nil then nil [] X|T then L|{Tails T} end end
Quelle est la complexité temporelle de l'algorithme implémenté par la
fonction Tails
? Tâchez d'obtenir les bornes les
plus strictes que possible.
Quelle est la complexité spatiale de l'algorithme ? Raisonnez en
représentant graphiquement les données sur un exemple.
Indication. En Oz, lorsqu'on accède à la queue d'une liste,
cette queue n'est pas recopiée en mémoire.