Alcuni famosi enigmi nella lista dei classici enigmi dell'informatica sono :
- Filosofi a cena (Concurrency and Deadlocks)
- Cinque filosofi siedono intorno ad un tavolo circolare. Davanti ad ogni filosofo c'è un grande piatto di riso. I filosofi alternano il loro tempo tra mangiare e pensare. C'è una bacchetta tra ogni filosofo, alla loro immediata destra e sinistra. Per mangiare, un dato filosofo deve usare entrambe le bacchette. Come si può garantire che tutti i filosofi possano mangiare in modo affidabile senza morire di fame? Ci sono varie soluzioni che vanno dallo stesso risolutore del problema, Edsger W. Dijkstra, ad altre risposte arbitrarie.
- Venditore itinerante (P=NP)
- Un venditore ha un percorso di città che costituiscono il suo giro. Qual è il percorso di vendita più efficiente che visita ogni città esattamente una volta, e poi ritorna alla città di origine? Abbiamo un'euristica, ma non si sa ancora se può essere risolto con un algoritmo a tempo polinomiale.
- Otto regine (Algoritmo di progettazione)
- Poste otto regine su una scacchiera standard 8 x 8, quante posizioni uniche--escludendo le rotazioni e le immagini speculari--possono occupare queste otto regine senza attaccarsi a vicenda? Backtracking è una, branch and bound un'altra.
- Due generali (Protocolli di comunicazione)
- Due eserciti, ognuno guidato da un generale, si stanno preparando ad attaccare una città. Gli eserciti sono accampati fuori dalla città su due montagne separate da una grande valle. Per catturare la città, i generali devono attaccare esattamente nello stesso momento. L'unico modo per i generali di comunicare è quello di inviare messaggeri attraverso la valle. Sfortunatamente, la valle è occupata dai difensori della città, quindi c'è la possibilità che ogni messaggero venga catturato. Ogni generale non ha modo di sapere se il suo messaggero è arrivato. Come fanno i generali a coordinare il loro attacco?
- Towers of Hanoi (Recursion)
- Hai una pila di dischi, dal più grande al più piccolo, che scivolano sul primo piolo di una tavola a tre pioli. Il tuo obiettivo è spostare l'intera pila di dischi dal primo al terzo piolo. Tuttavia, puoi spostare solo il disco più in alto di qualsiasi piolo, e i dischi più piccoli devono sempre essere posizionati su quelli più grandi. Quante mosse ci vorranno?
- Risposta : Per [math]n[/math] dischi, abbiamo [math]2^n-1[/math] passi/mosse da risolvere, che possono essere fatte usando la ricorsione.
Fonte : Classic Computer Science Puzzles
Un ottimo libro è The Science of Programming di David Gries in cui discute varie idee dietro i puzzle di Dijkstra e altre idee classiche di puzzle. Per esempio questo: Un classico puzzle combinatorio :
Un sacchetto contiene alcune palline bianche e nere. Il seguente processo deve essere ripetuto il più a lungo possibile (supponendo di avere una scorta infinita di palle bianche e nere).
- Selezionare casualmente due palle dal sacchetto. Se sono dello stesso colore, buttale via, ma metti una pallina nera in più.
- Se sono di colori diversi, rimetti quella bianca nel sacchetto e butta via quella nera.
Prova a risolverlo, è molto più semplice quando lo fai sulla carta.