====== Algoritmica e Laboratorio - Corso B ====== ===== Anno accademico 2016/2017 ===== ===== Informazioni Generali ===== **Docenti Teoria/Esercitazioni:** [[http://www.di.unipi.it/~annab/|Anna Bernasconi]] ([[informatica:all-b:start|corso B]]) e [[http://www.di.unipi.it/~ferragin/|Paolo Ferragina]] ([[informatica:all-a:start|corso A]]) **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 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. **Ricevimento studenti:** mercoledì, 11-13, ufficio BERNASCONI (per ricevimento in orari diversi da quanto previsto inviare e-mail a anna.bernasconi@unipi.it), fino a mercoledì 14 giugno. Dal 19 giugno il ricevimento sarà SOLO SU APPUNTAMENTO. ===== Anni accademici precedenti ===== * [[informatica/all-b/algoB_16/start|A.A. 2015/2016]] * [[informatica/all-b/algoB_15/start|A.A. 2014/2015]] * [[informatica/all-b/algoB_14/start|A.A. 2013/2014]] ===== Orario Lezioni ===== ^ Orario delle Lezioni ^^^^ |Lunedì | 9-11 | A | Teoria | |Martedì | 16-18 | H, I, M | Laboratorio | |Mercoledì | 14-16 | A | Teoria | |Giovedì | 9-11 | 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. * 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 E 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 GIA' SOSTENUTE. ** * Chiaramente la registrazione del voto di esame potrà essere effettuata soltanto dopo che tutte e tre prove sono state superate con successo. Per avere una idea della tipologia delle prove, si consultino i testi dell'[[.algoB_16:|anno scorso]]. **Prossime date per la prova scritta:** ^ Data ^ Tipo Prova ^ Documento ^ Note ^ | 11/04/2017 | Primo compitino | {{ :informatica:all-b:algoritmica-11042017.pdf |testo}} | {{ :informatica:all-b:voti110417.pdf |lista dei risultati}}.\\ **Correzione e visione scritti**: venerdì 21 aprile, ore 14, aula A.| | 11/04/2017 | Appello Straordinario | {{ :informatica:all-b:appellostraordinarioaprile.pdf | testo}} | {{ :informatica:all-b:ris11-4-17.pdf |lista dei risultati}}\\ Contattare la Prof.ssa Linda Pagli per visione scritti e prove orali. | | 01/06/2017,\\ **ore 08.30** | Secondo compitino | {{ :informatica:all-a:algo_010617.pdf |testo}} e {{ :informatica:all-a:soluzione_compitino_2.pdf |soluzione}} | {{ :informatica:all-b:risultaticompitini.pdf |lista dei risultati}}.\\ **Visione compitino: martedì 6 giugno, ore 9:00, aula C** | | 12/06/2017,\\ ore 09.30 | Primo appello | {{ :informatica:all-b:algo_120617.pdf |testo}} e {{ :informatica:all-b:algo_120617sol.pdf |soluzione}} | {{ :informatica:all-b:appellogiugno2017.pdf |lista dei risultati}}.\\ **Visione scritto: giovedì 15 giugno, ore 9:00, aula F1** | | 3/07/2017,\\ ore 09.30 | Secondo appello | {{ :informatica/all-a/algo_030717.pdf |testo}} e {{ :informatica/all-a/soluzione_appello_02-07-2017.pdf |soluzione}} | {{ :informatica:all-b:appelloluglio2017.pdf |lista dei risultati}}.\\ **Visione scritto: mercoledì 5 luglio, ore 9:00, ufficio BERNASCONI** | | 5/09/2017,\\ ore 09.00 | Terzo appello |{{ :informatica:all-a:algo_050917.pdf |testo}} e {{ :informatica:all-a:soluzioni_-_05-09-2017.pdf |Soluzione}} |{{ :informatica:all-b:appellosettembre2017.pdf |lista dei risultati}}.\\ **Visione scritto**: giovedì 7 settembre, ore 9:30, ufficio BERNASCONI \\ **Orali**: giovedì 7 settembre e lunedì 11 settembre, ore 10:00, ufficio BERNASCONI, obbligatorio iscriversi (via email)| | 31/10/2017,\\ ore 09.00 | Appello straordinario | {{ :informatica:all-b:algo_311017.pdf |testo}} | **Visione del compito e orali**: su appuntamento, a partire da lunedì 6 novembre. \\ **Risultati**: \\ 516639: 18 \\ 520333: 18 \\ 557687: 21 | | 19/01/2018,\\ ore 09.00 | Quarto appello |{{ :informatica:all-b:Algo_190118.pdf |testo}} | **Visione del compito e orali**: martedì 23 gennaio, ore 10, ufficio BERNASCONI (oppure su appuntamento). \\ **Risultati**: \\ 519061: 18 \\ 531391: 18 \\ 550743: 24 \\ 561515: ins| | 05/02/2018,\\ ore 09.00 | Quinto appello |{{ :informatica:all-b:Algo_050218.pdf |testo}} | **Visione del compito e orali**: mercoledì 7 febbraio, ore 10, ufficio BERNASCONI (oppure su appuntamento). \\ **Risultati**: \\ 519061: 21 \\ 544935: 21 \\ 545289: 19| **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 | **Prossime date per le prove orali:** ^ Data ^ Ora ^ Aula ^ Note ^ | 06/06/2017 | **dalle ore 9:30** | aula C | obbligatorio iscriversi (via email) | | 07/06/2017 | **dalle ore 11:30** | ufficio BERNASCONI| obbligatorio iscriversi (via email) | | 08/06/2017 | **dalle ore 8:30** | aula C1 | obbligatorio iscriversi (via email) | | 15/06/2017 | **dalle ore 9:00** | ufficio BERNASCONI | obbligatorio iscriversi (via email) | | 26/06/2017 | **dalle ore 9:00** | ufficio BERNASCONI | obbligatorio iscriversi (via email) | | 5/07/2017 | **dalle ore 9:30** | ufficio BERNASCONI | obbligatorio iscriversi (via email) | | 24/07/2017 | **dalle ore 9:30** | ufficio BERNASCONI | obbligatorio iscriversi (via email) | | 7/09/2017 | **dalle ore 10:00** | ufficio BERNASCONI | obbligatorio iscriversi (via email) | | 11/09/2017 | **dalle ore 10:00** | ufficio BERNASCONI | obbligatorio iscriversi (via email) | ===== 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://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 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 (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 ^ | 20/02/2017 | Presentazione del corso. Moltiplicazione Egizia: algoritmo e analisi. Analisi di un problema semiserio: il problema delle 12 monete.|{{: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, al caso pessimo, al caso ottimo e al caso medio. Insertion sort: correttezza e analisi di complessità (tempo e numero di confronti) al caso ottimo, medio e pessimo. Selection sort: analisi di complessità (numero di confronti).| [CLRS] cap 1, cap 2: 2.1, 2.2.| | 23/02/2017 | Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. |[CLRS] cap 3. {{:informatica:all-b:TCScheat.pdf|TCS cheat sheet}} {{:informatica:all-b:esercizi0-2017.pdf|Esercizi}}| | 27/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: introduzione, 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}}| | 1/03/2017 | Ricerca binaria. Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. | [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. | | 2/03/2017| Limite inferiore per l'ordinamento per confronti. Relazioni di ricorrenza: Teorema dell'esperto (Teorema principale) con esempi di applicazione. Dimostrazione del teorema (solo per potenze esatte).| [CLRS] cap 8: 8.1, cap 4: 4.5, 4.6.1.| | 6/03/2017| Moltiplicazione veloce di interi di //n// cifre. **Esercitazione**: applicazione del Teorema dell'esperto e analisi di complessità.|{{ :informatica:all-a:prodotto_interi_e_matrici.pdf |Note di F. Luccio}} e di {{ :informatica:all-b:moltveloce.pdf|R. Grossi}} sulla moltiplicazione veloce di interi e matrici. | |7/03/2017 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} | |8/03/2017| **Esercitazione**: progettazione di algoritmi e analisi di complessità.|{{:informatica:all-b:Esercizi1-2017.pdf|Esercizi (ricorrenze, ricerca, ordinamento, divide et impera)}} | |9/03/2017 | Quicksort: proprietà, pseudocodice e analisi della complessità nel caso ottimo e pessimo. Discussione sul costo nel caso medio: analisi delle prestazioni per ripartizioni di proporzionalità costante. Quicksort randomizzato: discussione e pseudocodice. | [CLRS] cap 7: 7.1, 7.2, 7.3| |13/03/2017 | Quicksort randomizzato: analisi della complessità nel caso medio. Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo atteso lineare.| [CLRS] cap 7: 7.4.2, cap 9: 9.1, 9.2 (senza analisi nel caso medio). {{:informatica:all-b:quicksort.pdf|Numero di confronti di Randomized-Quicksort (Note di F.Luccio)}}| |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 | Heap: definizione, realizzazione implicita come array, proprietà, conservazione della proprietà di heap: procedura Max-Heapify. Costruzione di un heap in tempo lineare: algoritmo Build-Max-Heap. |[CLRS] cap 6: 6.1, 6.2, 6.3.| |16/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.| |20/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**: progettazione di algoritmi e analisi di complessità.|{{:informatica:all-b:esercizi3-2015.pdf|Esercizi (heap)}}| |23/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.|[CLRS] cap 10 (tutto), cap 11: 11.1, 11.2, 11.3, 11.3.1.| |27/03/2017 | Gestione delle collisioni mediante concatenamento: analisi al caso medio. Tabelle hash a indirizzamento aperto: inserimento, ricerca, cancellazione; scansione lineare, scansione quadratica, doppio hashing; analisi al caso pessimo e medio (ricerca senza successo).|[CLRS] cap 11: 11.2, 11.4. {{:informatica:all-b:hash.pdf|Tabelle hash (Note di F.Luccio)}}| |28/03/2017| **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-b:lezione6-1415.pdf|Slide}} | |29/03/2017 | Tabelle hash a indirizzamento aperto: analisi al caso medio di inserimento e ricerca con successo. Alberi binari: visite.|[CLRS] cap 10: 10.4, cap 11: 11.4. | |30/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, predecessore).| [CLRS] cap 10: 10.4, cap 12: 12.1, 12.2. [CGGR]: {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}} {{:informatica:all-b:esercizialberi2016.pdf|Esercizi (alberi e alberi binari)}}| |3/04/2017 | Dizionari: realizzazione con alberi binari di ricerca (inserimento e cancellazione). **Esercitazione**: progettazione di algoritmi efficienti (dizionari, alberi binari, alberi binari di ricerca). | [CLRS] cap 12: 12.3. {{:informatica:all-b:alberihash2017.pdf|Esercizi (dizionari, alberi binari, alberi binari di ricerca)}}| |04/04/2017 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{:informatica:all-b:lezione9.pdf|Slide}} | |5/04/2017 |**Esercitazione**: Esercizi sulla prima parte del corso in preparazione del compitino.|Esercizi svolti: {{ :informatica:all-b:lezione24mar.pdf |array}}, {{ :informatica:all-b:alberi-diz.pdf |alberi e dizionari}} | |11/04/2017|**Primo compitino**: ore 14, aule A, B, C, G, A1|{{ :informatica:all-b:algoritmica-11042017.pdf |testo}} | |20/04/2017| Alberi 2-3: definizione, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi 2-3 (ricerca; inserimento; cancellazione).| [DFI]: {{ informatica:all-b:alberi2-3.pdf |Alberi 2-3}} | |21/04/2017 \\ **ore 14, aula A**|Correzione del primo compitino e visione scritti| | |21/04/2017 \\ **ore 16-18**|**Laboratorio**: Liste.| {{:informatica:all-a:lezione8-1415.pdf|Slide}}| |24/04/2017| **Lezione rinviata a venerdì 28 aprile, ore 14, aula A.** | | |26/04/2017 | Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva. |{{:informatica:all-b:PD.pdf|Programmazione Dinamica (note di F. Luccio)}} \\ [CLRS] cap 15: 15.4.| |27/04/2017 | LCS: ricostruzione della soluzione, algoritmi LCS-LENGTH e PRINT-LCS. Il problema della Edit Distance: definizione, regola ricorsiva e ricostruzione della soluzione, algoritmo ED.|{{:informatica:all-b:ED.pdf|Edit Distance (note di F. Luccio)}}. [CLRS] cap 15: 15.4. | | 28/04/2017 | Edit Distance: algoritmo ALLINEA. Studiare anche il problema della ricerca approssimata di un pattern in un testo sulle {{:informatica:all-b:ED.pdf|note di F. Luccio}}. \\ **Esercitazione**: Programmazione Dinamica.| {{:informatica:all-b:esercizipd2017.pdf|Esercizi sulla Programmazione Dinamica}} {{:informatica:all-b:esercizipd-sol.pdf|Soluzioni}} {{:informatica:all-b:simulazioni.pdf|Soluzioni (simulazioni)}}| |2/05/2017 | **Laboratorio**: Alberi binari di ricerca.| {{:informatica:all-b:lezione9-1415.pdf|Slide}}| |3/05/2017 | Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. Generazione delle sequenze binarie e algoritmo enumerativo per il problema dello zaino. Algoritmi pseudopolinomiali.| [CLRS] cap 16: 16.2, {{:informatica:all-b:ZainoPD.pdf|Algoritmo PD per lo Zaino}}. [BFL]: {{:informatica:all-b:binperm.pdf |generazione delle sequenze binarie e delle permutazioni}}. [CGGR]: {{:informatica:all-b:pseudo.pdf |pseudopolinomialità}}. \\ {{:informatica:all-b:lezione11mag.pdf|Appunti AA 2015/16}}| |4/05/2017 | Generazione delle permutazioni. \\ **Esercitazione**: dizionari. | | |8/05/2017 | **Esercitazione**: programmazione dinamica, sequenze binarie e permutazioni. | {{:informatica:all-b:esercizipdbinperm.pdf |Esercizi}} {{:informatica:all-b:partizionepd.pdf|Partizione di un insieme di interi}} {{ :informatica:all-b:partitionen.pdf| Algoritmo enumerativo}}| | 09/05/2017 | **Laboratorio**: Tabelle Hash. | {{:informatica:all-b:lezione10-1415.pdf|Slide}} | |10/05/2017 | Grafi: definizioni, rappresentazione di grafi in memoria, esempi di problemi su grafi.| [CLRS]: appendice B.4, cap 22: 22.1. | | 11/05/2017 | Grafi: visita in ampiezza (BFS), algoritmo e analisi di complessità e correttezza.| [CLRS] cap 22: 22.2 con lem/teo/cor da 22.1 a 22.5. | | 15/05/2017 | Grafi: albero di visita in ampiezza e algoritmo PRINT-PATH; visita in profondità (DFS): analisi di complessità, proprietà. | [CLRS] cap 22: 22.3 con lem/teo/cor 22.7, 22.8 e 22.9. | | 16/05/2017 | **Laboratorio**: Simulazione prova di esame. | | | 17/05/2017 | Grafi: visita in profondità e classificazione degli archi; ordinamento topologico di grafi diretti aciclici. | [CLRS] cap 22: 22.3, 22.4 con lem/teo/ 22.10, 22.11 e 22.12. | | 18/05/2017 | **Esercitazione**: progettazione di algoritmi efficienti su grafi.| {{ :informatica:all-b:esercizigrafi2017.pdf | Esercizi}} | | 22/05/2017 | Introduzione alla computabilità: problemi indecidibili, il problema dell'arresto. Problemi intrattabili: le Torri di Hanoi.| {{ :informatica:all-b:appunticalcolabilita2017.pdf | Lucidi 2017}} {{ :informatica:all-b:thetowersofhanoi.pdf | The Towers of Hanoi: note di Tom Leighton e Ronitt Rubinfeld, MIT, 2006}}| | 23/05/2017 | **Laboratorio**: Simulazione prova di esame. | | | 24/05/2017 | Teoria della complessità: le classi P e NP, i problemi NP completi (**intervento di Fabrizio Luccio**). |[BFL]: {{ :informatica:all-b:p-np.pdf | Le classi P, NP e NPC}} {{ :informatica:all-b:npc.pdf | Riduzioni polinomiali e problemi NP completi}}| | 25/05/2017 | **Esercitazione**: certificati polinomiali e algoritmi di verifica. | | | 29/05/2017 | **Esercitazione**: esercitazione conclusiva in preparazione della prova scritta. | [[ https://www.youtube.com/watch?v=Q4gTV4r0zRs|Time with class! Let's count!]]| |1/06/2017|**Secondo compitino**: ore 8:30 (aula A) | |