Corso di Studi in INFORMATICA, Università di Pisa, Anno accademico 2000/2001

Docente Prof. Roberto Grossi

Pagina Web principale  Algoritmi e Strutture Dati I

Calendario delle lezioni previste
(25 lezioni + 15 esercitazioni + 2 esercitazioni di recupero)

	Data	Inizio	Fine			Data	Inizio	Fine			Data	Inizio	Fine
1	12 Feb	9.00	11.00		16	8 Mar	9.00	11.00		31	10 Apr	11.00	13.00
2	13 Feb	11.00	13.00		17	12 Mar	9.00	11.00		32	11 Apr	11.00	13.00
3	14 Feb	11.00	13.00		18	13 Mar	11.00	13.00
4	15 Feb	9.00	11.00		19	14 Mar	11.00	13.00		33	23 Apr	9.00	11.00
5	19 Feb	9.00	11.00		20	15 Mar	9.00	11.00		34	24 Apr	11.00	13.00
6	20 Feb	11.00	13.00		21	19 Mar	9.00	11.00
7	21 Feb	11.00	13.00		22	20 Mar	11.00	13.00		35	26 Apr	9.00	11.00
8	22 Feb	9.00	11.00		23	22 Mar	9.00	11.00		36	30 Apr	9.00	11.00
9	26 Feb	9.00	11.00		24	22 Mar	16.00	18.00		37	2 Mag	11.00	13.00
10	27 Feb	11.00	13.00		25	29 Mar	9.00	10.00		38	3 Mag	9.00	11.00
11	28 Feb	11.00	13.00		26	2 Apr	9.00	11.00		39	7 Mag	9.00	11.00
12	1 Mar	9.00	11.00		27	3 Apr	11.00	13.00		40	8 Mag	11.00	13.00
13	5 Mar	9.00	11.00		28	4 Apr	11.00	13.00		41	9 Mag	11.00	13.00
14	6 Mar	11.00	13.00		29	5 Apr	9.00	11.00		42	10 Mag	9.00	11.00
15	7 Mar	11.00	13.00		30	9 Apr	9.00	11.00

Calendario dei ricevimenti durante il semestre
(3 ore a settimana)

	Data	Inizio	Fine			Data	Inizio	Fine			Data	Inizio	Fine
1	12 Feb	14.30	17.30		5	12 Mar	14.30	17.30		9	23 Apr	14.30	17.30
2	19 Feb	14.30	17.30		6	19 Mar	14.30	17.30		10	30 Apr	14.30	17.30
3	26 Feb	14.30	17.30		7	2 Apr	16:30	17.30		11	7 Mag	14.30	17.30
4	5 Mar	14.30	17.30		8	9 Apr	14.30	17.30		12	14 Mag	14.30	17.30

Il ricevimento si svolge nella stanza del docente, oppure in aula ALFA/BETA, in Corso Italia 40, su richiesta. È fortemente consigliato agli studenti che abbiano evidente difficoltà nel seguire le lezioni.  In tal caso, il docente ripeterà i concetti principali delle lezioni da lui tenute nella settimana corrente.

Contenuti dettagliati delle lezioni
[I libri di testo sono nelle pagine principali. Premere qui per una versione breve.]

Problemi, algoritmi e complessità

1. Presentazione del corso e dei suoi prerequisiti.
   1. Struttura e scopo, modalità di svolgimento delle lezioni, esercitazioni ed esami, pagine Web [Pagina Web].
   2. Crescita polinomiale ed esponenziale [LP, cap.1].
2. Prerequisiti e analisi asintotica delle funzioni.
   1. Prerequisiti matematici richiesti [Pagina Web].
   2. Ordine di grandezza e comportamento asintotico. Notazione O, Omega e Teta [CLR, cap.2].
   3. Confronto asintotico tra funzioni [CLR, cap.2].
3. Esercitazioni.
   1. Verifica dei prerequisiti.
   2. Ordini di grandezza, comportamento e confronto asintotico di funzioni.
4. Formalizzazione di problemi, dati e algoritmi. Ordinamento e Insertion Sort.
   1. Cenni sulla rappresentazione dei dati elementari: bit, interi, puntatori, caratteri/stringhe (ASCII e Unicode), reali (IEEE 754) [Pagina Web].
   2. Formalizzazione di un problema mediante la notazione matematica. Esempio dell'ordinamento [CLR, cap.1].
   3. Formalizzazione dell'algoritmo di risoluzione mediante un linguaggio di programmazione. Pseudocodice adottato nel libro di testo [CLR, cap.1].
   4. Progettazione di un algoritmo e verifica della correttezza. Esempio dell'Insertion Sort [CLR, cap.1] [Animazione].
5. Modello di calcolo RAM e analisi di complessità.
   1. Modello di computazione secondo von Neumann (Modello RAM = Random Access Machine). Operazioni elementari supportate e ipotesi di costo unitario [Pagina Web]. Analisi di alcuni costrutti dello psudocodice adottato in [CLR] [Pagina Web].
   2. Dimensione dei dati. Risorse computazionali (tempo e spazio). 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)].
   3. Analisi di complessità di un algoritmo al caso ottimo, medio e pessimo. Esempio dell'Insertion Sort [CLR, cap.1].
6. Esercitazioni.
   Formalizzazione del problema, progetto dell'algoritmo risolutore, dimostrazione della correttezza e analisi della complessità al caso pessimo:
   1. Ricerca del massimo in un vettore.
   2. Ricerca sequenziale di un elemento in un vettore.
7. Ricorsione: sua interpretazione mediante induzione e sua realizzazione mediante pila.
   1. Relazione tra induzione e soluzione ricorsiva di un problema [Lu, sez.3.1].
   2. Esempio di calcolo ricorsivo del massimo in un vettore [Lu, sez.3.1].
   3. Realizzazione della ricorsione mediante pila delle chiamate [Lu, sez.6.5].
8. Algoritmi divide et impera (1): Calcolo del massimo in un vettore. Primo e secondo elemento in un vettore. Ricerca binaria in un vettore ordinato.
   1. Schema generale di un algoritmo ricorsivo divide et impera e sua relazione con il principio di induzione [CLR, cap.1].
   2. Calcolo del massimo e del primo e secondo elemento in un vettore con visualizzazione dell'esecuzione mediante pila [Lu, sez.3.1].
   3. Ricerca sequenziale e ricerca binaria in un vettore ordinato (Esempio del vocabolario e dell'elenco telefonico) [Lu, cap.5 par.5.2.1] [Pagina Web].
9. Algoritmi divide et impera (2): Equazioni di ricorrenza e teorema principale. Analisi degli algoritmi divide et impera.
   1. Schema generale DIVetIMP per un algoritmo ricorsivo divide et impera [Lu, cap.3, par 3.4].
   2. Impostazione e risoluzione delle equazioni di ricorrenza per DIVetIMP con esempi:
      
      • massimo (1): T(n) = T(n-1) + O(1);
      • massimo (2) e primo/secondo : T(n) = 2 T(n/2) + O(1);
   3. Metodo di sostituzione (cenni) e iterativo [CLR, cap.4].
   4. Metodo principale e teorema principale [CLR, cap.4].
10. Algoritmi divide et impera (3): Applicazioni del teorema principale. MergeSort.
    1. Ordinamento con il MergeSort [CLR, cap.1] [Lu, cap.5 par.5.3.2] [Codice Java] [Animazione].
    2. Applicazioni del teorema principale:
       
       • ricerca binaria : T(n) = T(n/2) + O(1);
       • MergeSort : T(n) = 2 T(n/2) + O(n);
11. Algoritmi divide et impera (4): Moltiplicazione veloce di interi lunghi. Generazione delle permutazioni e delle sequenze binarie.
    1. Moltiplicazione rapida di interi lunghi: T(n) = 3 T(n/2) + O(n) [Lu, cap.5 par.5.2.2] [Pagina Web].
    2. Generazione delle sequenze binarie in ordine lessicografico: T(n) = 2 T(n-1) + O(1).
    3. Generazione di tutte le permutazioni di un insieme: T(n) = n T(n-1) + O(n) [Lu, cap.3].
12. Esercitazioni con la ricorsione e la risoluzione delle equazioni di ricorrenza [Pagina Web].

Ordinamento e selezione

13. Heap e HeapSort.
1. Definizione di heap [CLR, cap.7 par 7.1].
2. Mantenimento della proprietà di heap [CLR, cap.7 par 7.2].
3. Costruzione di uno heap [CLR, cap.7 par 7.3].
4. L'algoritmo HeapSort [CLR, cap.7 par 7.4].
14. Esercitazioni.
Animazione dei seguenti algoritmi [Animazione]:
1. InsertionSort
2. MergeSort
3. HeapSort
15. QuickSort.
1. Animazione del QuickSort [Animazione].
2. Descrizione del QuickSort [CLR, cap.8 par 8.1].
3. Versione randomizzata del QuickSort [CLR, cap.8 par 8.3].
16. Tecniche di base per i limiti inferiori. Limite inferiore all'ordinamento per confronti.
1. Tecniche di base per i limiti inferiori [Lu, cap.4 par 4.2].
2. Limite inferiore all'ordinamento per confronti [CLR, cap.9 par 9.1].
17. Mediano e k-esimo elemento.
1. Selezione del mediano e del k-esimo elemento [CLR, cap.10 par 10.1-10.2].
18. Counting Sort e Radix Sort (lezione svolta il 14/3).
1. Descrizione e analisi di Counting Sort e Radix Sort [CLR, cap.9 par 9.2-9.3].
2. Animazione di Counting Sort e Radix Sort [Animazione].
3. Lettura consigliata di Bucket Sort [CLR, cap.9 par 9.4].

Strutture di dati e algoritmi di ricerca

19. Strutture informative di base (I): pile, code e liste.
1. Cenni su pile e code (visti nella lezione del 12/3) [CLR, cap.11 par 11.1].
2. Liste concatenate, loro rappresentazione e operazioni supportate [CLR, cap.11 par 11.2].
3. Un esempio ragionato di liste annidate [Pagina Web].
20. Esercitazioni.
1. Cancellazione di tutte le occorrenze di chiavi in liste annidate [Pagina Web].
2. Cancellazione di un elemento dallo heap [Pagina Web].
3. Animazione di QuickSort e RadixSort [Animazione].
21. Dizionari. Tabelle hash (1): liste concatenate.
1. Il problema del dizionario [CLR, Parte III (introduzione)].
2. Concetto di funzione hash con esempi [CLR, cap.12 par 12.3].
3. Collisioni e loro gestione mediante liste concatenate [CLR, cap.12 par 12.2].
22. Tabelle hash (2): indirizzamento aperto.
1. Analisi della gestione mediante liste concatenate [CLR, cap.12 par 12.2] [Pagina Web].
2. Indirizzamento aperto: scansione lineare, quadratica e doppio hash [CLR, cap.12 par 12.4 senza analisi].
23. Esercitazioni preparatorie alla prima verifica.
1. Risoluzione di alcuni degli esercizi forniti nel materiale didattico [Pagina Web].
2. Risoluzione di alcuni degli esercizi delle verifiche degli anni passati [Pagina Web].
24. Esercitazioni preparatorie alla prima verifica.
1. Risoluzione di alcuni degli esercizi forniti nel materiale didattico [Pagina Web].
2. Risoluzione di alcuni degli esercizi delle verifiche degli anni passati [Pagina Web].
25. Discussione delle soluzioni agli esercizi proposti nella prima verifica (1 ora).
26. Esercitazioni sulle liste [Pagina Web].
27. Strutture informative di base (II): alberi radicati.
1. Pile e code [CLR, cap.11 par 11.1].
2. Alberi liberi, radicati e ordinati [CLR, cap.5 par 5.5].
3. Rappresentazione di alberi e loro visita [CLR, cap.11 par 11.4] [Lu, cap.6 par 6.2].
28. Alberi binari di ricerca.
1. Definizione di albero binario di ricerca con esempi [Lu, cap.5 par 5.2.1] [CLR, cap.13 par 13.1].
2. 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].
3. Successore, predecessore, inserzione e cancellazione in un albero binario di ricerca [CLR, cap.13 par 13.3].
29. Alberi bilanciati (1): alberi AVL (prima parte).
1. Problema del ribilanciamento. Definizione di 1-bilanciamento e alberi AVL [Lu, cap.5 par 5.2.1] [Bi, cap.10 par 10.1].
2. Altezza logaritmica degli AVL: alberi di Fibonacci [Lu, cap.5 par 5.1.2] [Bi, cap.10 par 10.1].
30. Alberi bilanciati (1): alberi AVL (seconda parte).
1. Rotazioni (SS, DS, SD, DD), inserimento e cancellazione logica in un AVL [Lu, cap.5 par 5.2.1] [Bi, cap.10 par 10.1].
2. Esempi di inserimenti con rotazioni.
31. Esercitazioni su alberi binari di ricerca e alberi AVL [Pagina Web].
32. Alberi bilanciati (2): alberi 2-3-4 e B-alberi.
1. B-Alberi e loro uso in memoria secondaria [CLR, cap.19 (introduzione)].
2. Definizione di B-alberi [CLR, cap.19 par 19.1].
3. Ricerca e inserimento in un B-albero [CLR, cap.19 par 19.2].
4. Altezza logaritmica dei B-alberi [CLR, cap.19 par 19.1].

Algoritmi su grafi. Intrattabilità e NP-completezza.

33. Grafi e visite in ampiezza (BFS) e profondità (DFS).
1. Terminologia sui grafi [CLR, cap.5 par 5.4].
2. Rappresentazione di grafi [CLR, cap.23 par 23.1].
3. Visita in ampiezza (BFS) [CLR, cap.23 par 23.2].
4. Visita in profondità (DFS) [CLR, cap.23 par 23.3].
34. Esercitazioni su B-alberi e grafi [Pagina Web].
35. Esercitazioni su grafi [Pagina Web].
36. Grafi diretti aciclici (DAG) e ordinamento topologico. Algoritmi di enumerazione.
1. Oridnamento topologico [CLR, cap.23 par 23.4].
2. Algoritmi di enumerazione, con esempi [Lu, cap.7 par 7.1.1 e 7.2.2].
37. Classi P e NP. Nozione di NP-completezza.
1. Problemi in P e NP [CLR, cap.36 par 36.1].
2. Verifica in tempo polinomiale e certificati [CLR, cap.36 par 36.2].
3. NP-completezza e riducibilità [CLR, cap.36 par 36.3].
38. Discussione di alcuni problemi NP-completi.
1. Dimostrazioni di NP-completezza, con esempi [CLR, cap.36 par 36.4].
39. Esercitazioni su enumerazione e NP-completezza [Pagina Web].
40. Esercitazioni preparatorie alla seconda verifica [Pagina Web].
41. Esercitazioni preparatorie alla seconda verifica [Pagina Web].
42. Esercitazioni preparatorie alla seconda verifica [Pagina Web].

Letture facoltative

• Alberi rosso-neri (red-black trees), Capitolo 14 del testo [CLR]
• Alberi di intervalli (interval trees), Capitolo 15 del testo [CLR]
• Programmazione dinamica, Capitolo 16 del testo [CLR]
• Algoritmi greedy e codici di Huffman per la compressione dati, Capitolo 17 del testo [CLR]
• Insiemi disgiunti (union-find), Capitolo 22 del testo [CLR]
• Alberi di copertura minimi, Capitolo 24 del testo [CLR]
• String matching esatto, Capitolo 34 del testo [CLR]
• Inviluppo convesso (convex hull), Capitolo 35 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]

Programma d'esame degli anni passati

• Anno accademico 1997/1998
• Anno accademico 1998/1999
• Anno accademico 1999/2000