====== Algoritmica e Laboratorio - Corso A ====== ===== Anno accademico 2019/2020 ===== ===== IMPORTANTE ===== A partire dal 9 marzo Le lezioni si svolgeranno telematicamente nelle ore previste dall'orario. Per partecipare accedere all'URL: **http://unipi.it/corsionline **ed eseguire le istruzioni della guida per partecipare alle lezioni su Teams di Microsoft. Il ricevimento studenti sarà fatto via mail, oppure via Skype su appuntamento. ===== Informazioni per le lezioni di laboratorio ===== Le lezioni di laboratorio si svolgeranno on line (streaming), a partire da martedì 10 marzo alle ore 11 sulla piattaforma Meet di Google. **Attenzione: le lezioni non saranno registrate. Seguitele rispettando gli orari del corso.** Gli studenti del corso di laurea in Informatica sono pregati di collegarsi (il martedi alle ore 11) utilizzando questo [[https://meet.google.com/dfz-nrtj-vex|link]] Gli studenti del corso di laurea in Data Science sono pregati di collegarsi (il martedi alle ore 11) utilizzando questo [[https://meet.google.com/fci-jqui-ixb|link]] Gruppo Telegram con gli assistenti di laboratorio: [[https://t.me/joinchat/ASipw0Z4bi_AysizF4GFhQ|link]] ===== Informazioni Generali ===== **Docenti Teoria/Esercitazioni:** [[http://www.di.unipi.it/~pagli/|Linda Pagli]] e [[http://sbrinz.di.unipi.it/~peppe/|Giuseppe Prencipe]] ([[informatica:all-a:start|corso A]]) **Docenti Laboratorio:** [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]], [[http://hpc.isti.cnr.it/~nardini/|Franco Maria Nardini]], [[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:** Pagli: su appuntamento, scrivere a linda.pagli@unipi.it **Ricevimento studenti** Prencipe: Martedì dalle ore 11:00 alle ore 13:00 (o su appuntamento) **Ricevimento studenti** Bernasconi: Mercoledì, dalle 9 alle 11, sulla piattaforma [[https://meet.google.com/dfz-nrtj-vex|Meet di Google]]. Ricevo inoltre via Skype su appuntamento. Tramite mail avverrà lo scambio dei contatti skype e l'accordo sul giorno e sull'orario. **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. ===== Anni accademici precedenti ===== * [[.all19:|A.A. 2018/2019]] * [[.all18:|A.A. 2017/2018]] * [[.all17:|A.A. 2016/2017]] * [[.all16:|A.A. 2015/2016]] * [[.all15:|A.A. 2014/2015]] * [[.all14:|A.A. 2013/2014]] * [[.all12:|A.A. 2012/2013]] ===== Gruppi Laboratorio ===== **NEWS**: Starting from Tuesday March 3rd, the Python Lab slot dedicated to Data Science Master Degree students is anticipated at 11:00-13:00 (still in class-room I). Therefore Data Science students should head to that time slot, while first year students are now allowed to attend the C Lab class at 14:00 even in classroom I.\\ ^ Gruppo ^ Aula e orario ^ |A1 | Aula H, martedì 11:00 - 13:00| |A2 | Aula M, martedì 11:00 - 13:00| |A3 (Riservata a studenti della LM in Data Science - Dedicated to Data Science Master students) | Aula I, martedì 11:00 - 13:00| ===== Orario Lezioni ===== ^ Orario delle Lezioni ^^^^ | Lunedì | 11-13 | aula E | Teoria | | Martedì | 11-13 | aule H-I-M | Laboratorio | | Giovedì | 16-18 | 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===== MODALITA’ DI ESAME PER GLI STUDENTI DELLA LAUREA TRIENNALE L'esame degli appelli estivi consistono in due prove obbligatorie: * Una **prova di Laboratorio** che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi. La prova avra’ luogo sulla consueta piattaforma d’esame accessibile via browser, e sara’ validata da un colloquio orale immediatamente successivo. Tale prova è da intendersi come un __test di idoneità__. * Una **prova orale** sul programma del corso la cui valutazione finale è __in trentesimi__, atta a valutare l'apprendimento delle nozioni teoriche e la capacità di "problem solving" dello studente. * La prova orale puo' essere sostenuta solo dopo aver superato la prova di Laboratorio. * Le prove possono essere sostenute in appelli diversi. * Se la prova orale non viene superata, occorre ripetere soltanto quella. Istruzioni piu’ dettagliate verranno fornite via mail agli iscritti alle prove. Per questo motivo, e per la necessita’ nelle nuove condizioni di organizzare al meglio le prove, l’iscrizione e’ tassativamente obbligatoria. **Attenzione**: la scadenza per iscriversi non sara’ molto a ridosso delle prove d’esame, controllate l'apposito portale.\\ DATA SCIENCE STUDENTS: PLEASE CONTACT ANY OF THE PROFESSORS FOR INSTRUCTIONS **Prossime date per la prova di Laboratorio:** ^ Data ^ Tipo Prova ^ Documenti ^ Aula Virtuale ^ | 26/5/2020 | 09:00 | Laboratorio | | | 16/6/2020 | 09:00 | Laboratorio | | | 07/07/2020 | 09:00 | Laboratorio | | | 01/09/2020 | 09:00 | Laboratorio | | | 11/01/2021 | 14:00 | Laboratorio | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | | 01/02/2021 | 14:00 | Laboratorio | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | | 22/03/2021 | 14:30 | Laboratorio | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | | 8/06/2022 | 9:00 | Laboratorio | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | **Prossime date per la prova orale:** Gli orali della I sessione autunnale si svolgeranno il 3 Settembre, a partire dalle ore 14:00: [[https://agende.unipi.it/ssc-vme-ekp]] Per la discussione orale, si utilizza il canale Teams che è stato utilizzato per lo svolgimento delle lezioni. **Prossime date per la prova di laboratorio linguaggio Python per studenti della LM in Data Science:** ^ Data ^ Ora ^ Tipo Prova ^ Avvisi ^ Aula Virtuale ^ Iscrizione ^ | 26/5/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 24/05/2020 all'indirizzo email rossano.venturini@unipi.it. | [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 21/5 | | 16/6/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 14/06/2020 all'indirizzo email rossano.venturini@unipi.it. | [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 11/6 | | 7/7/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 5/7/2020 all'indirizzo email rossano.venturini@unipi.it. | [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 2/7/2020 | | 1/9/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 30/8/2020 all'indirizzo email rossano.venturini@unipi.it. | [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 27/8/2020 | | 27/10/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 25/10/2020 all'indirizzo email rossano.venturini@unipi.it. | [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Sul portale di iscrizione esami entro il 19/10/2020 | | 11/01/2021 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 09/01/2021 all'indirizzo email rossano.venturini@unipi.it. | [[https://meet.google.com/fci-jqui-ixb | QUI ]] | | | 01/02/2021 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 30/01/2021 all'indirizzo email rossano.venturini@unipi.it. | [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Nota: Se la data dell'esame coincide con quella di altri esami, inviatemi un'email per concordare un'altra data. | | 23/03/2021 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 21/03/2021 all'indirizzo email rossano.venturini@unipi.it. | [[https://meet.google.com/fci-jqui-ixb | QUI ]] | Nota: Se la data dell'esame coincide con quella di altri esami, inviatemi un'email per concordare un'altra data. | ===== Registrazioni delle Lezioni ===== [[http://sbrinz.di.unipi.it/peppe/AlgoLezioniVideo/AlgoLezioniVideo2020]] ===== 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. * [[https://github.com/DrDav/Algo1819/|Materiale didattico di supporto per il laboratorio]] * [[https://github.com/jfet97/UniPiComputerScience| Altro materiale di supporto per il laboratorio preparato da uno studente]] * **__Sistema di Autovalutazione__**: [[http://algo1920.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 ^ | 17/02/2020 | 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 12 monete. | Capitolo 1 del CLRS, e [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/12monete.pdf | 12 monete]] | | 18/02/2020 | **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/2020 | 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. | | 21/02/2020 | InsertionSort: algoritmo, correttezza e complessita'. SelectionSort (correttezza e analisi sul libro di testo). Paradigma del Divide et Impera: descrizione, pseudo-codice e analisi della complessità in tempo mediante relazioni di ricorrenza. Esempio su calcolo del massimo e minimo di un vettore.| | | 24/02/2020 | MergeSort: algoritmo, correttezza e analisi di complessità del Merge. | [CLRS] cap 2: 2.3; cap 4: 4.4. Consultare [FL]. | | 25/02/2020 | **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/2020 | 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. | Consultare [FL]. | | 28/02/2020 | Teorema dell'esperto, esempi, e sua dimostrazione per il caso delle potenze. | [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte) | | 02/03/2020 | Esercitazione: Ordini di grandezza, Ricerca sequenziale e varie versioni ricerca binaria. Analisi complessità|{{ :informatica:all-a:esercitazione_1.pdf |Es 1}} | | 03/03/2020 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} | | 09/03/2020 | Esercitazione: Ricerca Binaria Sinistra, limiti inferiori al problema della ricerca, problema 2.1 pag. 37 del Cormen: MergeInsertionSort|{{ :informatica:all-a:esercitazione_2.pdf |Es 2}} | | 10/03/2020 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-a:lezione4.pdf|Slide}} | |12/03/2020 | 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. {{ :informatica:all-a:lez12marzo.pdf |lavagna}} | | 13/03/2020 | 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). Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo medio lineare. | [CLRS] cap 7 (leggere analisi al caso medio dalla {{ :informatica:all-a:rand_select_comm.pdf |seguente nota}}). \\ cap 9: 9.1, 9.2 | | 16/03/2020 | Limiti inferiori con la tecnica dell'avversario: problema del primo e secondo. Partizione con elementi uguali (Problema [CLRS] 7.2). Moltiplicazione nel bit model |{{:informatica:all-b:TCScheat.pdf|TCS cheat sheet}} Note di F. Luccio su {{ :informatica:all-a:prodotto_interi_e_matrici.pdf |moltiplicazione interi e matrici}} {{ :informatica:all-a:lez16marzo.pdf |lavagna }}| | 17/03/2020| **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5.pdf |Slide}}| | 19/03/2020 | Moltiplicazione Egizia e Moltiplicazione Rapida, Moltiplicazione di matrici: Algoritmo di Strassen. Introduzione alle cose con priorità |{{ :informatica:all-a:lez19m.pdf |lavagna}} | | 20/03/2020 | 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à. Heapsort. | [CLRS] cap 6: 6.1 - 6.5. | | 23/03/2020 | Code di priorità: definizione, operazioni, realizzazione mediante heap. 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). Funzioni hash: metodo della divisione. | [CLRS] cap 6: 6.1 - 6.5. cap 11: 11.1, 11.2, 11.3, 11.3.1, 11.3.2.| | 24/03/2020 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-a:lezione6.pdf|Slide}} | | 26/03/2020 | Funzioni hash: metodo della moltiplicazione. Dizionari: realizzazione con tabelle a indirizzamento aperto e analisi di ricerca senza successo e inserimento. Probing lineare, quadratico, e con double hashing. Tabelle hash con stringhe come chiavi. | [CLRS] cap 11: 11.3.2, 11.4. | | | 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. | | | 27/03/2020 |Esercitazione. Dimostrazioni per induzione su alberi binari. Simulazione di HeapSort. Equazioni di ricorrenza| {{ :informatica:all-a:ese3.pdf |lavagna}} | | 30/03/2020 | Esercitazione scritta | | | 31/03/2020 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} | | 02/04/2020 | Esercitazione. Esercizi vari su Heap e HeapSort.| {{ :informatica:all-a:eser4.pdf |lavagna}} | | 03/04/2020 | Esercitazione. Esercizi di simulazione di tabelle hash con diversi metodi gestione delle collisioni. Il problema della cancellazione nell'open hash, uso della marcatura. | {{ :informatica:all-a:e5.pdf |lavagna}} | | 06/04/2020 | Definizione di albero, con radice, ordinato k-ario. Algoritmi ricorsivi su alberi binari, dimensione, altezza. Visite, Paradigma generale tipo Divide et Impera, con equazioni di ricorrenza | [CGGR]: {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}} {{ :informatica:all-a:lez6.pdf | lavagna}} | | 07/04/2020 | **Laboratorio**: Liste monodirezionali e bidirezionali. | {{ :informatica:all-a:lezione8-1415.pdf |Slide}}|. | 09/04/2020 | Trasformazione da albero ordinato ad albero binario. Alberi binari di ricerca. Operzioni di ricerca, inserzione, cancellazione, ordinamento, minimo, massimo, predecessore e successore. | [CLRS] cap 12: 12.1, 12.2, 12.3 (senza alg TRASPLANT). {{ :informatica:all-a:leza9aprile.pdf |lavagna}}| | 16/04/2020 | Alberi bilanciati in altezza: alberi AVL. Studio del caso pessimo: Alberi di Fibonacci. Rotazioni dopo inserzione e cancellazione, esempi. | [CGGR]: {{:informatica:all-b:AVL.pdf|Alberi AVL}}, {{:informatica:all-b:rotazioniavl.pdf| rotazioni}} {{ :informatica:all-a:lez16aprilr.pdf |lavagna}}| | 17/04/2020 | Esercitazione. alberi binari, alberi binarizzati, inserzioni in albero AVL. |{{ :informatica:all-a:lez17aprile.pdf |lavagna}} | | 20/04/2020 | Array di dimensione variabile. Sorting in tempo lineare: Counting Sort e Radix Sort. |[CGGR] par 1.1.3, [CLRS] cap 8: 8.2, 8.3 {{ :informatica:all-a:arrayvariabili.pdf |array variabili}}{{ :informatica:all-a:lez20aprile.pdf |lavagna}}| | 21/04/2020 | **Laboratorio**: Tabelle Hash. | {{ :informatica:all-b:lezionehash.pdf |Slide}} \\ {{:informatica:all-a:Esercizio1.pdf |Esercizio 1}} {{:informatica:all-a:Esercizio2.pdf |Esercizio 2}} | | 23/04/2020 |Esercitazione. Radix Sort, esempi e confronti. Esercizi su alberi binari di ricerca. | {{ :informatica:all-a:ABR2019.pdf | Esercizi (alberi binari di ricerca)}}{{ :informatica:all-a:lez23aprile.pdf |lavagna}} | | 24/04/2020 |Introduzione alla Programmazione Dinamica. Generazione dei numeri di Fibonacci. Il problema della Longest Common Subsequence. |[CLRS] cap 15: 15.4.{{ :informatica:all-a:lez24aprilr.pdf |lavagna}} | | 27/04/2020 |Programmazione Dinamica. Il problema della Edit Distance |[[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/pd.pdf|Note del Prof. Luccio]].{{ :informatica:all-a:lez27aprile.pdf |lavagna}} | | 28/04/2020 | **Laboratorio**: Alberi binari di ricerca. | {{ :informatica:all-a:lezioneabr.pdf |Slide}} \\ {{:informatica:all-a:Esercizio1AB.pdf |Esercizio 1}} {{:informatica:all-a:Esercizio2AB.pdf |Esercizio AVL}}| | 30/04/2020 |Esercitazione. Esercizi di Programmazione Dinamica. |{{ :informatica:all-a:algo1_090614.pdf | esercizio 3}} {{ :informatica:all-a:esercizipd.pdf | scacchiere}} | | 04/05/2020 |Il problema dello Zaino e dello Zaino frazionato. Algoritmo greedy per lo Zaino frazionato. Programmazione Dinamica per lo Zaino. Pseudopolinomialità. Algoritmo brute force per lo Zaino. |[CGGR] par 6.5{{ :informatica:all-a:lez4maggio.pdf | lavagna }}| | 05/05/2020 | **Laboratorio**: simulazione prova d'esame.|{{ :informatica:all-a:SolAlberi.pdf |Slide}} | | 07/05/2020 |Introduzione ai grafi. Definizioni. Rappresentazione con Matrice e liste di adiacenza. Visita BFS. |[CLRS] cap.22, 22.1 e 22.2 fino a analisi e appendice B4, {{ :informatica:all-a:all7maggio.pdf |lavagna}}| |11/05/2020 |Grafi: albero BFS, Vista DFS, foresta DFS. Etichettamento degli archi. Esempi |[CLRS] cap.22, 22.2 {{ :informatica:all-a:lez11maggio.pdf |lavagna}}| |12/05/2020 | **Laboratorio**: grafi. |{{ :informatica:all-a:lezionegrafi20.pdf |Slide}} {{:informatica:all-a:grafobipartito.pdf |Esercizio 1 (Grafo Bipartito)}} {{ :informatica:all-b:ese2_grafi.pdf| Esercizio 2 (grafo connesso)}}| |14/05/2020 |Grafi: DAG e Ordinamento Topologico. BFS per grafi dinamici. Esempi |[CLRS] cap.22, 22.3 e 22.4, [CGGR] pag.225| |15/05/2020 |Esercitazione: esercizi sui grafi| {{ :informatica:all-b:esercizigrafi2017.pdf | Esercizi}} {{ :informatica:all-a:lez15maggio.pdf |lavagna}}| |18/05/2020 |Il problema P e NP. Introduzione all'NP-Completezza|{{ :informatica:all-a:pvsnp.pdf |PvsNP}} | |19/05/2020 | **Laboratorio**: esercitazione finale | {{ :informatica:all-b:solgrafi.pdf |Slide}}| |21/05/2020 | Verifica polinomiale. NP-Completezza, Definizioni. Riducibilità polinomiale. Teorema di Cook-Levin (senza dimostrazione), esempi di riduzioni. |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. {{ :informatica:all-a:all21maggio.pdf |lavagna}} | |22/05/2020 | Esercitazione: esercizi su grafi, programmazione dinamica, algoritmi enumerativi e verifica polinomiale.| {{ :informatica:all-a:pagli_20190529_173206.pdf|GeneraBinarie e GeneraPermutazioni}} {{ :informatica:all-a:ese22maggio.pdf |lavagna}} |