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 e Laboratorio A.A. 2011-2012 ======



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

**Docente**: Linda Pagli

**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.

===== Anno accademico 2011/2012 =====
   * [[informatica:all-a:start|A.A. 2011/2012]] (NB: il corso è unico; per comodità vengono usate le pagine del corso A)
===== Anni accademici precedenti =====

   * [[informatica:all-a:all10:|A.A. 2010/2011]]
   * [[informatica:all-a:all09:|A.A. 2009/2010]]
   * [[informatica:all-a:all08:|A.A. 2008/2009]]

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

^           Orario delle Lezioni           ^^^^
|Martedì   | 14-16  |   A      | Teoria  |
|Mercoledì |  9-11  |   A      | Teoria  |
|Giovedì   | 16-18  | 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/all10/start|anno scorso]].

^ Data ^ Tipo Prova ^ Documento ^ Note ^
| 07/06/2012, ore 09.30 | Scritto|{{:informatica:all-a:algo1_07062012.pdf|}} |{{:informatica:all-a:risalg1-7-6-12.pdf|lista dei risultati}}. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà Mercoledì 13 Giugno alle ore 9 nelle aule H e M; è possibile anche sostenere la prova in altro appello. L'orale sarà il 22 Giugno, alle ore 10 (studio Pagli) |
| 13/06/2012, ore 09.00 | Laboratorio|  {{:informatica:all-a:esame.tgz|Testo e input}} | |
| 26/06/2012, ore 14.30 |Scritto |{{:informatica:all-a:algo1_26062012.pdf|}}| {{:informatica:all-a:risalg1-26-6-12.pdf|lista dei risultati}}. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà Venerdì 29 Giugno alle ore 9:30 nelle aule H e M. Chi non ha superato lo scritto non è ammesso alla prova di laboratorio. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. L'orale sarà il 6 luglio alle ore 10 (studio Pagli). Un numero limitato di studenti potrà sostenere l'orale venerdì alle 11 subito dopo la prova di laboratorio, sempre nell'ufficio Pagli.|
| 29/06/2012, ore 09.30 | Laboratorio|  {{:informatica:all-a:esamegiugno29.tgz|Testo e input}} | |
| 11/07/2012, ore 09.30 |Scritto |{{:informatica:all-a:algo1_11072012.pdf|}}|{{:informatica:all-a:risalg1-11-7-12.pdf|lista dei risultati}}. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà venerdì 13 luglio alle ore 9:00 nelle aule H e M.  Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per venerdì 13 dopo la prova di laboratorio oppure il 19 luglio alle 10 ufficio Pagli.|
| 13/07/2012, ore 09.00 | Laboratorio|   {{:informatica:all-a:esame13072012.tgz|Testo e input}} | |
| 11/09/2012, ore 15 | Scritto | {{:informatica:all-a:algo1_11092012.pdf|}}|{{:informatica:all-a:risalg11-09-12.pdf|lista dei risultati}}. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà il 13 settembre alle ore 9:30 nelle aule H e M.  Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per il 13 alle 15 oppure il 21 settembre alle 10 ufficio Pagli.|
| 13/09/2012, ore 09.30 | Laboratorio|   {{:informatica:all-a:esame20120913.tgz|Testo e input}} | |
| 15/01/2013, ore 9.30 | Scritto{{:informatica:all-a:algo1_150113.pdf|}}| {{:informatica:all-a:risalg15-01-2013.pdf|}}| Coloro che hanno superato lo scritto con un voto ≥16, possono sostenere la prova di laboratorio.  Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per il giorno 23 gennaio alle 9.30 nell'ufficio Pagli oppure il 5 febbraio alle 10 (aula A).|
| 18/01/2013, ore 09.30 | Laboratorio|   {{:informatica:all-a:esame18012013.tar.gz|Testo e input}} | |
| 5/02/2013, ore 9.30 |Scritto{{:informatica:all-a:algo1_050213.pdf|}} |{{:informatica:all-a:risalg5-02-2013.pdf|}} | Coloro che hanno superato lo scritto con un voto ≥17, possono sostenere la prova di laboratorio.  Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per il giorno 11 febbraio alle 9.30 oppure il 14 febbraio alle 9.30 nell'ufficio Pagli.|
| 08/02/2013, ore 09.30 | Laboratorio|  {{:informatica:all-a:esame20130208.pdf|Testo}} | |
===== Libri di testo =====


  * **[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 ^
| 21/02/2012 | Introduzione al corso. Moltiplicazione Egizia. Nozioni di Algoritmo, Problema, Limite Inferiore. Analisi di un problema semiserio | {{:informatica:all-a:all10:lucciolb.pdf|appunti}}|
| 22/02/2012 | Definizioni: problema, istanza, dimensione. Problemi indecidibili, il problema della fermata. Problemi intrattabili: le torri di Hanoi, algoritmo, analisi del numero di mosse. Crescita esponenziale. |Libro [CGG] cap.1|
| 23/02/2012 | **Laboratorio**: Editing e compilazione. Richiami di linguaggio C: Istruzioni varie e operatori, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. {{:informatica:all-a:lez1.pdf|Lucidi}}|
| 24/02/2012 | **Laboratorio**: Ripasso e esercizi su funzioni e puntatori. |Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{:informatica:all-a:lez2.pdf|Lucidi}} {{:informatica:all-a:sol-lez02.zip|Soluzioni}}|
| 28/02/2012 | Definizione classi P, NP, NP-completi, EXPTIME. Esempio di problema in NP: il Sudoku, algoritmo esponenziale. Il certificato polinomiale.| Libro [CGG] cap.1 |
| 29/02/2012 | Nozione di Riduzione Polinomiale. Esempi di problemi NPC: Problema SAT, Ciclo Hamiltoniano,  k-clique. Esempio di riduzione: SAT - k-Clique. | Una riduzione ({{:informatica:all-a:all10:k-clique.pdf|K-clique}}). |
| 01/03/2012 | **Laboratorio**: Puntatori, funzioni e passaggio parametri. | Sez. 4.1-4.5 e 5.1-5.5 di [KR].\\ {{:informatica:all-a:lez3.pdf|Lucidi}} {{:informatica:all-a:sol-lez03.zip|Soluzioni}}| 
| 02/03/2012| **Laboratorio**: Allocazione dinamica della memoria (malloc) e stringhe. |{{:informatica:all-a:lez4.pdf|Lucidi}} {{:informatica:all-a:sol-lez04.zip|Soluzioni}}|
| 06/03/2012 | 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. Considerazioni genrali su algortimi ricorsivi. | Libro [CGG] cap.1 |
| 07/03/2012 |Il modello RAM. Selection Sort e Insertion Sort: proprietà e complessità. Valutazione complessità asintotica al caso ottimo e pessimo. |{{:informatica:all-a:all10:prerequisiti.pdf|Formule utili}}  |
| 08/03/2012 | **Laboratorio**: Sottoarray di somma massima. Redirezione dell'input e //timing// di un programma. | {{:informatica:all-a:sommaarray.pdf|Lucidi}} {{:informatica:all-a:test_maxsum.zip|TestFile}} {{:informatica:all-a:sol05.zip|Soluzioni}} Libro [CGG] Sez.2.3 |
| 09/03/2012 | Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero delle decisioni e dell'oracolo. Esempi: primo e secondo, ordinamento. Algoritmo del torneo e del doppio torneo. | {{:informatica:all-a:all10:lucciolb.pdf|limiti inferiori}} |
| 13/03/2012 | Il problema della ricerca: limite inferiore, ricerca binaria iterativa e ricorsiva, rango. Analisi. Equazioni di ricorrenza. Paradigma Divide et Impera. | Libro [CGG] Sez.2.4 e 2.5 |
| 14/03/2012 | Equazioni di ricorrenza; Teorema principale; Esempi di applicazioni del teorema. | {{:informatica:all-a:ricorrenze.pdf|ricorrenze}} |
| 15/03/2012 | **Laboratorio**: Insertion Sort su interi e stringhe. Ricerca Binaria. L'intero mancante.  | {{:informatica:all-a:arraystrings.pdf|Lucidi}} {{:informatica:all-a:esercizi6.pdf|Esercizi}} {{:informatica:all-a:sol06.zip| Soluzioni}}|
| 16/03/2012 | Moltiplicazione rapida, analisi. Un algoritmo  ottimo di ordinamento di tipo Divide et Impera: MergeSort. | Libro [CGG] Sez.2.5.2 e 2.5.3  |
| 20/03/2012 | Moltiplicazione rapida di matrici, analisi. Esercizi su algortimi ricorsivi di tipo Divide et Impera e calcolo della complessità. | Libro [CGG] Sez.2.6.1  |
| 21/03/2012 | Ordinamento per distribuzione, Quick Sort, analisi del caso medio su istanze equiprobabili. Equazioni di ricorrenza non bilanciate, Quick Select per la selezione del k-esimo elemento.  | Libro [CGG] Sez.2.5.4 + Errata corrige del paragrafo  |
| 22/03/2012 | **Laboratorio**: Quick Sort su interi e su stringhe. Varianti (//pari&dispari//, //3-way partition//). La scala e cavalli.| {{:informatica:all-a:esercizi7.pdf|Esercizi}} {{:informatica:all-a:quick_sort_parziale.c.zip|Quicksort parziale}} {{:informatica:all-a:testfiles.tgz|La scala testfile}} {{:informatica:all-a:sol_lez07.zip|Soluzioni}}| 
| 23/03/2012 | Code di priorità. Definizione di Heap, operazioni Enqueue, Dequeue e Read per un Heap di massimo, Complessità. Allocazione implicita in array. Riorganizza Heap. | Libro [CGG] Sez.8.1 e 8.2  |
| 27/03/2012 | Code di priorità. Creazione dell'Heap in tempo lineare, Heap Sort, analisi. Introduzione alla Programmazioen Dinamica| Libro [CGG] Sez.8.2.3  {{:informatica:all-a:pr_din.pdf|Programmazione Dinamica}} |
| 28/03/2012 | Algoritmi di programmazione dinamica per l'Edit Distance e la Longest Common Subsequence. Analisi e ricostruzione delle soluzioni | Libro [CGG] Sez.2.7 e 2.7.1 |
| 29/03/2012 | **Laboratorio**: Funzione //qsort//. Esercizi su stringhe e diversi ordinamenti. Il pirellone.| {{:informatica:all-a:qsort.pdf|Lucidi}} {{:informatica:all-a:esercizi8.pdf|Esercizi}} {{:informatica:all-a:code8.zip|Soluzioni}}|
| 30/03/2012 | Esercitazione scritta. Discussione e soluzione durante la lezione del 17/4.   | {{:informatica:all-a:eserctizion_scritta.pdf|esercitazione_scritta}}| 
| 12/04/2012 | **Laboratorio**: Esercizi con le //struct// e //qsort//. Elemento maggioritario e due uova.| {{:informatica:all-a:struct.pdf|Lucidi}} {{:informatica:all-a:esercizi9.pdf|Esercizi}} {{:informatica:all-a:sol9.zip|Soluzioni}}|
| 13/04/2012 |Counting Sort e Radix Sort. | {{:informatica:all-a:cormen-contingradixsort.pdf|[CLR] cap. 8}}  |
| 17/04/2012 | Esercitazione. Discussione e soluzione della esercitazione scritta del 12/04/2012   | | 
| 18/04/2012 | Programmazione dinamica per problemi difficili: Partizione e Zaino. Pseudopolinomialità.| Libro [CGG] Sez.2.7.2, 2.7.3 e 2.7.4 |
| 19/04/2012 | **Laboratorio**: Esercizi liste. Ciclo in una lista.|{{:informatica:all-a:list.pdf|Lucidi}} {{:informatica:all-a:esercizi10.pdf|Esercizi}} {{:informatica:all-a:sol10.zip|Soluzioni}}|
| 20/04/2012 | Definizione di problemi NP-hard. Riduzione polinomiale da Partizione a Zaino. Algoritmo di programmazione dinamica per Zaino. Introduzione alle strutture con puntatori: liste e alberi. | Libro [CGG] Sez. 9.1 e 9.2.4|
| 24/04/2012 | Trasformazione da albero ordinato a albero binario. Allocazione in memoria di alberi binari. Alberi binari di ricerca e operazioni del dizionario | Libro [CGG] Sez. 4.1 e 4.3 e 4.3.1 Sez 5.1, 5.2, 5.4.1|
| 26/04/2012 | **Laboratorio**: Esercizi alberi binari di ricerca. Orco e hobbit.|{{:informatica:all-a:alberi.pdf|Lucidi}} {{:informatica:all-a:esercizi11.pdf|Esercizi}} {{:informatica:all-a:sol11.zip|Soluzioni}}|
| 27/04/2012 | Alberi binari di ricerca bilanciati in altezza. Alberi AVL, alberi di Fibonacci come caso pessimo. Altezza logaritmica degli AVL. Operazione di inserzione, rotazioni semplice e doppia.| Libro [CGG] Sez. 5.4.2 {{:informatica:all-a:binet.pdf|La formula di Binet}}|
| 02/05/2012 | Alberi AVL: cancellazione. Tabelle hash, funzioni hash, organizzazione con liste di trabocco, analisi. Open hash: scansione lineare, agglomerati. | Libro [CGG] Sez. 5.3, 5.3.1 |
| 03/05/2012 | **Laboratorio**: Esercizi Tabelle Hash. Griglia infetta.|{{:informatica:all-a:hashtable.pdf|Lucidi}} {{:informatica:all-a:esercizi12.pdf|Esercizi}}|
| 04/05/2012 | Tabelle hash, indirizzamento aperto, scansione lineare: analisi, fenomeno degli agglomerati. Scansione quadratica, Doppio hash. Esempio.| Libro [CGG] Sez.  5.3.2 |
| 08/05/2012 | Esercitazione su alberi binari.| |
| 09/05/2012 | Grafi: Definizioni e rappresentazione con matrice di adiacenza e liste di adiacenza| Libro [CGG] Sez.  6.1.1, 6.1.2 |
| 10/05/2012 | **Laboratorio**: Simulazione di una prova di esame.|{{:informatica:all-a:prova20120510.tgz|Esercizio}}|
| 11/05/2012 | Grafi: Visita BFS, albero BFS, teorema dei cammini minimi; visita DFS, albero DFS e classificazione degli archi. | Libro [CGG] nuova edizione {{:informatica:all-a:visite.pdf|}} |
| 15/05/2012 | Grafi orientati aciclici: Ordinamento Topologico. Il problema del routing. Grafi pesati con pesi positivi: algoritmo di Dijstra per i cammini minimi. | Libro [CGG] Sez. 7.5.1, 8.3, 8.3.1 |
| 16/05/2012 | Algoritmo di Dijstra: esempio completo, dimostrazione di correttezza, analisi con implementazione di coda a Heap. | Libro [CGG] Sez.  8.3.2 e 8.2.2|
| 17/05/2012 | Richiami sulle tabelle hash. Studio di una legge di scansione quadratica, eliminazione con spostamento nell'open hash a scansione lineare. Esempi di applicazioni delle tecniche di hashing.| |
| 18/05/2012 | Problema del minimo albero di copertura. Algortimo di Kruskal. Union-Find con liste disgiunte. | Libro [CGG] Sez.  8.4.1, 8.4.2 e 3.4.1|
| 22/05/2012 | Problema del minimo albero di copertura. Algortimo di Jarnik-Prim, complessità, esempi. | Libro [CGG] Sez.  8.4.3|
| 23/05/2012 | Esercitazione su grafi| |
| 24/05/2012 | Esercitazione di riepilogo| |