Discussion :

[Zavonen]

ol. bon j'ai peut-etre été un peu vite dans l'explication.

Dans un hanoi classique, on connait les mouvements a priori => Le calcul de CHAQUE COUP est indépendant des précedents ou des suivants. Ce calcul dépend uniquement du n° du coup et du nombre total de disque.

Par exemple, je sais que le mouvement n° 1234567 consiste a bouger le petit disque (puisque c'est un nombre impair).

Désolé mais ça va ENCORE trop vite pour moi .

[pseudocode]

Désolé mais ça va ENCORE trop vite pour moi .

Comme je l'ai dit precedement:

On a un état intermediaire obligatoire connu. Donc on peut séparer le processus "etat initial -> état intermediaire obligatoire" et le processus "état intermediaire obligatoire -> etat final". Et donc paralleliser ces 2 processus.

par recursion, on peut reappliquer ce principe a ces 2 processus. Car comme ca a été dit, l'etape n-1 de résolution de hanoi est un probleme de hanoi d'ordre inferieur.

[Zavonen]

Faisons simple !
Pouvez vous me décrire un algo parallèle resolvant hanoi 3 disques 3 piquets, 7 mouvement, process by process, step by step.
Et surtout ne me dîtes pas
process1 envoie le petit disque sur piquet 3, PUIS process2 le disque moyen sur piquet 2, etc...
pour moi, je le répète ce n'est pas du parallélisme.
Je voudrais lire process1 fait ceci TANDIS QUE process2 fait cela (bref, des actions simultanées, des croisements)

[Zavonen]

J'affine un peu ma pensée.
Je pense qu'en Hanoï dit classique (3 piquets) ce n'est pas possible.
Mais que cela devient possible si on augmente le nombre des piquets.
Exemple 6 disques 6 piquets
On emmène les 3 plus petits disques sur les piquets 4,5,6 (3 mvts)
process1 s'occupe d'empiler les 3 petits disques sur 6 (2 mvts)
PENDANT ce temps process2 s'occupe de résoudre hanoi classique d'ordre 3 sur les piquets 1,2,3 avec les 3 plus gros disques (7 mvts).
Pour finir on n'a plus qu'à amener le petit tas sur le gros.
Cette solution n'est évidemment pas optimisée, mais elle montre deux processus travaillant parallèlement à la résolution du pb.

[pseudocode]

J'affine un peu ma pensée.
Je pense qu'en Hanoï dit classique (3 piquets) ce n'est pas possible.

Ah ca y est. Je viens de capter le probleme. j'ai la comprenette difficile aujourd'hui.

Bien sur, les opérations PHYSIQUES nécessaires a la résolution ne sont pas parallelisables. Etant donné que chaque mouvement monopolise 2 piquets sur 3, il n'est pas possible de faire 2 mouvements en meme temps.

Moi je répondais au post #4:

Q: qu'est ce que tu voudrais paralléliser ?
R: Le calcul de toutes les étapes pour arriver de la position de départ à celui d'arrivée.

c-a-d la parallelisation du calcul des étapes: une suite de phrases du type "déplacer les disque ? du piquet ? vers le piquet ?".