Il libro
Algoritmi e strutture dati, edito dalla casa editrice
McGraw-Hill, è un libro indispensabile per tutti coloro che operano nel mondo dell'IT. Autori del libro sono: Camil Demetrescu, Irene Finocchi, e Giuseppe F. Italiano.
Il libro è suddiviso in diciassette capitoli molto eterogenei tra loro. Ogni capitolo infatti si occupa di descrivere e risolvere un particolare problema; tali problemi sono legati sia allo studio degli algoritmi, sia allo studio delle strutture dati. Nel libro non è incluso alcun CD-ROM o DVD.
Il primo capitolo, sebbene introduttivo, fa capire con molta chiarezza il ruolo rivestito dagli algoritmi nelle prestazioni di un progetto informatico. Attraverso un esempio legato al calcolo del numero di Fibonacci, gli autori riescono a mostrare la differenza che intercorre tra l'utilizzo di un algoritmo efficiente da uno inefficiente. Per misurare le prestazioni sono introdotte le quantità di tempo e spazio. Ed infine, è fornita un'introduzione concernente la notazione asintotica.
Il secondo capitolo descrive quali sono le principali metodologie per l'analisi degli algoritmi. La trattazione sottolinea l'importanza di utilizzare opportuni modelli di calcolo per verificare l'utilizzo delle risorse(tempo di esecuzione e spazio di memoria). Nella seconda parte del capitolo è ripresa la trattazione circa la notazione asintotica. Di essa sono affrontati i temi relativi allo studio del caso peggiore e del caso medio(in particolare descrivendo la tecnica della randomizzazione). Infine, è analizzato il tempo di esecuzione degli algoritmi ricorsivi.
Nel terzo capitolo sono descritte le tecniche che consentono la gestione di collezioni di oggetti nella memoria di un calcolatore. E' sottolineata la differenza che esiste tra un tipo di dato e una struttura dati, e sono descritte le principali tecniche di rappresentazione: indicizzata e collegata. Di tali tecniche sono sottolineate le differenze che intercorrono nel loro utilizzo a seguito delle operazioni da effettuare. In conclusione sono descritte le possibili realizzazioni dei tipi di dato pile, code, alberi.
In questo capitolo è affrontato l'importante concetto dell'ordinamento. Inizialmente, la trattazione introduce un modello astratto, per poi mostrare tecniche di progettazione e di analisi degli algoritmi. Tra esse è analizzata la tecnica del divide et impera, l'utilizzo di strutture dati efficienti, la tecnica di randomizzazione, e la dipendenza dal modello.
Il quinto capitolo è incentrato sull'analisi del problema del calcolo del mediano di un insieme di elementi. La trattazione prende ad esempio l'algoritmo quick sort per poter giungere tramite opportuni accorgimenti ad un algoritmo randomizzato. Infine, è progettato un algoritmo lineare deterministico basato su una tecnica di campionamento.
Nel sesto capitolo è affrontato il problema del dizionario analizzandolo mediante strutture basate sul confronto. Nel capitolo sono sottolineati tutti gli aspetti legati agli alberi binari di ricerca relativi al problema dell'inserimento, della cancellazione, e della ricerca di elementi all'interno del dizionario.
In questo capitolo, il problema del dizionario è affrontato utilizzando operazioni che richiedono tempo costante in media. La tecnica descritta è l'hashing. L'hashing è descritto nei particolari, mettendo in evidenza il problema delle collisioni e come risolverlo utilizzando funzioni hash con buon grado di uniformità. Sono trattate due diverse tecniche di risoluzione delle collisioni, esse sono le liste di collisione e l'indirizzamento aperto.
L'ottavo capitolo affronta il tema del mantenimento del minimo valore in un insieme di dati che richiedono frequenti aggiornamenti. Attraverso il tipo di dato coda con priorità sono illustrate quattro realizzazioni del problema. Esse sono: DHeap, HeapBinominale, HeapBinominaleRilassato, HeapFibonacci.
Il capitolo descrive algoritmi efficienti per la risoluzione del problema union-find. Ad una trattazione di strutture molto semplici, quali gli alberi QuickUnion e QuickFind, che non offrono prestazioni soddisfacenti, si passa alla descrizione di euristiche di bilanciamento(union by size e union by rank) che portano risultati ottimi relativamente all'operazione di union. Seguendo, sono descritte le euristiche per la compressione dei cammini molto appropriate per l'operazione di find. L'unione delle due euristiche consente di ottenere algoritmi molto veloci.
Nel decimo capitolo sono affrontate alcune fra le più importanti tecniche algoritmiche. Esse sono: divide et impera, la programmazione dinamica, e il metodo goloso o greedy. Alcune delle tecniche descritte in questo capitolo saranno riprese nel proseguo del libro.
L'undicesimo capitolo si occupa dei problemi riguardanti le stringhe. I problemi per i quali sono proposti algoritmi risolutivi sono il calcolo della distanza tra due stringhe, la ricerca delle occorrenze di una stringa all'interno di un testo, e la ricerca di opportune sottostringhe all'interno di una data stringa.
In questo capitolo è introdotta la nozione di grafo e sono illustrate due modalità di rappresentazione degli stessi mediante liste di adiacenza e matrici di adiacenza. Inoltre sono descritte le tecniche di visita, analizzando sia la visita in profondità che quella in ampiezza. Tale capitolo è propedeutico per i successivi nei quali verranno analizzati specifici problemi legati ai grafi.
Nel capitolo tredici è affrontato il problema del minimo albero ricoprente in un grafo non orientato. Il problema è affrontato mediante un'applicazione di una tecnica golosa che prevede l'utilizzo della regola del taglio e della regola del ciclo. A seguito della descrizione fatta nella prima parte del capitolo, il seguito dimostra la correttezza di alcuni dei più noti algoritmi per il calcolo del minimo albero ricoprente.
Nel quattordicesimo capitolo è affrontato il problema di trovare i cammini minimi in un grafo orientato. Nella prima parte del capitolo vengono fornite delle nozioni generali sul problema. Nella seconda parte dello stesso, invece, sono descritti alcuni algoritmi per la risoluziona del problema. Gli algoritmi descritti sono quelli di Bellman e Ford, di Dijkstra, e infine Floyd e Warshall.
In questo capitolo viene affrontato un problema complementare al problema dei cammini minimi, ossia il problema del flusso. Tale problema studia come inviare la massima quantità di flusso da una sorgente ad una destinazione non eccedendo la capicità degli archi. Due approcci sono descritti per la risoluzione del problema: il metodo delle reti residue e il metodo dei cammini aumentati.
In questo capitolo è affrontato il concetto di classe di complessità. A seguito di una classificazione insiemistica delle classi di complessità, la trattazione si sofferma sulla classe NP dei problemi risolubili in tempo polinomiale non deterministico.
Nell'appendice sono brevemente illustrati alcuni concetti(soprattutto matematici) utili per la comprensione del testo.
In conclusione, il libro affronta in modo completo le problematiche relative all'ottimizzazione degli algoritmi e allo studio delle strutture dati. Molti dei problemi affrontati sono importanti per le persone che lavorano nel mondo dell'informatica. Infatti, saper distinguere tra un algoritmo efficiente ed uno con scarse prestazioni e ciò che distingue il buon software dal software di bassa lega.
Il libro, inoltre, è un ottimo supporto anche per i corsi di laurea universitari poichè spiega ed illustra le problematiche in maniera molto dettagliata ed analitica. Inoltre, gli esercizi proposti ad ogni fine capitolo permettono al lettore di fissare i concetti espressi nello stesso.
Il libro è quindi consigliato in un contesto di corsi universitari, ma altresi che è molto utile a tutti coloro che vogliano approfondire una tra le tematiche più importanti dell'ingegneria del software.
Di seguito è riportata la lista dei capitoli presenti nel libro appena descritto:
