Dr. Carlo Pescio
Recensione: The Stanford GraphBase


Scheda Libro
Autore: Donald E. Knuth Titolo: The Stanford GraphBase
Editore: Addison Wesley ISBN: 0-201-54275-7
Lingua: Inglese Anno: 1994 Pagine: 580 Allegati: nessuno

Commenti
Donald Knuth è il noto autore del trittico "The Art of Computer Programming" (da me recensito in Computer Programming No. 46), un’opera fondamentale nel campo degli algoritmi. Meno noto è il fatto che, idealmente, l’opera avrebbe dovuto estendersi su 7 volumi, il quarto dei quali doveva essere dedicato agli algoritmi combinatori. Knuth è tuttora impegnato al completamento della serie, ma The Stanford GraphBase si può considerare un anello di congiunzione fra alcuni suoi lavori precedenti (sul literate programming) ed il quarto volume della sua opera monumentale. Il testo discute molti algoritmi combinatori, come l’algoritmo di Dijkstra per il cammino minimo, gli algoritmi di Hopcroft e Tarjan, vari algoritmi euristici e greedy, con un importante obiettivo: chiarire al meglio il costo di un certo algoritmo quando è applicato ad un certo tipo di grafo.

Pro
Il testo è ricco di valutazioni quantitative, che sono fondamentali per orientarsi al meglio tra le possibili alternative. Sorprendentemente, l’apparato matematico usato è molto limitato rispetto allo standard di Knuth, e ciò dovrebbe permettere una lettura agevole anche a chi non va matto per le serie di potenze. A differenza dei volumi di The Art of Computer Programming, qui ogni algoritmo è presentato anche in forma di codice o pseudocodice, per quanto la scelta di usare CWeb sia discutibile. Per chi ha interessi di ricerca, il testo pone una serie di quesiti tuttora irrisolti che possono sicuramente stimolare approfondimenti di rilievo.

Contro
L’unica critica che mi sento di muovere al testo è l’uso del sistema CWeb per la presentazione degli algoritmi. CWeb è uno strumento di literate programming, un’idea di Knuth che per varie ragioni non ha mai avuto molti proseliti. Usando uno strumento come CWeb, i programmi vengono scritti in una variante del C che consente di esprimere parti in pseudocodice, implementandole poi "a latere", integrando di fatto la tecnica dei raffinamenti successivi con il linguaggio di programmazione. Purtroppo ciò costringe non solo a scaricarsi dal sito internet di Stanford l’intero sistema CWeb, ma anche ad imparare un nuovo linguaggio ed i suoi idiomi caratteristici. Anche se, comprensibilmente, l’autore vuole dimostrare la bontà del suo sistema, il testo avrebbe guadagnato in immediatezza (di lettura ed uso) per molti lettori se avesse adottato un linguaggio più tradizionale.