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).

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.