Presentazione dell’edizione italiana
Prefazione

Capitolo 1 – Programmazioneorientata agli oggetti in Java

1.1 Elementi essenziali di Java
1.1.1 Dichiarazioni di variabili
1.1.2 Operatori
1.1.3 Enunciati decisionali
1.1.4 Cicli
1.1.5 Gestione delle eccezioni
1.2 Programmazione orientata agli oggetti in Java
1.2.1 Incapsulamento
1.2.2 Tipi di dati astratti
1.2.3 Ereditarietà
1.2.4 Polimorfismo
1.3 Ingresso e uscita
1.4 Java e i puntatori
1.5 I vettori in java.util
1.6 Strutture dati e programmazione orientata agli oggetti
1.7 Caso di studio: file ad accesso casuale
1.8 Esercizi
1.9 Esercizi di programmazione
Bibliografia

2.1 Complessità computazionale e asintotica
2.2 Notazione O-grande
2.3 Proprietà della notazione O-grande
2.4 Notazioni speciali 2.5 Possibili problemi
2.6 Esempi di complessità
2.7 Trovare la complessità asintotica: esempi
2.8 I casi migliore, medio e peggiore
2.9 Complessità ammortizzata
2.10 Esercizi
Bibliografia

3.1 Liste semplicemente concatenate
3.1.1 Inserimento
3.1.2 Eliminazione
3.1.3 Ricerca
3.2 Liste doppiamente concatenate
3.3 Liste circolari
3.4 Liste con salti
3.5 Liste auto-organizzanti
3.6 Tabelle sparse
3.7 Liste concatenate in java.util
3.8 Note conclusive
3.9 Caso di studio: una biblioteca
3.10 Esercizi
3.11 Esercizi di programmazione

4.1 Pile
4.1.1 Pile in java.util
4.2 Code
4.3 Code prioritarie
4.4 Caso di studio: uscire da un labirinto
4.5 Esercizi
4.6 Esercizi di programmazione
Bibliografia

5.1 Definizioni ricorsive
5.2 Invocazione dei metodi e realizzazione della ricorsione
5.3 Anatomia di un’invocazione ricorsiva
5.4 Ricorsione in coda
5.5 Ricorsione non in coda
5.6 Ricorsione indiretta
5.7 Ricorsione annidata
5.8 Ricorsione eccessiva
5.9 Backtracking
181 5.10 Considerazioni conclusive
5.11 Caso di studio: un interprete a discesa ricorsiva
5.12 Esercizi
5.13 Esercizi di programmazione
Bibliografia

6.1 Alberi, alberi binari e alberi binari di ricerca
6.2 Realizzare alberi binari
6.3 La ricerca in un albero binario di ricerca
6.4 Attraversamento di un albero
6.4.1 Attraversamento in ampiezza
6.4.2 Attraversamento in profondità
6.4.3 Attraversamento in profondità senza pila
6.5 Inserimento
6.6 Eliminazione
6.6.1 Eliminazione per fusione
6.6.2 Eliminazione per copiatura
6.7 Bilanciamento di un albero
6.7.1 L’algoritmo DSW
6.7.2 Alberi AVL
6.8 Alberi auto-adattativi
6.8.1 Alberi auto-ristrutturanti
6.8.2 Apertura
6.9 Heap
6.9.1 Heap come code prioritarie
6.9.2 Organizzare array come heap
6.10 Notazione polacca ed alberi di espressione
6.10.1 Operazioni su alberi di espressione
6.11 Caso di studio: calcolare la frequenza di parole
vi Sommario 6.12 Esercizi
6.13 Esercizi di programmazione
Bibliografia

7.1 La famiglia di alberi B
7.1.1 Alberi B
7.1.2 Alberi B*
7.1.3 Alberi B+
7.1.4 Alberi B+ con prefissi
7.1.5 Alberi di bit
7.1.6 Alberi R
7.1.7 Alberi 2-4
7.1.8 Insiemi in java.util
7.1.9 Mappe in java.util
7.2 Trie
7.3 Considerazioni conclusive
7.4 Caso di studio: verificatore ortografico
7.5 Esercizi
7.6 Esercizi di programmazione
Bibliografia

8.1 Rappresentazione dei grafi
8.2 Attraversamenti di grafi
8.3 Percorsi più brevi
8.3.1 Il problema del percorso più breve “da tutti a tutti”
8.4 Rilevazione di cicli
8.4.1 Il problema di trovare l’unione
8.5 Alberi di attraversamento
8.5.1 Algoritmo di Boruvka
8.5.2 Algoritmo di Kruskal
8.5.3 Algoritmo di Jarník-Prim
8.5.4 Il metodo di Dijkstra
8.6 Connettività
.380 8.6.1 Connettività nei grafi non orientati
8.6.2 Connettività nei grafi orientati
8.7 Ordinamento topologico
8.8 Reti
8.8.1 Flussi massimi
8.8.2 Flussi massimi di costo minimo
8.9 Accoppiamento
8.9.1 Problema di assegnamento
8.9.2 Accoppiamento in grafi non bipartiti
8.10 Grafi euleriani e hamiltoniani
8.10.1 Grafi euleriani
8.10.2 Grafi hamiltoniani
8.11 Caso di studio: rappresentanti distinti
8.12 Esercizi
8.13 Esercizi di programmazione
Bibliografia

9.1 Algoritmi di ordinamento elementari
9.1.1 Ordinamento per inserimento
9.1.2 Ordinamento per selezione
9.1.3 Ordinamento a bolle
9.2 Alberi di decisione
9.3 Algoritmi di ordinamento efficienti
9.3.1 Ordinamento di Shell
9.3.2 Ordinamento heap
9.3.3 Quicksort
9.3.4 Ordinamento per fusione
9.3.5 Ordinamento per radice
9.4 Ordinamento in java.util
9.5 Considerazioni conclusive
9.6 Caso di studio: sommare polinomi
9.7 Esercizi
9.8 Esercizi di programmazione
Bibliografia

10.1 Funzioni di hash
10.1.1 Divisione
10.1.2 Ripiegamento
10.1.3 Funzione mid-square
10.1.4 Estrazione
10.1.5 Cambio di radice
10.2 Risoluzione delle collisioni
10.2.1 Indirizzamento aperto
10.2.2 Concatenamento
10.2.3 Indirizzamento bucket
10.3 Eliminazione
10.4 Funzioni di hash perfette
10.4.1 Il metodo di Cichelli
10.4.2 L’algoritmo FHCD
10.5 Funzione di hash per file che crescono
10.5.1 Hashing estensibile
10.5.2 Hashing lineare
10.6 Hashing in java.util
10.7 Caso di studio: hashing con bucket
10.8 Esercizi
10.9 Esercizi di programmazione
Bibliografia

11.1 Condizioni per la compressione dei dati
11.2 Codifica di Huffman
11.2.1 Codifica di Huffman adattativa
11.3 Codice di Shannon-Fano
11.4 Codifica mediante la lunghezza delle serie
11.5 Codice di Ziv-Lempel
11.6 Caso di studio: il metodo di Huffman con codifica mediante la lunghezza delle serie
11.7 Esercizi
11.8 Esercizi di programmazione
Bibliografia

12.1 Metodi di assegnamento sequenziali
12.2 Metodi di assegnamento non sequenziali
12.2.1 Sistemi buddy
12.3 Garbage collection
12.3.1 Marca e raccogli
12.3.2 Metodi di copiatura
12.3.3 Garbage collection incrementale
12.4 Considerazioni conclusive
12.5 Caso di studio: un garbage collector sul posto
12.6 Esercizi
12.7 Esercizi di programmazione
Bibliografia

A.1 Serie armonica
A.2 Approssimazione della funzione lg(n!)
A.3 O-grande per il caso medio in quicksort
A.4 Lunghezza media dei percorsi in un albero binario casuale