====== Algoritmica e Laboratorio - Corso A ======

===== Informazioni Generali =====

**Docenti:**  [[http://www.di.unipi.it/~pagli/|Linda Pagli]], [[http://www.di.unipi.it/~prencipe/|Giuseppe Prencipe]]


(**Docenti corso B:** [[http://www.di.unipi.it/~annab/|Anna Bernasconi]], [[http://www.di.unipi.it/~rossano/|Rossano Venturini]]  )

**Assistente:**  [[http://www.di.unipi.it/~ceccarel/doku.php?id=start/|Diego Ceccarelli]]

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

**Semestre:** secondo.

**Ricevimento studenti:** dopo ogni lezione e su appuntamento.

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.


===== Anni accademici precedenti =====
   * [[informatica:all-a:all11:|A.A. 2011/2012]]
   * [[informatica:all-a:all10:|A.A. 2010/2011]]
   * [[informatica:all-a:all09:|A.A. 2009/2010]]

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

^           Orario delle Lezioni           ^^^^
|Martedì   |  9-11  |   A      | Teoria  |
|Mercoledì | 11-13  |   A      | Teoria  |
|Giovedì   | 14-16  |   H, M   | Laboratorio  |
|Venerdì   | 11-13  |   A      | 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.

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/all11/start|anno scorso]].


^ Data ^ Tipo Prova ^ Documento ^ Note ^
| 03/04/2013, ore 11.00 | Scritto (primo compitino)|{{:informatica:all-b:algo1_030413.pdf|}}|{{:informatica:all-a:risalg3-41-3.pdf|Risultati}}|
| 30/05/2013, ore 9.00 | Scritto (secondo compitino)|{{:informatica:all-b:algo1_300513.pdf}} |{{:informatica:all-a:risalg_30-5-2013.pdf|Risultati}}|
| 12/06/2013, ore 9.00 | Scritto (primo appello)|{{:informatica:all-a:algo1_120613.pdf}}{{:informatica:all-b:soluzioni.pdf|soluzioni}}|{{:informatica:all-a:risalg12-6-13.pdf|Risultati}}|
| 12/07/2013, ore 9.00 | Scritto (secondo appello)|{{:informatica:all-a:algo_120713.pdf|testo}}|{{:informatica:all-a:risalg12-7-13.pdf|risultati}}|
| 9/09/2013, ore 15.00 | Scritto | {{:informatica:all-b:Algo1_090913.pdf}}|{{:informatica:all-a:risalg9-9-13.pdf|risultati}}|Orale: 13/9/2013 ore 9.30 ufficio Pagli|
| 4/11/2013, ore 14.00 | Scritto | {{:informatica:all-b:Algo1_041113.pdf}}|{{:informatica:all-a:risalg4-11-13.pdf|risultati}}| Visione scritti: mercoledì 6 novembre, ore 9:30, ufficio Bernasconi.|
| 21/01/2014, ore 9.30 | Scritto | {{:informatica:all-b:Algo1_210114SOL.pdf}} |{{:informatica:all-a:risalg21-1-14.pdf|}}| Visione scritti: venerdi'ore 11, ufficio Pagli.|
| 7/02/2014, ore 9.30 |Scritto ||{{:informatica:all-a:risalg7-2-14.pdf|}}|Visione scritti: 11/2/2014 ore 15.30, ufficio Pagli.|
Prossime date per le prove di laboratorio:
^ Data ^ Ora ^ Aule ^
| 11/06/2013 | 9:30 |H e M |
| 14/06/2013 | 9:30 |H e M |
| 16/07/2013 | 9:30 |H e M |
| 12/09/2013 | 9:30 |H e M |
| 24/01/2014 | 9:30 |H e M |

Prossime date per le prove orali:
^ Data ^ Ora ^ Aule ^
| 11/06/2013 | dopo il laboratoio |ufficio Pagli |
| 14/06/2013 | 9-13 |aula L |
| 24/06/2013 | 9:30 |ufficio Pagli|
| 16/07/2013 | 11:00 |ufficio Pagli|
| 17/07/2013 | 9.00  |ufficio Pagli|
| 24/01/2014 | 11:00 |ufficio Pagli|
| 11/02/2014 | 15:30 |ufficio Pagli|


===== Libri di testo =====

  * **[CGGR]** P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. //Strutture di dati e algoritmi: progettazione, analisi e programmazione (seconda edizione)//. Pearson, 2012. [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/]]
  
  * **[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


  * **[CLRS]** T. Cormen, C. Leiserson, R. Rivest, C. Stein. //Introduzione agli algoritmi e strutture dati//. McGraw-Hill, Terza edizione, 2010. 

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.

===== Lavagna =====

{{:informatica:all-b:lavagna1.pdf|Primo "quaderno"}}

{{:informatica:all-a:risalg3-41-3.pdf|}}

===== Registro delle Lezioni =====
^ Data ^ Argomento ^ Rif. Biblio ^
| 19/02/2013 | Introduzione al corso. Moltiplicazione Egizia. Nozioni di Algoritmo, Problema, Limite Inferiore. Analisi di un problema semiserio | {{:informatica:all-b:12monete.pdf|appunti}}|
| 20/02/2012 | **Laboratorio**: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. somma == P[b-1) [[http://algoritmica.spox.spoj.pl/ALGLAB2013|Sito Esercitazioni]]|
| 21/02/2012 | **Laboratorio**: Ripasso e esercizi su funzioni e puntatori. |Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{{{:informatica:all-b:lez2.pdf|Lucidi}}|
| 22/02/2013 | Problemi intrattabili: le torri di Hanoi, algoritmo, analisi del numero di mosse. Crescita esponenziale.|[CGGR] {{:informatica:all-b:capitoloonline.pdf|prologo}}; [CGG] cap. 1 |
| 27/02/2012 | **Laboratorio**: Funzioni e passaggio dei parametri. |Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-b:lez3.pdf|Lucidi}}|
| 28/02/2012 | **Laboratorio**: Allocazione dinamica della memoria (malloc) e stringhe. |{{:informatica:all-b:lez4.pdf|Lucidi}} |
| 01/03/2013 | Teoria della calcolabilità. Insiemi numerabili.Esistenza di problemi non decidibili. Il problema dell'arresto |{{:informatica:all-b:calc.pdf|Lucidi}};|
| 05/03/2013 | Rappresentazione degli elementi di un insieme con vettore di appartenenza. Generazione di tutte le stringhe binarie, applicazione a PARTITION. Generazione di tutte le permutazioni, applicazione a HAMILTONIAN CYCLE. Esempi di certificati polinomiali. La classe NP.| [CGGR] {{:informatica:all-b:capitoloonline.pdf|prologo}}; [CGG] cap. 1 |
| 06/03/2013 | Il certificato polinomiale. Nozione di Riduzione Polinomiale. Problemi NP-completi. Il Problema SAT. | [CGGR]: {{:informatica:all-b:capitoloonline.pdf|prologo}}; [CGG]: cap. 1|
| 07/03/2013 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. | {{:informatica:all-b:test_set.zip|File di test per intersezione}} {{:informatica:all-b:test_maxsum.zip|File di test per sottoarray di somma massima}}|
| 08/03/2013 | Esempi di problemi NPC: Problema SAT, Ciclo Hamiltoniano,  k-clique. Esempio di riduzione: da SAT a k-Clique. Il modello RAM e costo delle istruzioni if, for, while. | Una riduzione ({{:informatica:all-a:all10:k-clique.pdf|K-clique}}). [CGG]: cap. 1, {{:informatica:all-a:esercizi0.pdf|}}|
| 12/03/2013 | Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. Array di dimensione variabile.  Selection Sort analisi complessità.| [CGGR]:introduzione e cap. 1; [CGG]: cap. 2; {{:informatica:all-b:prerequisiti.pdf|Formule utili}}|
| 13/03/2013 | Insertion Sort, analisi. Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero delle decisioni e dell'oracolo. Esempi: ordinamento. Algoritmo del torneo e del doppio torneo. | {{:informatica:all-a:all10:lucciolb.pdf|limiti inferiori}} |
| 14/03/2013 | **Laboratorio**: Sottoarray di somma massima lineare, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-b:sommaarray.pdf|Lucidi sottoarray somma massima}} {{:informatica:all-b:arraystrings.pdf|Lucidi Array Stringhe}} {{:informatica:all-b:puzzlelez6.pdf|Puzzle: L'intero mancante}} |
|15/03/2013 |Esercitazione: Limite inferiore per il problema della ricerca con albero di decisione. Soluzione degli esercizi proposti : generazione di tutti i sottoinsiemi di k elementi. Algoritmo di soluzione e verifica della k-clique. Algoritmo per il problema della Subset-Sum.| {{:informatica:all-a:esercizi0sol.pdf|esercizi corretti}} |
| 19/03/2013 | Il problema della ricerca: ricerca binaria ricorsiva; Analisi. Paradigma Divide et Impera. Un algoritmo ottimo di ordinamento di tipo Divide et Impera: MergeSort.| [CGGR]: cap 3; [CGG]: cap. 2; |
| 20/03/2013 | Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Equazioni di ricorrenza:  enunciato teorema principale e esempi.| [CGGR]: cap 3; [CGG]: cap. 2; {{:informatica:all-a:ricorrenze.pdf|ricorrenze}} |
| 21/03/2012 | **Laboratorio**: Quick Sort su interi e su stringhe. Varianti (//pari&dispari//, //3-way partition//).| {{:informatica:all-a:quick_sort_parziale.c.zip|Quicksort parziale}} {{:informatica:all-b:partition.pdf|Pseudocodice Distribuzione}} {{:informatica:all-b:puzzlelez7.pdf|Puzzle: la scala e cavalli}}|
| 22/03/2013 | Randomized-Quicksort: analisi della complessità nel caso medio. Equazioni di ricorrenza:  dimostrazione teorema principale e esempi.| [CGGR]: cap 5; [CGG]: cap. 2; {{:informatica:all-a:esercizi1.pdf|}}  |
| 26/03/2013 | Moltiplicazione veloce di interi e matrici. Esercitazione: progettazione di algoritmi e analisi di complessità.|[CGGR]: cap 3; [CGG]: cap. 2; |
| 27/03/2013 | Selezione dell'erresimo elemento, QickSelect: analisi caso pessimo e caso medio. Esercitazione: progettazione di algoritmi e analisi di complessità.|[CGGR]: cap 3; [CGG]: cap. 2; |
| 3/04/2013 | {{:informatica:all-b:algo1_030413.pdf|Prima prova di verifica intermedia.}}|{{:informatica:all-a:risalg3-41-3.pdf|risultati}} |
| 9/04/2013 | Correzione della prima prova di verifica intermedia.  Code con priorità, Heap come albero binario completo a sinistra, relazione tra numero di nodi e altezza. |[CGGR]: cap 2 ; [CGG]: cap. 8; |
|10/04/2013 | Operazioni Enqueue, First, Dequeue per un Heap di massimo. Complessità. Allocazione implicita in array. HeapSort. |[CGGR]: cap 2 ; [CGG]: cap. 8; |
| 11/04/2012 | **Laboratorio**: Esercizi d'esame: qsort e struct|{{:informatica:all-b:puzzlelez9.pdf|Puzzle: Elemento maggioritario}}|
| 12/04/2012 | Ordinamento di interi: Counting sort e Radix Sort. Introduzione alla Programmazione Dinamica.|{{:informatica:all-a:cormen-contingradixsort.pdf|[CLR] cap. 8}}; {{:informatica:all-a:pr_din.pdf|Programmazione dinamica (dispensa Prof. Luccio)}} ; [CGGR]: cap 6; [CGG]: cap 2; |
| 16/04/2013 | Programmazione Dinamica: Edit Distance, Longest Common Subsequence (introduzione al problema).|{{:informatica:all-a:pr_din.pdf|Programmazione dinamica (dispensa Prof. Luccio)}}; [CGGR]: cap 6; [CGG]: cap 2; |
| 17/04/2013 | Programmazione Dinamica: Longest Common Subsequence, Partizione di un insieme di interi. |[CGGR]: cap 6; [CGG]: cap 2; |
| 18/04/2013 | **Laboratorio**: Liste |{{:informatica:all-b:puzzlelez10.pdf|Puzzle: Ciclo in una lista}}|
| 19/04/2013 | Programmazione Dinamica: Il problema dello Zaino. Pseudopolinomialità. Esercizi sulla programmazione dinamica. |[CGGR]: cap 6; [CGG]: cap 2; {{:informatica:all-b:esercizipd.pdf|Esercizi}}|
| 23/04/2013 | Alberi binari: visite, algoritmi ricorsivi su alberi binari. Alberi con un numero qualsiasi di figli: memorizzazione binarizzata. Dizionari. |[CGGR]: cap 1, cap 3, cap 4; [CGG]: cap 4, cap 5; |
| 24/04/2013 | Dizionari: realizzazione con alberi binari di ricerca. Alberi AVL: definizione. |[CGGR]: cap 4; [CGG]: cap 5; |
| 26/04/2013 | Esercitazione: operazione DecreaseKey in un heap; simulazione di un algoritmo di programmazione dinamica per il problema dello Zaino. Progettazione di algoritmi di programmazione dinamica per problemi su scacchiera.  | {{:informatica:all-a:ese26-4-2012.pdf}}|
| 30/04/2013 | Alberi binari 1-bilanciati: dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni; cancellazione: cenni). |[CGGR]: cap 4; [CGG]: cap 5; |
| 3/05/2013 | Esercitazione: progettazione di algoritmi efficienti su alberi binari, ABR e AVL. |{{:informatica:all-a:ese03-5-2013.pdf|esercizi corretti}}|
| 07/05/2013 | Dizionari: funzioni hash, realizzazione del dizionario con tabelle hash con liste di trabocco e a indirizzamento aperto. Il problema della cancellazione. |[CGGR]: cap 4; [CGG]: cap 5; |
| 08/05/2013 | Dizionari: tabelle hash a indirizzamento aperto: analisi al caso medio; scansione lineare, quadratica, doppio hash. |[CGGR]: cap 4; [CGG]: cap 5; {{:informatica:all-b:16_hash.pdf|tabelle hash (dispensa Prof. Luccio)}};|
| 09/05/2013 | **Laboratorio**: Tabelle Hash | {{:informatica:all-b:hashtable.pdf|Lucidi}} {{:informatica:all-b:puzzlelez12.pdf|Puzzle: Griglia infetta}}|
| 10/05/2013 | Grafi: definizioni, rappresentazione di grafi in memoria; visita in ampiezza. |[CGGR]: cap 7; [CGG]: cap 6; |
| 14/05/2013 | Visita in ampiezza di un grafo: analisi e proprietà. Visita in profondità. Ordinamento topologico di un grafo diretto aciclico.  |[CGGR]: cap 7; [CGG]: cap 6; |
| 15/05/2013 | Ordinamento topologico di un DAG: algoritmo e analisi. Ricerca di cammini minimi su grafi pesati: algoritmo di Dijkstra.  |[CGGR]: cap 7; [CGG]: cap 6; |
| 16/05/2013 | **Laboratorio**: Simulazione della prova di laboratorio|{{:informatica:all-b:prova.pdf|Testo}} {{:informatica:all-b:input.tar|Input}} [[http://www.di.unipi.it/~ceccarel/algo/|Codice sottomesso]]|
| 17/05/2013 | Algoritmo di Dijkstra: simulazione, correttezza e analisi.  |[CGGR]: cap 7; [CGG]: cap 6; |