Détection de cycle

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Le problème algorithmique de détection de cycle consiste à trouver un cycle dans la suite des valeurs d'une fonction itérée. Il existe plusieurs algorithmes pour ce problème comme l'algorithme du lièvre et de la tortue et l'algorithme de Brent. Ce problème apparait dans des contextes divers : les générateurs de nombres pseudo-aléatoires, la théorie des nombres, la cryptographie, les automates cellulaires, etc.

Description

Soit une fonction f d'un ensemble fini D dans lui-même. En itérant la fonction f à partir d'un élément de D, on retrouve nécessairement la même valeurs plusieurs fois. À partir d'une telle valeur, on parcourt un cycle. La détection de cycle consiste à trouver un tel cycle[1].

Algorithmes

Des algorithmes pour ce problème sont l'algorithme du lièvre et de la tortue, attribué à Floyd[2], l'algorithme de Brent[3] et l’algorithme de Gosper[1].

Notes et références

  1. ↑ a et b Gabriel Nivasch, « Cycle Detection », sur Université d'Ariel.
  2. ↑ Donald E. Knuth, The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, , Chapitre 7, exercice 6 et 7.
  3. ↑ Richard P. Brent, « An improved Monte Carlo factorization algorithm », BIT Numerical Mathematics , vol. 20, no 2,‎ , p. 176-184 (DOI 10.1007/BF01933190, lire en ligne).