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 B  ======





===== Anno accademico 2018/2019 =====














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





**Docenti Teoria/Esercitazioni:**  [[http://pages.di.unipi.it/pisanti/|Nadia Pisanti]],  [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]]  

**Docenti Laboratorio:** [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]], [[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 tre lezioni di didattica frontale in aula e di una esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

**Semestre:** secondo.



===== AVVISO =====

Questa settimana il ricevimento collettivo con gli studenti counselor si terra' **venerdì 3 maggio, 11-13** nella sala riunioni EST del dipartimento di Informatica.

La lezione del giorno 16/4/2019 prevista dalle 11 alle 13 non avrà luogo a causa dell'indisponibilità delle Aule del Polo Didattico Fibonacci, occupate per il concorso per la specializzazione all’insegnamento di sostegno nelle scuole.

**I laboratori del 16/4 avranno luogo regolarmente.** Tuttavia, l'Ateneo chiede agli studenti la cortesia di stazionare il meno possibile nei corridoi prima e dopo la lezione. 

===== Ricevimento Collettivo con i Counselor =====

A partire dal 13 Marzo, ogni Mercoledi' dalle 11 alle 13 nella Sala Riunioni Est del Dipartimento di Informatica si terra' un ricevimento collettivo delle attivita' di Laboratorio tenuto dai quattro studenti counselor assegnati a questo corso.

[[https://docs.google.com/forms/d/e/1FAIpQLSe9YHV8NtwnsNsymVLGuUhoToT5ohH_xk-AjNvpvrk9vAV9mQ/viewform|Feedback per il Counseling]]

[[https://github.com/DrDav/Algo1819/|Materiale didattico di supporto per il laboratorio (preparato dai counselor)]]  
===== Anni accademici precedenti =====

   * [[informatica/all-b/algoB_18:|A.A. 2017/2018]]
   * [[informatica/all-b/algoB_17:|A.A. 2016/2017]]
   * [[informatica/all-b/algoB_16:|A.A. 2015/2016]]
 
===== Gruppi Laboratorio =====
^ Gruppo ^ Aula e orario ^ 
|B1 (da AAA a DE)    | Aula H, lunedì 9:00 - 11:00  |
|B2 (da DEA a MAN)  | Aula M, martedì 14:00 - 16:00  |
|B3  (da MAO a ZZZ)  | Aula H, martedì 14:00 - 16:00 |
 




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


^           Orario delle Lezioni           ^^^^
|Lunedì    |  9-11  |    H     | Laboratorio (gruppo B1)  |
|Martedì    |  11-13  |   E     | Teoria  |
|Martedì   |  14-16  |  H,  M   | Laboratorio (gruppi B2 e B3) |
|Mercoledì  |  14-16  |   E      | Teoria  |
|Giovedì    |  9-11  |    E    | 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 due prove obbligatorie e una facoltativa:

   * Una prova scritta (obbligatoria) 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 (obbligatoria) 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 (facoltativa) sul programma del corso, la cui valutazione finale è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta.
   * La prova di laboratorio puo' essere sostenuta solo dopo aver superato la prova scritta.  
   * Le prove possono essere sostenute in appelli diversi. In particolare, un volta superato lo scritto, la prova di laboratorio puo' essere sostenuta anche in appelli successivi, fermo restando quanto sopra e quanto sotto.
   * Se la prova di laboratorio non viene superata puo' essere ripetuta senza ripetere lo scritto, ma **SE LA PROVA DI LABORATORIO NON VIENE SUPERATA PER DUE VOLTE CONSECUTIVE, OCCORRE RIPETERE ANCHE LO SCRITTO. **
   * La prova orale e' facoltativa (salvo eccezioni motivate dal docente), puo' essere sostenuta solo dopo aver superato la prova scritta e la prova di laboratorio, e puo' dar luogo ad un incremento massimo di 4 punti rispetto al voto dello scritto. Se lo studente non intende sostenere la prova orale, ne' il docente ritiene che debba sostenerla, puo' registrare il voto dello scritto incrementato di 2 punti.
   * Se la prova orale non viene superata, occorre ripetere soltanto quella.

Per avere una idea della tipologia delle prove, si consultino i testi degli anni scorsi.
**Prossime date per la prova scritta:**

^ Data ^ Prova ^ Documenti ^ Avvisi ^
| 01/04/19 | Primo Compitino | {{:informatica:all-b:algo010419.pdf| Testo }}\\  {{:informatica:all-b:algoritmica-b_-_esito-1ocompitino.pdf|   Risultati}} \\ {{:informatica:all-b:solu1compitino.pdf|Soluzione}} | Coloro che devono ancora assolvere gli OFA possono sostenere il compitino come test di autovalutazione, ma l'esito della loro prova non puo' essere considerato valevole come (semi)prova scritta d'esame. |
| 03/06/19 | Secondo Compitino | {{:informatica:all-b:2compitino030619.pdf| Testo }}\\ {{informatica:all-b:algoritmica-b-2ocompitino.pdf| Risultati}} \\ {{:informatica:all-b:Solu2compitino2019.pdf|Soluzione}} | Per visione Compitini, e per Registrazione del voto di chi ha superato la prova di Laboratorio: Venerdi' 7 Giugno ore 12:00 Sala Riunioni Est |
| 24/06/19 | Primo appello | {{:informatica:all-b:Algo240619.pdf| Testo }}\\ {{:informatica:all-b:VotiGiugno2019.pdf| Risultati}}  \\  {{:informatica:all-b:solAppGiugno.pdf|Soluzione}} | Sono ammessi alla prova di laboratorio gli studenti con voto maggiore o uguale a 16. \\ Visione scritti: Mercoledì 26 Giugno, ore 9:00, ufficio Prof.ssa Pisanti |
| 15/07/19 | Secondo appello | {{:informatica:all-b:Algo150719.pdf| Testo }}\\  {{informatica:all-b:algoritmica-b_-_esito-luglio.pdf | Risultati}}\\ {{:informatica:all-b:solAppLuglio.pdf|Soluzione}} | Sono ammessi alla prova di laboratorio gli studenti con voto maggiore o uguale a 16. \\ Visione scritti (e registrazione per chi avesse superato il laboratorio precedentemente): Mercoledì 17 Luglio, ore 9:00, ufficio Prof.ssa Pisanti |
| 6/09/19 | Terzo appello | {{:informatica:all-b:algo050919.pdf| Testo }}\\  {{informatica:all-b:algoritmica-b_-_esito-settembre.pdf | Risultati}}\\ {{:informatica:all-b:SolSett19.pdf|Soluzione}} | Sono ammessi alla prova di laboratorio gli studenti con voto maggiore o uguale a 16. \\ Visione scritti (e registrazione per chi avesse superato il laboratorio precedentemente): Lunedì 9 settembre, ore 9:00, ufficio Prof.ssa Bernasconi |
| 16/01/20 | Quarto appello | {{:informatica:all-a:all16012020.pdf | Testo }}\\  {{informatica:all-b:esito-gennaio-20.pdf | Risultati}}\\ {{:informatica:all-a:solall16_1_20.docx|Soluzione}} | Sono ammessi alla prova di laboratorio gli studenti con voto maggiore o uguale a 16. \\ Visione  dei compiti Lunedì 20 gennaio dalle ore 12 presso ufficio Pagli.\\ Registrazione Lunedì 20 gennaio ore 14:30 presso ufficio Pisanti.|
| 11/02/20 | Quinto appello | {{:informatica:all-b:all11022020.pdf | Testo }}\\  {{:informatica:all-b:votiFeb20ALL.pdf | Risultati}} \\ {{:informatica:all-b:ALL11022020SOL.pdf|Soluzione}} | Sono ammessi alla prova di laboratorio gli studenti con voto maggiore o uguale a 17. \\ Visione  dei compiti: Mercoledì 12 febbraio, ore 12, ufficio Bernasconi.|










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

^ Data ^ Ora ^ Aule ^   


**Prossime date per le prove orali:**
^ Data ^ Ora ^ Aula ^ Note ^ 
===== 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-b:alberi2-3.pdf|Solo pagine 161-166}}.
  * **[CGGR]** P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. //Strutture di dati e algoritmi: progettazione, analisi e programmazione (seconda edizione)//. Pearson, 2012. {{:informatica:all-b:alberibinari.pdf|Solo pagine 87-96}}.
  * **[BFL]** A. Bernasconi, P. Ferragina, F. Luccio. //Elementi di Crittografia //. Pisa University Press, 2015. Solo il capitolo 3.
 

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://algo1819.dijkstra.di.unipi.it/]]





===== Programma del corso =====
  - 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.
  - Cenni di trattabilità (P, NP, NPC, EXP-TIME).
  - 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 ^  
| 18/02/2019  19/02/2019 | **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}} |
| 19/02/2019 | Nozioni di Problema, Algoritmo, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete.|{{:informatica:all-b:12monete.pdf|12 monete}} |
| 20/02/2019 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo, al caso ottimo e al caso medio. Insertion sort: descrizione, pseudocodice, esempio. | [CLRS] cap 1, cap 2: 2.1, 2.2.|
| 21/02/2019 | Insertion sort: analisi di complessità al caso ottimo e pessimo. Invariante di ciclo e dimostrazione di correttezza. Selection sort: pseudocodice, esempio, e analisi di complessità. | [CLRS] cap 2.2.|
| 25/02/2019  26/02/2019| **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.pdf |Slide}} |
| 26/02/2019 | Esercitazione: Invariante di ciclo di SelectionSort, Ricerca Sequenziale e Binaria, Vettore Unimodulare. Per casa: Problema delle 9 monete, sorting di vettore binario in loco. | |
| 27/02/2019 | Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. Caso ottimo e caso pessimo con la notazione asintotica. |[CLRS] cap 3. {{:informatica:all-b:TCScheat.pdf|TCS cheat sheet}} |
| 28/02/2019 | Paradigma del Divide et Impera: descrizione del paradigma, alberi di ricorsione, dimostrazione di correttezza mediante induzione. Esempi (min-max e potenza ennesima). MergeSort: cenno. | [CLRS] cap 2: 2.3, cap 4: introduzione.| 
| 04/03/2019 05/03/2019 | **Laboratorio**:  Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} |
| 05/03/2019 | MergeSort: algoritmo, correttezza, analisi di complessità (metodo iterativo e albero di ricorsione). Esempio. | [CLRS] cap 2: 2.3, cap 4: 4.3 e 4.4.| 
| 06/03/2019 | Esercitazione: soluzione esercizi dati per casa. Mergeinsort. Altri esercizi su vettori. |  | 
| 07/03/2019 | Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Limite inferiore per l'ordinamento per confronti. | [CLRS] cap 8: 8.1. [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/limitiinf.pdf | Note di F. Luccio]] su limiti inferiori.  |
| 11/03/2019 12/03/2019 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-a:lezione4.pdf|Slide}} |
| 12/03/2019 | Enunciato del Teorema dell'esperto, con esempi. Dimostrazione del Teorema dell'esperto per il caso delle potenze esatte. | [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte) | 
| 13/03/2019 | Relazioni di ricorrenza di ordine k. Esercizitazione sul Teorema dell'esperto: algoritmo della Moltiplicazione veloce con analisi della complessità. (Studiare anche prodotto veloce tra matrici.) | {{:informatica:all-a:Ricorrenze.pdf| Ricorrenze}} (dispensa Prof.Luccio: leggere introduzione, sezioni 1 e 3, saltando la sezione 2). {{ :informatica:all-a:prodotto_interi_e_matrici.pdf |moltiplicazione interi e matrici}} (note Prof.Luccio). |
| 16/03/2019 | Quicksort: descrizione intuitiva, pseudo-codice, correttezza e complessita' di Partition. Correttezza di Quicksort. Esempi. | [CLRS] cap 7 |
| 18/03/2019 19/03/2019| **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5.pdf |Slide}}|
| 19/03/2019 | Quicksort: analisi della complessità al caso pessimo, al caso ottimo e al caso medio. Versione randomizzata, e analisi della complessità. | [CLRS] cap 7 |
| 20/03/2019 | La struttura dati Heap: definizione, realizzazione implicita come array, proprieta', costruzione (BuildHeap) con Max-Heapify. Analisi della complessità e correttezza di MaxHeapify. | [CLRS] cap 6: 6.1, 6.2, 6.3.|
| 21/03/2019 | Analisi della complessità e correttezza di BuildHeap. L'algoritmo Heapsort. Esercizi sull'Heap. Code di priorità, operazioni, definizione e realizzazione mediante heap. | [CLRS] cap 6: 6.3, 6.4., 6.5 |  
| 25/03/2019 26/03/2019 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-a:lezione6.pdf|Slide}} |
| 26/03/2019 | Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. | [CLRS] cap 8: 8.2, 8.3.  |
| 27/03/2019 | Esercitazione. Esercizi di ripasso su Divide et Impera, equazioni di ricorrenza e ordinamento .| |
| 28/03/2019 | Esercitazione. Esercizi di ripasso su QuickSort e su heap e heapsort. | |
| 01/04/2019 | **PRIMA VERIFICA INTERMEDIA** Corso B 11-13| |
| 08/04/2019 09/04/2019 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} |
|9/04/2019 | 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.2, 11.2, 11.3, 11.3.1.   {{https://drive.google.com/file/d/1ve9JkUNGV4plfsRH3G1PV5Y3MDgRPvLD/view?usp=sharing|lavagna}} |
|10/04/2019 | Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica. |[CLRS] cap 11: 11.4.  {{https://drive.google.com/file/d/18kO8NoyjedvR8iucUICP7CrhW5FsOFAl/view?usp=sharing|lavagna}}  |
|11/04/2019 | Tabelle hash a indirizzamento aperto: doppio hash. Alberi e alberi binari: visite.|[CLRS] cap 11: 11.4, cap 10: 10.4. {{https://drive.google.com/file/d/16EuMhxkIgzk7cd9SptyVQfwbsEPvl1z0/view?usp=sharing|lavagna}}  {{ :informatica:all-b:EserciziHash.pdf | Esercizi (hash)}} {{ :informatica:all-b:SoluzioniHash.pdf | Soluzioni (hash)}} |
| 15/04/2019 16/04/2019 | **Laboratorio**: Liste monodirezionali e bidirezionali. LUNEDI' gruppo B1, MARTEDI' gruppi B2 e B3| {{ :informatica:all-a:lezione8-1415.pdf |Slide}}|
|16/04/2019 | **LEZIONE NON TENUTA** a causa dell'indisponibilità delle Aule del Polo Didattico Fibonacci, occupate per il concorso per la specializzazione all’insegnamento di sostegno nelle scuole. ||
|17/04/2019 | Algoritmi ricorsivi su alberi binari. Dizionari: realizzazione con alberi binari di ricerca (interrogazioni: ricerca, minimo, massimo, successore, predecessore). |[CLRS] cap  12: 12.1, 12.2.   [CGGR]: {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}}   {{https://drive.google.com/file/d/1cwv8n6cKTC9DLJHJhIiERxy-TTv__V6h/view?usp=sharing|lavagna}} |
| 29/04/2019 30/04/2019 | **Laboratorio**: Tabelle Hash. LUNEDI' gruppo B1, MARTEDI' gruppi B2 e B3| {{ :informatica:all-b:lezionehash.pdf |Slide}}|
|30/04/2019 | Dizionari: realizzazione con alberi binari di ricerca (inserimento e cancellazione). Correzione della prima prova di verifica intermedia. |[CLRS] cap  12: 12.3 {{https://drive.google.com/file/d/1Se297vYwiGO3Q26KmKkcQOKwMdSKsQzE/view?usp=sharing|lavagna}}  |
| 02/05/2019 | **Esercitazione**: Esercizi su  alberi binari e alberi binari di ricerca.| {{ :informatica:all-b:eserciziAlberi2016.pdf | Esercizi (alberi binari)}} {{ :informatica:all-a:ABR2019.pdf | Esercizi (alberi binari di ricerca)}} {{https://drive.google.com/file/d/1SV9gggMdKuQitXNWLDr3ZdKyrDdBY1CH/view?usp=sharing|lavagna}}  {{ :informatica:all-b:SoluzioniABABR.pdf | Alcune altre soluzioni}} |
| 06/05/2019 07/05/2019 | **Laboratorio**: Alberi binari di ricerca. | {{ :informatica:all-a:lezioneabr.pdf |Slide}}|
| 07/05/2019| Alberi AVL: definizione, alberi di Fibonacci, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni; cancellazione: cenni).| [CGGR]: {{:informatica:all-b:AVL.pdf|Alberi AVL}},  {{:informatica:all-b:rotazioniavl.pdf| rotazioni}} {{https://drive.google.com/file/d/1iVO5_93fYfhQ55L1Oy4LEh1NojChmEeF/view?usp=sharing|lavagna}}| 
|08/05/2019 | Grafi: definizioni, rappresentazione in memoria. Grafi: visita in ampiezza (BFS), algoritmo.| [CLRS]: appendice B.4, cap 22: 22.1, 22.2 {{https://drive.google.com/file/d/116PqRGAh-SioY2x5abhZEVwIbRhhutBV/view?usp=sharing|lavagna}}| 
|09/05/2019 | Grafi: visita in ampiezza (BFS), analisi di complessità, proprietà, albero BF e algoritmo PRINT-PATH. Grafi: visita in profondità (DFS), algoritmo, analisi di complessità, foresta DF.| [CLRS]: cap 22: 22.2, 22.3  {{https://drive.google.com/file/d/1VDU2GFKTGVFECSpiYVcd1A3Mc2LfA1-u/view?usp=sharing|lavagna}}  | 
| 13/05/2019 14/05/2019 | **Laboratorio**: Grafi. | {{ :informatica:all-b:lezionegrafi.pdf |Slide}} {{{:informatica:all-b/grafo_bipartito.pdf|Esercizio1}}|
| 14/05/2019 | Grafi: visita in profondità (DFS), classificazione degli archi, ordinamento topologico di grafi diretti aciclici.|[CLRS] cap 22: 22.3, 22.4.  {{https://drive.google.com/file/d/15brzf2VC7VeePXq_0pqVC18u7uBvm-hq/view?usp=sharing|lavagna (versione corretta)}}|
| 15/05/2019 | Esempi di problemi su grafi: clique, ciclo hamiltoniano, ciclo euleriano.   **Esercitazione**: progettazione di algoritmi efficienti su grafi.|{{:informatica:all-b:esercizigrafi19.pdf|Esercizi}} {{https://drive.google.com/file/d/1sw6hl-u6HtqIhmcMuduEparHkDR4MsrZ/view?usp=sharing|lavagna (versione corretta)}} {{https://drive.google.com/file/d/183NuU0VQ6Kl0buwu9zemOOEjrmcgPgpx/view?usp=sharing|altre soluzioni}}|
| 16/05/2019 | Problemi indecidibili e problemi intrattabili. Generazione delle sequenze binarie e delle permutazioni. | {{{:informatica:all-b/calc2019.pdf|Calcolabilità}} {{ :informatica:all-b:thetowersofhanoi.pdf | The Towers of Hanoi: note di Tom Leighton e Ronitt Rubinfeld, MIT, 2006}}  {{:informatica:all-b:binperm.pdf |[BFL]: generazione delle sequenze binarie e delle permutazioni}} [[https://www.youtube.com/watch?v=Q4gTV4r0zRs|Time with class! Let's count!]] {{https://drive.google.com/file/d/1A151G5JNmxyWpWIgyJXpJtCZSKt2EzJZ/view?usp=sharing|lavagna}}|
| 20/05/2019 21/05/2019 | **Laboratorio**: Simulazione prova di esame.|{{ :informatica:all-b:solgrafi.pdf |Slide}} |
| 21/05/2019 | Introduzione alla Programmazione Dinamica (PD). Calcolo dei numeri di Fibonacci. Requisiti di un problema su cui applicare la PD a confronto con il paradigma Divide et Impera. Il problema della Edit Distance: definizione. |{{:informatica:all-b:PD.pdf|Programmazione Dinamica (note di F. Luccio)}} \\ [CLRS] cap 15: 15.3.| 
| 22/05/2019 | Calcolo della Edit Distance con la PD: regola ricorsiva e ricostruzione della soluzione, algoritmo ED. Complessita'. Esempio.|{{:informatica:all-b:ED.pdf|Edit Distance (note di F. Luccio)}}. | 
| 23/05/2019 | Il problema dello Zaino: Tecnica Greedy e Programmazione Dinamica.  Algoritmo enumerativo per il problema dello zaino basato su genera binarie. Algoritmi pseudopolinomiali. | [CLRS] cap 16: 16.2,\\ {{:informatica:all-b:ZainoPD.pdf|Algoritmo PD per lo Zaino}}.\\ [CGGR]: {{:informatica:all-b:pseudo.pdf |pseudopolinomialità}}.  |
| 28/05/2019 | Teoria della complessità: le classi P e NP, i problemi NP-completi. |[BFL]: {{ :informatica:all-b:p-np.pdf | Le classi P, NP e NPC}} \\ {{ :informatica:all-b:p-np-slides.pdf | Lucidi P-NP}} \\ [CLRS] cap 34 |
| 28/05/2019 | **Laboratorio**: esercitazione finale su grafi e alberi (strutture dati, visita DFS, ricerca cicli). |{{ :informatica:all-b:testset.zip |}} |
| 29/05/2019 | **Esercitazione**: Programmazione Dinamica, Certificati Polinomiali, Algoritmi Enumerativi. | |
| 30/05/2019 | **Esercitazione**: esercitazione conclusiva in preparazione della prova scritta.|{{:informatica:all-b:DizAlberi2019.pdf|Esercizi}} {{https://drive.google.com/file/d/1y-8OUKZTx-3Kt3-4KR2VFSz2__BJrj3g/view?usp=sharing|lavagna}}|
DidaWiki

Strumenti Utente

Strumenti Sito

Strumenti Pagina
