====== Algoritmica e Laboratorio - Corso A ====== ===== Anno accademico 2017/2018 ===== ===== Informazioni Generali ===== **Docenti Teoria/Esercitazioni:** [[http://www.di.unipi.it/~ferragin/|Paolo Ferragina]] e [[http://sbrinz.di.unipi.it/~peppe/|Giuseppe Prencipe]] ([[informatica:all-a:start|corso A]]) e [[http://www.di.unipi.it/~pagli/|Linda Pagli]] ([[informatica:all-b:start|corso B]]) **Docenti Laboratorio:** [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]], [[http://pages.di.unipi.it/sirbu/|Alina Sirbu]], [[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:** Ferragina lunedì 14-16 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]] Nel periodo estivo si segnalano i seguenti ricevimenti del Prof. Ferragina: 4 giugno ore 15:30, 14 giugno ore 9, 18 giugno ore 14.30. **Ricevimento studenti** Prencipe: Venerdì dalle ore 11:00 alle ore 13:00 **Registro delle lezioni:** si tratta del [[http://unimap.unipi.it/registri/dettregistriNEW.php?re=2088114::::&ri=9142|registro ufficiale]] che riporta quanto indicato nel seguito. ===== 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 | ===== 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 ^ | 04/04/18 | Primo Compitino | {{ :informatica:all-a:algo_040418_versione_1_.pdf |testo1}} e {{ :informatica:all-a:algo_040418_versione_2_.pdf |testo2}}, {{ :informatica:all-a:risollllluzione_04.04.2018.pdf |soluzione}}. {{ :informatica:all-a:algoritmica-2018.pdf |Lista dei risultati}} (solo quelli che hanno riportato una votazione >=17 e sono quindi ammessi al secondo compitino). Mancando di matricola, in quanto non registrati, si segnalano anche Bertolucci Simone 24, Dardanis Nicola 23, Morini Virginia 17.\\ Per la correzione e visione del compito: mercoledì 11 aprile, Aula G, ore 17:00 | | 30/05/18 | Secondo Compitino | {{ :informatica:all-a:algo_300518_versione_1.1_.pdf |testo}}, {{ :informatica:all-a:sol_compitino_2.pdf |soluzione}}, {{ :informatica:all-a:risultati_compitino_2.pdf |lista dei risultati}} (solo quelli che hanno riportato una votazione >=18).\\ Per la correzione e visione del compito: Aula C, martedì 5 giugno, ore 9:00.\\ La prova orale e la prova di laboratorio possono essere sostenute in qualunque appello secondo le regole su indicate. L'aumento +2 al voto di media (valido solo per i compitini) viene perso se si decide di sostenere la prova orale, la quale è quindi **facoltativa** per chi ha passato i compitini, ma può portare a un incremento max di 4 punti. La registrazione del voto, dopo aver passato anche la prova di laboratorio, può avvenire in **qualunque appello**. La visione dei compiti è possibile durante l'orario di ricevimento: 4 giugno ore 15:30, 14 giugno ore 9, 18 giugno ore 14.30. | | 22/06/18 | Primo Appello | {{ :informatica:all-a:algo_220618.pdf |testo}}, {{ :informatica:all-a:soluzione_algo_220618.pdf |soluzione}}, {{ :informatica:all-a:primo-appello.pdf |lista dei risultati}} (solo quelli che hanno riportato una votazione >=18).\\ Per la correzione e visione del compito: Aula C, lunedì 25 giugno, ore 17:00.\\ La prova orale e la prova di laboratorio possono essere sostenute in qualunque appello secondo le regole su indicate. L'aumento +2 al voto dello scritto viene perso se si decide di sostenere la prova orale, la quale è quindi **facoltativa** e può portare a un incremento max di 4 punti. La registrazione del voto, dopo aver passato anche la prova di laboratorio, può avvenire in **qualunque appello** o **ricevimento** del docente. | | 13/07/18 \\ ore 9-11 | Secondo appello | {{ :informatica:all-a:algo_130718.pdf |testo}}, {{ :informatica:all-a:soluzione_del_13-7-2018.pdf |soluzione}}, {{ :informatica:all-a:prova_terza.pdf |lista dei risultati}}. | | 04/09/18 \\ ore 9-11 | Terzo appello | {{ :informatica:all-a:algo_040918.pdf |testo}}, {{ :informatica:all-a:risultati-sett2018.pdf |risultati}}.\\ Gli studenti interessati a sostenere la prova orale (opzionale) devono inviare un'email al docente.\\ La registrazione del voto (avendo superato anche il laboratorio) e l'orale (opzionale) possono avvenire in qualunque appello. L'aumento +2 al voto dello scritto viene perso se si decide di sostenere la prova orale, la quale è quindi facoltativa e può portare a un incremento max di 4 punti. La prossima data utile per orale/registrazione è lunedì 17 settembre, ore 14.30, studio Ferragina. La correzione e visione del compito può avvenire lunedì 10 settembre, ore 14.30, studio Ferragina. | | 21/01/19 | Quarto appello | {{ :informatica:all-a:all18:algo210119.pdf |testo}}, {{ :informatica:all-a:all18:algoritmica_-_gennaio_2019.pdf |risultati (solo per quelli che hanno riportato un voto >= 16, che possono svolgere la prova di laboratorio.)}}.\\ La **correzione e visione** dei compiti avverrà giovedì 24 gennaio 2019, ore 11.00, **studio Prof.ssa Pagli**.\\ La prossima data utile per la **registrazione** del voto è giovedì 24 gennaio 2019, ore 9:00, aula C con il **Prof. Ferragina**.\\ La registrazione del voto (avendo superato anche il laboratorio) e l'orale (facoltativo) possono avvenire in qualunque appello. L'aumento +2 al voto dello scritto viene attribuito automaticamente alla registrazione del voto, ma esso viene perso se si decide di sostenere la prova orale, la quale è facoltativa e può portare a un incremento max di 4 punti. Gli studenti interessati a sostenere la prova orale devono inviare un'email al docente Prof. Ferragina. | ===== 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://algo1718.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 ^ | 19/02/2018 | 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 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]] | | 20/02/2018 | **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}} | | 21/02/2018 | 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]] | | 23/02/2018 | Esercitazione sulla notazione asintotica | | | 26/02/2018 | Selection sort versus Insertion sort: correttezza e complessità asintotica al caso pessimo e al caso ottimo. | CLRS: Sezione 2.1 e 2.2. | | 27/02/2018 | **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}} | | 28/02/2018 | 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. | | | 02/03/2018 | MergeSort: algoritmo, correttezza e analisi di complessità (metodo iterativo e albero di ricorsione). | [CLRS] cap 2: 2.3; cap 4: 4.4. | | 05/03/2018 | **Lezione non tenuta per sospensione elettorale** | | | 06/03/2018 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} | | 07/03/2018 | 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}}. | | 09/03/2018 | Enunciato del Teorema dell'esperto, con esempi. Dimostrazione del Teorema dell'esperto per il caso delle potenze. | [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte) | | 12/03/2018 | Esercizi sul Teorema dell'esperto. Algoritmo della Ricerca Binaria e della Moltiplicazione veloce con analisi della complessità. (Studiare anche prodotto veloce tra matrici.) | [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}}. | | 13/03/2018 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-b:lezione4-1415.pdf|Slide}} | | 14/03/2018 | Esercizi sul Teorema dell'esperto. | {{ :informatica:all-a:20180314_esercizimasterth.pdf |Slides}} | | 16/03/2018 | 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 | | 19/03/2018 | Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo medio lineare. | [[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.\\ [CLRS] cap 9: 9.1, 9.2 (leggere analisi al caso medio dalla {{ :informatica:all-a:rand_select_comm.pdf |seguente nota}}). | | 20/03/2018 | **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5-1617.pdf |Slide}}| | 21/03/2018 | 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à. L'algoritmo Heapsort.| [CLRS] cap 6: 6.1 - 6.4. | | 22/03/2018 | Code di priorità: definizione, operazioni, realizzazione mediante heap. | [CLRS] cap 6: 6.5. | | 26/03/2018 | Esercitazione su ordinamento e Heap. | {{:informatica:all-b:esercizi3-2015.pdf|Esercizi (heap)}} | | 27/03/2018 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-b:lezione6-1415.pdf|Slide}} | | 28/03/2018 | Esercitazione pre-compitino | 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]]. | | 11/04/2018 | Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. | [CLRS] cap 8: 8.2, 8.3. | | | 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. | | | 13/04/2018 | 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. | | 16/04/2018 | Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica, doppio hashing. |[CLRS] cap 11: 11.4. | | 17/04/2018 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} | | 18/04/2018 | Alberi e alberi binari: Definizione e memorizzazione. Dizionari: realizzazione con alberi binari di ricerca; interrogazioni (minimo, massimo, successore, predecessore); inserimento e cancellazione. Analisi della loro complessità in tempo. | [CLRS] cap 10: 10.4. cap 12: 12.1, 12.2, 12.3. | | 20/04/2018 | Visita di alberi binari di ricerca: Pre/in/post visita e loro applicazioni. Algoritmi ricorsivi su alberi binari. 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}}, [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/lezione21apr.pdf|lavagna 3]]. | | 23/04/2018 | Alberi 2-3: definizione, conteggio numero di nodi e foglie (con dimostrazione). Dizionari: realizzazione con alberi 2-3 (ricerca; inserimento; cancellazione). | [DFI]: {{ :informatica:all-b:alberi2-3.pdf |alcune pagine}} (no sezione B-alberi), | | 24/04/2018 | **Laboratorio**: Liste monodirezionali e bidirezionali. | {{ :informatica:all-a:lezione8-1415.pdf |Slide}}{{ :informatica:all-a:e1.pdf |Esercizio 1 in aula.}}| | 27/04/2018 | Generazione delle sequenze binarie. Generazione delle permutazion. Esempi. | [CGGR]: {{:informatica:all-b:generaBinPerm.pdf | alcune note su generazione binarie e permutazioni}} | | 30/04/2018 | Esercizi su alberi binari | | | 02/05/2018 | Esercizi su alberi hash, genera binarie/permutazioni | | | 04/05/2018 | Grafi: definizioni, rappresentazione di grafi in memoria, esempi di problemi su grafi. Il problema del ciclo euleriano e il problema del ciclo hamiltoniano: definizioni, e considerazioni computazionali. Teorema di Eulero. | Alcune {{ :informatica:all-a:eulero_vs_hamiltoniano.pdf |note}} su ciclo euleriano e hamiltoniano. [CLRS]: appendice B.4, cap 22: 22.1. | | 07/05/2017 | 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 . | | 08/05/2018 | **Laboratorio**: Alberi binari di ricerca. | {{ :informatica:all-a:lezione9.pdf |Slide}}| | 09/05/2017 | 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 | | 11/05/2017 | Lezione non tenuta, ma qui a fianco trovate esercizi da svolgere/svolti su alberi e tabelle hash.| {{ :informatica:all-a:esercizi_alberi_e_tabelle_hash.pdf |Testo 1}} (no ex 2-3 albero) e {{ :informatica:all-a:esercizi_hash.pdf |testo 2}} | | 14/05/2018 | 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. |[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}} | | 15/05/2018 | **Laboratorio**: Tabelle hash. | {{ :informatica:all-a:lezione10.pdf |Slide}} {{ :informatica:all-b:ht.pdf |Esercizio 1 in aula}}| | 16/05/2018 | Il problema della sequenza ottima di moltiplicazioni di matrici. 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)}} | | 18/05/2018 | Esercitazione sui grafi. | | | 21/05/2018 | Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino (intero e frazionario). Algoritmi pseudopolinomiali. Il problema dello scheduling delle attivita'.| [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à}} | | 22/05/2018 | **Laboratorio**: Simulazione prova di esame. | | | 23/05/2018 | 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}} | | 25/05/2018 | Esercizi su Programmazione Dinamica | {{ :informatica:all-a:EserciziProgDin_pubblicati.pdf |soluzioni}}.[[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/esercizipd-sol.pdf|altri esercizi]]. | | 28/05/2018 | Esercizi su NPC e grafi | | | 29/05/2018 | **Laboratorio**: Grafi. | {{ :informatica:all-b:lezione12grafi.pdf | Slide}}|