Divertente come un algoritmo

A chi non piacciono i rompicapi, gli indovinelli, i puzzle che stimolano logica e intuizione? Anche i testi antichi ci raccontano dell’importanza dell’enigma: solo chi ha la sapienza e la pazienza di risolverlo ha accesso alla saggezza superiore. La verità si presenta sotto forma di enigma perché ciò che è importante non può essere immediatamente manifesto, ci dicono gli dei, ma si ottiene solo con sforzi intellettuali e perseveranza. Risolvere un enigma ha una forza d’attrazione a cui è difficile resistere. Capire un problema, progettare un algoritmo e tradurlo in un programma di computer può essere considerato un enigma dei nostri tempi, almeno per la seduzione che provoca in chi si cimenta in quest’attività e l’emozione che si accompagna al trovare una soluzione. Una sfida intellettuale, attraente e totalizzante, ma anche decisamente divertente o, per dirla in inglese, fun. La ricerca algoritmica, anzi, ha spesso nell’elemento ludico una componente centrale del percorso. Il gioco può essere l’esito di tutto il processo o uno dei motivi che l’hanno attivato. Per Donald Knuth, uno dei giganti del settore, “probabilmente il divertimento è stato davvero la meta più importante in tutto il percorso”. L’affermazione è abbastanza sovversiva in una disciplina che nel sentire comune è caratterizzata soprattutto da precisione e rigore. Di fatto, anche se (quasi) tutti i ricercatori fanno finta di non divertirsi mentre lavorano (non sia mai!) i temi potenzialmente fun dell’algoritmica sono molteplici e classificabili in quattro grandi categorie, a seconda della componente ludica dominante: narrativa, problema, oggetto ed estraneità.

Narrativa

Afferiscono a questa categoria lavori che affrontano e risolvono, almeno parzialmente, temi algoritmici classici, presentandoli però in modo creativo. La componente fun è quindi nella narrazione: il problema esaminato è riformulato usando metafore inattese e spesso già di per sé divertenti. Così, per esempio, un particolare problema di online scheduling è raccontato come motivato dal desiderio di mantenere il più possibile la privacy quando si accede a una fila di orinatoi senza divisori in un bagno pubblico maschile. La descrizione e l’analisi di un algoritmo per la riconfigurazione di una fila di micro-robot dopo il guasto di alcuni di loro sono narrate come la decifrazione da parte di un team di archeologi dei rituali sacri preistorici disegnati sulle pareti di una caverna. Un gruppo di problemi di geometria computazionale sono riformulati all’interno
del discorso corrente su “genere e privacy”, diventando così problemi di decisione della posizione di spogliatoi o servizi igienici in palestre la cui utenza è multi-genere, cioè non limitata al bipolarismo sessuale, in modo da garantire il livello di privacy richiesto da ciascun gruppo.

Problema

A questo gruppo appartengono lavori in cui non è la narrazione ad essere divertente, bensì l’obiettivo della ricerca: si tratta di problemi algoritmici astrusi, avulsi da motivazioni applicative o pratiche, problemi di fantasia, che però vengono analizzati formalmente e risolti rigorosamente. In questa vena, un quesito posto nel film Die Hard – duri a morire su come disinnescare una bomba viene generalizzato e risolto usando proprietà di teoria dei numeri. Un altro esempio è costituito dal problema di come ci si saluta prima di uscire da una festa. In alcune società, la pratica comune è di salutare all’uscita scambiando baci (da uno a tre a seconda del rituale), o con una semplice stretta di mano. Quando più persone lasciano contemporaneamente la festa, riuscire tutti a salutare tutti individualmente richiede un processo di spostamenti, complicati dalla dimensione (di solito ridotta) del locale d’uscita e dal numero di persone. A questo gruppo appartengono anche i lavori dove il problema è classico ma l’obiettivo della ricerca è algoritmicamente “invertito”: un algoritmista cerca solitamente la soluzione più efficiente possibile per il problema esaminato, mentre qui le soluzioni esaminate e rigorosamente analizzate sono le peggiori possibili, o illogiche, e per questo assurdamente divertenti.

Oggetto

Molti algoritmisti si occupano della complessità di risoluzione di giochi esistenti e ben noti oppure di nuova progettazione. In questo tipo di lavori, il gioco stesso e il suo svolgimento vengono analizzati facendo uso di tecniche di teoria degli algoritmi e complessità. La varietà di giochi esaminati è realmente sorprendente: giochi di parole tipo Scarabeo; giochi di carte tipo Uno; puzzles (Sudoku, Tantrix, Kaboozle, Nonogram); giochi da tavolo (Mastermind, Honey-Bee); labirinti (Alice’s Maze) e chiaramente video-giochi, sia famosissimi (Super Mario, Classic Nintendo Games), sia specializzati (Lemmings, Prince of Persia, Heroes of Might and Magic). Nonostante la loro incredibile diversità, i giochi e i puzzle hanno in comune il fatto di non essere banali da risolvere. Impegnano la fantasia, l’intuizione e la logica dei giocatori, li coinvolgono appassionandoli, producendo in loro esaltazione oppure frustrazione, ma sempre di certo fun. Quello che emerge di interessante da questi lavori di analisi è che quasi tutti questi giochi/puzzle risultano essere problemi “computazionalmente costosi”, cioè difficili. Per apprezzare le implicazioni di questi risultati è necessario ricordare che in informatica ci sono due famose classi di problemi: la classe P di quelli risolvibili in tempo polinomiale (cioè ragionevole) deterministicamente (cioè dai computer odierni) e la classe NP, di quelli risolvibili in tempo polinomiale ma non-deterministicamente, cioè da una macchina astratta che non si sa se potrà mai essere costruita. Il più grande mistero tuttora esistente nell’informatica è se P=NP o no. Anche se sprovvisti di una risposta certa, il pensiero comune è che la risposta sia negativa; ci sarebbero problemi come quelli in NP che non sono né mai saranno risolvibili in tempi ragionevoli (tipo la durata di una vita umana) senza un oracolo, un miracolo, o una profonda trasformazione tecnologica, come quella promessa dalla quantistica. È proprio basandosi sulla difficoltà inerente alla risoluzione di questi problemi che si fonda per esempio la sicurezza delle transazioni finanziarie odierne o si regge la solidità dei protocolli crittografici. Ritornando ai nostri giochi e puzzle, essi appartengono quasi tutti alla famigerata classe di problemi NP-hard, cioè quelli difficili almeno quanto il più difficile di tutti i problemi in NP!

Estraneità

I problemi considerati sono reali e provengono non dall’informatica ma dall’uso comune e sono affrontati con le tecniche algoritmiche e di programmazione, in modo da ottenere risultati nuovi e interessanti. Nell’articolo di E. Gethner et al. dal titolo M.C. Escher Wrap Artist: Aestetic Coloring of a Ribbon Pattern, si parte da un’idea del famoso artista grafico olandese, che studiava la generazione di disegni periodici decorativi, e si definisce una piastrella di Escher come un quadrato contenente motivi che possono essere colorati in modi diversi. Ci si chiede allora se questa possa essere replicata in tante copie e concatenata, usando traslazioni verticali e orizzontali, per realizzare un disegno più grande, in grado di tassellare il piano, colorato in modo gradevole. Quello che Escher faceva a occhio diventa qui il risultato di un teorema dimostrato in modo costruttivo, cioè con l’algoritmo di generazione. Se la piastrella ha determinate proprietà, la tassellazione voluta si può sempre ricavare. Nella fig. 1 si vedono, al centro del disegno, una piastrella di Escher che tassella il piano e una prima colorazione poco soddisfacente che interrompe il colore di ogni nastro, mentre nella fig. 2 la colorazione è soddisfacente. Un altro esempio curioso proviene dal mondo dei tessuti: si mostra come la maglia stimoli il ragionamento formale e l’astrazione matematica che nell’esecuzione pratica del lavoro trovano un’immediata realizzazione. La maglia, riletta con gli strumenti dell’algoritmica, aiuta a ridisegnare, generalizzare e generare automaticamente schemi vecchi e nuovi da cui attingere per crearne una gamma infinita. Il motivo a trecce della figura 3, per esempio, rappresenta la struttura di una rete di computer di definizione ricorsiva detta butterfly, lavorata a maglia.