|
 |
|
|
|
|
 |
|
La scheda del libro
Autori: C. Demetrescu, I. Finocchi, G. F. Italiano
Editore: McGraw-Hill
Prezzo: € 32,00
Caratteristiche: 485 pagine
ISBN: 9788838664687
Anno di edizione: 2008
Argomento: Informatica |
|
|
|
|
|
|
|
I capitoli del libro
Il libro Algoritmi e strutture dati, edito dalla casa editrice McGraw-Hill, è un libro indispensabile per tutti coloro che operano nel mondo dell'IT. Esso è 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.
Capitolo 1: Un'introduzione informale agli algoritmi
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.
Capitolo 2: Modelli di calcolo e metodologie di analisi
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.
Capitolo 3: Strutture dati elementari
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.
Capitolo 4: Ordinamento
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.
Capitolo 5: Selezione e statistiche di ordine
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.
Capitolo 6: Alberi di ricerca
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.
Capitolo 7: Tabelle hash
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.
Capitolo 8: Code con priorità
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.
Capitolo 9: Union-find
Il capitolo nono 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.
Capitolo 10: Tecniche algoritmiche
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.
Capitolo 11: Stringhe
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.
Capitolo 12: Grafi e visite di grafi
nel dodicesimo 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.
Capitolo 13: Minimo albero ricoprente
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.
Capitolo 14: Cammini minimi
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 risoluzione del problema. Gli algoritmi descritti sono quelli di Bellman e Ford, di Dijkstra, e infine Floyd e Warshall.
Capitolo 15: Flusso
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 capacità degli archi. Due approcci sono descritti per la risoluzione del problema: il metodo delle reti residue e il metodo dei cammini aumentati.
Capitolo 16: Teoria della NP-completezza
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.
Appendice
Nell'appendice sono brevemente illustrati alcuni concetti (soprattutto matematici) utili per la comprensione del testo.
Come acquistare il libro
Se desiderate acquistare questo libro, lo potete fare direttamente online da questo sito.
Conclusioni
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 alla fine di ogni capitolo permettono al lettore di fissare i concetti espressi nello stesso.
Il libro è quindi consigliato in un contesto di corsi universitari, ma è altresì utile a tutti coloro che vogliano approfondire una tra le tematiche più importanti dell'ingegneria del software.
 |
|
L’autore della recensione
Piergiorgio Faraglia è un Ingegnere informatico con specializzazione in Ingegneria del Software. Ha conseguito un master thesis presso la Linköping University lavorando inoltre presso un’azienda svedese. Dall’esperienza svedese ha ereditato soprattutto la grande passione per sistemi Linux/Unix. Le aree informatiche di suo maggior interesse sono quelle dei sistemi distribuiti, dei motori di ricerca semantici, e delle applicazioni in ambiente mobile. Attualmente sviluppa applicazioni utilizzando l’ambiente J2EE. |
Note sul copyright
Questa recensione è stata fornita con esplicito consenso dell'autore sotto licenza Creative Commons.
Leggi la licenza d'uso.
|
