CPGE OUJDA SPE

Complexité recherche dichotomique et tour de Hanoi

Recherche par dichotomie dans un tableau trié :

Principe :

on compare l’élément cherché X avec l’élément du milieu de tab . s’il y’a égalité la recherche est terminée , sinon on poursuit le processus en ne considérant que la moitié inférieure ou la moitié supérieure de tab , selon le résultat de la comparaison.

Problème de Hanoï :

Le jeu est constitué d’une plaquette de bois où sont plantées trois tiges numérotées 1,2 et 3. Sur ces tiges sont empilés des disques de diamètres tous différents. Les seules règles du jeu sont que l’on ne peut déplacer qu’un seul disque à la fois, et qu’il est interdit de poser un disque sur un disque plus petit.

Au début, tous les disques sont sur la tige 1 ( celle de gauche), et à la fin ils doivent être sur celle de droite.

Solutions

def rechercheDichotomique( t, x):
      g = 0

d = N-1
while(g <= d):

          m = (g+d)/2
if(t[m] == x):
return m;
elif(t[m] < x):
              d = m-1;
else:
              g = m+1;
return -1;

Notons que l'on peut écrire cette fonction sous forme récursive :

  // recherche de x dans t[g..d[
def dichoRec( t, x, g, d) :

if(g >= d): // l'intervalle est vide
return -1;
      m = (g+d)/2;
if(t[m] == x):
return m;
elif(t[m] > x):
return dichoRec(t, x, g, m)
else:
return dichoRec(t, x, m+1, d)


def int rechercheDicho( t, x):
return dichoRec(t, x, 0, len(t));
  }

Algorithme  Hanoi:

Procédure   Hanoi(n, départ, intermédiaire, destination)

            Si n > 0 alors

Hanoi(n-1,départ, destination, intermédiaire)

                        Déplacer un disque de départ vers destination

Hanoi(n-1,intermédiaire,départ,destination)

            Fin Si

Fin

Complexité recherche dichotomique

Le nombre maximal de comparaisons à effectuer pour un tableau de taille n est:

T(n) = 1 + T(n/2).

Pour résoudre cette récurrence, on écrit n = 2^t, ce qui conduit à

T(2^t) = T(2^t-1)+1 = ⋯ = T(1)+t

d'où un coût en O(t) = O(logn).

Complexité Tour de Hanoi:

L'évaluation de la complexité de cet algorithme est assez simple. Nous allons chercher à savoir combien de déplacements de disques sont nécessaires pour arriver à nos fins. Très simplement, la fonction calculant ceci peut être définie de la manière suivante : f(1) = 1; f(n) = 2*f(n-1)+1. On peut démontrer par récurrence que ceci est égal à f(n) = 2^n-1 : On a f(n+1) = 2*f(n)+1. En supposant que f(n) = 2^n-1, on a f(n+1) = 2*(2^n-1)+1. On développe ensuite en f(n+1) = 2*2^n-2+1 ce qui nous donne au final f(n+1) = 2^(n+1)-1. On a ainsi démontré que si c'est vrai pour n, alors c'est vrai pour (n+1). Comme on a f(1) = 2*0+1 = 2^1-1 = 1, c'est vrai pour tous les n supérieurs à 1 et 1. La complexité exacte de l'algorithme présenté ci-dessus est donc en 2^n-1 pour n disques à déplacer de la tour A vers la tour C. Avec la notation de Landau, on dit qu'il s'agit là d'une complexité exponentielle, c'est à dire en O(2^n).