Prefazione

1 Un’introduzione informale agli algoritmi
1.1 I numeri di Fibonacci
1.2 Un algoritmo numerico
1.3 Un algoritmo ricorsivo
1.4 Un algoritmo iterativo
1.5 Occupazione di memoria
1.6 Notazione asintotica
1.7 Un algoritmo basato su potenze ricorsive
1.8 Problemi
1.9 Sommario
1.10 Note bibliografiche

2 Modelli di calcolo e metodologie di analisi 23
2.1 Modelli di calcolo
2.1.1 Criteri di costo uniforme e logaritmico
2.2 La notazione asintotica O, Ω, Θ
2.3 Delimitazioni inferiori e superiori
2.4 Metodi di analisi
2.4.1 Caso peggiore, caso migliore e caso medio
2.4.2 Analisi della ricerca sequenziale
2.4.3 Un algoritmo piu' veloce: la ricerca binaria
2.5 Analisi di algoritmi ricorsivi
2.5.1 Metodo dell’iterazione
2.5.2 Metodo della sostituzione
2.5.3 Il teorema fondamentale delle ricorrenze
2.5.4 Altre tecniche utili
2.6 Analisi di algoritmi randomizzati
2.7 * Analisi ammortizzata
2.7.1 Il metodo dei crediti
2.7.2 Il metodo del potenziale
2.8 * Modelli evoluti: la gerarchia di memoria
2.9 Problemi
2.10 Sommario
2.11 Note bibliografiche

3 Strutture dati elementari
3.1 Tecniche per rappresentare collezioni di oggetti
3.1.1 Strutture indicizzate: array
3.1.2 Strutture collegate: record e puntatori
3.2 Pile e code
3.3 Alberi
3.3.1 Rappresentazioni indicizzate
3.3.2 Rappresentazioni collegate
3.3.3 Visite di alberi
3.4 Problemi
3.5 Sommario
3.6 Note bibliografiche

4 Ordinamento
4.1 Una delimitazione inferiore al numero di confronti
4.1.1 Alberi di decisione
4.1.2 La delimitazione inferiore nel caso peggiore
4.2 Ordinare in tempo quadratico
4.2.1 Ordinamenti incrementali
4.2.2 Ordinamento a bolle
4.3 Heapsort
4.3.1 Struttura dati heap
4.3.2 Ordinare in loco mediante heap
4.4 Mergesort
4.5 Quicksort
4.5.1 Analisi di Quicksort
4.6 Bucketsort
4.7 Radixsort
4.8 Problemi
4.9 Sommario
4.10 Note bibliografiche

5 Selezione e statistiche di ordine
5.1 Selezione per piccoli valori di k
5.1.1 Ricerca del secondo minimo
5.1.2 L’algoritmo Heapselect
5.2 Calcolo randomizzato del mediano
5.3 Calcolo deterministico del mediano
5.3.1 Mediano dei mediani
5.4 Problemi
5.5 Sommario
5.6 Note bibliografiche

6 Alberi di ricerca
6.1 Alberi binari di ricerca
6.2 Alberi AVL
6.2.1 Altezza di un albero AVL
6.2.2 Ribilanciamento tramite rotazioni
6.2.3 Modifiche del dizionario
6.3 * Alberi auto-aggiustanti
6.3.1 L’operazione splay
6.3.2 Analisi basata sul potenziale
6.4 Alberi 2-3
6.4.1 Fusioni e separazioni di nodi
6.5 B-alberi
6.5.1 Definizioni e proprieta'
6.5.2 Inserimenti e cancellazioni di chiavi
6.6 Alberi 2-3-4 ed alberi red-black
6.7 Problemi
6.8 Sommario
6.9 Note bibliografiche

7 Tavole hash
7.1 Tavole ad accesso diretto
7.2 Tavole hash
7.2.1 Definizione di funzioni hash
7.3 Risoluzione delle collisioni
7.3.1 Liste di collisione
7.3.2 Indirizzamento aperto
7.4 Problemi
7.5 Sommario
7.6 Note bibliografiche

8 Code con priorita'
187
8.1 d-heap
8.2 Heap binomiali
8.3 * Heap di Fibonacci
8.3.1 Heap binomiali rilassati
8.3.2 Heap di Fibonacci
8.4 Problemi
8.5 Sommario
8.6 Note bibliografiche

9 Union-find
9.1 Approcci elementari al problema union-find
9.1.1 Algoritmi di tipo QuickFind
9.1.2 Algoritmi di tipo QuickUnion
9.2 Euristiche di bilanciamento nell’operazione union
9.2.1 Bilanciamento per algoritmi di tipo QuickFind
9.2.2 Bilanciamento per algoritmi di tipo QuickUnion
9.3 Euristiche di compressione nell’operazione find
9.4 * Union-find con bilanciamento e compressione
9.4.1 Proprieta' del rank
9.4.2 Un’analisi preliminare
9.4.3 Un’analisi piu' raffinata
9.5 Problemi
9.6 Sommario
9.7 Note bibliografiche

10 Tecniche algoritmiche
10.1 Tecnica divide et impera
10.1.1 Moltiplicazione di interi di grandezza arbitraria
10.1.2 Moltiplicazione tra matrici
10.2 Programmazione dinamica
10.2.1 La distanza tra due stringhe di caratteri
10.2.2 Associativita' del prodotto tra matrici
10.3 Tecnica golosa (o greedy)
10.3.1 Il distributore automatico di resto
10.3.2 Problemi di sequenziamento
10.4 Problemi
10.5 Sommario
10.6 Note bibliografiche

11 Grafi e visite di grafi
11.1 Definizioni preliminari sui grafi
11.2 Strutture dati per rappresentare grafi
11.3 Visite di grafi
11.3.1 Visita in ampiezza
11.3.2 Visita in profondita'
11.3.3 Visite in ampiezza ed in profondita' su grafi orientati
11.4 Componenti connesse di un grafo non orientato
11.5 Componenti fortemente connesse di un grafo orientato
11.6 Problemi
11.7 Sommario
11.8 Note bibliografiche

12 Minimo albero ricoprente
12.1 Proprieta' dei minimi alberi ricoprenti
12.2 Algoritmo di Kruskal
12.2.1 Implementazione mediante union-find
12.3 Algoritmo di Prim
12.3.1 Implementazione mediante code con priorita'
12.4 Algoritmo di Bor°uvka
12.5 Problemi
12.6 Sommario
12.7 Note bibliografiche

13 Cammini minimi
13.1 Cammini minimi e distanze in un grafo
13.1.1 Cammini minimi in grafi con cicli
13.1.2 Distanza fra vertici in un grafo
13.1.3 Costruire cammini minimi a partire da distanze
13.1.4 Alberi di cammini minimi
13.1.5 Varianti del problema dei cammini minimi
13.2 La tecnica del rilassamento
13.3 Algoritmo di Bellman e Ford
13.4 Algoritmo per grafi diretti aciclici
13.4.1 Ordinamento topologico
13.4.2 Rilassamento in ordine topologico
13.5 Algoritmo di Dijkstra
13.5.1 Implementazione mediante code con priorita'
13.6 Algoritmo di Floyd e Warshall
13.7 Problemi
13.8 Sommario
13.9 Note bibliografiche

14 Flusso 347
14.1 Reti di flusso
14.2 Metodo delle reti residue
14.2.1 Versione ricorsiva del metodo delle reti residue
14.3 Metodo dei cammini aumentanti
14.4 Algoritmo di Ford e Fulkerson
14.5 Algoritmo di Edmonds e Karp
14.6 Flusso massimo e taglio minimo
14.7 Problemi
14.8 Sommario
14.9 Note bibliografiche

15 Algoritmi geometrici
15.1 Inviluppo convesso
15.1.1 Un approccio “induttivo”
15.1.2 Il metodo dell’incartamento dei regali
15.1.3 La scansione di Graham
15.2 Localizzazione di punti in suddivisioni planari
15.2.1 La sequenza di triangolazioni
15.2.2 La struttura dati
15.2.3 L’algoritmo di interrogazione
15.3 Problemi di ricerca multidimensionali
15.3.1 Il caso di una dimensione
15.3.2 Il range tree
15.3.3 Il priority search tree
15.4 Intersezione di rettangoli
15.4.1 Il metodo di plane sweep
15.4.2 L’albero degli intervalli
15.5 Problemi
15.6 Sommario
15.7 Note bibliografiche

16 Teoria della NP-completezza
16.1 Complessita' di problemi decisionali
16.1.1 Decidere, ricercare, ottimizzare
16.1.2 Classi di complessita'
16.2 La classe NP
16.2.1 Non determinismo
16.2.2 Uno sguardo alla gerarchia
16.3 Problemi NP-completi
16.3.1 Riducibilita' polinomiale
16.3.2 Il teorema di Cook
16.3.3 Dimostrazioni di NP-completezza
16.4 Algoritmi di approssimazione
16.5 Problemi
16.6 Sommario
16.7 Note bibliografiche

17 Appendice
17.1 Logaritmi e numero di Nepero
17.2 Serie e successioni
17.2.1 Serie aritmetica e geometrica
17.2.2 Calcolo di somme per integrazione
17.2.3 La successione di Fibonacci
17.3 Elementi di calcolo della probabilita'
17.4 Elementi di calcolo combinatorio
17.5 Elementi di teoria dei grafi
17.5.1 Alberi
17.5.2 Grafi planari
17.6 Note bibliografiche