Algorithme du lièvre et de la tortue

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Le Lièvre et la Tortue.

L'algorithme de détection de cycle de Floyd, également connu sous le nom d'algorithme du lièvre et de la tortue, est un algorithme qui permet de détecter en espace constant un cycle dans une suite récurrente engendrée par une certaine fonction f définie d'un ensemble fini S dans lui-même. L'algorithme a un bon comportement quand la fonction f a un comportement pseudo-aléatoire, et celui-ci peut être analysé par le paradoxe des anniversaires.

Algorithme[modifier | modifier le code]

Soit une fonction, et S un ensemble fini de cardinal n. On considère la suite définie par et

Il est clair que cette suite aboutit nécessairement à un cycle, le nombre de ses valeurs possibles étant limité à n. Une manière naïve de déterminer la longueur de ce cycle consiste à stocker chaque élément de la séquence et, à chaque étape, de vérifier si le nouvel élément fait partie des éléments déjà rencontrés. L'espace utilisé est en O(μ + λ), où μ est la longueur du cycle et λ le nombre d'éléments à l'extérieur du cycle.

Si l'on parvient à trouver deux éléments de la séquence et tels que

alors est un multiple de la longueur du cycle.

L'algorithme de Floyd de détection de cycle détermine une telle égalité en parcourant la séquence simultanément à deux vitesses différentes, respectivement 1 et 2. L'algorithme aboutit nécessairement sur deux valeurs égales, i.e. détermine m tel que

Dès lors, est un multiple de la longueur du cycle, μ.

Pour déterminer la valeur exacte de μ, il suffit de refaire tourner l'algorithme à partir de m+1, jusqu'à trouver un autre nombre tel que . Dès lors on a d'une part (car on retombe alors sur ) et d'autre part μ qui divise (car il divise et ), donc .

Visualisation[modifier | modifier le code]

Exemple de cycle de μ=6 nœuds obtenu après être passé sur λ=2 nœuds

La meilleure façon de visualiser l'algorithme consiste à représenter la séquence. Le dessin obtenu ressemble à la lettre grecque ρ. La séquence démarre en bas, monte et emprunte le cycle dans le sens des aiguilles d'une montre. Suivant l'algorithme de Floyd, les deux parcours se rencontrent en après 6 itérations. Un deuxième tour de l'algorithme amène les deux parcours à se rencontrer après 6 nouvelles itérations, d'où la valeur .

Parcours
Lent
Rapide

Pseudo-code[modifier | modifier le code]

 m = 1; x = f(); y = f(x);
 tant que x != y faire
    m = m + 1
    x = f(x)
    y = f(f(y))
 { la valeur de m est telle que  }

Si on souhaite obtenir la valeur de , il suffit d'ajouter à la suite le code suivant :

 mu = 0
 répéter
    mu = mu+1
    x = f(x)
    y = f(f(y))
 tant que x != y

Complexité[modifier | modifier le code]

L'algorithme effectue au minimum λ comparaisons, étant donné que le parcours lent de la séquence doit au moins atteindre le cycle pour rencontrer le parcours rapide. Le nombre maximum de comparaisons est , étant donné que le parcours lent ne peut effectuer plus d'un tour du cycle avant d'être rattrapé par le parcours rapide. L'algorithme utilise un espace O(1).

Applications[modifier | modifier le code]

L'algorithme rho de Pollard pour la factorisation de même que celui pour le calul du logarithme discret utlisent tous deux l'algorithme de détection de cycle de Floyd, pour des suites pseudo-aléatoires particulières.

Attribution[modifier | modifier le code]

L'algorithme est sommairement décrit en 1969 par Donald Knuth dans le volume 2 de The Art of Computer Programming[1] et attribué à Robert W. Floyd sans autre précision. Contrairement à ce que l'on trouve parfois, il n'est pas décrit dans un article de 1967[2] de ce dernier[3].

Références[modifier | modifier le code]

  1. Donald E. Knuth, The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, , p. 7, exercises 6 and 7
  2. (en) R.W. Floyd, « Non-deterministic Algorithms », , pp. 636-644
  3. The Hash Function BLAKE, Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21, footnote 8.

Bibliographie[modifier | modifier le code]