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


===== Informazioni Generali =====
{{ :informatica:all-a:all09: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 ''"#algo2010"''.

**Ricevimento studenti:** ore 16-19, ogni Lunedì, studio docente presso il Dipartimento di Informatica.

**Registro:** Disponibile nel sito [[http://unimap.unipi.it/registri/dettregistriNEW.php?re=35865::::&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ì    |  11-13  |   E      | Teoria  |
|Martedì   |  11-13  |   M      | Laboratorio  |
|Giovedì |  11-13  |   C      | Teoria  |
|Venerdì   |  9-11  |   E      | Teoria  |
 

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.

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 ^
| 08/04/2010, ore 11.00 | Primo Compitino | {{:informatica:all-a:all09:algo1_100408-sol.pdf|testo con soluzione}}, {{:informatica:all-a:all09:risultati-comp1.pdf|risultati}} |  |
| 24/05/2010, ore 9.00 | Secondo Compitino | {{:informatica:all-a:all09:algo1_100524-sol.pdf|testo con soluzione}}, {{:informatica:all-a:all09:risultati-comp2.pdf|risultati}} |  |
| 31/05/2010, ore 15.00 | Prova di Laboratorio | | |
| 22/06/2010, ore 14.30 | Scritto | {{:informatica:all-a:all09:algo1_100622sol.pdf|testo con soluzione}}, {{:informatica:all-a:all09:risultati04.pdf|risultati}} | |
| 23/06/2010, ore 15.00 | Prova di Laboratorio | | |
| 13/07/2010, ore 14.30 | Scritto | {{:informatica:all-a:all09:algo1_100713sol.pdf|testo con soluzione}} e {{:informatica:all-a:all09:voti.pdf|voti}} |  |
| 14/07/2010 | Prova di Laboratorio |  | |
| 13/09/2010, ore 9.00 | Scritto | {{:informatica:all-a:all09:algo1_100913.pdf|Testo}} |  |
| 13/09/2010 | Prova di Laboratorio |  |  |
| 01/02/2011 | Scritto | {{:informatica:all-a:all09:algo1_110201.pdf|Testo}}.  |  
| 02/02/2011 | Prova di laboratorio |  |  
| 16/02/2011 | Scritto | {{:informatica:all-a:all09:algo1_110216.pdf|Testo}} |  
| 02/02/2011 | Prova di laboratorio |   |  
__**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. 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, Karp-Rabin.
  - 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 ^
| 22/02/10 | **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:all09:lez1_220210.pdf|slides}}|
| 23/02/10 | **Laboratorio**: Puntatori, funzioni e passaggio parametri. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-a:all09:lez2_230210.pdf|slides}}| 
| 23/02/10 | **Laboratorio**: Esercitazione. | {{:informatica:all-a:all09:lez3_230210.pdf|slides}}  | 
| 25/02/10 | **Laboratorio**: Allocazione dinamica della memoria (malloc) |{{:informatica:all-a:all09:lez4_250210.pdf| slides}}  {{:informatica:all-a:all09:sol_2e3.zip| soluzioni(2 e 3) }}|
| 26/02/10 | **Laboratorio**: Stringhe. | {{:informatica:all-a:all09:lez5_260210.pdf| slides}} (svolgere gli esercizi 3 e 4)  |
| 01/03/10 | 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. | {{:informatica:all-a:all09:prerequisiti.pdf|Prerequisiti matematici.}}|
| 02/03/10 | **Laboratorio**: Codifica binaria. Poblema del maggioritario: soluzione quadratica, algoritmo ottimo | {{:informatica:all-a:all09:lez6_codifica.pdf|slides}} {{:informatica:all-a:all09:soluzioni_lez2602.zip| soluzioni esercizi 3 e 4 del 26/02}} {{:informatica:all-a:all09:nota_maggioritario.pdf|note sul maggioritario (con esempio)}} |
| 04/03/10 | Problema sequenza somma-max: soluzione cubica, quadratica e lineare. Problemi indecidibili: tecnica della diagonalizzazione, problema della fermata. Problema delle torri di Hanoi. | Una nota sul [[http://it.wikipedia.org/wiki/Problema_della_fermata|problema della fermata]]|
| 02/03/10 | Problema del RoadBlock. Definizione classi P, NP, NP-completi, EXPTIME. Nozione di Riduzione Polinomiale. Esempi di problemi NPC: Problema SAT, Ciclo Hamiltoniano (e confronto con Ciclo Elueriano), Zaino. Esempi di riduzioni: SAT - IP01 e SAT - Clique | Alcuni appunti utili ({{:informatica:all-a:all09:p-np.pdf|P/NP}} e {{:informatica:all-a:all09:k-clique.pdf|K-clique}}). |
| 08/03/10 | Notazione: O-grande, Omega-grande, o-piccolo, omega-piccolo e theta, con esercizi | {{:informatica:all-a:all09:notazioni_asint.pdf|Notazioni Asintotiche (con esercizi)}} Sez. 2.2.1 e pag. 10 dell'appendice dell'errata corrige di [CGG]. |
| 09/03/10 | **Laboratorio**: Coding del sottoarray di somma massima. Redirezione dell'input e //timing// di un programma. | {{:informatica:all-a:all09:maxsum_ex.pdf|note}} {{:informatica:all-a:all09:test_maxsum.zip| testfiles }}{{:informatica:all-a:all09:codice_somma_massima.zip| codice somma massima}}{{:informatica:all-a:all09:esercizio_intersezione.pdf| Esercizio}}|
| 11/03/10 | **Laboratorio**: tecnica del doubling per allocazione dinamica di array, calcolo numero elementi distinti di un array ordinato. | {{:informatica:all-a:all09:doubling.pdf|slides}}{{:informatica:all-a:all09:testfile_doubling.zip|testfiles}} {{:informatica:all-a:all09:intersezione.zip| intersezione in tempo quadratico}}|
| 12/03/10 | **Laboratorio**: note sull'implementazione del doubling. Selection Sort, esercizio: adattare Selection Sort all'ordinamento di stringhe. (N.B.: gli esercizi per casa sono un'utile verifica sulla comprensione degli argomenti trattati in laboratorio)| {{:informatica:all-a:all09:codice_doubling.zip|soluzione esercizio su doubling}}{{:informatica:all-a:all09:lez9.pdf| slides}}{{:informatica:all-a:all09:ex2_lez9.pdf| testo degli esercizi}} |
| 15/03/10 | Insertion Sort: proprietà e complessità. 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). | Studiare anche questo {{:informatica:all-a:all09:lucciolb.pdf|approfondimento}} dal libro di F. Luccio “La struttura degli algoritmi” (Boringhieri, 1982). |
| 16/03/10 | **Laboratorio:** funzione di libreria qsort. Svolgere l'esercizio 3 a casa | {{:informatica:all-a:all09:esempio_qsort.zip| esempio}} {{:informatica:all-a:all09:qsort_esercizi.pdf|}} {{:informatica:all-a:all09:soluzioni_qsort.zip|soluzioni(1 e 2)}} |
| 18/03/10 | Tecnica “divide et impera”. Relazioni di Ricorrenza e teorema per la loro risoluzione. MergeSort: algoritmo, proprietà, e analisi della complessità. | La versione del Teorema da studiare è {{:informatica:all-a:all09:master.pdf|quella del CLR}} commentata anche in questi {{:informatica:all-a:all09:teoprinc.pdf|appunti}}. |
| 19/03/10 | Moltiplicazione veloce di due interi di n cifre. Ricerca Binaria: iterativa e ricorsiva, con analisi di complessità. |  |
| 19/03/10 | //Esercitazione extra:// Esercizi su notazione asintotica, algoritmi ricorsivi, e calcolo della loro complessità in tempo. Sul funzionamento degli algoritmi ricorsivi. | **Aula F1** |
| 22/03/10 | Programmazione dinamica: definizione, proprietà, esempi: Numeri Fibonacci, coefficiente binomiale, problema del "rod cutting". | Alcuni appunti: {{:informatica:all-a:all09:dynprog.pdf|clr}}, {{:informatica:all-a:all09:luccio-progdyn.pdf|luccio}}. |
| 23/03/10 | **Laboratorio:** Esercizi sul MergeSort. Svolgere l'esercizio 4 a casa|{{:informatica:all-a:all09:sol_120310.zip|soluzioni (12/03/10)}} {{:informatica:all-a:all09:ric_bin.zip| esercizio 3 (16/03/10)}} {{:informatica:all-a:all09:ex.pdf| Esercizi}} {{:informatica:all-a:all09:input.zip| input}}  |
| 23/03/10 | //Lezione extra:// Quicksort: proprietà, analisi della complessità (caso medio, ottimo e pessimo) e considerazioni pratiche. Due tecniche di “distribuzione". Quicksort randomizzato. ''qsort'' del ''C'' come quicksort + insertionSort.  | Studiare anche {{:informatica:all-a:all09:quick.pdf|questi appunti}} e altra tecnica di {{:informatica:all-a:all09:altropivot.pdf|distribuzione}}.  |
| 25/03/10 | Counting sort e Radix sort, con valutazione della complessità. |   |
| 26/03/10 | //Esercitazione pre-compitino.// |   |
|    | // Soluzioni esercizi di laboratorio del 23/03: // {{:informatica:all-a:all09:soluzioni2303.zip|codice}} |    |
| 13/04/10 | Due paradigmi algoritmici: Genera Binarie e Permutazioni, con esempi | {{:informatica:all-a:all09:genera.pdf|appunti per chi possiede il [CLR]}}  |
| 15/04/10 | Le liste, operazioni, e la loro variante //randomizzata// (skip list) | {{:informatica:all-a:all09:skip.pdf|appunti per chi possiede il [CLR]}} |
| 16/04/10 | Code con priorità: Heap, e sue operazioni -- Empty, First, Enqueue, Dequeue, IncreaseKey, DecreaseKey. Valutazione della complessità.  Heapify (con dimostrazione di correttezza), BuildHeap e Heapsort. | |
| 19/04/10 | Funzioni hash: metodo della moltiplicazione e della divisione. Tabelle hash con liste di trabocco.  | |
| 20/04/10 | Tabelle hash con indirizzamento aperto. Pattern matching su stringhe: metodo di Karp e Rabin. | Algoritmo KR: [[http://www-igm.univ-mlv.fr/~lecroq/string/node5.html|simulazione]] e {{:informatica:all-a:all09:kr.pdf|note}}|
| 22/04/10 | //Esercitazione// su Heap e Tabelle hash. Un richiamo sull'analisi ammortizzata. | {{:informatica:all-a:all09:luccio_ammortizzata.pdf|Appunti}} su analisi ammortizzata|
| 23/04/10 | **Laboratorio**: tipi di dato //struct// e liste | {{:informatica:all-a:all09:lez_2404.pdf| slides}}|
| 26/04/10 | Alberi: definizione, proprietà e algoritmi ricorsivi. Visite: anticipata, simmetrica, e posticipata. Operazioni dinamiche: inserimento e cancellazione di un nodo. |  |
| 27/04/10 | **Laboratorio**: Richiami sulle liste, Tabelle hash con liste di trabocco. Decsirzione e uso di ''DDD''. |{{:informatica:all-a:all09:lez_2704.pdf| slides}} {{:informatica:all-a:all09:es_2704.pdf| esercizi}}{{:informatica:all-a:all09:sol11.zip|soluzioni}}|
| 29/04/10 | Alberi Binari di Ricerca: definizione, proprietà e algoritmi per la ricerca di una chiave, l'inserimento e la cancellazione di un nodo. Alberi 1-bilanciati e alberi di Fibonacci. Alberi AVL e tecniche di bilanciamento: rotazione oraria e anti-oraria. | Appunti su {{:informatica:all-a:all09:bst.pdf|cancellazione}} e {{:informatica:all-a:all09:delta.pdf|ribilanciamento}}.|
| 30/04/10 | Pile e Code. Grafi: terminologia e notazione. Rappresentazione e chiusura transitiva. Esercizi sugli alberi. | |
| 03/05/10 | Visita BFS: proprietà, algoritmo e dimostrazione di correttezza. //Esercitazione.// |  |
| 04/05/10 | **Laboratorio**: Esercizi sugli alberi binari di ricerca. | {{:informatica:all-a:all09:es_alberi.pdf|esercizi}}{{:informatica:all-a:all09:slides_tree.pdf| slides}}{{:informatica:all-a:all09:sol12.zip|soluzioni}} |
| 07/05/10 | Visita DFS: proprietà, algoritmo, complessità, e dimostrazione di correttezza. DAG e ordinamento topologico.   |  |
| 10/05/10 | **Laboratorio**: Esercitazione su alberi, liste ed heaps.  | {{:informatica:all-a:all09:lez13.pdf|slides}}|
| 11/05/10 | Simulazione della prova di laboratorio | |
| 13/05/10 | Minimum Spanning Trees: Approccio Greedy, e dimostrazione correttezza. Algoritmo di Kruskal. Struttura dati Union-Find. |{{:informatica:all-a:all09:ex_lez13.pdf| Esercizio da svolgere per il prossimo laboratorio}} |
| 14/05/10 | Minimum Spanning Trees: Algoritmo di Prim. | |
| 17/05/10 | Cammini Minimi: Algoritmo di Dijkstra, esempio e dimostrazione di correttezza. | |
| 18/05/10 | **Laboratorio**: Correzione esercizio di auto-valutazione. | {{:informatica:all-a:all09:lez14.pdf| slides}} {{:informatica:all-a:all09:sol_14.zip| soluzioni}} |
| 20/05/10 | Esercitazione su argomenti secondo compitino |  | 
| 21/05/10 | Esercitazione su argomenti secondo compitino |  |