Metraipolis › archive › dc_ccc07bd22eaf

Algorithme du lièvre et de la tortue — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Algorithme_du_li%C3%A8vre_et_de_la_tortue
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-17T11:51:44.815Z
SHA-256 of the archived text
101bab9d35f0352bc8d24eaf5737583dd2f556ab315583f544e176da7e762866
Stable URL of this page
https://metraipolis.com/documento/dc_ccc07bd22eaf

How to cite

Algorithme du lièvre et de la tortue — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_du_li%C3%A8vre_et_de_la_tortue (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ccc07bd22eaf (Metraipolis archive dc_ccc07bd22eaf, sha256 101bab9d35f0352bc8d24eaf5737583dd2f556ab315583f544e176da7e762866)
BibTeX
@misc{dcccc07bd22eaf,
  title = {Algorithme du lièvre et de la tortue — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Algorithme_du_li%C3%A8vre_et_de_la_tortue},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ccc07bd22eaf; sha256 101bab9d35f0352bc8d24eaf5737583dd2f556ab315583f544e176da7e762866},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_du_li%C3%A8vre_et_de_la_tortue. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Algorithme du lièvre et de la tortue» — https://fr.wikipedia.org/wiki/Algorithme_du_li%C3%A8vre_et_de_la_tortue
Wikidata Q1588200: «algorithm of cycle finding» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1588200
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_du_li%C3%A8vre_et_de_la_tortue?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 212945352, consultata il 2026-10-17T11:18:28.627Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 6a1034bd0df820ccb1fcf8119759324ad9039168f436423d5ba7d74bbf10d5f8