Tours de Hanoï : méthode bourrin ?

[CM63]

Bonjour,

Cela faisait un moment que je voulais faire un post sur la méthode bourrin pour les tours de Hanoï, à comparer avec la méthode récursive. Mais je me suis fait doubler par BenoÎt Rittaud de la Sorbone. Voici un lien sur sa vidéo sur la chaîne AuDi Math, où il ne parle pas que de la méthode bourrin, d'ailleurs. Bonne vision.
-----

[invite7b7f1ad0]

Bonjour, le plus bourrin est de faire pivoter le plateau d'un 1/2 tour..

[CM63]

C'est uniquement parce qu'il n'a pas pensé à les mettre en triangle, pour mieux illustrer de la symétrie d'ordre 3.

[obi76]

Intéressante comme vidéo, merci

[A voir en vidéo sur Futura]

[invite7b7f1ad0]

Intéressante comme vidéo, merci

Tout à fait, (@ CM63 tu n'as pas visualisé mon trait d'humour bourrin , relis et imagines un gamin devant le plateau de jeu )

[CM63]

Ah oui, d'ailleurs BenoÎt Rittaud le fait à plusieurs reprises, ni vu ni connu.

[amineyasmine]

Bonjour

Si la solution du problème PNP est P=NP cet exercice serait une piste.
Mais si la solution est P différent de NP, c’est difficile de trouver une piste

[Deedee81]

Salut,

La résolution de la tour de Hanoï est polynomiale.
Donc aucune chance de trouver une solution à la question P=NP de ce coté là

(franchement, tu aurais pu vérifier avant de lâcher une telle chose)

[amineyasmine]

Salut,

La résolution de la tour de Hanoï est polynomiale.
Donc aucune chance de trouver une solution à la question P=NP de ce coté là

(franchement, tu aurais pu vérifier avant de lâcher une telle chose)

si la réponse est P=NP, c'est par des astuces polynomiales qu'on trouvera la solution.

mais si P différent NP, ce n'est pas l'astuce qu'il faut mais un livre de démonstration

[Deedee81]

Salut,

si la réponse est P=NP, c'est par des astuces polynomiales qu'on trouvera la solution.

Holàlà, comme tu est naïf. Ca n'a rien d'aussi simple. Et il est fort possible qu'on prouve P=NP aussi par démonstration non constructive (donc sans pouvoir exhiber un algorithme). Et dans tous les cas on a déjà pu montrer (voir le document explicatif à l'institut Clay) qu'aucune méthode simple ne permettra d'y arriver.

[pm42]

Et il est fort possible qu'on prouve P=NP aussi par démonstration non constructive (donc sans pouvoir exhiber un algorithme)

Tout à fait. Ou qu'on trouve une méthode constructive qui amène à des polynômes avec degré et des coefficients tels qu'ils ne seront pas utilisables en pratique.

[Deedee81]

Tout à fait. Ou qu'on trouve une méthode constructive qui amène à des polynômes avec degré et des coefficients tels qu'ils ne seront pas utilisables en pratique.

En effet, c'est ce qu'ils disaient aussi dans le document de l'institut Clay.

A noter qu'on avait trouvé un algorithme déterministe, exact et polynomial pour les tests de primalités, il y a quelques années (à l'époque il restait un doute).
Mais l'algo état N^7 (exposant 6 sous une condition conjecturée).
Donc inutilisable en pratique mais intéressant au niveau théorique.

[CM63]

Il y a beaucoup de hors sujet ces derniers temps sur ce fil, cependant je demande au modérateurs de ne pas clore la discussion pour cela, la discussion n'a pas à pâtir des hors sujet, ce n'est à mon avis pas une bonne raison de clôture.
Merci aux posteurs de se recentrer sur le sujet.

[Deedee81]

Salut,

Akuna matata, je n'y ait même pas pensé (à la fermeture). Ceci dit, il ne tient qu'à toi aussi de relancer la bêbête. On dirait que personne n'a plus grand chose à dire (mais on ne ferme pas un sujet pour ça, sauf si ça tourne à chipoteries, margailles, dérives, délires.... Ici ce n'est pas la petite glissade ci-dessus qui va mettre ta discussion en péril).