====== Algoritmica e Laboratorio - Corso A - 2010/2011 ======


===== Informazioni Generali =====
{{ :informatica:all-a:all10:alk.gif?100|Al Kowarizmi}}
**Docente**: [[http://www.di.unipi.it/~ferragin/|Paolo Ferragina]]

**Impegno:** 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio.

**Informazioni:** News distribuite tramite [[http://twitter.com/FerraginaTeach|Twitter]] con hashtag ''"#algo2011"''.

**Ricevimento studenti:** su appuntamento.

**Registro:** Disponibile nel sito [[http://unimap.unipi.it/registri/dettregistriNEW.php?re=50991::::&ri=4673|UNIPI]].

Il corso consiste ogni settimana di 3 lezioni di didattica frontale in aula e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

===== Orario Lezioni =====

^           Orario delle Lezioni           ^^^^
|Lunedì    |  9-11  |   C1      | Teoria  |
|Martedì   |  9-11  |   B      | Teoria  |
|Mercoledì |  9-11  |   C      | Teoria  |
|Giovedì   |  9-11  |   M-lab      | Laboratorio  |
 

Si pregano gli studenti che dispongono di un portatile di portarlo **in Laboratorio**.

===== Obiettivi del Corso ===== 
L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo. 

Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.
===== Modalità e Appelli di Esame=====
 
L'esame consiste di tre prove:

  * Una prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacità di "problem solving" dello studente. Tale prova viene valutata in trentesimi, e si intende superata se la valutazione è maggiore o uguale a 18, nel qual caso lo studente è ammesso a sostenere la prova di laboratorio.
  * Una prova in laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi su array, liste, alberi e grafi. Tale prova è da intendersi come un __test di idoneità__ il cui superamento permette allo studente di essere ammesso a sostenere la prova orale. 
  * Una prova orale sul programma del corso, la cui valutazione è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta.

Le prove possono essere sostenute in appelli diversi. Se una prova non viene passata, occorre risostenere soltanto quella.

Per avere una idea della tipologia delle prove, si consultino i testi dell'[[http://www.cli.di.unipi.it/doku/doku.php/informatica/all-a/all09/start|anno scorso]].

^ Data ^ Tipo Prova ^ Documento ^ Note ^
| 06/06/2011, ore 09.00 | Scritto|  | [[http://www.di.unipi.it/~pagli/teaching10_11.html|Risultati della classe 26]] (questi sosterranno solo la prova orale con la Prof.ssa Pagli). Gli altri ({{:informatica:all-a:all10:algoritmica-2011.pdf|lista dei risultati}} ordinati per matricola) che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà il 15 Giugno, alle ore 15; è possibile anche sostenere la prova in altro appello. L'orale è il 20 Giugno, alle ore 10.30 (studio Ferragina) |
| 15/06/2011, ore 15.00 | {{:informatica:all-a:all10:esame_110615.pdf|Laboratorio}} | {{:informatica:all-a:all10:soluzione_110615.zip|soluzione}} | |
| 21/06/2011, ore 09.00 | {{:informatica:all-a:all10:algo1_110621.pdf|Scritto}} |  | Visione compiti ore 8.45, prima del Laboratorio, aula M. **Risultati:** Santo (INS), Capasso (27), Sammartano (INS), Lucchesi (18), Corsi (INS), Mazza (28), Salvadori (26), Bottai (INS), Gradilone (INS), Bonfigli (27), Mazzurco (28). |
| 22/06/2011, ore 09.00 | {{|Laboratorio}} |  | Orali Venerdì 24 Giugno, ore 13.30, aula B1 |
| 07/07/2011, ore 09.00 | {{:informatica:all-a:all10:algo1_110707.pdf|Scritto}} |  | Paonessa (18), Gradilone (INS). Visione compiti domani mattina prima del Laboratorio. |
| 08/07/2011, ore 09.00 | {{|Laboratorio}} |  | Orali Martedì 12 Luglio, ore 14, studio Ferragina. |
| 09/09/2011, ore 15.30 | {{:informatica:all-a:all10:algo1_110909.pdf|Scritto}} |  | Pandolfi (INS), Lorito (22), Sammartano (22). Gli studenti Gradilone e Mastrosimone sono ammessi con riserva a svolgere il Laboratorio di Lunedì 12 avendo riportato un voto leggermente insufficiente allo scritto; se passeranno il Lab allora la prova scritta gli verrà considerata superata, altrimenti dovranno ripetere lo scritto a un prossimo appello.|
| 12/09/2011, ore 14.30 | {{|Laboratorio}} |  | gli studenti che hanno passato il lab (incluso Paonessa) sono attesi domani martedì 13 presso lo studio del prof Ferragina per la prova orale alle ore 15.|
| 11/01/2012, ore 09.00 | {{:informatica:all-a:all10:algo1_120111.pdf|Scritto}} |  | Pandolfi (INS), Tovani (INS), Caprini (26), Gradilone (24).|
| 11/01/2012, ore 15.00 | {{|Laboratorio}} |  | Orale lunedì 16 gennaio, ore 18, studio Ferragina.|
| 01/02/2012, ore 09.00, aula A,B | {{:informatica:all-a:all10:algo1_120201.pdf|Scritto}} |  | |
| 01/02/2012, ore 15.00 | {{|Laboratorio}} |  | Risultati scritto Feb 1: Tempone (INS), Paolini (22), Lusardi (23), Pandolfi (22), Pulcinelli (28), Pantaleo (30). |
| 07/02/2012, ore 10.00, aula D | {{:informatica:all-a:all10:algo1_.pdf|Scritto}} |  | ** Recupero ** della prova d'esame dell'1.2.2012 a causa del maltempo.  |
| 07/02/2012, ore 14.00, aula H | {{:informatica:all-a:all10:.tgz|Laboratorio}} |  | La **prova orale** si svolgerà il giorno 15 febbraio alle ore 9.15 presso il Dipartimento di Informatica, studio Ferragina.|
__**IMPORTANTE**__: Gli studenti della **Classe 26** possono sostenere la prova scritta di ''ALL'', e questa verrà riconosciuta come scritto dell'esame di Algoritmica (vecchio corso). Per quanto riguarda l'orale questo dovrà essere sostenuto con la Prof.ssa Pagli. Di contro il laboratorio di ''ALL'' **non sostituisce** l'esame ''LLS'', che quindi dovrà essere svolto con il dott. Gervasi. 
===== Libri di testo =====

A scelta tra:

  * **[CLR]** T. Cormen, C. Leiserson, R. Rivest, C. Stein. //Introduction to Algorithms//. MIT Press, Third edition, 2009. 
  * **[CGG]** P. Crescenzi, G. Gambosi, R. Grossi. //Strutture di dati e algoritmi: progettazione, analisi e visualizzazione//. Addison-Wesley, 2005. Per approfondimenti ed errata: http://www.algoritmica.org/sda/pmwiki.php


Per il laboratorio, un testo fra: 
       * **[KR]** B.W. Kernighan, D.M. Ritchie. //Il Linguaggio C//, Pearson-Prentice Hall, seconda edizione, 2008.
       * **[KP]** A. Kelley, I. Pohl. //C: Didattica e Programmazione//, Addison-Wesley, quarta edizione, 2004.


===== Materiale per il Laboratorio =====

  * **__Prerequisito__**: Conoscenza approfondita della programmazione C per ciò che concerne gli operatori (aritmetici e relazionali), il flusso del controllo (If-then-else, while, for), le funzioni, gli array, i puntatori, le stringhe e l'allocazione dinamica della memoria. Quindi i capitoli 1-5 del libro "Il Linguaggio C", B.W. Kernighan e D.M. Ritchie, Pearson-Prentice Hall, seconda edizione, 2008.
  * **__Strumenti per la programmazione__**: Un editore testuale (tipo ''Emacs''), e il compilatore ''gcc'', sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di //coding// che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come [[http://www.eclipse.org/|Eclipse]] esteso con il suo plug-in [[http://www.eclipse.org/cdt/|Eclipse C/C++ Development Tooling]]. Per chi si trova a operare sotto Windows suggeriamo il compilatore e il debugger disponibili con [[http://www.mingw.org/|MinGW]], e consigliamo di istallare i 3 componenti suddetti secondo la sequenza: Eclipse-MinGW-CDevTool. Oppure istallare una macchina virtuale, come [[http://www.virtualbox.org/|VirtualBox]], con una qualunque distribuzione Linux sopra. Il **consiglio** è però quello di adoperare la combinazione minimale ''editor+gcc'' al fine di non perdersi nei meandri e nelle opzioni dei vari tools (non necessari per AIL), per concentrarsi **soltanto** sugli aspetti di //coding// degli algoritmi.
===== Programma del corso =====


  - Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
  - Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
  - Limiti del calcolo: albero di decisione, limiti superiori e inferiori. 
  - Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
  - Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
  - Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
  - Ordinamento di interi: Counting sort, Radix Sort. 
  - Ordinamento di stringhe: ''qsort''-based.
  - Sottosequenza di somma massima.
  - Programmazione dinamica: LCS, Partizione e Zaino
  - Algoritmi randomizzati: Quicksort.
  - Generazione di combinazioni e permutazioni
  - Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
  - Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
  - Alberi: rappresentazione e visite.
  - Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  - Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
  - Grafi III: Minimum Spanning Tree e Shortest Path.

===== Registro delle Lezioni =====

^ Data ^ Argomento ^ Rif. Biblio ^
| 07/03/11 | Introduzione al corso: nozioni di Algoritmo, Problema, istanza, dimensione dell'istanza, complessità in tempo e spazio al caso pessimo e caso medio, analisi asintotica e confronto di algoritmi. Algoritmi polinomiali ed esponenziali. Esistenza problemi indecidibili. | {{:informatica:all-a:all10:prerequisiti.pdf|Prerequisiti matematici}} e {{:informatica:all-a:all10:appuntimodelli.pdf|indecidibilità (par 1.4)}}|
| 08/03/2011 | Problemi indecidibili: tecnica della diagonalizzazione, problema della fermata. Problemi esponenziali: RoadBlock e torri di Hanoi. Definizione classi P, NP, NP-completi, EXPTIME. | Una nota sul [[http://it.wikipedia.org/wiki/Problema_della_fermata|problema della fermata]]. Alcuni appunti utili ({{:informatica:all-a:all10:p-np.pdf|P/NP}}). |
| 09/03/2011 | Nozione di Riduzione Polinomiale. Esempi di problemi NPC: Problema SAT, Ciclo Hamiltoniano (e confronto con Ciclo Elueriano), Zaino, k-clique. Esempi di riduzioni: SAT - IP01 e SAT - k-Clique. Notazione asintotica: O-grande, Omega-grande e Theta, con esempi. | Una riduzione ({{:informatica:all-a:all10:k-clique.pdf|K-clique}}). |
| 10/03/2011 | **Laboratorio**: Editing, compilazione. Richiami di linguaggio C: Istruzioni varie e operatori, array, printf, scanf. | Cap. 2-3, 7.1-7.4 di [KR].\\ {{:informatica:all-a:all10:lez1_220210.pdf|slides}} (soluzioni nelle slides della Esercitazione 2) |
| 10/03/2011 | **Laboratorio**: Puntatori, funzioni e passaggio parametri. | Sez. 4.1-4.5 e 5.1-5.5 di [KR].\\ {{:informatica:all-a:all10:lez2_230210.pdf|slides}} {{:informatica:all-a:all10:sol-lez02.zip|soluzioni}}| 
| 14/03/2011 | **Laboratorio**: Tecniche di passagio dei parametri. | {{:informatica:all-a:all10:lez3_230210.pdf|slides}}  {{:informatica:all-a:all10:sol-lez03.zip|soluzioni}} | 
| 15/03/2011| **Laboratorio**: Allocazione dinamica della memoria (malloc) |{{:informatica:all-a:all10:lez4_250210.pdf| slides}}  {{:informatica:all-a:all10:sol-lez04.zip| soluzioni}}|
| 16/03/2011 | **Laboratorio**: Stringhe | {{:informatica:all-a:all10:lez5_260210.pdf| slides}}  {{:informatica:all-a:all10:soluzioni_lez2602.zip| soluzioni}} |
| 21/03/2011 | Selection Sort e Insertion Sort: proprietà e complessità. Esercizi di valutazione complessità asintotica al caso pessimo. |  |
| 22/03/2011 | **Laboratorio**: Codifica binaria. Sottoarray di somma massima. Redirezione dell'input e //timing// di un programma. | {{:informatica:all-a:all10:lez6_codifica.pdf|slides(1)}} {{:informatica:all-a:all10:maxsum_ex.pdf|slides(2)}} {{:informatica:all-a:all10:sol-lez06.zip| soluzioni}} {{:informatica:all-a:all10:test_maxsum.zip| testfiles}} |
| 23/03/2011 | Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero delle decisioni. Esempi: min/max, ricerca di una chiave, ordinamento. Problema della ricerca di una chiave: scansione e ricerca binaria (iterativa e ricorsiva). | {{:informatica:all-a:all10:lucciolb.pdf|appunti}} |
| 24/03/2011 | Tecnica “divide et impera”. Relazioni di Ricorrenza e teorema per la loro risoluzione. MergeSort: algoritmo, proprietà, e analisi della complessità. |  |
| 28/03/2011 | Moltiplicazione veloce tra interi. Esercitazione su calcolo complessità algoritmi ricorsivi. |  |
| 29/03/2011 | Quicksort: algoritmo, complessità al caso pessimo e medio (con dimostrazione), esempi. 2 tipi di procedure PARTITION.| {{:informatica:all-a:all10:quick1.pdf|analisi caso medio}} e {{:informatica:all-a:all10:altropivot.pdf|altra distribuzione}}|
| 30/03/2011 | Heapsort: definizione heap, proprietà, realizzazione come array, fix-heap, build-heap, heapsort.| |
| 31/03/2011 | **Laboratorio**: Insertion sort su interi e stringhe. Ricerca binaria su stringhe. MergeSort su interi | {{:informatica:all-a:all10:es07.pdf|esercizi}} {{:informatica:all-a:all10:sol07.zip|soluzioni(1)}} | 
| 04/04/2011 | Pile, Code e code con priorità realizzate mediante heap. | | 
| 05/04/2011 | Considerazioni sulla crescita esponenziale e sulla rappresentazione degli elementi di un insieme. Il vettore di appartenenza. Algoritmo di base per la generazione di configurazioni binarie e sua applicazione a problemi di allocazione tipo "zaino". | | 
| 06/04/2011 | Algoritmo di base per la generazione di tutte le permutazioni di un insieme e sua applicazione a problemi tipo "ciclo hamiltoniano". Introduzione alla programmazione dinamica. | {{:informatica:all-a:all10:genera.pdf|genera e permuta}} | 
| 07/04/2011 | **Laboratorio**: Quick Sort su interi e su stringhe. Varianti (//pari&dispari//, //3-way partition//) | {{:informatica:all-a:all10:es08.pdf|esercizi}} {{:informatica:all-a:all10:quick_sort_parziale.c.zip|quick_sort_parziale}} | 
| 11/04/2011 | Problemi risolubili efficientemente atraverso sottobproblemi. Il calcolo dei coefficienti binomiali. Il calcolo della pi lunga sottosequenza comune. Esempi. | | 
| 12/04/2011 | Problema della edit distance. Individuazione delle apparizioni approssimate di un pattern in un testo. Esercizi. Introduzione all'odinamento in tempo lineare. | |
| 13/04/2011 | Gli algoritmi di Counting Sort e Radix Sort.  Esercizi. | |
| 14/04/2011 | Esercitazione pre-compitino. | |
| 28/04/2011 | **Laboratorio**: Libreria //qsort//. Esercizi su stringhe e diversi ordinamenti. | {{:informatica:all-a:all10:es09.pdf|esercizi}} {{:informatica:all-a:all10:sol09.zip|soluzioni}}| 
| 02/05/2011 | Le liste: ricerca, inserimento, cancellazione. Gli alberi binari di ricerca: definizione, proprietà, visite, ricerca, min, max, predecessore e successore, con analisi della complessità in tempo. | | 
| 03/05/2011 | Inserimento e cancellazione di un nodo in un albero binario di ricerca | | 
| 04/05/2011 | Alberi AVL: rotazione semplice e doppia | {{:informatica:all-a:all10:delta.pdf|appunti}} | 
| 05/05/2011 | **Laboratorio**: Le //struct// e le liste. Esercizi. | {{:informatica:all-a:all10:lez_struct.pdf|slides}}{{:informatica:all-a:all10:es10.pdf|esercizi}}\\ {{:informatica:all-a:all10:sol10.zip|soluzioni}}[[http://it.wikipedia.org/wiki/Indentazione|Lettura consigliata]]| 
| 09/05/2011 | Esercitazione su alberi e algoritmi ricorsivi. | | 
| 10/05/2011 | Tabelle hash: problema del dizionario, funzioni hash (metodo divisione, moltiplicazione e universale), gestione delle collisioni con liste di trabocco e open addressing. | | 
| 11/05/11 | **Laboratorio**: Esercizi sugli alberi binari di ricerca. | {{:informatica:all-a:all10:slides_tree.pdf|slides}} {{:informatica:all-a:all10:es_alberi.pdf|esercizi}} {{:informatica:all-a:all10:sol_alberi.zip|soluzioni}} |
| 12/05/11 | **Laboratorio**: //SIMULAZIONE PROVA DI LABORATORIO//. | {{:informatica:all-a:all10:simulazione20110511.pdf|testo esercizio e istruzioni}} {{:informatica:all-a:all10:solsimulazione.zip|soluzione}}|
| 16/05/11 | Grafi: definizione, notazione, terminologia, rappresentazioni (sequenza di archi, matrice di adiacenza e liste di adiacenza). Visita BFS con analisi di complessità ed esempio. | |
| 17/05/11 | Grafi: dimostrazione di correttezza della BFS. Visita DFS: algoritmo, complessità, tipologie di archi, teorema del cammino minimo. Esempio. | |
| 18/05/11 | **Laboratorio**: Richiami sulle liste, Tabelle hash con liste di trabocco. |{{:informatica:all-a:all10:lez_2704.pdf| slides}} {{:informatica:all-a:all10:es_2704.pdf| esercizi}} {{:informatica:all-a:all10:sol_hash.zip|soluzioni}}|
| 19/05/11 | Topological sort, algoritmo, complessità e dimostrazione di correttezza. Problema MST: schema algoritmico di risoluzione, correttezza, complessità. Algoritmo di Kruskal, con esempio. | |
| 24/05/11 | Algoritmo di PRIM. Esempio. | |
| 25/05/11 | Problema dei cammini minimi: Bellman-Ford e Dijkstra. Correttezza e complessità. | |
| 26/05/11 | **Laboratorio**: //SIMULAZIONE PROVA DI LABORATORIO//. | {{:informatica:all-a:all10:simulazione20110526.pdf|testo}} |
| 30/05/11 | Esercitazione in Aula A, con corso B. | |
| 31/05/11 | Esercitazione sul programma della seconda parte del corso. | |
| 01/06/11 | Esercitazione sul programma della seconda parte del corso. | |