Differenze

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

--- informatica:all-a:all12:start [07/02/2013 alle 20:08 (11 anni fa)]
anna bernasconi
+++ informatica:all-a:all12:start [13/02/2014 alle 11:16 (10 anni fa)] (versione attuale)
Linda Pagli [Anni accademici precedenti]
@@ Linea 1: / Linea 1: @@
+====== Algoritmica e Laboratorio - Corso A ======
 ===== Informazioni Generali =====
-**Docente**: Anna Bernasconi
+**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.
@@ Linea 7: / Linea 15: @@
 **Semestre:** secondo.
-**Ricevimento studenti:** martedì 11-13 e su appuntamento.
+**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; |

DidaWiki

Strumenti Utente

Strumenti Sito

Differenze

Strumenti Pagina