Indice
Algoritmica - corso A e B
Docente: Linda Pagli
Programma del corso
Orario delle lezioni
| Giorno | Orario | Aula |
|---|---|---|
| Lun | 9-11 | A |
| Mar | 9-11 | A |
| Gio | 9-11 | A |
Orario di ricevimento
Durante il periodo di lezione e esami:
| Giorno | Orario | Luogo |
|---|---|---|
| Mercoledì | 15.30-18.30 | Studio Pagli (277DE) presso Dipartimento di Informatica |
Altrimenti concordare via posta elettronica
Avvisi Urgenti
Per tutti gli avvisi urgenti vedete nella pagina degli avvisi.
E' possibile richiedere di essere avvisati automaticamente via e-mail ogni volta che un nuovo avviso viene postato. Seguire le istruzioni indicate nelle FAQ.
Materiale didattico
Il libro di testo è: P.Crescenzi, G.Gambosi, R.Grossi. Strutture di dati e algoritmi. Pearson-Addison Wesley 2006. ERRATA.
Al link http://www.algoritmica.org è disponibile il software di visualizzazione per quasi tutti gli algoritmi del libro.
Testo di consultazione di carattere enciclopedico è: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, second edition, 2001.
Altro testo di consultazione: C.Demetrescu, I. Finocchi, G. Italiano: Algoritmi e Strutture Dati, MacGraw-Hill, seconda edizione 2008.
Modalità di esame
L’esame di Algoritmica consiste di una prova scritta e di una prova orale. Durante la prova scritta gli studenti non possono consultare i propri libri e appunti. L'esame scritto dunque consiste di esercizi e domande teoriche. Il superamento di entrambe le verifiche intermedie consente l'esonero dalla prova scritta per la sola sessione invernale.
Risultati e soluzioni
Registro delle lezioni
| Giorno | Ore | Argomenti | Riferimenti |
|---|---|---|---|
| 22/9/2008 | 2 | Lezione: Introduzione agli algoritmi. Problema delle 12 monete. | |
| 23/9/2008 | 2 | Lezione: Problemi indecidibili. Problema della fermata. Problemi intrattabili. Torri di Hanoi e crescita esponenziale. | Cap. 1, par. 1.1, 1.2 |
| 25/9/2008 | 2 | Lezione: Classi di complessità P, NP e NPC e relazioni tra esse. Sudoku, backtracking, verifica polinomiale. | Cap. 1, par. 1.3 |
| 29/9/2008 | 2 | Lezione: Problema della Partizione, Generazione di stringhe binarie, Modello RAM | Cap. 1, par. 1.4 |
| 30/9/2008 | 2 | Lezione: Complessità asintotica, Notazioni “Teta”, “O” grande e “Omega” | Dispense in copisteria |
| 2/10/2008 | 2 | Esercitazione: Confronto tra funzioni. Segmento di somma massima: 3 soluzioni di complessità decrescente | Par.2.3, 2.3 |
| 6/10/2008 | 2 | Lezione: Allocazione dinamica della memoria, Limiti inferiori, albero di decisione. | Par.2.1.3, 2.3.1 |
| 7/10/2008 | 2 | Lezione: Il problema della ricerca: limite inferiore. Tecnica Divide et Impera, Ricerca Binaria | Par.2.4, 2.5 |
| 9/10/2008 | 2 | Esercitazione: Modifica di ricerca binaria per il calcolo del Rango. Alg. Divide et impera per determinare il Minimo e il Massimo di un insieme | |
| 13/10/2008 | 2 | Lezione: Teorema fondamentale. Moltiplicazione Rapida. MergeSort | Par.2.5.1, 2.5.2, 2.4.3 |
| 14/10/2008 | 2 | Esercitazione: Esercizi sul teorema fondamentale. Algoritmo di Fusione, MergeInsertionSort. | |
| 16/10/2008 | 2 | Lezioni sospese dal Preside. | |
| 20/10/2008 | 2 | Lezioni sospese dal Preside. | |
| 21/10/2008 | 2 | Lezione: Quicksort, Quickselect, analisi del tempo medio. | Par.2.5.4, 2.5.5 |
| 23/10/2008 | 2 | Lezione: Moltiplicazione di matrici. | Par.2.6, 2.6.1 |
| 27/10/2008 | 2 | Lezione: Serie di Fibonacci. Tecnica della Programmazione Dinamica. | Fibonacci, Par.2.7 |
| 28/10/2008 | 2 | Esercitazione: Esercizi su equazioni di ricorrenza, serie di Fibonacci e Divide et impera. | Esercizi |
| 29/10/2008 | 2 | Esercitazione: Soluzione del compito del novembre 2007. | Compito07 |
| 30/10/2008 | 2 | Esercitazione: Esercizi su equazioni di ricorrenza e Divide et impera. | |
| 03/11/2008 | 2 | Esercitazione scritta | primocompitino.doc |
| 06/11/2008 | 2 | Esercitazione: Correzione del primo compitino. | |
| 10/11/2008 | 2 | Lezione: Programmazione Dinamica: LCS; Ricostruzione della sequenza. | Par.2.7.1 |
| 11/11/2008 | 2 | Lezione: Programmazione Dinamica: Partizione e Zaino; Ricostruzione delle soluzioni. Problemi Pseudo-polinomiali. | Par.2.7.2, 2.7.3, 2.7.4 |
| 13/11/2008 | 2 | Lezione: Il problema dei matrimoni stabili. Strutture, algoritmo e dimostrazione di correttezza. | Par.3.2, 3.2.1, 3.2.2 |
| 17/11/2008 | 2 | Lezione: Analisi ammortizzata. Liste autoaggiustanti, Move to Front. | Par. 3.4.2 |
| 18/11/2008 | 2 | Lezione: Tecniche di analisi ammortizzata. Alberi e alberi binari. | Par.3.4.3, 4.1 |
| 20/11/2008 | 2 | Lezione: Alberi: Visite, Decomposizione, nodo cardine. Visita in ampiezza, trasformazione primo figlio, successivo fratello. | Par. 4.1.1, 4.1.2, 4.3.1, 4.3.2, 4.4 |
| 24/11/2008 | 1 | Lezione: Dizionari come tabelle hash: funzioni hash | Par. 5.3 |
| 25/11/2008 | 2 | Lezione: Tabelle hash: liste di trabocco e indirizzamento aperto | Par. 5.3.1, 5.3.2 |
| 01/12/2008 | 2 | Lezione: Dizionari come alberi binari di ricerca. Operazioni fondamentali. | Par. 5.4, 5.4.1 |
| 02/12/2008 | 2 | Lezione: Alberi AVL. Alberi di Fibonacci. Rotazioni | Par. 5.4.2 |
| 03/12/2008 | 2 | Esercitazione: Esercizi e applicazioni di tabelle hash. | |
| 04/12/2008 | 2 | Lezione: Grafi, definizioni, rappresentazione, visite BFS e DFS | Par. 6.1, 6.1.2, 6.1.3, 7.4.1, 7.4.2 |
| 09/12/2008 | 2 | Lezione: Esempi di visite. Code con priorità, Heap, operazioni di Inserzione e Estrazione in tempo logaritmico. Creazione e Heapsort | Par. 8.1, 8.2.2, 8.2.1, 8.2.3 |
| 10/12/2008 | 2 | Esercitazione: Esercizi su alberi binari e alberi binari di ricerca | Par. 8.1, 8.2.2, 8.2.1 |
| 11/12/2008 | 2 | Esercitazione: Esercizi di riepilogo e su alberi bilanciati | |
| 15/12/2008 | 2 | Esercitazione: Il problema dell'Edit Distance, esercizi su grafi e alberi immagine binaria di alberi ordinali |