Discussion:Algorithme du lièvre et de la tortue
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Moyenne |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Tout ou partie de cet article est issu de la traduction de l'article sous licence CC-BY-SA « (en) Cycle detection » dans sa version du 6 février 2007.
Consultez l'historique de la page originale pour connaître la liste de ses auteurs.
A propos du mu[modifier le code]
Ce que j'avais écrit à propos de la détermination de μ était correct (un seul tour supplémentaire suffit). Les calculs de pgcd ne sont pas nécessaires ici, à la différence de l'algorithme rho de Pollard Je me suis permis de modifier à nouveau la section Algorithme, mais avec plus d'explications cette fois et un pseudo-code pour déterminer μ (Backtracking 8 mars 2007 à 21:57 (CET))
Longueur du cycle[modifier le code]
J'ai un doute sur l'intérêt de la méthode décrite pour déterminer la longueur du cycle et je ne sais aps d'où ça sort (aucune source n'est indiquée).
La première étape permet de trouver un m tel que x_{m} = x_{2m} = x_{m+kl), c'est à dire que m = kl (l'algo trouve le plus petit k qui permet de rentrer dans la partie cyclique).
La seconde étape proposée actuellement est de recommencer la première étape à partir de m+1 : on va trouver forcément le r suivant vérifiant x_r = x_{2r} qui est r = m + l = (k+1)l (l'explication donnée me paraît d'ailleurs assez contournée même si correcte), en 2l étapes de calcul, alors qu'il suffirait de calculer la suite des a_[m+i} jusqu'à trouver a_m (et donc i = l), c'est conceptuellement plus simple, c'est ce qui est fait sur la version anglaise, ça ne demande que l étapes, c'est que je lis aussi dans Joux (cf. biblio en:). Bref je propose de reprendre cette partie. D'ailleurs il faudrait aussi déterminer la longueur de la "queue". La version anglaise est assez claire me smeble-t-il. Proz (discuter) 1 juin 2017 à 21:00 (CEST)
- Je viens de consulter justement cette discussion car l'algo proposé pour la longueur du cycle me semble inutilement compliqué.
- On pourrait mettre :
mu = 0répétermu = mu+1tortue = f(tortue)tant que tortue != lièvre- D'une part, ce serait une belle revanche pour la tortue, d'autre part il y a 3 fois moins d'évaluation de f, et c'est plus simple.
- À moins qu'un détail m'ait échappé ? Snarkturne (discuter) 4 décembre 2022 à 10:19 (CET)
Titre : Floyd ou les animaux[modifier le code]
Bonjour, il faudrait harmoniser le titre et les premiers mots du RI. Qu'est-ce qui est le plus utilisé, le titre avec Floyd, ou le titre avec les animaux ? --Roll-Morton (discuter) 4 juillet 2018 à 13:41 (CEST)