Détection de cycle
problème algorithmique
From Wikipedia, the free encyclopedia
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.
Cet article est une ébauche concernant l’informatique théorique.
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].
