Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- informatica:all-a:all11:start [15/02/2012 alle 02:20 (13 anni fa)] – creata peppe
+++ informatica:all-a:all11:start [21/02/2013 alle 09:01 (12 anni fa)] (versione attuale) – [Anni accademici precedenti] anna bernasconi
@@ Linea 1: / Linea 1: @@
 ====== Algoritmica e Laboratorio A.A. 2011-2012 ======
-Docente: **Linda Pagli**
+===== 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| |