I premi Turing: Edsger Dijkstra

Siete i soddisfatti possessori di un'auto sportiva fiammante con l'ultimo modello di navigatore satellitare touchscreen a bordo? Non vi separereste mai dal vostro smartphone e in particolare dall'app di navigazione, che ormai usate anche per percorrere strade ormai ben conosciute? Prima di intraprendere un viaggio qualsiasi, consultate sempre Google Maps e date un'occhiata al luogo di destinazione utilizzando Street View? Be', se è così, sappiate che la persona che dovete ringraziare più di ogni altra non è né l'amministratore delegato dell'azienda costruttrice della vostra macchina, né quello della compagnia che ha prodotto il vostro telefono, e nemmeno i fondatori di Google.

No, il vero artefice delle meraviglie che amate tanto è un signore olandese nato a Rotterdam nel 1930 e scomparso dodici anni fa.
Il suo nome, Edsger Wybe Dijkstra, è noto a tutti gli informatici per il celebre algoritmo che, in modo molto semplice ed elegante, consente di determinare il percorso più breve esistente tra un punto di partenza e un punto di arrivo su una rete di strade.

Figlio di un chimico e di una matematica, al liceo Edsger eccelleva in tutte le materie scientifiche, ma curiosamente era intenzionato a iscriversi alla facoltà di giurisprudenza. Furono i suoi genitori e i suoi insegnanti a convincerlo (per nostra fortuna, verrebbe da dire) a dedicarsi agli studi scientifici, e fu così che studiò fisica teorica all'università di Leida.
Nel 1951 frequentò un corso di programmazione a Cambridge, in Inghilterra. Per il giovane Edsger fu un'esperienza entusiasmante, che lo segnò in modo decisivo: pochi mesi dopo iniziò a lavorare come programmatore al Dipartimento di Informatica del Mathematical Centre di Amsterdam.
Nel 1956 si laureò in fisica, e nello stesso anno ideò il famoso algoritmo del cammino minimo, che sarebbe stato pubblicato tre anni dopo nell'articolo A note on two problems in connection with graphs (il secondo problema trattato, per la cronaca, era un'altra questione di teoria dei grafi: il problema del minimo albero ricoprente).
Sempre nel 1959 ottenne il Ph.D. all'Università di Amsterdam per la sua tesi intitolata Communication with an automatic computer.

Pare che quando Dijkstra si sposò, nel 1957, la burocrazia olandese non accettò che venisse scritta la misteriosa parola "programmatore" nella casella dedicata alla professione: così il neo-sposo optò per la più comprensibile dicitura "fisico teorico". Altri tempi.
Negli anni successivi, Dijkstra fu l'artefice di molte altre innovazioni cruciali per la storia del'informatica moderna: contribuì in modo determinante allo sviluppo del linguaggio ALGOL-60, e vi introdusse un costrutto apposito per la ricorsione; fu il primo a utilizzare il termine "stack", oggi comunissimo tra tutti gli informatici.
Nel 1962 divenne professore di matematica all'Università di Tecnologia di Eindhoven. Dieci anni dopo vinse il prestigioso premio Turing. Nel 1973 fu nominato Research Fellow alla Burroughs Corporation. Dal 1983 al 1999 insegnò informatica all'Università di Austin, in Texas.

Dijkstra è oggi considerato uno dei mostri sacri della storia della teoria degli algoritmi e della programmazione strutturata, e scrisse numerosi libri e articoli su questi temi.
Molteplici sono le sue scoperte, al di là del celebre algoritmo del cammino minimo: tra queste citerò l'algoritmo "shunting-yard", utilizzato per analizzare espressioni matematiche in notazione infissa, il pionieristico sistema operativo "THE", che supportava il multitasking ed era elegantemente strutturato come una "pila" di strati, il famoso algoritmo del banchiere e il geniale concetto di "semaforo", croci e delizie di ogni studente dei corsi di sistemi operativi.
Fu sempre Dijkstra a rendersi conto che, nei linguaggi di programmazione di alto livello, l'istruzione GOTO (che permette di saltare da una riga a un'altra all'interno di un programma) non è compatibile con una buona strutturazione del programma: nel 1968 scrisse l'articolo A case against the GO TO statement, che sosteneva questa tesi. Un altro settore di ricerca approfondito dall'informatico olandese fu quello della verifica formale della correttezza degli algoritmi.
Per tutti questi fondamentali contributi Dijkstra fu insignito del premio Turing nel 1972: ma certamente il suo elegante algoritmo del cammino minimo rappresentò il suo successo maggiore e il motivo della sua elevatissima reputazione nel mondo dell'informatica. Come funziona questo celebre algoritmo?

Immaginiamo di avere un grafo come quello illustrato in figura, formato da nodi e da archi. Ogni arco è contraddistinto da un valore numerico chiamato peso.
Un grafo come questo potrebbe rappresentare una rete di strade percorribili per viaggiare da un punto all'altro. In questo caso il peso di un arco sarà indicativo della lunghezza della tratta stradale che l'arco rappresenta, oppure del tempo necessario a percorrerla.
Supponiamo di voler applicare l'algoritmo di Dijkstra per spostarci dal punto A al punto F.
Il metodo di Dijkstra mantiene, in ogni istante dell'esecuzione, tre insiemi distinti di nodi della rete:
l'insieme V dei nodi visitati, l'insieme F dei nodi di frontiera, e l'insieme S dei nodi sconosciuti.
Per ogni nodo z, l'algoritmo tiene traccia di un valore (provvisorio) di distanza dal punto di partenza, d_z, e del predecessore (provvisorio) del nodo stesso, p_z.
All'inizio l'insieme V è vuoto, F è formato dal solo nodo di partenza A, e tutti gli altri nodi sono in S. Tutte le distanze d_z sono inizialmente considerate infinite (ad eccezione di quella del nodo di partenza A, posta a zero), e i predecessori p_z vengono considerati ignoti.
L'algoritmo consiste nel ripetere a ciclo continuo la seguente serie di operazioni. Si sceglie dall'insieme F il (o un) nodo z con distanza d_z minima, si sposta il nodo z nell'insieme V, e si spostano in F tutti i nodi ancora sconosciuti che sono successori di z (cioè che sono collegati a z). Per ciascuno di questi nodi successori viene calcolato un possibile nuovo valore della distanza, pari a d_z + a, dove a è il peso dell'arco che collega z con il nodo considerato. Se questo possibile nuovo valore è minore del precedente, esso viene "ufficializzato", e il predecessore del nodo viene aggiornato a z. In caso contrario, non succede nulla, e si passa al successivo dei nodi successori.

Da cs-exhibitions.uni-klu.ac.at

Quando i nodi successori sono terminati, si ripete la serie di operazioni allo stesso modo, e si prosegue così finché il nodo di destinazione F non risulta visitato, o finché l'insieme di frontiera non si svuota completamente. In quest'ultimo caso avremo capito che F non è raggiungibile partendo da A, altrimenti alla fine avremo compilato per tutti i nodi del grafo i valori di distanza e i predecessori.
Lascio ai lettori l'onore e l'onere di applicare il metodo illustrato al grafo in figura: vedrete che tutto sommato è divertente.

Dijkstra è famoso anche per una sua curiosa abitudine: amava scrivere, con la sua inseparabile penna stilografica, brevi memorie scientifiche, lettere e resoconti a mano, e le etichettava con il prefisso "EWD" (le sue iniziali) seguito da un numero d'ordine. L'archivio dell'Università del Texas ha catalogato più di 1300 documenti “EWD".
Un altro particolare passatempo di Dijkstra era quello di raccontare, anche all'interno dei suoi "EWD", le vicende di un'azienda immaginaria, la Mathematics Inc., il cui business era quello di provare teoremi matematici e poi metterli sul mercato, mantenendo però segreta la dimostrazione. Secondo i fantasiosi racconti di Dijkstra, nel catalogo dei prodotti della società vi era anche l'ipotesi di Riemann: uno dei principali problemi che l‘azienda doveva fronteggiare era la riscossione delle royalties dai matematici che utilizzavano l'ipotesi di Riemann come base di partenza per dimostrare altri teoremi.