Teoria - Torre di Hanoi

"L'esistenza di problemi indecidibili restringe la possibilita' di progettare algoritmi e programmi ai soli problemi decidibili." (Edgar Allan Poe)
ghghgh, no non l'ha scritta lui...

Cosi' parte la mia prima giornata di studio di Algoritmica e gia' mi sento male... Avevo voglia di mettere in pratica quello che sto studiando e non sono riuscito a trovare modo migliore che rompervi le balle.
Musica ascoltata durante la produzione: (I've) [KOTOKO](BALDR FORCE) Face of Fact (full).mp3 (roba jappo, sempre mitici ^^)
Minuti persi: troppi...
Ricordo che per la lettura sono indispensabili alcune basi di matematica e programmazione, soprattutto per la parte relativa all'induzione e alla ricorsione.
Ciancio alle bande, iniziamo!

- - - - - - - - - - - - 8< - - - Tagliare qui - - - 8< - - - - - - - - - - -
La maggior parte di voi, almeno spero, conosceranno questo simpatico oggettino peloso:




La torre di hanoi. Quella rappresentata in figura e' la versione giocattolo che rappresenta solo un dodiciesimo dell'assurdita' di quella vera.
Lo scopo del gioco, se cosi' possiamo chiamarlo, e' quello di spostare tutti i tasselli dal primo piolo all'ultimo seguendo le seguenti regole:
1) Si puo' spostare un solo tassello alla volta
2) Un tassello non puo' essere spostato su un tassello piu' piccolo

C'e' solo un piccolissimo problema... tornando alla prima frase che ho scritto, tra i problemi decidibili non tutti i problemi risultano risolvibili in tempo ragionevole. Come vi faro' notare entro breve, la Torre di Hanoi e' uno di quelli che, se si sapesse a priori quanto tempo impiegheremmo a completarlo, ci passerebbe la voglia di giocarci.
La VERA leggenda (che e' un po' paradossale, ma vi giuro che e' cosi') narra che in un tempio indiano dedicato alla divinita' Brahma ci sono 3 pioli, di cui il primo contiene 64 dischi d'oro impilati in ordine di diametro decrescente, con il disco piu' ampio in basso e il disco meno ampio in alto. Quando i monaci avranno terminato di spostare tutti i dischi dal primo all'ultimo piolo, seguendo le regole sopra descritte, avverra' la fine del mondo.
La leggenda e' fantastica, solo che secondo me il mondo finira' molto prima... ve ne do la dimostrazione.
La soluzione piu' banale per questo problema si ottiene utilizzando un algoritmo ricorsivo. Vi mostro brevemente uno pseudocodice:

Codice:

TorreHanoi( n, primo, secondo, terzo ):
  IF ( n = 1 ) {
      Scrivi("Dal " + primo + " al " + terzo);
  }
  ELSE {
      TorreHanoi( n-1, primo, terzo, secondo );
      Scrivi("Dal " + primo + " al " + terzo);
      TorreHanoi( n-1, secondo, primo, terzo );
  }

Seguendo ricorsivamente questo algoritmo a mano su un "n" piccolo a piacere, si scopre che il numero di mosse effettuate sono sempre (2 ^ n) - 1. Ad esempio con 3 dischi effettuereste 7 mosse.
Dimostriamo per induzione su "n" (numero di dischi) che il numero di mosse e' effettivamente quello
Il caso base e' semplice, per n = 1, spostiamo l'unico disco dal primo piolo all'ultimo con una mossa... vediamo.

Codice:

(2 ^ 1) - 1 = 1

Eh gia', funziona
Se guendo il codice di sopra, proviamo a generalizzare per tutti i casi con n > 1. Essendoci due chiamate nel ramo ELSE, risolveremo il caso di una singola chiamata moltiplicando per 2 il risultato, quindi... richiamando la funzione con n = (n-1) come si vede dal codice...

Codice:

2 x ((2^(n-1)-1))+1 = (2^n)-1

Purtroppo non e' possibile sperare che esista un programma che effettui la risoluzione della torre di hanoi in meno di (2^n)-1 mosse, in quanto e' stato dimostrato che sono NECESSARIE.

Ora, se per curiosita' non l'avete ancora fatto, provate a vedere quante mosse dovrebbero fare i nostri amici monaci per finire la loro a 64 dischi... Per i piu' pigri ci penso io.
Supponendo di fare una mossa al secondo (impossibile anche con la versione semplificata giocattolo)... (2^64)-1 = 18.446.744.073.709.551.615 secondi... che sono quasi 585 MILIARDI DI ANNI.
Per porvi un ulteriore confronto, la teoria del Big Bang pone l'inizio dell'universo dai 10 ai 20 miliardi di anni fa... Penso di aver reso l'idea.
- - - - - - - - - - - - 8< - - - Tagliare qui - - - 8< - - - - - - - - - - -

Ringraziamenti speciali:
Nessuno. Quando ci rimango male io non capisco perche' devo dire anche "grazie". Tie'