Programma di esame per
l'anno accademico 1999/2000
[I libri di testo
sono nelle
pagine principali.]
Problemi, algoritmi e complessità
-
Presentazione del corso e dei suoi prerequisiti. Analisi
asintotica.
- Struttura e scopo, modalità di svolgimento delle
lezioni, esercitazioni ed esami, pagine Web [Pagina Web].
- Prerequisiti matematici richiesti
[Pagina Web].
- Crescita polinomiale ed esponenziale [LP, cap.1].
- Ordine di grandezza e comportamento asintotico. Notazione O,
Omega e Teta [CLR, cap.2].
- Confronto asintotico tra funzioni [CLR, cap.2].
-
Esercitazioni.
- Verifica dei prerequisiti.
- Ordini di grandezza, comportamento e confronto asintotico di
funzioni.
-
Formalizzazione di problemi, dati e algoritmi. Ordinamento e Insertion Sort.
- Cenni sulla rappresentazione dei dati elementari: bit, interi,
puntatori, caratteri/stringhe (ASCII e Unicode), reali (IEEE 754)
[Pagina Web].
- Formalizzazione di un problema mediante la notazione
matematica. Esempio dell'ordinamento [CLR, cap.1].
- Formalizzazione dell'algoritmo di risoluzione mediante un
linguaggio di programmazione. Pseudocodice adottato nel libro di testo
[CLR, cap.1].
- Progettazione di un algoritmo e verifica della
correttezza. Esempio dell'Insertion Sort [CLR, cap.1]
[Animazione].
-
Modello di calcolo RAM e analisi di complessità.
- Modello di computazione secondo von Neumann (Modello RAM = Random
Access Machine). Operazioni elementari supportate e ipotesi di costo
unitario
[Pagina Web].
- Dimensione dei dati. Risorse computazionali. Complessità
asintotica di un problema e di un algoritmo. Caso ottimo, caso medio e
caso pessimo. Limite inferiore e superiore di complessità,
complessità polinomiale e superpolinomiale [Lu, cap. 4 (solo le
parti qui citate)].
- Analisi di complessità di un algoritmo al caso ottimo,
medio e pessimo. Esempio dell'Insertion Sort [CLR, cap.1].
-
Esercitazioni.
Formalizzazione del problema, progetto dell'algoritmo risolutore,
dimostrazione della correttezza e analisi della complessità al
caso pessimo:
- Ricerca del massimo in un vettore.
- Ricerca sequenziale di un elemento in un vettore.
- Fusione di due sottovettori ordinati (merge).
-
Algoritmi divide et impera (1). Ricerca binaria. MergeSort.
- Ricerca sequenziale e ricerca binaria in un vettore ordinato
(``Scommettiamo che?'': esempio del vocabolario e dell'elenco
telefonico) [Lu, cap.5 par.5.2.1]
[Pagina Web].
- Schema generale di un algoritmo ricorsivo divide et impera
e sua relazione con il principio di induzione [CLR, cap.1].
- Ordinamento con il MergeSort [CLR, cap.1] [Lu, cap.5
par.5.3.2]
[Animazione].
-
Algoritmi divide et impera (2). Moltiplicazione veloce. Coppia di
punti più vicini.
- Moltiplicazione rapida di interi lunghi [Lu, cap.5 par.5.2.2]
[Pagina Web].
- Un esempio impegnativo: ricerca della coppia di punti più
vicini [CLR, cap.35 par.35.4].
-
Esercitazioni.
Progettazione di algoritmi divide et impera:
- Riformulazione del massimo in maniera ricorsiva.
- Trovare il primo e secondo elemento [Lu, cap.3].
- Generazione delle sequenze binarie in ordine lessicografico.
- Generazione di tutte le permutazioni di un insieme [Lu, cap.3].
-
Equazioni di ricorrenza. Analisi degli algoritmi divide et
impera con esempi.
- Equazioni di ricorrenza e connessione con gli algoritmi divide
et impera con esempi:
- MergeSort : T(n) = 2 T(n/2) +O(n);
- coppia di punti più vicini: T(n) = 2 T(n/2) +O(n);
- massimo e primo/secondo : T(n) = 2 T(n/2) +O(1);
- ricerca binaria : T(n) = T(n/2) +O(1);
- moltiplicazione rapida : T(n) = 3 T(n/2) +O(n);
- Insertion Sort ricorsivo: T(n) = T(n-1) +O(n);
- generazione delle sequenze binarie: T(n) = 2 T(n-1) +O(1);
- generazione delle permutazioni : T(n) = n T(n-1) +O(n).
- Metodo principale e teorema principale [CLR, cap.4].
- Metodo di sostituzione (cenni) e iterativo [CLR, cap.4].
- Esercitazioni con la ricorsività e la risoluzione delle
equazioni di ricorrenza.
Ordinamento e selezione
-
Heap e HeapSort.
- Definizione di heap [CLR, cap.7 par 7.1].
- Mantenimento della proprietà di heap [CLR, cap.7 par 7.2].
- Costruzione di uno heap [CLR, cap.7 par 7.3].
- L'algoritmo HeapSort [CLR, cap.7 par 7.4].
- Cancellazione dallo heap (facoltativo)
[Pagina Web].
-
Esercitazioni.
Animazione dei seguenti algoritmi [Animazione]:
- InsertionSort
- MergeSort
- HeapSort
-
QuickSort.
- Animazione del QuickSort [Animazione].
- Descrizione del QuickSort [CLR, cap.8 par 8.1].
- Versione randomizzata del QuickSort [CLR, cap.8 par 8.3].
-
Analisi di HeapSort e QuickSort.
- Prestazioni di HeapSort [CLR, cap.7 par 7.2--7.4].
- Prestazioni di QuickSort [CLR, cap.8 par 8.2].
- Prestazioni di QuickSort [CLR, cap.8 par 8.2].
- Analisi del caso medio QuickSort [Lu, cap.3 par 3.3].
-
Limite inferiore all'ordinamento per confronti. Tecniche di base per i
limiti inferiori.
- Limite inferiore all'ordinamento per confronti [CLR, cap.9 par 9.1].
- Tecniche di base per i limiti inferiori [Lu, cap.4 par 4.2].
-
Mediano e k-esimo elemento. Counting Sort e Radix
Sort. (Bucket Sort.)
- Selezione del mediano e del k-esimo elemento [CLR, cap.10
par 10.1-10.3].
- Animazione di Counting Sort e Radix Sort [Animazione].
- Descrizione e analisi di Counting Sort e Radix Sort
[CLR, cap.9 par 9.2-9.3].
- Lettura consigliata di Bucket Sort [CLR, cap.9 par 9.4].
-
Esercitazioni preparatorie alla prima verifica.
- Risoluzione di alcuni degli esercizi forniti nel materiale
didattico [Pagina Web].
- Risoluzione di alcuni degli esercizi delle verifiche degli anni
passati [Pagina Web].
-
Esercitazioni preparatorie alla prima verifica.
- Risoluzione di alcuni degli esercizi forniti nel materiale
didattico [Pagina Web].
- Risoluzione di alcuni degli esercizi delle verifiche degli anni
passati [Pagina Web].
Strutture dati e algoritmi di ricerca
-
Strutture informative di base: pile, code, liste e alberi radicati.
- Pile e code [CLR, cap.11 par 11.1].
- Liste concatenate e loro rappresentazione [CLR, cap.11 par 11.2].
- Alberi liberi, radicati e ordinati [CLR, cap.5 par 5.5].
- Rappresentazione di alberi [CLR, cap.11 par 11.4].
-
Esercitazioni.
-
Dizionari. Tabelle hash (1): liste concatenate.
- Il problema del dizionario [CLR, Parte III (introduzione)].
- Concetto di funzione hash con esempi [CLR, cap.12 par 12.3].
- Collisioni e loro gestione mediante liste concatenate [CLR, cap.12 par 12.2].
-
Tabelle hash (2): indirizzamento aperto.
- Analisi della gestione mediante liste concatenate [CLR, cap.12
par 12.2]
[Pagina Web].
- Indirizzamento aperto: scansione lineare, quadratica e doppio
hash [CLR, cap.12 par 12.4 senza analisi].
-
Esercitazioni
-
Alberi binari di ricerca. Visite di alberi.
- Rappresentazione di alberi e loro visita [Lu, cap.6 par 6.2].
- Definizione di albero binario di ricerca con esempi [Lu, cap.5
par 5.2.1] [CLR, cap.13 par 13.1].
- Ricerca in un albero binario di ricerca e relazione con la
ricerca binaria [Lu, cap.5
par 5.2.1] [CLR, cap.13 par 13.2].
- Inserzione e cancellazione in un albero binario di ricerca [CLR, cap.13 par 13.3].
-
Alberi bilanciati (1): alberi AVL.
- Problema del ribilanciamento. Definizione di 1-bilanciamento e
alberi AVL [Lu, cap.5 par 5.2.1] [Bi, cap.10 par 10.1].
- Altezza logaritmica degli AVL: alberi di Fibonacci [Lu, cap.5 par 5.1.2] [Bi, cap.10 par 10.1].
- Rotazioni (SS, DS, SD, DD) e inserimento in un AVL [Lu, cap.5 par 5.2.1] [Bi, cap.10 par 10.1].
-
Esercitazioni.
-
Alberi bilanciati (2): alberi 2-3 e B-alberi.
- B-Alberi e loro uso in memoria secondaria [CLR, cap.19 (introduzione)].
- Definizione di B-alberi [CLR, cap.19 par 19.1].
- Ricerca e inserimento in un B-albero [CLR, cap.19 par 19.2].
- Altezza logaritmica dei B-alberi [CLR, cap.19 par 19.1].
-
Esercitazioni.
-
Alberi digitali. Trie, Patricia e alberi dei suffissi.
Note ausiliari alla lezione [PDF]
[Postscript].
- Definizione di trie non compatti e compatti.
- Definizione di Patricia.
- Ricerca e inserimento.
- Suffix tree.
- Sospensione della didattica per elezioni (D.R. n. 01/319 del 21 febbraio 2000).
- Sospensione della didattica per elezioni (D.R. n. 01/319 del 21 febbraio 2000).
- Sospensione della didattica per vacanze.
- Sospensione della didattica per vacanze.
- Sospensione della didattica per visita CAMPUS.
-
Ricerca testuale: algoritmo string matching di Karp-Rabin.
- Definizione del problema dello string matching [CLR, cap.34 (introduzione)].
- Algoritmo immediato per lo string matching [CLR, cap.34 par 34.1].
- Algoritmo di Karp-Rabin e sua relazione con le collisioni nelle
funzioni hash [CLR, cap.34 par 34.2].
Algoritmi su grafi, tecniche ``greedy'' e di programmazione
dinamica
-
Grafi e visite in ampiezza (BFS) e profondità (DFS).
- Terminologia sui grafi [CLR, cap.5 par 5.4].
- Rappresentazione di grafi [CLR, cap.23 par 23.1].
- Visita in ampiezza (BFS) [CLR, cap.23 par 23.2].
- Visita in profondità (DFS) [CLR, cap.23 par 23.3].
-
Esercitazioni.
-
Greedy: Alberi di ricoprimento minimo.
- Costruzione di un albero di copertura minimo [CLR, cap.24 par 24.1].
- Algoritmi di Prim e Kruskal [CLR, cap.24 par 24.2].
-
Esercitazioni.
-
Programmazione dinamica. Sottosequenza più lunga e string
matching con errori.
- Programmazione dinamica e ricorsione [CLR, cap.16 par 16.2].
- Sottosequenza comune più lunga e string matching
approssimato [CLR, cap.16 par 16.3 e problema 16-3].
-
Esercitazioni.
Intrattabilità e NP-completezza
-
Nozione di NP-completezza.
- Problemi in P e NP [CLR, cap.36 par 36.1].
- Verifica in tempo polinomiale e certificati [CLR, cap.36 par 36.2].
- NP-completezza e riducibilità [CLR, cap.36 par 36.3].
-
Esercitazioni
Approfondimenti facoltativi
- RB-alberi (red-black trees), Capitolo 14 del testo [CLR]
- Alberi di intervalli (interval trees), Capitolo 15 del testo [CLR]
- Liste con salti (skip lists), Capitolo 12 in Weiss [W]
- Alberi di ricerca randomizzati (treaps), Capitolo 12 in Weiss [W]
- k-d-alberi (k-d-trees), Capitolo 12 in Weiss [W]
- Insiemi disgiunti (union-find), Capitolo 22 del testo [CLR]
- Ordinamento topologico e componenti fortemente connesse, Capitolo 23 del testo [CLR]
- Inviluppo convesso (convex hull), Capitolo 35 del testo [CLR]
- Riduzioni polinomiali e dimostrazioni di NP-completezza, Capitolo 36 del testo [CLR]