Skip to content

Séquence 3

L'objectif de la séquence est de travailler sur la recherche d'un élément et de travailler sur le problème du tri. On poura lire les chapitres 2 et 3 de l'ouvrage

Algorithmique par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein Dunod 3ième édition 2010 lien des versions plus anciennes sont accessibles partiellement sur internet.

Question 1

On considère une recherche dichotomique dans un tableau trié de taille \(n=2^k-1\) et on compte le nombre de comparaisons d'éléments pour la recherche d'un élément présent ou non dans le tableau.

  1. Le coût le coût au mieux de l'algorithme est \(1\), \(k\), \(\frac n2\), \(n\)
  2. Le coût le coût au pire de l'algorithme est \(1\), \(k\), \(\frac n2\), \(n\)
  3. Le nombre d'éléments pour lesquels le coût au pire est atteint est \(1\), \(k\), \(\frac {n+1}2\), \(n\)
  4. On suppose qu'un même élément est répété \(4\) fois dans le tableau, le nombre de comparaisons nécessaires sera au plus \(1\), \(k-2\), \(k-1\), \(k\), \(\frac {n+1}2\)

réponses (éléments)

  1. \(1\) si le premier élément cherché est au centre du tableau
  2. \(k\) par exemple pour l'élément en première position. D'autre part, cf l'arbre associé) tous les éléments d'indice pair (numérotation à partir de \(0\)) sont à une profondeur de \(k-1\), les éléments d'indice impair sont dans les niveaux supérieurs dans l'arbre.
  3. \(\frac {n+1}2\) ce sont les éléments d'indice pair
  4. \(k-2\) en effet les éléments sont consécutifs dans le tableau trié et donc on a 2 feuilles, au pire un père et un grand-père

Question 2

Dans l'algorithme de tri par sélection

  1. Le nombre de comparaisons effectuées est \(\frac n2\), \(n-1\), \(n\), \(\frac {n(n-1)}2\), \(n(n-1)\)
  2. Le nombre d'échanges effectués est \(\frac n2\), \(n-1\), \(n\), \(\frac {n(n-1)}2\), \(n(n-1)\)
  3. Le nombre de lectures dans le tableau est \(\frac n2\), \(n-1\), \(n\), \(\frac {n(n-1)}2\), \(n(n-1)\)

Question 3

Dans le tri par insertion d'un tableau de taille \(n\) , on détermine la position de l'élément à insérer en faisant une recherche dichotomique. Le nombre total de comparaisons est donc modifié. On suppose tous les éléments du tableau différents.

  1. Le nombre de comparaisons pour réaliser le tri sera au mieux de \(O(1)\), \(O(n)\), \(O(n\log(n))\), \(O(n^2)\)
  2. Le nombre d'affectations pour réaliser le tri sera au mieux de \(O(1)\), \(O(n)\), \(O(n\log(n))\), \(O(n^2)\)

réponses (éléments)

  1. \(O(n\log(n))\) On note \(T(n)\) le coût au pire en nombre de comparaisons, on a \(T(n) = T(n-1) +\log(n-1)\) d'où \(T(n) = \log(n-1)+\log(n-2)+\cdots \log(2)+\log(1)= O(n\log(n))\)
  2. \(O(n^2)\) le nombre de décalages est i,changé donc le nombre d'affectations au pire sera \((n-1)+(n-2) + \cdots +2 +1 = \frac{n(n-1)}2 = O(n^2)\), à l'implémentation le code offrirait des performances similaires à l'algorithme sans la recherche dichotomique.

Question 4

On considère l'algorithme suivant

tri_mystere(T)
  i = taille(T) -1
  tableau_trié = Faux
  tant que non tableau_trié et i >0
    tableau_trié = vrai
    pour j allant de 0 à i-1
        si T[j+1] < T[j]
          Echange (T,j,j+1)
          tableau_trié = Faux
    i = i-1

exemple = ['o', 'i', 's', 'e', 'a', 'u']
On pourra s'aider d'un programme python implémentant l'algorithme, \(n\) est la taille du tableau T

  1. On exécute l'algorithme tri_mystère sur exemple après 2 itérations du tant que le tableau T a pour valeur ['i','o','s','e','a','u'], ['e','a','o','i','s','u'],['o', 'i', 's', 'e', 'a', 'u'],['i', 'o', 'e', 's', 'a', 'u'],['i', 'e', 'a', 'o', 's', 'u']
  2. On exécute l'algorithme tri_mystère sur exemple, l'algorithme se termine après un nombre d'exécution du bloc tant que égal à 1,2,3,4 ou 5
  3. L'algorithme effectue au mieux un nombre d'échanges égal à \(0\), \(\log(n)\), \(\frac n2\), \(n\), \(\frac {n(n-1)}2\)
  4. L'algorithme effectue au pire un nombre d'échanges égal à \(0\), \(\log(n)\), \(\frac n2\), \(n\), \(\frac {n(n-1)}2\)
  5. À faire : la preuve que tri_mystère(T) trie le tableau T

réponses (éléments)

  1. ['i', 'e', 'a', 'o', 's', 'u']
  2. l'algorithme se termine en 3 étapes
  3. \(0\) si le tableau est trié par ordre croissant et on a \(n-1\) comparaisons
  4. Au pire le nombre d'échanges est \(\frac {n(n-1)}2\), en effet le nombre d'échanges est majoré par \(\frac {n(n-1)}2\) (cas où toutes les conditions du ifsont vraies) et il existe un exemple qui atteint \(\frac {n(n-1)}2\) (cas du tableau trié par ordre décroissant.