|
|
CONSIGLIATO DA LIBRINFORMATICA
Strutture di dati e algoritmi - Progettazione, analisi e visualizzazione
|
| Editore | Pearson Education Italia |
| Autore | Crescenzi Pierluigi ; Gambosi Giorgio ; Grossi Roberto |
| Pagine | 363 |
| Volumi | 1 |
| Livello | Introduttivo-Intermedio |
| Lingua | Italiano |
| Data pubblicazione | 06 - 2006 |
| ISBN | 8871922735 |
|
|
| Prezzo di copertina |
| Euro 27,00 |
|
Prefazione
1 Problemi computazionali
1.1 Indecidibilità di problemi computazionali
1.2 Trattabilità di problemi computazionali
1.2.1 Rappresentazione e dimensione dei dati
1.2.2 Algoritmi polinominali ed esponenziali
1.3 Problemi NP- completi
1.4 Modello RAM e complessità computazionale
2 Sequenze: array
2.1 Sequenze lineari
2.1.1 Modalità di accesso
2.1.2 Allocazione della memoria
2.1.3 Array di dimensione variabile
2.2 Opus libri: scheduling della CPU
2.2.1 Ordinamento per selezione
2.2.2 Ordinamento per inserimento
2.3 Complessità di problemi computazionali
2.3.1 Limiti superiori e inferiori
2.4 Ricerca di una chiave
2.4.1 Ricerca binaria
2.4.2 Complessità della ricerca per confronti
2.5 Ricorsione e paradigma del divide et impera
2.5.1 Equazione di ricorrenza e teorema fondamentale
2.5.2 Moltiplicazione veloce di due numeri interi
2.5.3 Ordinamento per fusione
2.5.4 Ordinamento e selezione per distribuzione
2.5.5 Alternativa al teorema fondamentale delle ricorrenze
2.6 Opus libri: grafica e moltiplicazione di matrici
2.6.1 Moltiplicazione veloce di due matrici
2.6.2 Sequenza ottima di moltiplicazioni e paradigma della programmazione dinamica
2.7 Paradigma della programmazione dinamica
2.7.1 Sicurezza dei sistemi e sotto-sequenza comune più lunga
2.7.2 Sistemi di backup e partizione di un insieme di interi
2.7.3 Problema della bisaccia
2.7.4 Pseudo-polinomialità e programmazione dinamica
3 Sequenze: liste
3.1 Liste
3.1.1 Ricerca, inserimento e cancellazione
3.1.2 Liste doppie e liste circolari
3.2 Opus libri: problema dei matrimoni stabili
3.2.1 Strutture di dati utilizzate
3.2.2 Implementazione dell’algoritmo
3.3 Liste randomizzate
3.4 Opus libri: gestione di liste ammortizzate e ad auto-organizzazione
3.4.1 Unione e appartenenza a liste disgiunte
3.4.2 Liste ad auto-organizzazione
3.4.3 Tecniche di analisi ammortizzata
4 Alberi
4.1 Alberi binari
4.1.1 Algoritmi ricorsivi su alberi binari
4.1.2 Inserimento e cancellazione
4.2 Opus libri: minimo antenato comune
4.2.1 Trasformazione da antenati comuni a minimi in intervalli
4.2.2 Soluzione efficiente in spazio
4.3 Visita per ampiezza e rappresentazione di alberi
4.3.1 Rappresentazione implicita di alberi binari
4.3.2 Rappresentazione succinta per ampiezza
4.3.3 Implementazione di rank e select
4.3.4 Limite inferiore allo spazio delle rappresentazioni succinte
4.4 Alberi cardinali e ordinali, e parentesi bilanciate
4.4.1 Rappresentazione succinta mediante parentesi bilanciate
5 Dizionari
5.1 Dizionari
5.2 Liste e dizionari
5.3 Opus libri: funzioni hash e peer-to-peer
5.3.1 Tabelle hash: liste di trabocco
5.3.2 Tabelle hash: indirizzamento aperto
5.4 Opus libri: kernel Linux e alberi binari di ricerca
5.4.1 Alberi binari di ricerca
5.4.2 AVL: alberi binari di ricerca bilanciati
5.5 Opus libri: basi dati e B-alberi
5.6 Opus libri: liste invertite e trie
5.6.1 Trie o alberi digitali di ricerca
5.6.2 Trie compatti e alberi suffissi
6 Grafi
6.1 Grafi
6.1.1 Alcuni problemi su grafi
6.1.2 Rappresentazione di grafi
6.1.3 Cammini minimi, chiusura transitiva e prodotto di matrici
6.2 Opus libri: colorazione di grafi e algoritmi golosi
6.2.1 Il problema dell’assegnazione delle lunghezze d’onda
6.2.2 Grafi a intervalli
6.2.3 Colorazione di grafi a intervalli
6.2.4 Massimo insieme indipendente in un grafico a intervalli
6.2.5 Paradigma dell’algoritmo goloso
6.3 Grafi casuali e modelli di reti complesse
6.3.1 Grafi casuali alla Erdös-Rényi
6.3.2 Grafi casuali con effetto di piccolo mondo
6.3.3 Grafi casuali invarianti di scala
6.4 Opus libri: motori di ricerca e classificazione
6.4.1 Significatività delle pagine con PageRank
6.4.2 Significatività delle pagine con HITS
6.4.3 Convergenza del calcolo iterativo di PageRank e HTIS
7 Pile e code
7.1 Pile
7.1.1 Implementazione di una pila mediante un array
7.1.2 Implementazione di una pila mediante una lista
7.2 Opus libri: Postscript e notazione postfissa
7.3 Code
7.3.1 Implementazione di una coda mediante un array
7.3.2 Implementazione di una coda mediante una lista
7.4 Opus libri: Web crawler e visite di grafi
7.4.1 Visita in ampiezza di un grafo
7.4.2 Visita in profondità di un grafo
7.5 Applicazioni delle visite di grafi
7.5.1 Grafi diretti aciclici e ordinamento topologico
7.5.2 Componenti (fortemente) connesse
8 Code con priorità
8.1 Code con priorità
8.2 Heap
8.2.1 Implementazione di uno heap implicito
8.2.2 Insolito caso di DecreaseKey
8.2.3 Costruzione di heap e ordinamento
8.3 Opus libri: routing su Internet e cammini minimi
8.3.1 Problema della ricerca di cammini minimi su grafi
8.3.2 Cammini minimi in grafi con pesi positivi
8.3.3 Cammini minimi in grafi pesati generali
8.4 Opus libri: data mining e minimi alberi ricoprenti
8.4.1 Problema della ricerca del minimo albero di ricoprimento
8.4.2 Algoritmo di Kruskal
8.4.3 Algoritmo di Jarnìk-Prim
9 NP-completezza
9.1 Problemi NP-completi
9.1.1 Classi P e NP
9.1.2 Riducibilità polinomiale
9.1.3 Problemi NP- completi
9.1.4 Teorema di Cook-Levin
9.1.5 Problemi di ottimizzazione
9.2 Esempi e tecniche di NP-completezza
9.2.1 Tecnica di sostituzione locale
9.2.2 Tecnica di progettazione di componenti
9.2.3 Tecnica di similitudine
9.2.4 Tecnica di restrizione
9.2.5 Come dimostrare risultati di NP-completezza
9.3 Algoritmi di approssimazione
9.4 Opus libri: il problema del commesso viaggiatore
9.4.1 Problema del commesso viaggiatore su istanze metriche
9.4.2 Paradigma della ricerca locale
A Notazioni
B Teorema delle ricorrenze
Indice analitico
|
|
|
|
