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

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

**Docenti:**  [[http://www.di.unipi.it/~pagli/|Linda Pagli]], [[http://www.di.unipi.it/~rossano/|Rossano Venturini]]


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

**Assistente:**  [[http://zola.di.unipi.it/andrea/|Andrea Farruggia]]

**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:all12:|A.A. 2012/2013]]
   * [[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ì   | 11-13  |  B     | Teoria  |
|Mercoledì | 11-13  |  B     | Teoria  |
|Giovedì   | 16-18  |  H, M  | Laboratorio  |
|Venerdì   | 11-13  |  B     | 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 ^
| 02/04/2014, ore 09 | Primo Compitino | |{{:informatica:all-a:risprimocomp.pdf|}} |
| 02/04/2014, ore 09 | Secondo Compitino| |{{:informatica:all-a:risalg2-4-2014.pdf|}} |
| 28/05/2014, ore 09 |  Appello Straordinario  | |{{:informatica:all-a:ris28-5-2014.pdf|}}
| 09/06/2014, ore 11.00 | Scritto |{{:informatica:all-b:Algo1_090614.pdf|}} |
| 08/07/2014, ore 9.00 | Scritto |{{:informatica:all-a:algo1_08072014.pdf|}}, {{:informatica:all-b:algo1_08072014sol.pdf| Soluzioni}} | {{:informatica:all-a:risalg8-7-2014.pdf|}}| 
| 08/09/2014, ore 9.30 | Scritto |{{:informatica:all-a:algo1_08092014.pdf|}}, {{:informatica:all-b:algo1_08092014sol.pdf| Soluzioni}}|{{:informatica:all-a:risalg8-9-2014.pdf|}}|
| 04/11/2014, ore 9.00 | Scritto |{{:informatica:all-b:algo1_04112014.pdf|}}|{{:informatica:all-a:risalg4-10-2014.pdf|Risultati}}. **Visione scritti**: mercoledì 5 novembre, ore 9:30 nel mio ufficio.  **Orali**: su appuntamento.|     
| 14/01/2015, ore 9.00 | Scritto |{{:informatica:all-a:algo1_14012015.pdf|}},{{:informatica:all-a:algo140115sol.pdf|}} |{{:informatica:all-a:risalg14-1-2015.pdf|Risultati}}. **Visione scritti**: giovedì 15 gennaio, ore 11-13  ufficio Bernasconi.  **Orali**: 22 gennaio ore 9.30 ufficio Pagli.| 
| 12/02/2015, ore 9.00 | Scritto |{{:informatica:all-a:algo1_12020215.pdf|}}|{{:informatica:all-a:risalg12-2-2015.pdf|Risultati}}. **Visione scritti** e **Orali**: 19 gennaio ore 11 ufficio Pagli.| 
Prossime date per le prove di laboratorio:
^ Data ^ Ora ^ Aule ^ Documento ^
| 13/06/2014 | 9:00 |H, I, M |{{:informatica:all-b:lab20140613t1.pdf|Testo 1}} {{:informatica:all-b:lab20140613t2.pdf|Testo 2}} [[http://zola.di.unipi.it/andrea/wp-content/uploads/2014/03/EsameAIL_13062014_1.zip|Test1]] [[http://zola.di.unipi.it/andrea/wp-content/uploads/2014/03/EsameAIL_13062014_2.zip|Test2]]|
| 27/06/2014 | 9:00 |H, I, M |{{:informatica:all-b:testo20140627.pdf|Testo}} [[http://zola.di.unipi.it/andrea/wp-content/uploads/2014/03/EsameAIL_27062014.zip|Test]] |
| 16/07/2014 | 9:00 |H, I, M |{{:informatica:all-b:testo20140716.pdf|Testo}} [[http://zola.di.unipi.it/andrea/wp-content/uploads/2014/03/EsameAIL_16072014.zip|Test]] |
| 15/09/2014 | 9:00 |H, I, M | {{:informatica:all-b:20140915.zip|Testo e test}} |
| 06/11/2014 | 9:00 |I, M | {{:informatica:all-b:testo20141106.pdf|Testo}} e {{:informatica:all-b:testset20141106.zip|test}} |
| 16/01/2015 | 9:00 |H, I, M | {{:informatica:all-b:testo20150116.pdf|Testo}} e {{:informatica:all-b:testset20150116.zip| test}} |
| 17/02/2015 | 9:00 |H, I, M | |
===== 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.
  * **__Sistema di Autovalutazione__**: [[http://vinello.isti.cnr.it:8888]]


===== 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 ^
| 18/02/2014 | Introduzione al corso: intervento del Prof. Roberto Grossi.  |  
| 19/02/2014 | **Laboratorio**: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. {{:informatica:all-b:lezione1.pdf|Lucidi}} {{:informatica:all-b:istruzioni.pdf|Istruzioni per testing}} |
| 20/02/2014 | **Laboratorio**: Funzioni e puntatori. |Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-b:lezione2.pdf|Lucidi}}|
| 21/02/2014 | Concetto di algoritmo, moltiplicazione Egizia e problema delle 12 monete. |{{:informatica:all-b:12monete.pdf|12 monete}} |
| 25/02/2014 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo e caso medio. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo, con esempi.| {{:informatica:all-b:2_asintotica.pdf|Notazione asintotica (dispensa Prof. Luccio)}}; [CGGR]: introduzione;   {{:informatica:all-b:prerequisiti.pdf|Formule utili}}|
| 26/02/2014 | **Laboratorio**: Puntatori, Array, e stringhe. Uso di Valgrind. |Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-b:lezione3.pdf|Lucidi}}|
| 27/02/2014 | **Laboratorio**: Allocazione dinamica della memoria. |{{:informatica:all-a:lezione4.pdf|Lucidi}}||
| 28/02/2014 |Esempi di tasso di crescita asintotico. Array di dimensione variabile.  Selection Sort, proprietà e complessità al caso ottimo, medio e pessimo.| [CGGR]: cap. 1.|
| 04/03/2014 |InsertionSort, analisi e complessità. Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero delle decisioni. Esempi: algoritmo del torneo e del doppio torneo.| [CGGR]: cap. 1 {{:{:informatica:all-b:limitiInf.pdf|limiti inferiori}}|
| 05/03/2014 |Tecnica dell'oracolo per la determinazione del limite inferiore al problema del doppio torneo. Limite inferiore per il problema della ricerca, Ricerca Binaria Ricorsiva, Divide et impera.| [CGGR]: cap. 3 par.3.{{:informatica:all-a:oracolo.pdf|oracolo}}|
| 06/03/2014 | **Laboratorio**:  Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{:informatica:all-b:lezione5.pdf|Lucidi}} |
| 07/03/2014 |Ordinamento ottimo: MergeSort, algoritmo e analisi. Esecizi.  | [CGGR]: cap. 3 par.1.|
| 11/03/2014 | Relazioni di ricorrenza: Teorema principale (con dimostrazione) ed esempi di applicazione.| {{:informatica:all-a:Ricorrenze.pdf| Ricorrenze (dispensa Prof. Luccio)}}.|
| 12/03/2014 | Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato: analisi al caso medio.| [CGGR]: cap 3 e cap 5.|
| 13/03/2014 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-b:lezione6.pdf|Lucidi}} |
| 14/03/2014 | Selezione dell'elemento di rango r in un array (QuickSelect). Moltiplicazione veloce di interi e matrici.|[CGGR]: cap 3 e cap 5.|
| 18/03/2014 | **Esercitazione**: progettazione di algoritmi e analisi di complessità. |{{:informatica:all-b:esercizi2014.pdf|Esercizi}}|
| 19/03/2014 | Code con priorità. Heap di massimo: definizione, proprietà e rappresentazione in memoria. Operazioni Enqueue e Dequeue.  |[CGGR]: cap 2.|
| 20/03/2014 | **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Puzzle: La scala e Corsa di cavalli | {{:informatica:all-b:lezione7.pdf|Lucidi}} {{:informatica:all-b:quicksort_parziale.c.zip|QuickSortParziale}} {{:informatica:all-b:partition.pdf|Partizionamento}} |
| 21/03/2014 |Simulazione di Enqueue e Dequeue. HeapSort: definizione e analisi. |[CGGR]: cap 2.|
| 25/04/2013 | Ordinamento di interi: Counting sort e Radix Sort. |{{:informatica:all-a:cormen-contingradixsort.pdf|[CLR] cap. 8}}|
| 26/03/2014 | **Esercitazione**: progettazione di algoritmi e analisi di complessità. |  
| 27/03/2014 | **Laboratorio**: Qsort e ripasso delle struct|{{:informatica:all-b:lezione8.pdf|Lucidi}}|
| 28/03/2014 | **Esercitazione**: progettazione di algoritmi e analisi di complessità (heap). |  
| 08/04/2014 | **Esercitazione**: Correzione del primo compitino | 
| 09/04/2014 | Introduzione alla Programmazione Dinamica. Distanza tra due stringhe (Edit Distance). | {{:informatica:all-a:pr_din.pdf|Programmazione dinamica (dispensa Prof. Luccio)}} ; [CGGR]: cap 6.|
| 10/04/2014 | **Laboratorio**: Esercizi d'esame: qsort e struct|{{:informatica:all-b:lezione9.pdf|Lucidi}} |
| 11/04/2014 | Alberi: definizioni algoritmi e visite. Algoritimi ricorsivi su alberi binari|[CGGR]: par.3.8 |
| 15/04/2014 | Programmazione Dinamica, ricostruzione della soluzione dell'Edit Distance; Problema dell' Approximate String Matching e della LCS (Sottosequenza di Lunghezza Massima)|[CGGR]:cap 6.  |
| 16/04/2014 | Programmazione Dinamica: Partizione e Zaino. Complessità Pseudopolinomiale|[CGGR]:cap 6.  |
| 17/04/2014 | **Laboratorio**: Liste | {{:informatica:all-b:lezione10.pdf|Lucidi}}|
| 30/04/2014 | Programmazione dinamica: Zaino. Dizionari: alberi binari di ricerca, operazioni di ricerca e inserzione. |[CGGR]:cap 6 e cap.4 |
| 02/05/2014 |Alberi binari di ricerca; cancellazioni. Alberi bilanciati in altezza: alberi di Fibonacci, alberi AVL. Relazione logaritmica tra altezza e numero di nodi. Esempi di rotazioni | [CGGR]: cap.4 |
| 06/05/2014 | Alberi AVL: esempio di inserimento con rotazioni, cancellazione: cenni. Introduzione alle tabelle hash. |[CGGR]: cap 4.|
| 07/05/2014 | Dizionari: realizzazione con tabelle hash (con liste di trabocco e a indirizzamento aperto). |[CGGR]: cap 4.|
| 07/05/2014 | **Esercitazione**: progettazione di algoritmi di programmazione dinamica per problemi su scacchiera; |{{:informatica:all-b:esercizipd-sol.pdf|EserciziPD: soluzioni}}|
| 08/05/2014 | **Laboratorio**: Alberi| {{:informatica:all-b:lezione11.pdf|Lucidi}}|
| 09/05/2014 | **Esercitazione**: progettazione di algoritmi efficienti su alberi binari, ABR e AVL.|{{:informatica:all-b:esercizialberi2014.pdf|EserciziAB}} {{:informatica:all-a:ese9-5-2014.pdf|soluzioni}}|
| 13/05/2013 | Grafi: definizioni, rappresentazione di grafi in memoria. |[CGGR]: cap 7.|
| 14/05/2013 | Grafi: visita in ampiezza e in profondità; classificazione degli archi. |[CGGR]: cap 7.|
| 14/05/2013 | **Esercitazione**: progettazione di algoritmi efficienti (dizionari e alberi). |{{:informatica:all-b:esercizi_su_dizionari_e_alberi.pdf|Esercizi}}, {{:informatica:all-b:soluzioniDiz.pdf|soluzioni}}.|
| 15/05/2014 | **Laboratorio**: Tabelle Hash| {{:informatica:all-b:lezione12.pdf|Lucidi}}|
| 16/05/2013 | Ordinamento topologico di un grafo diretto aciclico (DAG): algoritmo e analisi. |[CGGR]: cap 7.|
| 20/05/2014 | Problemi indecidibili: il problema della fermata. Problemi intrattabili: le torri di Hanoi (algoritmo, analisi del numero di mosse;  generazione  delle stringhe binarie. | [CGGR] {{:informatica:all-b:Capitolo00.pdf|prologo}}.|
| 21/05/2014 | Generazione di tutte le permutazioni. Le classi di complessità P e EXP. Il certificato polinomiale e la classe NP. Nozione di Riduzione Polinomiale. Problemi NP-completi. | [CGGR] {{:informatica:all-b:Capitolo00.pdf|prologo}}; [CGGR]: cap 8.{{:informatica:all-a:kclique-_sat.pdf|}}|
| 21/05/2014 | **Esercitazione**: progettazione di algoritmi efficienti su grafi. | |
| 22/05/2014 | **Laboratorio**: Simulazione prova d'esame| |
| 27/05/2014 | **Esercitazione**: generazione di combinazioni e algoritmi di verifica.| |
| 28/05/2014  |Seconda prova di verifica intermedia.| |