====== Algoritmica e Laboratorio - Corso A ====== ===== Anno accademico 2018/2019 ===== ===== Informazioni Generali ===== **Docenti Teoria/Esercitazioni:** [[http://sbrinz.di.unipi.it/~peppe/|Giuseppe Prencipe]] e [[http://www.di.unipi.it/~pagli/|Linda Pagli]] ([[informatica:all-a:start|corso A]]) **Docenti Laboratorio:** [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]], [[http://pages.di.unipi.it/desensi/|Daniele De Sensi]] [[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** Prencipe: Martedì dalle ore 11:00 alle ore 13:00 (o su appuntamento) **Ricevimento studenti:** Pagli: su appuntamento, scrivere a linda.pagli@unipi.it **Registro delle lezioni:** si tratta del [[https://unimap.unipi.it/registri/dettregistriNEW.php?re=3290010::::&ri=080240|registro ufficiale]] che riporta quanto indicato nel seguito. ===== NEW: Ricevimento Collettivo con i Counselor !!!! ===== A partire dal 13 Marzo, ogni Martedi' 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/1FAIpQLScwAWf_UnsXKJ0hfdVb20vYA5KpxtkC0L_IQq5J1X75GfQHig/viewform|Feedback per il Counseling.]] [[https://github.com/DrDav/Algo1819/|Materiale didattico di supporto per il laboratorio (preparato dai counselor)]] ===== Gruppi Laboratorio ===== ^ Gruppo ^ Aula e orario ^ |A1 (da AA a DE) | Aula H, martedì 16:00 - 18:00| |A2 (da DI a NA) | Aula M, martedì 16:00 - 18:00| |A3 (da NE a ZZ) | Aula M, venerdì 14:00 - 16:00 | ===== Orario Lezioni ===== ^ Orario delle Lezioni ^^^^ | Lunedì | 9-11 | aula E | Teoria | | Martedì | 16-18 | aule H-I-M | Laboratorio | | Mercoledì | 11-13 | aula E | Teoria | | Venerdì | 9-11 | aula E | Teoria | | Venerdì |14-16 | aula M | 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, 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. **Prossime date per la prova scritta:** ^ Data ^ Tipo Prova ^ Documenti ^ Avvisi ^ | 01/04/19 | Primo Compitino | {{:informatica:all-a:algo010419-a.pdf|testo}}| {{informatica:all-a:votiesami.pdf|Risultati}} corso A. Correzione e visione dei compiti: lezione di lunedì 8 Aprile 2019. 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 d'esame. | | 01/04/19 | Appello Straordinario | {{:informatica:all-a:algo010419.pdf|testo}} |{{ :informatica:all-a:ris1_4_2019.docx |Risultati}} corso A e corso B. Sono ammessi all'esame di laboratorio gli studenti con voto ≥16. Per visione dei compiti lunedì 8 alle 12 ufficio Pagli.| | 03/06/19 | Secondo Compitino | {{:informatica:all-b:2compitino030619.pdf| Testo }}\\ {{:informatica:all-b:Solu2compitino2019.pdf|Soluzione}} | {{informatica:all-a:20190306-iiprovainitinere.pdf|Risultati}} corso A (sufficienza ≥17). Visione dei compiti: ufficio prof. Pagli, Venerdì 7 Giugno dalle 12.30 in poi; Lunedì 10, alle 11.30 | | 24/06/19 | Primo appello | {{:informatica:all-b:Algo240619.pdf| Testo }}\\ {{:informatica:all-b:solAppGiugno.pdf|Soluzione}} | {{informatica:all-a:votiesami24giu2019.pdf|Risultati}} corso A. Visione dei compiti: ufficio prof. Pagli, Lunedì 1 Luglio dalle 11.00 in poi. Gli studenti con * sono invitati a presentarsi Lunedì 1 Luglio dalle 11.00 presso l'ufficio della prof. Pagli | | 15/07/19 | Secondo appello | {{:informatica:all-b:Algo150719.pdf| Testo }}\\ {{:informatica:all-b:solAppLuglio.pdf|Soluzione}} | {{ :informatica:all-a:rsi150719-3.docx |Risultati}} Visione dei compiti e registrazione lunedì 22 luglio dalle ore 11 presso ufficio Pagli. Per solo registrazione consultare il prof. Prencipe | | 05/09/19 | Terzo appello | {{ :informatica:all-a:algo050919.pdf| Testo }}\\ {{ :informatica:all-a:soluzione.pdf |Soluzione}} |{{ :informatica:all-a:ris050619_ris050619.csv.pdf |Risultati}} Sono considerati sufficienti i voti ≥17. Visione dei compiti lunedì 9 settembre dalle ore 12 presso ufficio Pagli. Per registrazione martedì 10 dalle 16 ufficio Pagli | | 16/01/20| Quarto appello | {{ :informatica:all-a:all16012020.pdf | Testo }}\\ {{ :informatica:all-a:solall16_1_20.docx|Soluzione}} |{{ :informatica:all-a:risall16_1_20.docx |Risultati}} Sono considerati sufficienti i voti ≥17. Visione dei compiti e registrazione lunedì 20 gennaio dalle ore 12 presso ufficio Pagli. | | 11/02/20| Quinto appello | {{ :informatica:all-b:all11022020.pdf | Testo }} \\ {{ :informatica:all-b:ALL11022020SOL.pdf|Soluzione}} |{{ :informatica:all-a:votiFeb20A.pdf|Risultati}} 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. | **II Appello Invernale (Feb 2021)** Si svolgeranno il giorno **4 Febbraio 2021**, qui: [[https://meet.google.com/wnq-vdub-oyz]] **Calendario orali per il II appello invernale (Feb 2021)**: [[https://agende.unipi.it/xxf-rts-ckc]] ===== Registrazioni delle Lezioni ===== [[http://sbrinz.di.unipi.it/peppe/AlgoLezioniVideo/]] ===== 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}}. * **[FL]** P. Ferragina, F. Luccio. //Il Pensiero Computazionale: dagli algoritmi al coding//. Il Mulino, 2017. Solo pagine 64-65, Capitolo 7 e Capitolo 10. 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 ===== - 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 ^ | 18/02/2019 | Questioni organizzative: pagina web, 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 3, 4, 5 e 12 monete. | Capitolo 1 del CLRS, e [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/12monete.pdf | 12 monete]] | | 19/02/2019 22/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}} | | 20/02/2019 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio: caso pessimo, caso ottimo e caso medio. Notazione asintotica: O-grande, Omega e Theta, o-piccolo e omega-piccolo. | CLRS: Capitolo 3\\ [[https://www.dropbox.com/s/r4u3xf0avjrzyhz/20180221_ClassiComplessita.pdf?dl=0|Slide]] | | 22/02/2019 | Esercitazione: Notazione asintotica. SelectionSort, algoritmo, complessità. | {{:informatica:all-b:TCScheat.pdf|TCS cheat sheet}} | | 25/02/2019 | InsertionSort: algoritmo, correttezza e complessita'. | | | 26/02/2019 01/03/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}} | | 27/02/2019 | Paradigma del Divide et Impera: descrizione, pseudo-codice e analisi della complessità in tempo mediante relazioni di ricorrenza. Esempio su calcolo del massimo di un vettore. MergeSort: algoritmo, correttezza e analisi di complessità del Merge. | [CLRS] cap 2: 2.3; cap 4: 4.4. | |01/03/2019 | Esercitazione. Ricerca Sequenziale, con analisi caso medio, Ricerca Binaria ricorsiva, iterativa, che restituisce il k più a sinistra. Confronti e analisi.| | | 04/03/2019 | Algoritmi polinomiali ed esponenziali: definizione, confronto e caso di PC k-volte più veloce, con considerazioni. Problema della Torre di Hanoi: definizione, risoluzione con algoritmo ricorsivo e valutazione della complessità con relazione di ricorrenza. Pseudo-codice ricorsivo con valutazione della complessità: caso lineare e caso logaritmico. | Consultare [FL].\\ {{ :informatica:all-a:20180307_compl_ric.pdf |Slide}}. | | 05/03/2019 08/03/2019 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} | | 06/03/2019 | Enunciato del Teorema dell'esperto, con esempi.| | | 08/03/2019 | Dimostrazione del Teorema dell'esperto per il caso delle potenze. | [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte) | | 11/03/2019 | Esercizi sul Teorema dell'esperto. Algoritmo della Moltiplicazione veloce di interi e di matrici con analisi della complessità. | [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}}. | | 12/03/2019 15/03/2019| **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-a:lezione4.pdf|Slide}} | | 13/03/2019 | 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 | | 15/03/2019 | Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Algoritmi per determinare il primo e secondo, algoritmo del doppio torneo.| [[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. | | 18/03/2019 | 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. Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. | [CLRS] cap 9: 9.1, 9.2 (leggere analisi al caso medio dalla {{ :informatica:all-a:rand_select_comm.pdf |seguente nota}}).\\ [CLRS] cap 6: 6.1 - 6.4. | | 19/03/2019 22/03/2019| **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5.pdf |Slide}}| | 20/03/2019 | Heapsort. Code di priorità: definizione, operazioni, realizzazione mediante heap. | [CLRS] cap 6: 6.5. | |22/03/2019 |Esercitazione: problema del mergeInsertionSort, con analisi e limite inferiore. Algoritmi Divide et impera e come trasformazione di ricerca Binaria (cuspide, trova occorrenze)|{{:informatica:all-a:ricercabinariasin.pdf|ricerca binaria sinistra}} | |25/03/2019 | Esercizi Master Theorem.| {{ :informatica:all-a:20180314_esercizimasterth.pdf |Slides}} | | 26/03/2019 29/03/2019 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-a:lezione6.pdf|Slide}} | | 27/03/2019 |Esercitazione: calcolo della potenza di a alla n con O(log n) moltiplicazioni; trova due elementi a somma k, limite inferiore con albero di decisione, algoritmo lineare; Intersezione di due insiemi con e senza ordinamento;| | | 29/03/2019 |Esercitazione: esercizi di ripasso su QuickSort, MergeSort, Heap e HeapSort | | | 08/04/2019 | Correzione prima prova di verifica intermedia. | | | 9/04/2018 12/04/2019 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} | | 10/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.1, 11.2, 11.3, 11.3.1, 11.3.2. | | | 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. | | | 12/04/2019 | Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. | [CLRS] cap 8: 8.2, 8.3. | | 15/04/2019 | Alberi e alberi binari: Definizione e memorizzazione. Interrogazioni (minimo, massimo, successore, predecessore); inserimento e cancellazione. Analisi della loro complessità in tempo. Visita di alberi binari di ricerca: Visite Anticipata/Simmetrica/Posticipata. | [CLRS] cap 10: 10.4. cap 12: 12.1, 12.2, 12.3. | | 16/04/2019 | **Laboratorio**: Liste monodirezionali e bidirezionali. MARTEDI' GRUPPI A1, A2 e A3| {{ :informatica:all-a:lezione8-1415.pdf |Slide}}| | 17/04/2019 | Esercitazione: Algoritmi ricorsivi su alberi binari, dimensione, altezza, controlo perfettamente bilanciato, nodi cardine. Esempio di open hash con scansione lineare quadratica e doppio hash. | [CGGR]: {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}} {{ :informatica:all-b:eserciziAlberi2016.pdf | Esercizi (alberi binari)}} | | 29/04/2019 | Grafi: definizioni, rappresentazione di grafi in memoria. Grafi: visita in ampiezza (BFS), algoritmo e analisi di complessità e correttezza, albero di visita in ampiezza e algoritmo PRINT-PATH.| [CLRS] cap 22: 22.2 con lem/teo/cor da 22.1 a 22.5. [CLRS]: appendice B.4 | | 30/04/2019 03/05/2019 | **Laboratorio**: Tabelle Hash. MARTEDI' gruppi A1 e A2, VENERDI' gruppo A3| {{ :informatica:all-b:lezionehash.pdf |Slide}}| | 03/05/2019 | **Esercitazione**: Alberi binari di ricerca. | {{ :informatica:all-a:ABR2019.pdf | Esercizi (alberi binari di ricerca)}} {{https://drive.google.com/file/d/1Yq-VYzzbhUwx-SAKshPz3x_oN7Si8lFI/view?usp=sharing|lavagna}}| | 06/05/2019 | Grafi: visita in profondità (DFS), analisi di complessità e correttezza, 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 | | 07/05/2019 10/05/2019 | **Laboratorio**: Alberi binari di ricerca. | {{ :informatica:all-a:lezioneabr.pdf |Slide}}| | 08/05/2019 | 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. Il problema del taglio della corda. Il problema del calcolo dei 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}} | | 10/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}} | | 13/05/2019 | Il problema della sequenza ottima di moltiplicazioni di matrici. Il problema della determinazione della Longest Common Subsequence. Il problema dello zaino 0-1. | {{:informatica:all-b:ED.pdf|Edit Distance (dispense Prof. Luccio)}} | | 14/05/2019 17/05/2019 | **Laboratorio**: Grafi. | {{ :informatica:all-b:lezionegrafi.pdf |Slide}} {{:informatica:all-a:grafobip.pdf|Esercizio 1}}| | 15/05/2019 | **Esercitazione**: progettazione di algoritmi efficienti su grafi.|{{:informatica:all-b:esercizigrafi19.pdf|Esercizi}}| | 17/05/2019 | **Esercitazione**: esempi di algoritmi programmazione dinamica, Zaino e Edit Distance|[[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/pd.pdf|Note di F. Luccio]]| | 20/05/2019 | Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino frazionario. Algoritmi pseudopolinomiali. Il problema dello scheduling delle attivita'. Partizione di un insieme di interi. Edit Distance. Come passare l'esame (problema di programmazione dinamica!). Data Center. | [CLRS] cap 16: 16.2, {{:informatica:all-a:ProblemaZaino_pubblicato.pdf|Il problema dello zaino intero e frazionario.}} {{:informatica:all-b:ZainoPD.pdf|esercizio 16.2.2 (algoritmo PD per lo Zaino)}}. {{:informatica:all-b:pseudo.pdf |pseudopolinomialità}} | | 21/05/2019 24/05/2019 | **Laboratorio**: Simulazione prova di esame. |{{ :informatica:all-b:solgrafi.pdf |Slide}} | | 22/05/2019 | 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}} | | 24/05/2019 | Esercitazione: Genera binarie, Genera permutazioni, Scacchiera, Problema dell'Imbalance su alberi binari. |{{:informatica:all-a:pagli_20190529_173206.pdf|GeneraBinarie e GeneraPermutazioni}} | | 29/05/2019 | Esercitazione: Algoritmo enumerativo per TSP. Verifica polinomiale per Vertex Cover. Problemi di ripasso | | | 31/05/2019 | Esercitazione non tenuta causa sciopero del personale addetto all'apertura delle aule.| {{:informatica:all-b:DizAlberi2019.pdf|Esercizi}}| | 31/05/2019 | **Laboratorio** (gruppo A3): Lezione non tenuta causa sciopero del personale addetto all'apertura delle aule e sostituita con ricevimento studenti (ufficio Bernasconi, 14-16) | |