Licence Info
Algorithmique Avancée
TD 1: 2-3/2/04

  1. L'algorithme minmax utilise 3n/2-2 comparaisons pour trouver le minimum et maximum de n nombres (n pair).

    1. Combien sont utilisées quand n est impair?
    2. Pour l'algorithme plus naif qui compare chaque nombre après le deuxième avec le maximum des précédents et (s'il était inférieur au maximum) avec le minimum, le nombre de comparaisons dépend de l'ordre des données; Quels sont les nombres minimum et maximum de comparaisons?
    3. On veut démontrer que tout algorithme basé sur les comparaisons doit utiliser au moins le même nombre que minmax. On va utiliser une méthode de l'adversaire : chaque fois que l'algorithme effectue une comparaison, l'adversaire donne une réponse qui est cohérente avec les réponses précédentes mais choisie afin d'obliger l'algorithme à prendre le maximum de temps; ici l'adversaire devrait essayer de garder le plus grand nombre possible d'éléments du tableau qui pourraient être le minimum et/ou le maximum.
      Donner une stratégie pour l'adversaire qui oblige tout algorithme à effectuer au moins le nombre de comparaisons de minmax.
      Conclure que tout algorithme nécessite ce nombre, au moins dans le pire cas.
    4. Pour étudier le comportement d'un algorithme en moyenne, on peut supposer que tous les n! ordres possibles des n données ont la même probabilité; avec cette supposition, est-il vrai que tout algorithme doit faire autant de comparaisons que minmax en moyenne?
  2. On considère la taille maximum de la pile utilisée par le tri rapide.

    1. Démontrer que pour tout ordre des n données, cette taille est forcement au moins log2n
    2. Avec la même supposition sur les probabilités de données que dans l'exercice précédent, et en utilisant le fait que la taille est au moins 1+ la taille de la pile utilisée par l'appel sur la plus grande des deux parties, démontrer un minorant de l'espérance de la forme k log2 n (k > 1).



File translated from TEX by TTH, version 3.05.
On 26 Jan 2004, 15:27.