Questa è una vecchia versione del documento!
Docente: Linda Pagli
Giorno | Orario | Aula |
---|---|---|
Lun | 9-11 | A |
Mar | 9-11 | A |
Gio | 9-11 | A |
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
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.
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.
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 primo appello
soluzione primo appello
risultati secondo appello
soluzione secondo appello
TERZO APPELLO 10/6/2009
QUARTO APPELLO 30/6/2009
La correzione dello scritto e gli orali sono fissati per l'8 luglio alle ore 15, nell'aula seminari est al dipartimento di informatica (accanto ufficio Pagli).
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 |