DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== 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|  |