Dr. Carlo Pescio
Recensione: Randomized Algorithms


Scheda Libro
Autore: Rajeev Motwani, Prabhakar Raghavan Titolo: Randomized Algorithms
Editore: Cambridge University Press ISBN: 0-521-47465-5
Lingua: Inglese Anno: 1995 Pagine: 480 Allegati: Nessuno

Commenti
Esiste una classe di problemi, detti NP-completi, che sembra non possano essere risolti in tempo polinomiale usando un algoritmo deterministico. Non si tratta di problemi squisitamente accademici: molto spesso esiste una controparte decisamente concreta, come la connessione di nodi di una rete in presenza di vincoli, o la rottura di sistemi di crittografia. Esistono però degli approcci meno tradizionali al problema, sotto forma di algoritmi che eseguono scelte casuali durante l’esecuzione. Tali algoritmi possono arrivare ad una risposta approssimata in tempo polinomiale, con un grado di precisione che in alcuni casi (ad es. test di primalità) sfiora decisamente la certezza. Il testo è interamente dedicato alle diverse categorie di algoritmi randomizzati, e fornisce da un lato il necessario background matematico, dall’altro numerosi esempi di applicazioni.

Pro
Il libro tratta con precisione sistematica un argomento che è spesso confinato nei "cenni" degli altri testi sugli algoritmi. L’impostazione è decisamente da "libro di testo", ma considerando l’oggettiva complessità di alcune parti, si tratta probabilmente di una scelta quasi obbligata. L’insieme di problematiche considerate è molto ampio, e gli esempi spaziano dalla scelta delle strutture dati, agli algoritmi geometrici e di programmazione lineare, fino agli algoritmi paralleli ed online. È comunque necessario un certo sforzo per arrivare dalla discussione degli algoritmi, sempre molto astratta, ad una effettiva implementazione.

Contro
La parte matematica ha un peso molto rilevante all’interno del testo. Anche se ciò è comprensibile in un libro dedicato agli algoritmi, in questo caso viene richiesta maggiore dimestichezza del consueto con il calcolo delle probabilità. Catene di Markov, probabilità condizionali, lemma di Lovász, disuguaglianza di Chebyshev vengono usati con disinvoltura all’interno del testo. Per contro, gli algoritmi vengono al più presentati in forma di pseudocodice, comunque ad un livello di astrazione piuttosto alto. Tutto sommato, un testo di gran pregio ma rivolto più allo studente di dottorato che al programmatore in cerca di una soluzione pratica.