Floyd Cycle Detection Algorithm

FR Texto en francés Aún no hay artículo en tu idioma: extracto en francés.

L'algorithme du lièvre et de la tortue, également connu sous le nom d'algorithme de détection de cycle de Floyd, est un algorithme pour détecter 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. Alors qu'un algorithme naïf consisterait à stocker chaque élément de la suite et, à chaque étape, de vérifier si le nouvel élément fait partie des éléments déjà rencontrés, l'algorithme de Floyd, lui, utilise un espace constant. 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. L'algorithme est sommairement décrit en 1969 par Donald Knuth dans un exercice du volume 2 de The Art of Computer Programming et attribué à Robert Floyd sans autre précision. Il est aussi décrit dans la note 3.8 de et est aussi attribué à Robert W. Floyd. Contrairement à ce que l'on trouve parfois, il n'est pas décrit dans un article de 1967 de ce dernier. L'algorithme rho de Pollard pour la décomposition en nombres premiers de même que celui pour le calcul du logarithme discret utilisent tous deux l'algorithme de détection de cycle de Floyd, pour des suites pseudo-aléatoires particulières. Soit f : S → S {\displaystyle f\colon S\rightarrow S} une fonction, et S un ensemble fini de cardinal n. On considère la suite ( a i ) {\displaystyle (a_{i})} définie par a 0 ∈ S {\displaystyle a_{0}\in S} et a i + 1 = f ( a i ) {\displaystyle a_{i+1}=f(a_{i})} . Cette suite possède un cycle, car le nombre de ses valeurs possibles est majoré par n.