====== Algoritmica - corso A e B ====== **Docente**: [[http://www.di.unipi.it/~pagli/|Linda Pagli]] ===== Programma del corso ===== [[http://compass2.di.unipi.it/didattica/inf/share/corsi/corso.asp?id=2545&cds=inf&anno=2007 |Programma]] ===== 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. [[http://www.algoritmica.org/sda/pmwiki.php?n=PDF.Errata|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 ===== {{:alg-b:algoritmica-app1-09.pdf|soluzione primo appello}}\\ {{:alg-b:algoritmica-app2-09.pdf|soluzione secondo appello}} ===== 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.| {{:alg-b:fib.pdf|Fibonacci}}, Par.2.7 | |28/10/2008 | 2 | **Esercitazione**: Esercizi su equazioni di ricorrenza, serie di Fibonacci e Divide et impera.|{{:alg-b:esercizi.pdf|Esercizi}}| |29/10/2008 | 2 | **Esercitazione**: Soluzione del compito del novembre 2007. | {{:alg-b:alg_6-11-07.doc|Compito07}}| |30/10/2008 | 2 | **Esercitazione**: Esercizi su equazioni di ricorrenza e Divide et impera. | | |03/11/2008 | 2 | **Esercitazione scritta**|{{:alg-b: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| |