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 - Corso A ======


===== Anno accademico 2016/2017 =====

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

**Docenti Teoria/Esercitazioni:**  [[http://www.di.unipi.it/~ferragin/|Paolo Ferragina]] ([[informatica:all-a:start|corso A]]) e [[http://www.di.unipi.it/~annab/|Anna Bernasconi]] ([[informatica:all-b:start|corso B]])

**Docenti Laboratorio:** [[http://pages.di.unipi.it/marino/|Andrea Marino]], [[http://pages.di.unipi.it/rosone/|Giovanna Rosone]], [[http://pages.di.unipi.it/rossano/|Rossano Venturini]] 

**Impegno:** 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. 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.

**Semestre:** secondo.

**Ricevimento studenti:** lunedì 9-12 e su appuntamento. Eventuali variazioni di orario sulle lezioni e/o ricevimento, o comunicazioni sul corso verranno segnalate tramite Twitter all'account [[https://twitter.com/ferraginateach|@FerraginaTeach]]

**Registro delle lezioni:** si tratta del [[ http://unimap.unipi.it/registri/dettregistriNEW.php?re=180395::::&ri=9142 | registro ufficiale]] che riporta quanto indicato nel seguito.



^           Prossimi Ricevimenti (periodo estivo)           ^
| 30 agosto, ore 9:00, studio Ferragina |
| 4 settembre, ore 9:00, studio Ferragina |





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

^           Orario delle Lezioni           ^^^^
| Martedì  | 11-13  | aula A | Teoria  |
| Martedì  | 14-16  | aule H-I-M | Laboratorio |
| Mercoledì  | 11-13  | aula A | Teoria  |
| Venerdì  | 11-13  | aula A | Teoria  |
 


===== 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.
   * 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à__. 
   * 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. 
   * La prova orale e quella di laboratorio possono essere sostenute in qualunque ordine, ma solo dopo aver superato la prova scritta.
   * Se la prova orale non viene superata, occorre ripetere soltanto quella.
   * Se la prova di laboratorio non viene superata per due volte consecutive, occorre ripetere tutte le prove già sostenute.   
   * La registrazione del voto di esame potrà essere effettuata soltanto dopo che tutte e tre prove sono state superate con successo, e questo potrà avvenire in **qualunque appello durante la prova orale**.


Per avere una idea della tipologia delle prove, si consultino i testi degli anni scorsi.

^ Data ^ Tipo Prova ^ Documento ^ Note ^
| 11/04/2017,\\ ore 14.00\\ Aule A, A1, B, C  | Primo Compitino | {{:informatica:all-a:compitino1.pdf |testo}} | {{:informatica:all-a:algo-compitino_1.pdf |lista dei risultati}} (solo quelli che hanno riportato una votazione >=18).\\ Per la correzione e visione del compito: mercoledì 3 maggio, ore 16 aula C. |
| 01/06/2017,\\ ore 08.30\\ Aule A, A1, B, C | Secondo Compitino | {{ :informatica:all-a:algo_010617.pdf |testo}} e {{ :informatica:all-a:soluzione_compitino_2.pdf |soluzione}} | {{ :informatica:all-a:algoritmica-2017-comp2.pdf |lista dei risultati}} (solo quelli che hanno riportato una votazione >=18 in entrambi i compitini).\\ Orali, venerdì 9 giugno, ore 14, aula A (Polo Fibonacci, si invitano **tutti gli studenti che hanno passato i compitini a partecipare all'orale**).\\ Visione compitino, martedì 6 giugno, ore 9:00, studio Ferragina. |
| 12/06/2017,\\ ore 09.00\\ Aula A | Esame scritto | {{ :informatica:all-a:algo_120617.pdf |testo}}\\ {{ :informatica:all-a:soluzione_appello_12-06-2017.pdf |Soluzione}} | {{ :informatica:all-a:risultati_appello_1.pdf |lista dei risultati}} (solo quelli che hanno riportato una votazione >=18)\\ Orali, giovedì 29 giugno, ore 9, aula A (Polo Fibonacci)  \\ I compiti possono essere visionati nelle ore di ricevimento o venerdì 16 giugno, ore 9-10.  |
| 03/07/2017,\\ ore 09.30\\ Aula A | Esame scritto | {{ :informatica:all-a:algo_030717.pdf |testo}}\\ {{ :informatica:all-a:soluzione_appello_02-07-2017.pdf |Soluzione}} | Orali, giovedì 27 luglio, ore 9, aula A (Polo Fibonacci)  \\ {{ :informatica:all-a:risultati_appello_2.pdf |lista dei risultati}} (solo quelli con votazione >= 16, gli studenti che hanno riportato una votazione pari a 16 se non superano la prova orale devono ripetere lo scritto). |
| 05/09/2017,\\ ore 09.00\\ Aula G | Esame scritto | {{ :informatica:all-a:algo_050917.pdf |testo}}\\ {{ :informatica:all-a:soluzioni_-_05-09-2017.pdf |Soluzione}} | La visione del compito avviene il mercoledì 6 settembre, hr 14:30, studio Ferragina.\\ Orali, lunedì 11 settembre, ore 9, aula A1 (Polo Fibonacci)\\ {{ :informatica:all-a:risultati-appello4.pdf |lista dei risultati}}  |
| 31/10/2017,\\ ore 09.00 | Appello straordinario | testo\\ | Visione del compito e orali (su appuntamento)\\ Risultati: 544006 - insufficiente, 543740 - 23 |
| 19/01/2018,\\ ore 09.00\\ Aula C | Esame Scritto | {{ :informatica:all-a:algo_190118.pdf |testo}} | Risultati: Boccolini 24, Bolla 24.\\ Orali: Lunedì 22 gennaio, ore 14:00, Aula Seminari EST (Dipartimento di Informatica)|
| 05/02/2018,\\ ore 09.00\\ Aula C | Esame Scritto | {{ :informatica:all-a:algo_050218.pdf |testo}} | Risultati: Vannucci 23, Stagno 19, Tumino 18.\\ Orali: Venerdì 16 febbraio, ore 9:00, aula L1.|

**Prossime date per la prova di laboratorio:**

^ Data ^ Ora ^ Aule ^  
| 07/06/2017 | **ore 9.00** | Aule H,I,M |
| 16/06/2017 | **ore 9.00** | Aule H,I,M |
| 07/07/2017 | **ore 9.00** | Aule H,I,M |
| 08/09/2017 | **ore 9.00** | Aule H,I,M |

===== Libri di testo =====

  * **[CLRS]** T. Cormen, C. Leiserson, R. Rivest, C. Stein. //Introduzione agli algoritmi e strutture dati//. McGraw-Hill, Terza edizione, 2010. 
  * **[DFI]** C. Demetrescu, I. Finocchi, G. Italiano. //Algoritmi e strutture dati//. McGraw-Hill, Seconda edizione, 2008. {{:informatica:all-a:parte_libro_dfi_.pdf|Solo pagine 161-165}}.

 

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 consigliamo di installare una macchina virtuale, come [[http://www.virtualbox.org/|VirtualBox]], con una qualunque distribuzione Linux. 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 il corso), per concentrarsi **soltanto** sugli aspetti di //coding// degli algoritmi.
  * **__Sistema di Autovalutazione__**: [[http://algo1617.dijkstra.di.unipi.it/]]





===== 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 "dell'esperto".
  - 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 (Alberi 2-3), 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/2017 | Questioni organizzative: pagina web, canale twitter, laboratori, ricevimento studenti e modalità di esame.\\ Introduzione al corso: nozione di algoritmo, problema, dimensione dell'input, limite inferiore/superiore alla complessità di un problema/algoritmo. Analisi di un problema semiserio: il problema delle 12 monete. Moltiplicazione Egizia. | Capitolo 1 del CLRS, e [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/12monete.pdf | 12 monete]] |
| 21/02/2017 | **Laboratorio:** Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. {{ :informatica:all-a:lezione1.pdf |Slide}} |
| 22/02/2017 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio: caso pessimo, caso ottimo e caso medio. Selection sort //versus// Insertion sort: correttezza e conteggio numero passi. | CLRS: Sezione 2.1 e 2.2. |
| 24/02/2017 | Notazione asintotica: O-grande, Omega e Theta (con accenni a o-piccolo e omega-piccolo). Applicazione alla valutazione della complessità asintotica di Insertion Sort e Selection Sort. | CLRS: Capitolo 3 |
| 28/02/2017 | Paradigma del Divide et Impera. MergeSort: algoritmo, correttezza e analisi di complessità (metodo iterativo e albero di ricorsione). | [CLRS] cap 2: 2.3; cap 4: 4.4. |
| 28/02/2017 | **Laboratorio**: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{ :informatica:all-a:lezione2-1617.pdf |Slide}}|
| 01/03/2017 | Algoritmi polinomiali ed esponenziali al variare delle prestazioni dei computer. Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. | [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/limitiinf.pdf | Note di F. Luccio]] su limiti inferiori. [CLRS] cap 8: 8.1 |
| 03/03/2017 | Enunciato del Teorema dell'esperto, con esempi.  | [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte) |
| 07/03/2017 | Dimostrazione del Teorema dell'esperto per il caso delle potenze. Moltiplicazione veloce di interi (e studiare anche il prodotto tra matrici da note).   | [CLRS]  con {{ :informatica:all-a:esercizi1-2017.pdf |esercizi}}. Note di F. Luccio su {{ :informatica:all-a:prodotto_interi_e_matrici.pdf |moltiplicazione interi e matrici}}.|
| 07/03/2017 | **Laboratorio**:  Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} |
| 08/03/2017 | Ricerca binaria con analisi complessità e correttezza, con simulazione della sua esecuzione. Esempi sull'applicazione del Teorema Master |  |
| 10/03/2017 | Quicksort: descrizione intuitiva, pseudo-codice, versione randomizzata, analisi della complessità al caso pessimo, al caso ottimo e al caso medio. Studiare anche Partizione di Hoare (Problema [CLRS] 7.1) e Partizione con elementi uguali (Problema [CLRS] 7.2)  | [CLRS] cap 7 |
| 14/03/2017 | Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo medio lineare. La struttura dati Heap: proprietà, esempi, Max-Heapify con analisi della complessità e correttezza. | [CLRS] cap 9: 9.1, 9.2 (leggere analisi al caso medio dalla {{ :informatica:all-a:rand_select_comm.pdf |seguente nota}}); cap 6: 6.1 e 6.2.  |
| 14/03/2017 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-b:lezione4-1415.pdf|Slide}} |
| 15/03/2017 | Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. L'algoritmo Heapsort. Code di priorità: definizione, operazioni, realizzazione mediante heap.	| [CLRS] cap 6: 6.3, 6.4, 6.5. |
| 17/03/2017 | Esercizi su Heap e sul calcolo della complessità asintotica di algoritmi ricorsivi	|  |
| 21/03/2017 | Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. | [CLRS] cap 8: 8.2, 8.3.  |
| 21/03/2017 | **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5-1617.pdf |Slide}}|
| 22/03/2017 | Esercitazione su ordinamento e Heap. | {{:informatica:all-b:esercizi3-2015.pdf|Esercizi (heap)}} |
| | Si invitano gli studenti a studiare il Capitolo 10 [CLRS] per ripassare le nozioni di Pila, Coda e Lista, e algoritmi su queste strutture dati elementari. | |
| 24/03/2017 | Dizionari: realizzazione con tabelle a indirizzamento diretto e con tabelle hash; funzioni hash (metodo della divisione e metodo iterativo); gestione delle collisioni mediante concatenamento (analisi al caso pessimo e medio). |[CLRS] cap 11: 11.1, 11.2, 11.3, 11.3.1, 11.3.2. |
| 28/03/2017 | Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica, doppio hashing. |[CLRS] cap 11: 11.4.  |
| 28/03/2017 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-b:lezione6-1415.pdf|Slide}} |
| 29/03/2017 | Alberi e alberi binari: algoritmi ricorsivi su alberi binari, memorizzazione binarizzata. Dizionari: realizzazione con alberi binari di ricerca; interrogazioni (ricerca, minimo, massimo, successore);  inserimento e cancellazione. Analisi della loro complessità in tempo. | [CLRS] cap 10: 10.4. cap 12: 12.1, 12.2, 12.3. | 
| 31/03/2017 | **Lezione non tenuta causa sciopero del personale addetto all'apertura delle aule** | Esercizi svolti: [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/lezione24mar.pdf|lavagna 1]], [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/lezione14apr.pdf|lavagna 2]], [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/lezione21apr.pdf|lavagna 3]]. |
| 04/04/2017 | Visita di alberi binari di ricerca: Pre/in/post visita e loro applicazioni. Esercizi sugli alberi binari di ricerca. | {{:informatica:all-b:esercizialberi2016.pdf|Esercizi su alberi}}, {{:informatica:all-b:esercizi_su_dizionari_e_alberi.pdf|Esercizi su dizionari e alberi}}. |
|04/04/2017 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{:informatica:all-b:lezione9.pdf|Slide}} |
| 05/04/2017 | Esercizi sulla prima parte del corso in preparazione del compitino. |  |
| 11/04/2017 | **Primo compitino**: ore 14, aule A, A1, B, C. |  |
| 21/04/2017 \\ **ore 14-16**|**Laboratorio**: Liste.| {{:informatica:all-a:lezione8-1415.pdf|Slide}}|
| 21/04/2017| Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Inefficienza degli algoritmi ricorsivi su sottoinsiemi di dati con alta sovrapposizione: esempi sui numeri di Fibonacci e sui coefficienti binomiali. |[CLRS] cap 15: 15.4. [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/pd.pdf|Note del Prof.
 Luccio]]. {{:informatica:all-b:esercizipd.pdf|Esercizi sulla Programmazione Dinamica}} | 
| 26/04/2017 | Il problema dell'Edit Distance e la matrice di distanza. Ricostruzione degli allineamenti per l'edit distance. Come migliorare il codice. Il problema della ricerca approssimata di un pattern in un testo. Il problema della determinazione della Longest Common Subsequence.  | {{:informatica:all-b:ED.pdf|Edit Distance (dispense Prof. Luccio)}} | 
| 28/04/2017 | Alberi 2-3: definizione, conteggio numero di nodi e foglie (con dimostrazione). Dizionari: realizzazione con alberi 2-3 (ricerca; inserimento; cancellazione). | [DFI]: {{ :informatica:all-a:23alb-new.pdf |alcune pagine}} (no sezione B-alberi),  | 
| 02/05/2017 | Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. Algoritmi pseudopolinomiali. | [CLRS] cap 16: 16.2, {{:informatica:all-b:ZainoPD.pdf|esercizio 16.2.2 (algoritmo PD per lo Zaino)}}.  {{:informatica:all-b:pseudo.pdf |pseudopolinomialità}} |
| 02/05/2017 | **Laboratorio**: Alberi binari di ricerca.| {{:informatica:all-b:lezione9-1415.pdf|Slide}}|
| 02/05/2017 | Esercizi su Programmazione Dinamica | [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/esercizipd-sol.pdf|soluzioni]]. |
| 03/05/2017 | Generazione delle sequenze binarie e algoritmo enumerativo per il problema dello zaino. Generazione delle permutazioni con esempi. | [CGGR]: {{:informatica:all-b:generaBinPerm.pdf | alcune note su generazione binarie e permutazioni}} |
| 05/05/2017 | Esercizi su generazione binarie e permutazioni.  |  |
| 09/05/2017 | Grafi: definizioni, rappresentazione di grafi in memoria, esempi di problemi su grafi.| [CLRS]: appendice B.4, cap 22: 22.1. |
| 09/05/2016 | **Laboratorio**: Tabelle Hash. | {{:informatica:all-b:lezione10-1415.pdf|Slide}} |
| 10/05/2017 | Grafi: visita in ampiezza (BFS), algoritmo e analisi di complessità, albero di visita in ampiezza e algoritmo PRINT-PATH.| [CLRS] cap 22: 22.2 con lem/teo/cor da 22.1 a 22.5 . |
| 12/05/2017 | Grafi: visita in profondità (DFS), analisi di complessità, classificazione degli archi; ordinamento topologico di grafi diretti aciclici.| [CLRS] cap 22: 22.3, 22.4 con lem/teo/cor 22.7, 22.8 e 22.9 |
| 16/05/2017 | Esercizi su algoritmi efficienti su grafi.|  | 
| 16/05/2017 | **Laboratorio**: Simulazione prova di esame. | | 
| 17/05/2017 | Esercizi su algoritmi efficienti su grafi. | {{:informatica:all-b:eserciziGRAFI.pdf|Esercizi}} |  
| 19/05/2017 | Introduzione alla computabilità, problemi indecidibili e (intrinsecamente) intrattabili. Il problema dell'arresto e della torre di Hanoi, Aritmetica di Presburger. | {{:informatica:all-b:Calc2016.pdf|Calcolabilità}} |
| 22/05/2017 | Teoria della complessità: le classi  P e NP, ed NP-completi. Esempio di riduzione da SAT a Clique. | Su P vs NP si consultino: {{ :informatica:all-a:p-np.pdf |nota 1}} e {{ :informatica:all-a:altre_note.pdf |nota 2}}, quest'ultima nelle pagine 4-6. Per la dimostrazione di NPC per Clique si vedano pag 1-3 di {{ :informatica:all-a:p-np_e_k-clique.pdf |nota 3}} |
| 23/05/2017 | Esercizi. |  |
| 23/05/2017 | **Laboratorio**: Simulazione prova di esame. | |
| 24/05/2017 | Esercizi. |  |
| 28/05/2017 | Esercizi. |  |