Séance 4
Complexité calculatoire

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.

Enoncés des exercices

  1. 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.

  2. 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
   end
    Donnez 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 ?

  3. 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 end
    Quelles 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.

  4. 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
    En y regardant bien, vous verrez que Loop1 fait appel à la fonction récursive Loop2. On parle ici de boucles imbriquées.

  5. 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 ?

  6. 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}
   end
    On voit que la fonction InsertList utilise la liste temporaire triée Ys comme un accumulateur.

  7. 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

    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
    Note. Vous pouvez supposer que la taille du tuple est une puissance de 2.

Exercices supplémentaires

  1. 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)
   end
    L'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}}

  2. 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}.

  3. 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

Raphaël Collet et Pierre Dupont - 13 octobre 2005