Differenze

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

--- informatica:all-a:all09:start [17/02/2010 alle 14:35 (15 anni fa)] – Paolo Ferragina
+++ informatica:all-a:all09:start [10/04/2013 alle 19:33 (12 anni fa)] (versione attuale) – [Modalità e Appelli di Esame] Rossano Venturini
@@ Linea 1: / Linea 1: @@
-====== Algoritmica e Laboratorio - Corso A - 2008/2009 ======
+====== Algoritmica e Laboratorio - Corso A - 2009/2010 ======
-====== Informazioni Generali ======
+===== 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.
-^           Ricevimento studenti  ^^^^
+**Informazioni:** News distribuite tramite [[http://twitter.com/FerraginaTeach|Twitter]] con hashtag ''"#algo2010"''.
-|Ferragina    |    16-19  |    Lunedì   |   Stanza 295, Dipartimento di Informatica    |
+**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    |    A     |   Teoria  |
+|Lunedì    |  11-13  |   E      | Teoria  |
-|Martedì   |     9-11    |    A     |    Teoria  |
+|Martedì   |  11-13  |   M      | Laboratorio  |
-|Mercoledì |     9-11    |    A     |    Teoria  |
+|Giovedì |  11-13  |   C      | Teoria  |
-|Giovedì   |     11-13    |    H     |   Laboratorio |
+|Venerdì   |  9-11  |   E      | Teoria  |
 Si pregano gli studenti che dispongono di un portatile di portarlo **in Laboratorio**.
-===== Appelli di Esame=====
+===== 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 ^
-| 07/04/09 | 1° Compitino | {{:informatica:all-a:all09:algo1sol_090407.pdf|testo e soluzione}} | |
+| 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}} |  |
-| 25/05/09 | 2° Compitino | {{:informatica:all-a:all09:algo1sol_090525.pdf|testo e soluzione}} | Possono partecipare soltanto gli studenti che hanno superato con successo (voto >= 18) il primo compitino. |
+| 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}} |  |
-| 28/05/09 | Prova Lab | {{:informatica:all-a:all09:Lab20090528.zip|testo e soluzione}} | Possono partecipare soltanto gli studenti che hanno superato con successo (voto >= 18) **entrambi** i compitini. Laboratori H e M ore 16.|
+| 31/05/2010, ore 15.00 | Prova di Laboratorio | | |
-| 10/06/09 | Appello 1 | {{:informatica:all-a:all09:algo1_090610.pdf|testo dello scritto}} e {{:informatica:all-a:all09:lab20090610.zip|prova di laboratorio con soluzione}} | Prova di Algoritmica ore 9, aule H,I,M,A1,L1. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. |
+| 22/06/2010, ore 14.30 | Scritto | {{:informatica:all-a:all09:algo1_100622sol.pdf|testo con soluzione}}, {{:informatica:all-a:all09:risultati04.pdf|risultati}} | |
-| 26/06/09 | Appello 2 | {{:informatica:all-a:all09:algo1_090626.pdf|testo dello scritto}} e {{:informatica:all-a:all09:lab20090626.pdf|prova di laboratorio}} , {{:informatica:all-a:all09:lab20090626-testcase.zip|casi di test}} | Prova di Algoritmica ore 9, aule A1,D1,E,H,M. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. |
+| 23/06/2010, ore 15.00 | Prova di Laboratorio | | |
-| 14/07/09 | Appello 3 | {{{{:informatica:all-a:all09:algo1sol_090714.pdf|testo dello scritto}} e {{{{:informatica:all-a:all09:lab20090714.pdf|prova di laboratorio}} | Prova di Algoritmica ore 9, aule A,E,H,M. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. |
+| 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}} |  |
-| 11/09/09 | Appello 4 | {{:informatica:all-a:all09:algo1sol090911.pdf|testo dello scritto}} e {{:informatica:all-a:all09:lab20090911.pdf|prova di laboratorio}}  | Prova di Algoritmica ore 9, aule A. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. |
+| 14/07/2010 | Prova di Laboratorio |  | |
-| 11/01/10 | Appello 5 | {{:informatica:all-a:all09:algo1_100111.pdf|testo dello scritto}} e {{:informatica:all-a:all09:lab20100201.pdf|prova di laboratorio}}  | Prova di Algoritmica ore 9. Chi supera la prova scritta, sosterrà la prova di laboratorio alle ore 15 dello stesso giorno, aule H e M. |
+| 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.
-======= Libro di testo =======
+===== Libri di testo =====
+A scelta tra:
-  * **[CGG]** P. Crescenzi, G. Gambosi, R. Grossi. //Strutture di dati e algoritmi: progettazione, analisi e visualizzazione//. Addison-Wesley, 2005.
+  * **[CLR]** T. Cormen, C. Leiserson, R. Rivest, C. Stein. //Introduction to Algorithms//. MIT Press, Third edition, 2009.
-       * Per approfondimenti ed errata: http://www.algoritmica.org/sda/pmwiki.php
+  * **[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:
+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.
@@ Linea 48: / Linea 74: @@
   * **__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 =====
-====== Programma del corso ======
@@ Linea 60: / Linea 84: @@
   - Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
   - Ordinamento di interi: Counting sort, Radix Sort.
-  - Ordinamento di stringhe: ''qsort''-based e multi-key quicksort.
+  - 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
-  - Greedy: Huffman e Interval Scheduling
+  - Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
-  - Strutture dati auto-aggiustanti: MTF. Analisi ammortizzata e competitiva.
-  - Alberi: rappresentazione e visite.
-  - Trie: rappresentazione, ricerca, Lcp e modifica.
   - Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
-  - Algoritmi randomizzati: Quicksort, Karp-Rabin.
+  - 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 ^
-| 23/2/09 | **Laboratorio**: richiami di linguaggio C. Editing, compilazione, debugging. | {{:informatica:all-a:all09:lez1.zip|C code}}|
+| 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}}|
-| 24/2/09 | **Laboratorio**: richiami di linguaggio C. Istruzioni varie e operatori, printf, scanf, vettori| Cap. 2-3, 7.1-7.4 di [KR], {{:informatica:all-a:all09:lez2.zip|C code}}|
+| 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}}|
-| 26/2/09 | **Laboratorio**: richiami di linguaggio C. Puntatori, funzioni e passaggio parametri | Cap. 5 di [KR], {{:informatica:all-a:all09:lez3.pdf|slides}}, {{:informatica:all-a:all09:lez3.zip|C code}}|
+| 23/02/10 | **Laboratorio**: Esercitazione. | {{:informatica:all-a:all09:lez3_230210.pdf|slides}}  |
-| 27/2/09 | **Laboratorio**: richiami di linguaggio C. Allocazione dinamica della memoria (malloc), stringhe, vettori bidimensionali. \\ //Esercizio per casa//: calcolo del bigramma di massima frequenza in una stringa. | Cap. 4 di [KR],{{:informatica:all-a:all09:lez4.pdf|slides}}, {{:informatica:all-a:all09:lez4.zip|C code}}|
+| 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) }}|
-| 2/3/09 | Introduzione al corso: prerequisiti, definizione di algoritmo, modello RAM, problema formale e istanza, dimensione di una istanza, complessità in tempo e spazio, analisi asintotica al caso pessimo e caso medio, numero passi, confronto tra algoritmi.| Sez. 1.4 e 2.1 di [CGG]|
+| 26/02/10 | **Laboratorio**: Stringhe. | {{:informatica:all-a:all09:lez5_260210.pdf| slides}} (svolgere gli esercizi 3 e 4)  |
-| 3/3/09 | Problema della sottosequenza di somma massima: algoritmi e analisi di complessità in tempo al caso pessimo. Classi P, NP e NP-completi (cenni). Risolvere vs Verificare. Un esempio di problema NP-Completo: Subset sum. | Sez. 2.3 di [CGG] |
+| 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.}}|
-| 4/3/09 | Problemi EXP-TIME. Problemi decidibili //vs// indecidibili. Tecnica della diagonalizzazione. Problema della fermata. | Sez. 1.1, 1.2, 1.2.1 e 1.3 di [CGG]. Non fare 1.2.2.|
+| 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)}} |
-| 5/3/09 | **Laboratorio**: Problema del Maggioritario: soluzione quadratica e lineare.\\ //Esercizio per casa//: coding delle 3 soluzioni per il problema della "sottosequenza di somma massima". | {{:informatica:all-a:all09:lez5.pdf|esercizi}}, {{:informatica:all-a:all09:testfile.zip|testfile}}, {{:informatica:all-a:all09:code5.zip|C code}}|
+| 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]]|
-| 9/3/09 | Notazione: O-grande, Omega-grande, o-piccolo, omega-piccolo e theta. Alcuni esercizi sulla notazione e sua interpretazione in termini di complessità di algoritmi e/o problemi. Introduzione al problema dell'ordinamento e algoritmo SelectionSort con analisi della complessità. | Sez. 2.2.1 e pag. 10 dell'appendice dell'errata corrige di [CGG]. |
+| 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}}). |
-| 10/3/09 | 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).| Sez. 2.2.2 e 2.3.1 e 2.4 di [CGG]. Studiare anche questo {{:informatica:all-a:all09:lucciolb.pdf|approfondimento}} dal libro di F. Luccio "La struttura degli algoritmi" (Boringhieri, 1982). |
+| 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]. |
-| 11/3/09 | Tecnica "divide et impera". Relazioni di Ricorrenza e teorema per la loro risoluzione (con dimostrazione). Risoluzione ricorsiva del problema "del massimo" e analisi di complessità. MergeSort: algoritmo, proprietà, e analisi della complessità.| Sez. 2.5.1 e 2.5.3 di [CGG], con teorema e sua dimostrazione alle pagine 10-11 dell'Errata Corrige. |
+| 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}}|
-| 12/3/09 | **Laboratorio**: Lettura di un array da tastiera senza conoscerne la lunghezza: tecnica del //doubling//. Calcolo del numero di elementi distinti in un array ordinato. \\ //Esercizio per casa//: coding di Selection Sort e Insertion Sort. | {{:informatica:all-a:all09:lez6.pdf|esercizi}}, {{:informatica:all-a:all09:testfile6.zip|testfile}}, {{:informatica:all-a:all09:code6.zip|C code}}|
+| 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}}|
-| 16/3/09 | Moltiplicazione veloce di due interi di n cifre. Esercizi sul calcolo della complessità di algoritmi ricorsivi. Calcolo del numero x di occorrenze di un elemento in un vettore parzialmente ordinato di lunghezza n: soluzione O(n), soluzione di costo O(log n + x), soluzione di costo O(logn).    | Sez. 2.5.2 |
+| 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}} |
-| 17/3/09 | Quicksort: proprietà, analisi della complessità (caso medio, ottimo e pessimo) e considerazioni pratiche. Due tecniche di "distribuzione. qsort del C come quicksort + insertionSort  | Sez. 2.5.4 e per altra tecnica di distribuzione (oltre al codice 2.14) studiare anche questi {{:informatica:all-a:all09:altropivot.pdf|appunti}}|
+| 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). |
-| 18/3/09 | Quicksort randomizzato. QuickSelect. Genera Binarie. Genera Permutazioni. | Sez. 1.2.2 |
+| 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)}} |
-| 19/3/09 | **Laboratorio**: Implementazione del Quick Sort.\\ //Esercizio per casa//: coding del Quicksort con three-way partition. | {{:informatica:all-a:all09:lez7.pdf|esercizi}},  {{:informatica:all-a:all09:code7.zip|C code}}|
+| 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}}. |
-| 23/3/09 | Programmazione dinamica e ricorsione con tabulazione (memoization): esempio con i numeri di Fibonacci. Sottosequenza comune più lunga: regola ricorsiva.| Sez. 2.7 tutta |
+| 19/03/10 | Moltiplicazione veloce di due interi di n cifre. Ricerca Binaria: iterativa e ricorsiva, con analisi di complessità. |  |
-| 24/3/09 | Programmazione dinamica: Sottosequenza comune più lunga (lunghezza) -- metodo di riempimento della tabella per riga/colonna/diagonale. Calcolo di una sottosequenza comune avente la lunghezza massima, calcolo della tabella in spazio ridotto (due sole righe). Partizione di un insieme di interi: regola ricorsiva.| |
+| 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** |
-| 25/3/09 | Partizione di un insieme di interi: tabella e calcolo di una soluzione. Problemi NP-completi e algoritmi pseudo-polinomiali. Esercizio su "calcolo del minimo numero di caratteri da inserire in una stringa per renderla palindroma".| |
+| 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}}. |
-| 26/3/09 | **Laboratorio**: Esercizi con qsort su array di interi e stringhe.\\ //Esercizio per casa//: ricerca su un array di stringhe ordinate e esercizio Divide-et-impera.| {{:informatica:all-a:all09:lez8.pdf|esercizi}},  {{:informatica:all-a:all09:code8.zip|C code}}|
+| 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}}  |
-| 30/3/09 | Counting Sort ed esercizi. Esempio di calcolo della tabella per la sottosequenza comune più lunga tra due stringhe.| {{:informatica:all-a:all09:countingsort.pdf|appunti}} prestando attenzione al fatto che nello pseudo-codice gli indici degli array iniziano da 1|
+| 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}}.  |
-| 31/3/09 | Esercizi su Divide-et-impera. Ordinamento dei suffissi di un testo con soluzione più che quadratica.| |
+| 25/03/10 | Counting sort e Radix sort, con valutazione della complessità. |   |
-| 1/4/09 | Ordinamento dei suffissi di un testo con il ''qsort''. Radix sort e analisi della complessità. | {{:informatica:all-a:all09:radixsort.pdf|appunti}}  |
+| 26/03/10 | //Esercitazione pre-compitino.// |   |
-| 2/4/09 | Multi-key Quicksort, e analisi della sua complessità. Fingerprint di Karp-Rabin, analisi, e suo uso nel problema del dizionario di stringhe.  | {{:informatica:all-a:all09:mkqs.pdf|appunti}} su Multi-key quicksort, prestare attenzione al fatto che le stringhe hanno indici da 1 invece che 0, e quindi in classe abbiamo messo l invece di l+1. Per quanto riguarda KR-fingerprint si legga questo estratto di {{:informatica:all-a:all09:10_kr.pdf|libro}}.|
+|    | // Soluzioni esercizi di laboratorio del 23/03: // {{:informatica:all-a:all09:soluzioni2303.zip|codice}} |    |
-| 6/4/09 | Esercitazione pre-compitino.  | |
+| 13/04/10 | Due paradigmi algoritmici: Genera Binarie e Permutazioni, con esempi | {{:informatica:all-a:all09:genera.pdf|appunti per chi possiede il [CLR]}}  |
-| | **Challenge:** E' dato un [[http://www.di.unipi.it/~ferragin/Challenge/testoProva.txt|testo]] che contiene una sottostringa ripetuta due volte e di lunghezza circa 1600 caratteri. Tutte le altre sottostringhe che si ripetono in questo testo hanno una lunghezza inferiore a 300 caratteri. Progettare un algoritmo che scopre quella sottostringa e la stampa a video.\\ **Gruppi di lavoro:** composti da al massimo 2 studenti.\\  **Codice:** Utilizzare questo esempio di [[http://www.di.unipi.it/~ferragin/Challenge/CodiceEsempio.c|programma C]] per poter leggere il testo dal suddetto file.\\ **Come partecipare:** La soluzione --frase ripetuta e codice dell'algoritmo in C-- deve essere spedita via email a ''[email protected]'' entro le ore 20:00 del 14 Aprile 2009. L'email deve avere soggetto "Challenge Corso A", e deve riportare i nomi e le email degli studenti che l'hanno ottenuta.  | Una possibile {{:informatica:all-a:all09:challenge.zip|soluzione}}. Hanno partecipato con successo i gruppi: Ciccarelli-Miglianesi, Guelfi, Zanotto-Sabadin.|
+| 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/4/09 | **Laboratorio**: Le //struct// in ''C''. \\ //Esercizio per casa//: Leggere una stringa da stdin, costruire tutti i suoi //k//-grammi (dove //k// è passato come input), contare le loro frequenze, e poi ordinarli in ordine decrescente di frequenza.    | Sez. 6.1-6.4 di [KR] e {{:informatica:all-a:all09:code9.zip|C code}}. |
+| 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. | |
-| 20/4/09 | Le liste: definizione e codice C. Operazioni di ricerca per chiave e posizione, inserimento e cancellazione. Esercizio su: inclusione tra due liste. Il problema UNION-FIND e sua soluzione efficiente. | Sez. 3.1 e 3.4.1|
+| 19/04/10 | Funzioni hash: metodo della moltiplicazione e della divisione. Tabelle hash con liste di trabocco.  | |
-| 21/4/09 | L'analisi ammortizzata: Union-Find, k-ricerche in un vettore, il contatore binario, array dinamico. L'analisi competitiva: Move-To-Front. | Sez. 3.4.2 e 3.4.3. |
+| 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}}|
-| 23/4/09 | **Laboratorio**: Esercizi con le liste. Creazione di una lista e stampa dei suoi elementi. Ricerca in una lista e Move-To-Front.  | {{:informatica:all-a:all09:lez10.pdf|esercizi}} {{:informatica:all-a:all09:code10.zip|C code}} |
+| 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|
-| 27/4/09 | Algoritmi Greedy: Interval Scheduling e Codice di Huffman. | {{:informatica:all-a:all09:greedy1.pdf|appunti}} su Interval Scheduling e {{:informatica:all-a:all09:greedy2.pdf|appunti}} su Codice di Huffman |
+| 23/04/10 | **Laboratorio**: tipi di dato //struct// e liste | {{:informatica:all-a:all09:lez_2404.pdf| slides}}|
-| 28/4/09 | Codice di Huffman: esempio e dimostrazione di ottimalità. | |
+| 26/04/10 | Alberi: definizione, proprietà e algoritmi ricorsivi. Visite: anticipata, simmetrica, e posticipata. Operazioni dinamiche: inserimento e cancellazione di un nodo. |  |
-| 29/4/09 | Tabelle hash: definizione, proprietà, gestione dei conflitti (liste di trabocco e indirizzamento aperto), con analisi della complessità al caso pessimo e al caso medio. | Sez. 5.1-5.3 |
+| 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}}|
-| 30/4/09 | **Laboratorio**: Esercizi con le tabelle hash con gestione dei conflitti tramite liste di trabocco. | {{:informatica:all-a:all09:lez11.pdf|esercizi}} {{:informatica:all-a:all09:code11.zip|C code}}|
+| 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}}.|
-| 4/5/09 | Alberi: definizione, proprietà e algoritmi ricorsivi. Visite: anticipata, simmetrica, e posticipata. Operazioni dinamiche: inserimento e cancellazione di un nodo. | Tutta la sez. 4.1|
+| 30/04/10 | Pile e Code. Grafi: terminologia e notazione. Rappresentazione e chiusura transitiva. Esercizi sugli alberi. | |
-| 5/5/09 | Alberi Binari di Ricerca: definizione, proprietà e algoritmi per la ricerca di una chiave, l'inserimento e la cancellazione di un nodo. | Sez. 5.4|
+| 03/05/10 | Visita BFS: proprietà, algoritmo e dimostrazione di correttezza. //Esercitazione.// |  |
-| 6/5/09 | Alberi 1-bilanciati e alberi di Fibonacci. Alberi AVL e tecniche di bilanciamento: rotazione oraria e anti-oraria. | Sez. 5.4|
+| 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}} |
-| 7/5/09 | **Laboratorio**: Esercizi con alberi. | {{:informatica:all-a:all09:lez12.pdf|esercizi}} {{:informatica:all-a:all09:code12.zip|C code}} {{:informatica:all-a:all09:eserciziliste.pdf|ulteriori esercizi sulle liste}}|
+| 07/05/10 | Visita DFS: proprietà, algoritmo, complessità, e dimostrazione di correttezza. DAG e ordinamento topologico.   |  |
-| 11/5/09 | Trie: definizione, proprietà, ricerca esatta/prefisso, inserimento di una chiave. Richiami di Code e Pile, con loro implementazione mediante array e lista.  | Sez. 5.6.1, 7.1, 7.3 |
+| 10/05/10 | **Laboratorio**: Esercitazione su alberi, liste ed heaps.  | {{:informatica:all-a:all09:lez13.pdf|slides}}|
-| 12/5/09 | La struttura dati Heap: definizione, proprietà, ricerca, Enqueue, Dequeue, decreaseKey, Heapify. | Sez. 8.1 e 8.2 |
+| 11/05/10 | Simulazione della prova di laboratorio | |
-| 12/5/09 | //Esercitazione// |  |
+| 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}} |
-| 13/5/09 | Costruzione Heap e heapsort. Grafi: terminologia e notazione. | Sez. 8.2.3 e 6.1 |
+| 14/05/10 | Minimum Spanning Trees: Algoritmo di Prim. | |
-| 14/5/09 | **Laboratorio**: Esercizi su Heap e Alberi.\\ E' stata descritta la modalità di svolgimento della prova di laboratorio, il file ''mainCompito.c'', qui in allegato, contiene lo schema di codice C preliminare che verrà distribuito all'inizio di ogni prova. | {{:informatica:all-a:all09:lez13.pdf|esercizi}}, {{:informatica:all-a:all09:testfile13.zip|testfile}}|
+| 17/05/10 | Cammini Minimi: Algoritmo di Dijkstra, esempio e dimostrazione di correttezza. | |
-| 18/5/09 | Grafi: rappresentazione e chiusura transitiva. Visita BFS. | Sez. 6.1.2, 6.1.3, 7.4.1 |
+| 18/05/10 | **Laboratorio**: Correzione esercizio di auto-valutazione. | {{:informatica:all-a:all09:lez14.pdf| slides}} {{:informatica:all-a:all09:sol_14.zip| soluzioni}} |
-| 19/5/09 | Visita DFS. DAG e ordinamento topologico | Sez. 7.4.2, 7.5.1. {{:informatica:all-a:all09:graph.pdf|Note}} dal libro Cormen //et al//, non fare le dimostrazioni del teo 22.7, 22.9 e 22.10. |
+| 20/05/10 | Esercitazione su argomenti secondo compitino |  |
-| 19/5/09 | Esercitazione | ore 16-18 aula E, ore 18-19 prova del //sistema di sottomissione// per la prova in Lab. |
+| 21/05/10 | Esercitazione su argomenti secondo compitino |  |
-| 20/5/09 | Componenti (fortemente) connesse | Sez. 7.5.2|
-| 21/5/09 | Ricevimento studenti | Ore 17, studio Ferragina |