| 0.01 | | [frontespizio] |
| 0.02 | | [colophon] |
| 0.03 | | Sommario |
| 0.11 | | Prefazione all'edizione italiana [ di Alan Albert Bertossi ] |
| 0.15 | | Nota alla seconda edizione [ di Mauro Torelli ET Carlo Mereghetti ] |
| 0.17 | | Prefazione |
| 0.20 | | __ |
| 0.20 | | ___ |
| 1 | 1. | Introduzione |
| 1 | 1.1 | Algoritmi |
| 5 | 1.2 | Analisi di algoritmi |
| 10 | 1.3 | Progetto di algoritmi |
| 14 | 1.4 | Riepilogo |
| 18 | Parte prima. | Fondamenti di matematica |
| 19 | | Introduzione |
| 21 | 2. | Ordine di grandezza delle funzioni |
| 21 | 2.1 | Notazione asintotica |
| 29 | 2.2 | Notazioni standard e funzioni comuni |
| 39 | 3. | Sommatorie |
| 39 | 3.1 | Formule e proprietà sulle sommatorie |
| 43 | 3.2 | Definizione di limitazioni sulle sommatorie |
| 51 | 4. | Ricorrenze |
| 52 | 4.1 | Il metodo di sostituzione |
| 55 | 4.2 | Il metodo iterativo |
| 58 | 4.3 | Il metodo principale |
| 61 | *4.4 | Dimostrazione del teorema principale |
| 73 | 5. | Insiemi e affini |
| 73 | 5.1 | Insiemi |
| 77 | 5.2 | Relazioni |
| 79 | 5.3 | Funzioni |
| 81 | 5.4 | Grafi |
| 85 | 5.5 | Alberi |
| 93 | 6. | Calcolo combinatorio e delle probabilità |
| 93 | 6.1 | Calcolo combinatorio |
| 98 | 6.2 | Calcolo delle probabilità |
| 103 | 6.3 | Variabili casuali discrete |
| 107 | 6.4 | Distribuzione geometrica e distribuzione binomiale |
| 113 | * 6.5 | Code della distribuzione binomiale |
| 118 | 6.6 | Analisi probabilistica |
| 128 | Parte seconda. | Ordinamento e selezione |
| 129 | | Introduzione |
| 133 | 7. | Heapsort |
| 133 | 7.1 | Heap |
| 135 | 7.2 | Mantenimento della proprietà delllo heap |
| 137 | 7.3 | Costruzione di uno heap |
| 139 | 7.4 | L'algoritmo heapsort |
| 141 | 7.5 | Code con priorità |
| 145 | 8. | Quicksort |
| 145 | 8.1 | Descrizione del quicksort |
| 147 | 8.2 | Prestazioni del quicksort |
| 152 | 8.3 | Versione randomizzata del quicksort |
| 154 | 8.4 | Analisi del quicksort |
| 163 | 9. | Ordinamento in tempo lineare |
| 163 | 9.1 | Limiti inferiori per l'ordinamento |
| 166 | 9.2 | Counting sort |
| 168 | 9.3 | Radix sort |
| 170 | 9.4 | Bucket sort |
| 175 | 10. | Mediano e selezione |
| 175 | 10.1 | Minimo e massimo |
| 177 | 10.2 | Selezione con tempo medio lineare |
| 179 | 10.3 | Selezione in tempo lineare nel caso peggiore |
| 184 | Parte terza. | Strutture dati |
| 185 | | Introduzione |
| 189 | 11. | Strutture di dati fondamentali |
| 189 | 11.1 | Pile e Code |
| 192 | 11.2 | Liste concatenate |
| 197 | 11.3 | Realizzazione di puntatori e oggetti |
| 201 | 11.4 | Rappresentazione di alberi radicati |
| 207 | 12. | Tabelle hash |
| 207 | 12.1 | Tabelle ad indirizzamento diretto |
| 209 | 12.2 | Tabelle hash |
| 213 | 12.3 | Funzioni hash |
| 219 | 12.4 | Indirizzamento |
| 229 | 13. | Alberi binari di ricerca |
| 229 | 13.1 | Che cos'è un albero binario di ricerca? |
| 231 | 13.2 | Interrogazioni su un albero binario di ricerca |
| 235 | 13.3 | Inserzione e cancellazione |
| 238 | *13.4 | Alberi binari di ricercaa costruiti in modo casuale |
| 247 | 14. | RB-alberi |
| 247 | 14.1 | Proprietà degli RB-alberi |
| 249 | 14.2 | Rotazioni |
| 251 | 14.3 | Inserzione |
| 255 | 14.4 | Cancellazione |
| 263 | 15. | Estensione di strutture di dati |
| 263 | 15.1 | Selezione su un insieme dinamico |
| 268 | 15.2 | Come estendere una struttura di dati |
| 271 | 15.3 | Alberi di intervalli |
| 278 | Parte quarta. | Tecniche evolute per il progetto e l'analisi di algoritmi |
| 279 | | Introduzione |
| 283 | 16. | Programmazione dinamica |
| 284 | 16.1 | Prodotto di una sequenza di matrici |
| 291 | 16.2 | Elementi di programmazione dinamica |
| 296 | 16.3 | Il problema della più lunga sottosequenza comune |
| 302 | 16.4 | Triangolazione ottima di un poligono |
| 311 | 17 | Algoritmi greedy |
| 312 | 17.1 | Selezione di attività |
| 315 | 17.2 | Strategia greedy: concetti di base |
| 319 | 17.3 | Codici di Hufman |
| 326 | *17.4 | Fondammenti teorici dei metodi greedy |
| 332 | *17.5 | Un problema di scheduling |
| 337 | 18. | Analisi ammortizzata |
| 338 | 18.1 | Il metodo degli aggregati |
| 342 | 18.2 | Il metodo degli accantonamenti |
| 344 | 18.3 | Il metodo del potenziale |
| 348 | 18.4 | Tabelle dinamiche |
| 360 | Parte quinta. | Strutture di dati evolute |
| 361 | | Introduzione |
| 363 | 19. | B-alberi |
| 366 | 19.1 | Definizione dei B-alberi |
| 369 | 19.2 | Operazioni di base sui B-alberi |
| 376 | 19.3 | Eliminazione di una chiave da un B-albero |
| 383 | 20. | Heap binomiali |
| 384 | 20.1 | Alberi binomiali e heap binomiali |
| 389 | 20.2 | Opeerazioni su heap binomiali |
| 403 | 21. | Gli heap di Fibonacci |
| 404 | 21.1 | La struttura degli heap di Fibonacci |
| 406 | 21.2 | Operazioni che fondono heap |
| 413 | 21.3 | Decremento di una chiave ed eliminazione di un nodo |
| 417 | 21.4 | Limitazione del grado massimo |
| 423 | 22. | Strutture di dati per insiemi disgiunti |
| 423 | 22.1 | Operazioni su insiemi disgiunti |
| 426 | 22.2 | Rappresentazione a lista concatenata di insiemi disgiunti |
| 429 | 22.3 | Foreste di insiemi disgiunti |
| 432 | *22.4 | Analisi dell'unione per rango con compressione dei cammini |
| 444 | Parte sesta. | Algoritmi su grafi |
| 445 | | Introduzione |
| 447 | 23. | Algoritmi elementari su grafi |
| 447 | 23.1 | Rappresentazione di grafi |
| 450 | 23.2 | Visita in ampiezza |
| 458 | 23.3 | Visita in profondità |
| 465 | 23.4 | Ordinamento topologico |
| 468 | 23.5 | Componenti fortemente connesse |
| 477 | 24. | Alberi di copertura minimi |
| 478 | 24.1 | Costruzione di un albero di copertura minimo |
| 482 | 24.2 | Gli algoritmi di Kruskal e di Prim |
| 491 | 25. | Cammini minimi con sorgente singola |
| 495 | 25.1 | Cammini minimi e rilassamennto |
| 503 | 25.2 | Algoritmo di Dijkstra |
| 507 | 25.3 | Algoritmo di Bellman-Ford |
| 511 | 25.4 | Cammini minimi con sorgente singola in grafi orientati aciclici |
| 513 | 25.5 | Vincoli di differenza e cammini minimi |
| 525 | 26. | Cammini minimi tra tutte le coppie |
| 527 | 26.1 | Cammini minimi e moltiplicazione di matrici |
| 532 | 26.2 | Algoritmo di Floyd-Warshall |
| 539 | 26.3 | Algoritmo di Johnson per grafi sparsi |
| 543 | *26.4 | Un contesto generale in cui risolvere problemi di cammini in grafi orientati |
| 551 | 27. | Flusso massimo |
| 552 | 27.1 | Reti di flusso |
| 558 | 27.2 | Il metodo di Ford-Fulkerson |
| 570 | 27.3 | Abbinamento massimo in un grafo bipartito |
| 574 | *27.4 | Algoritmi di preflusso |
| 583 | *27.5 | Algoritmo lift-to-front |
| 598 | Parte settima. | Complementi ed estensioni |
| 599 | | Introduzione |
| 601 | 28. | Reti di confrontatori |
| 601 | 28.1 | Reti di confrontatori |
| 605 | 28.2 | Il principio zero-uno |
| 608 | 28.3 | Una rete di ordinamento bitonico |
| 611 | 28.4 | Una rete di fusione |
| 613 | 28.5 | Una rete di ordinamento |
| 619 | 29. | Circuiti aritmetici |
| 619 | 29.1 | Circuiti combinatori |
| 624 | 29.2 | Addizionatori |
| 634 | 29.3 | Circuiti moltiplicatori |
| 641 | 29.4 | Circuiti sequenziali |
| 651 | 30. | Algoritmi per calcolatori paralleli |
| 654 | 30.1 | Salto dei puntatori |
| 663 | 30.2 | Confronto tra algoritmi EREW e algoritmi CRCW |
| 670 | 30.3 | Il Teorema di Brent e l'efficienza rispetto al lavoro |
| 674 | *30.4 | Calcolo parallelo dei prefissi efficiente rispetto al lavoro |
| 679 | 30.5 | Risoluzione deterministica dei conflitti |
| 689 | 31. | Operatori sulle matrici |
| 689 | 31.1 | Proprietà delle matrici |
| 697 | 31.2 | Algoritmo di Strassen per la moltiplicazione tra matrici |
| 704 | *31.3 | Sistemi algebrici di numeri e moltiplicazione tra matrici booleane |
| 708 | 31.4 | Risoluzione di sistemi di equazioni lineari |
| 720 | 31.5 | Inversione di matrici |
| 724 | 31.6 | Matrici simmetriche definite positive e metodo dei minimi quadrati |
| 735 | 32. | Polinomi e FFT |
| 737 | 32.1 | Rappresentazione di polinomi |
| 742 | 32.2 | DFT e FFT |
| 749 | 32.3 | Realizzazioni efficienti della FFT |
| 759 | 33. | Algoritmi di teoria dei numeri |
| 760 | 33.1 | Nozioni elementari di teoria dei numeri |
| 765 | 33.2 | Masimo comun divisore |
| 770 | 33.3 | Aritmetica modulare |
| 776 | 33.4 | Rissoluzione di equazioni lineari modulari |
| 779 | 33.5 | Il teorema cinese del resto |
| 781 | 33.6 | Potenze di un elemento |
| 785 | 33.7 | Crittografia a chiave pubblica RSA |
| 791 | *33.8 | Verifica di primalità |
| 797 | *33.9 | Scomposizione di interi in fattori primi |
| 805 | 34. | Corrispondenza tra stringhe |
| 806 | 34.1 | Algoritmo ingenuo di corrispondenza tra stringhe |
| 809 | 34.2 | Algoritmo Rabin-Karp |
| 813 | 34.3 | Corrispondenza tra stringhe con gli automi a stati finiti |
| 819 | 34.4 | Algoritmo Knuth-Morris-Pratt |
| 825 | *34.5 | Algoritmo Boyer-Moore |
| 835 | 35. | Geometria computazionale |
| 835 | 35.1 | Proprietà dei segmenti |
| 840 | 35.2 | Verifica dell'intersezione di una coppia qualsiasi di segmenti |
| 846 | 35.3 | Calcolo dell'inviluppo convesso |
| 854 | 35.4 | Ricerca della coppia di punti più vicini |
| 863 | 36. | Problemi NP-completi |
| 864 | 36.1 | Tempo polinomiale |
| 870 | 36.2 | Verifica in tempo polinomiale |
| 875 | 36.3 | NP-completezza e riducibilità |
| 883 | 36.4 | Dimostrazioni di NP-completezza |
| 890 | 36.5 | Problemi NP-completi |
| 907 | 37. | Algoritmi approssimati |
| 909 | 37.1 | Il problema della copertura di vertici |
| 911 | 37.2 | Il problema del commesso viaggiatore |
| 916 | 37.3 | Il problema della copertura di un insieme |
| 920 | 37.4 | Il problema della somma di sottoinsieme |
| 927 | | Bibliografia |
| 937 | | Indice analitico |
| 956 | | _ |
| 956 | | ___ |
