| INDICE: |
| 11 | | Prologo |
| 29 | Parte Prima | Strutture informative |
| 31 | 0. | Tipi di dato e Strutture di dati |
| 31 | 0.1. | Strutture di dati: sèecifica e realizzazione |
| 35 | 0.2. | Rappresentazione in memoria |
| 38 | 1. | Liste |
| 41 | 1.1. | Realizzazione con puntatori |
| 46 | 1.2. | Realizzazione con cursori |
| 49 | 1.3. | Realizzazione con doppi puntatori |
| 51 | 2. | Pile |
| 53 | 2.1. | Realizzazione con vettore |
| 55 | 3. | Pile e prrocedure ricorsive |
| 63 | 4. | Code |
| 64 | 4.1. | Realizzazione efficiente con puntatori |
| 66 | 4.2. | Realizzaziione con vettore circolare |
| 68 | 5. | Alberi ordinati |
| 76 | 5.1. | Visita di alberi |
| 79 | 5.2. | Realizazione con vettore dei padri |
| 80 | 5.3. | Realizzazione con liste dei figli |
| 82 | 5.4. | Realizzazione con lista primofiglio/fratello |
| 84 | 6. | Alberi binari |
| 90 | 7. | Insiemi |
| 92 | 7.1. | Realizzazione con vettore booleano |
| 94 | 7.2. | Realizzazione con liste non ordinate |
| 96 | 7.3. | Realizzazione con liste ordinate |
| 98 | 8.1. | Realizzazione con vettore ordinato |
| 101 | 8.2. | Realizzazione con tabella hash |
| 103 | 8.2.1. | Funzioni hash |
| 105 | 8.2.2. | Metodi di scansione |
| 108 | 8.2.3. | Realizzazione Pascal della scansione lineare |
| 109 | 8.2.4. | Realizzazione Pascal della scansione esterna |
| 109 | 8.2.5. | Complessità media |
| 113 | 9. | Code con priorità |
| 113 | 9.1. | Realizzazione con liste |
| 114 | 9.2. | Realizzazione con alberi binari |
| 116 | 9.3. | Realizzazione con heap |
| 119 | 10. | Alberi bilanciati di ricerca |
| 120 | 10.1. | Alberi AVL |
| 125 | 10.2. | Alberi 2-3-4 |
| 130 | 10.3. | Alberi bilanciati e unione di insiemi disgiunti |
| 135 | 11. | Grafi |
| 141 | 11.1. | Realizzazione con matrice di adiacenza |
| 141 | 11.2. | realizzazione con vettori di adiacenza |
| 143 | 11.3. | esplorazione di un grafo |
| 145 | 11.3.1. | Componenti connesse |
| 147 | 11.3.2. | Alberi di copertura DFS |
| 151 | Parte Seconda | Progetto e analisi di algoritmi |
| 153 | 12. | Strutture di dati e progetto di algoritmi |
| 154 | 12.1. | Cammini minimi |
| 158 | 12.1.1. | Algoritmo di Dijkstra |
| 159 | 12.1.2. | Algoritmo di Johnson |
| 163 | 12.1.3. | Algoritmo di Bellman-Ford-Moore |
| 163 | 12.1.4. | Utilizzo di una pila |
| 166 | 13. | Divide et impera |
| 167 | 13.1. | Mergesort |
| 170 | 13.2. | Quicksort |
| 177 | 14. | Backtrack |
| 177 | 14.1. | Inviluppo convesso |
| 179 | 14.1.1. | Algoritmo di Graham |
| 182 | 14.2. | String Matching |
| 184 | 14.2.1. | Algoritmo di Knuth-Morris-Pratt |
| 188 | 15. | Greedy |
| 189 | 15.1. | Minimo albero di copertura |
| 192 | 15.2. | Scheduling di programmi |
| 194 | 16. | Programmazione dinamica |
| 195 | 16.1. | String matching approssimato |
| 198 | 16.2. | Cammini minimi tra tutte le coppie |
| 201 | 17. | Ricerca locale |
| 204 | 17.1. | Shellsort |
| 210 | 18. | Analisi di algoritmi ricorsivi |
| 210 | 18.1. | Relazioni di ricorrenza con partizione bilanciata |
| 212 | 18.1.1. | Moltiplicazione di polinomi |
| 215 | 18.1.2. | Moltiplicazione di matrici |
| 217 | 18.2. | Relazioni di ricorrenza lineari di ordine costante |
| 219 | 18.2.1. | Numeri di Fibonacci |
| 221 | 18.3. | Analisi per tentativi |
| 223 | Parte Terza | Complessità e decidibilità |
| 225 | 19. | Non determinismo ed enumerazione |
| 229 | 19.1. | Certificati polinomiali |
| 229 | 19.2. | Non determinismo |
| 233 | 19.3. | Enumerazione |
| 236 | 20. | Le classi P e NP |
| 238 | 20.1. | Riducibilità polinomiale |
| 240 | 20.2. | Teorema di Cook-Levin |
| 243 | 21. | Problemi NP-completi |
| 252 | 22. | Gerarchia di complessità |
| 252 | 22.1. | La classe co-NP |
| 254 | 22.2. | La classe P-SPAZIO |
| 255 | 22.3. | Le classi EXp e NEXP |
| 257 | 22.4. | Le classi EXP-SPAZIO ed E |
| 257 | 22.5. | Problemi C-completi |
| 259 | 23. | Algoritmi pseudo-polinomiali |
| 264 | 24. | Algoritmi di approssimazione |
| 264 | 24.1. | Approssimazione assoluta |
| 271 | 24.2. | ε-approssimazione |
| 275 | 25. | Branch-&-Bound |
| 281 | 26. | Euristiche |
| 287 | 27. | Indecidibilità e universalità |
| 288 | 27.1. | Il problema della terminazione |
| 292 | 27.2. | Gerarchia di indecidibilità |
| 296 | 28. | Macchine di Turing |
| 296 | 28.1. | L'argomento di Turing |
| 301 | 28.2. | La tesi di Church-Turing |
| 302 | 28.3. | Generalizzazioni e semplificazioni |
| 304 | 28.4. | Riduzioni mediante macchine di Turing |
| 310 | 29. | Algoritmi paralleli |
| 311 | 29.1. | Memoria condivisa |
| 312 | 29.1.1. | Somme parziali |
| 313 | 29.1.2. | Ordinamento |
| 314 | 29.1.3. | Cammini minimi |
| 316 | 29.2. | La Tesi della Computazione Parallela |
| 319 | | Epilogo |
| 325 | | Esercizi |
| 337 | | Bibliografia |
| 339 | | _ |
| 341 | | Errata Corrige |
