Questa è una vecchia versione del documento!
Docenti Teoria/Esercitazioni: Nadia Pisanti, Anna Bernasconi
Docenti Laboratorio: Anna Bernasconi, Giulio Pibiri, 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.
La didattica frontale e' sospesa dal 5 Marzo. Di conseguenza:
Le lezioni teoriche fino al 3 Aprile verranno registrate e rese disponibili per gli studenti mediante link in questa pagina web nella sezione “Registro delle Lezioni”. A partire da martedì 7 aprile, le lezioni di teoria si svolgeranno anche on line (streaming) sulla piattaforma Meet di Google, la stessa usata per il laboratorio. Gli studenti sono pregati di collegarsi (il martedì alle ore 9, il mercoledì alle ore 14 e il giovedì alle ore 9) utilizzando questo link
Per le lezioni di laboratorio, si veda la sezione “Informazioni per le lezioni di laboratorio”.
Come indicato nel seguente avviso, le verifiche intermedie previste per il 1 Aprile non avranno luogo. Consultate la sezione “Registro delle lezioni” per i compiti di autovalutazione sostitutivi assegnati e per l'esercitazione sostitutiva prevista i giorni 1 e 2 Aprile.
Gli studenti sono caldamente invitati a continuare a seguire le lezioni anche con le nuove modalita', e a non interrompere lo studio e la consultazione del materiale indicato. A supporto della preparazione degli studenti:
La prof. Pisanti riceve su skype o sulla piattaforma Google Meet al link previo appuntamento via mail.
La prof. Bernasconi riceve sulla piattaforma Meet di Google previo appuntamento via email.
Le lezioni di laboratorio si svolgeranno on line (streaming), a partire da martedì 10 marzo alle ore 14 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 14) utilizzando questo link
Gli studenti del corso di laurea in Data Science sono pregati di collegarsi (il martedi alle ore 11) utilizzando questo link
Gruppo Telegram con gli assistenti di laboratorio: link
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 |
---|---|
B1 | Aula H, martedì 14:00 - 16:00 |
B2 | Aula M, martedì 14:00 - 16:00 |
B3 | Aula I, martedì 14:00 - 16:00 |
Orario delle Lezioni | |||
---|---|---|---|
Martedì | 9-11 | E | Teoria |
Martedì | 14-16 | H, M, I | Laboratorio |
Mercoledì | 14-16 | E | Teoria |
Giovedì | 9-11 | E | Teoria |
Si pregano gli studenti che dispongono di un portatile di portarlo in Laboratorio.
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.
APPELLO DI LUGLIO: NUOVE MODALITA’ DI ESAME PER GLI STUDENTI DELLA LAUREA TRIENNALE
L'esame consiste in due prove obbligatorie che possono essere sostenute anche in appelli diversi:
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.
DATA SCIENCE STUDENTS ARE REQUESTED TO CONTACT ANY OF THE PROFESSORS FOR INSTRUCTIONS
Prossime date per la prova di laboratorio linguaggio C per studenti della Laurea Triennale:
Data | Ora | Tipo Prova | Avvisi | Aula Virtuale | Iscrizione |
---|---|---|---|---|---|
26/5/2020 | 09:00 | Laboratorio linguaggio C | Le istruzioni per l'accesso remoto alla piattaforma verranno inviate per mail agli iscritti | Piattaforma e poi discussione QUI | Sul portale di iscrizione esami, ed entro il 21/5 |
16/5/2020 | 09:00 | Laboratorio linguaggio C | Le istruzioni per l'accesso remoto alla piattaforma verranno inviate per mail agli iscritti | Piattaforma e poi discussione QUI | Sul portale di iscrizione esami entro l'11/6 |
7/7/2020 | 09:00 | Laboratorio linguaggio C | Le istruzioni per l'accesso remoto alla piattaforma verranno inviate per mail agli iscritti | Piattaforma e poi discussione QUI | Sul portale di iscrizione esami entro il 2/7 |
1/9/2020 | 09:00 | Laboratorio linguaggio C | Le istruzioni per l'accesso remoto alla piattaforma verranno inviate per mail agli iscritti | Piattaforma e poi discussione QUI | Sul portale di iscrizione esami entro il 27/8 |
27/10/2020 | 14:00 | Laboratorio linguaggio C | Le istruzioni per l'accesso remoto alla piattaforma verranno inviate per mail agli iscritti | Piattaforma e poi discussione QUI | Sul portale di iscrizione esami entro il 19/10 |
11/01/2021 | 14:00 | Laboratorio linguaggio C | Le istruzioni per l'accesso remoto alla piattaforma verranno inviate per mail agli iscritti | Piattaforma e poi discussione QUI | |
01/02/2021 | 14:00 | Laboratorio linguaggio C | Le istruzioni per l'accesso remoto alla piattaforma verranno inviate per mail agli iscritti | Piattaforma e poi discussione QUI |
Prossime date per le prove orali:
Per ogni data sono indicati i numeri di matricola degli iscritti alla prova.
Data | Ora | Tipo Prova | Note | Aula Virtuale | Iscrizione |
---|---|---|---|---|---|
27/5/2020 | 14:00 | Orale | 6-8 slot: Matricole 597443, 582593, 583191, 599933, 598319, 552497 | QUI | Iscrizioni Chiuse |
28/5/2020 | 09:00 | Orale | 6-8 slot: 568019, 600009, 600310, 596431, 599257, 601843 | QUI | Iscrizioni Chiuse |
29/5/2020 | 09:00 | Orale | 6-8 slot: 491919, 586306, 602549, 582077, 531425, 596363, 598067, 596883 | QUI | Iscrizioni Chiuse |
01/06/2020 | 09:00 | Orale | 10 slot: 602476, 584603, 583084, 563519, 598215, 578273, 584365 | QUI | Iscrizioni Chiuse |
04/06/2020 | 09:00 | Orale | 10 slot: 559768, 561119, 544545, 579633, 509902, 597983, 597287, 560445, 580259 | QUI | Iscrizioni Chiuse APPELLO MAGGIO TERMINATO |
17/06/2020 | 14:30 | Orale | 10 slot: 516482, 486651, 601241, 584365, 609124 | QUI | Iscrizioni Chiuse |
18/06/2020 | 09:00 | Orale | 10 slot: 572351, 589207, 596789, 598793 | QUI | Iscrizioni Chiuse |
19/06/2020 | 09:00 | Orale | 7 slot: 503317, 525069, 597525, 599427, 578743, 598871 | QUI | Iscrizioni Chiuse APPELLO GIUGNO TERMINATO |
08/07/2020 | 14:00 | Orale | 10 slot: 575656, 491265, 560141, 596681, 599523, 597415, 599329, 532492, 531889, 407651 | QUI | Iscrizioni Chiuse |
09/07/2020 | 09:00 | Orale | 9 slot: 465137, 559364, 525069, 597923, 600199, 602056, 543967, 600375, 599253 | QUI | Iscrizioni Chiuse |
10/07/2020 | 09:00 | Orale | 9 slot: 549045, 598296, 609124, 597455, 577947, 579839, 600035, 584615, 559441 | QUI | Iscrizioni Chiuse |
14/07/2020 | 14:00 | Orale | 10 slot: 562397, 549963, 522725, 601371, 598871, 562564, 476249, 588157, 545615 | QUI | Iscrizioni Chiuse APPELLO LUGLIO TERMINATO |
02/09/2020 | 09:00 | Orale | 10 slot: 562564, 609652, 600463, 598992, 566765, 598631, 578225, 559881; ore 14:30 605553. | QUI | Iscrizioni Chiuse |
03/09/2020 | 09:00 | Orale | 10 slot: 599065, 564777, 597603, 602495, 579271, 579477, 585477, 578287, 597765, 588157 | QUI | Iscrizioni Chiuse APPELLO SETTEMBRE TERMINATO |
28/10/2020 | 11:00 | Orale | 4 slot: 560353, 563798, 578177, 549963 | QUI | Iscrizioni Chiuse |
28/10/2020 | 15:00 | Orale | 8 slot: 598375, 597142, 588157 | QUI | Iscrizioni Chiuse APPELLO STRAORDINARIO TERMINATO |
18/1/2021 | 9:00 | Orale | 8 slot: 597727, 596135, 579151, 600894, 599899 | QUI | Iscrizioni Chiuse |
19/1/2021 | 9:00 | Orale | 8 slot: 552117, 581465, 588157 | QUI | Iscrizioni Chiuse APPELLO GENNAIO TERMINATO |
11/2/2021 | 8:30 | Orale | 9 slot: 564755, 588157, 598537, 581147, 562564, 578225, 407651, 597631, 600361 | QUI | Iscrizioni Chiuse |
11/2/2021 | 15:00 | Orale | 8 slot: 552685, 601717, 597339, 578976 | QUI | Iscrizioni Chiuse APPELLO FEBBRAIO TERMINATO |
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. | 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. | 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. | 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. | 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. | 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. | 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. | QUI | Nota: Se la data dell'esame coincide con quella di altri esami, inviatemi un'email per concordare un'altra data. |
Per il laboratorio, un testo fra:
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 Eclipse esteso con il suo plug-in Eclipse C/C++ Development Tooling. Per chi si trova a operare sotto Windows consigliamo di installare una macchina virtuale, come 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.Data | Argomento | Rif. Biblio |
---|---|---|
18/02/2020 | Nozioni di Problema, Algoritmo, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete. | 12 monete lavagna |
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]. Slide |
19/02/2020 | 12 monete (continua). 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. lavagna |
20/02/2020 | Insertion sort: analisi di complessità al caso ottimo e pessimo. Invariante di ciclo e dimostrazione di correttezza. Selection Sort: pseudocodice, esempio, enunciato dell'invariante di ciclo (da dimostrare a casa). | [CLRS] cap 2.2. lavagna |
25/02/2020 | Complessita' di Selection Sort. 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. TCS cheat sheet lavagna |
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]. Slide |
26/02/2020 | Esercitazione: Problema delle 9 monete. Ricerca Sequenziale e Ricerca Binaria. Esercizi sulla notazione asintotica. Sorting di vettore binario in loco. | lavagna |
27/02/2020 | 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. lavagna |
03/03/2020 | MergeSort: descrizione algoritmo, correttezza, analisi di complessità (con metodo iterativo e con albero di ricorsione). Esempio. | [CLRS] cap 2: 2.3, cap 4: 4.3 e 4.4. lavagna |
03/03/2020 | Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante | Slide |
04/03/2020 | Esercitazione: Algoritmi come tecnologia. Vettore Unimodulare. Mergeinsort. Altri esercizi su vettori: cerca i tale che A[i]=i; cerca uguali, sommak. | lavagna |
Da qui in poi le lezioni del corso teorico sono registrate | Ogni lezione ha una parte1 e una parte2, e per ciascuna di esse e' disponibile un file lavagna, e un file lezione | Il file lavagna* e' un .pdf Il file lezione* e' un .mp4 ATTENZIONE: PER AVERE L'AUDIO IL VIDEO DEVE ESSERE SCARICATO |
Lezione prevista il 05/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. Note di F. Luccio su limiti inferiori. lavagna1 lezione1 lavagna2 lezione2 |
Lezione prevista il 10/03/2020 | 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) lavagna1 lezione1 lavagna2 lezione2 |
10/03/2020 | Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | Slide |
Lezione prevista il 11/03/2020 | Relazioni di ricorrenza di ordine k. Esercizi sul Teorema dell'esperto. Algoritmo della Moltiplicazione veloce con analisi della complessità. Prodotto tra matrici. | Ricorrenze (dispensa Prof.Luccio: leggere introduzione, sezioni 1 e 3, saltando la sezione 2). moltiplicazione interi e matrici (note Prof.Luccio). lavagna1 lezione1 lavagna2 lezione2 |
Lezione prevista il 12/03/2020 | Quicksort: descrizione intuitiva, pseudo-codice, correttezza di Partition. Correttezza di Quicksort. Esempi di Partition e di QuickSort. | [CLRS] cap 7 lavagna lezione1 lezione2 |
Lezione prevista il 17/03/2020 | Complessita' di Partition, Correttezza di Quicksort. Analisi della complessità di Quicksort al caso pessimo, al caso ottimo e al caso medio. Versione randomizzata, e analisi della complessità. | [CLRS] cap 7 lavagna lezione1 lezione2 |
17/03/2020 | Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | Slide |
Lezione prevista il 18/03/2020 | Esercitazione. Esercizi di ripasso su QuickSort, equazioni di ricorrenza e ordinamento | lavagna lezione1 lezione2 |
Lezione prevista il 19/03/2020 | Correzione esercizi dati per casa. La struttura dati Heap: definizione, realizzazione implicita come array, proprieta'. | [CLRS] cap 6: 6.1. lavagna lezione1 lezione2 |
Lezione prevista il 24/03/2020 | Costruzione (BuildHeap) con Max-Heapify. Analisi della complessità e correttezza di MaxHeapify. Analisi della complessità e correttezza di BuildHeap. L'algoritmo Heapsort. Esempio. | [CLRS] cap 6: 6.2, 6.3, 6.4. lavagna lezione1 lezione2 lezione3 |
24/03/2020 | Laboratorio: Qsort e ripasso delle struct. | Slide |
Lezione prevista il 25/03/2019 | Code di priorità, operazioni, definizione e realizzazione mediante heap. Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort. | [CLRS] cap 6: 6.5. cap 8: 8.2. lavagna lezione1 lezione2 |
Lezione prevista il 26/03/2019 | Radix sort. Esercitazione su Divide et Impera, su heap e Heapsort. | cap 8: 8.3. lavagna lezione1 lezione2 CORREZIONE ESERCIZIO DATO PER CASA |
31/03/2020 | Laboratorio: Esercizi d'esame: qsort e struct. | Slide |
01/04/2020 COMPITINO ANNULLATO avviso | A SOSTITUZIONE DEL COMPITINO QUALE MOMENTO DI AUTOVALUTAZIONE SVOLGETE IL PRIMO COMPITINO DEL 2019 E QUELLO DEL 2018 BUON LAVORO! | SEGUONO DUE ESERCITAZIONI EXTRA CON LO SVOLGIMENTO REGISTRATO DEGLI STESSI |
01/04/2020 | Esercizitazione: svolgimento Primo Compitino 2019 | PROVATE DAVVERO A SVOLGERLO PRIMA DI VISIONARNE LA SOLUZIONE!! lavagna lezione |
02/04/2020 | Esercizitazione: svolgimento Primo Compitino 2018 | PROVATE DAVVERO A SVOLGERLO PRIMA DI VISIONARNE LA SOLUZIONE!! lavagna lezione1 lezione2 |
07/04/2020 | 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 (teoremi 11.1 e 11.2) lavagna video |
07/04/2020 | Laboratorio: Liste monodirezionali e bidirezionali. | Slide |
08/04/2020 | Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). | [CLRS] cap 11: 11.4 (teoremi 11.6 e 11.8, corollario 11.7) lavagna video |
09/04/2020 | Tabelle hash a indirizzamento aperto: Scansione lineare, scansione quadratica, doppio hash. Alberi e alberi binari: definizioni e rappresentazione in memoria. | [CLRS] cap 11: 11.4 lavagna video |
15/04/2020 | Alberi e alberi binari: visite. Alberi cardinali, alberi ordinali e notazione binarizzata. Esercitazione: esercizi su dizionari e tabelle hash. | [CLRS] cap 10: 10.4 Esercizi (hash) Soluzioni lavagna video |
16/04/2020 | Algoritmi Ricorsivi su Alberi Binari: schema generale D&I su alberi. Alberi Binari Completamente Bilanciati. Algoritmi ricorsivi per trovare: dimensione, altezza, ABCB, nodi cardine, nodi centrali. | [CGGR] Algoritmi ricorsivi su alberi binari lavagna lezione1 lezione2 |
21/04/2020 | Alberi Binari di Ricerca | [CLRS] cap 12: 12.1, 12.2. lavagna lezione1 lezione2 |
21/04/2020 | Laboratorio: Tabelle Hash. | Slide Esercizio 1 Esercizio 2 |
22/04/2020 | 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]: Alberi AVL, rotazioni lavagna video |
23/04/2020 | Esercitazione | Esercizi su Alberi Binari Esercizi su Alberi Binari di Ricerca lavagna lezione1 lezione2 |
28/04/2020 | Grafi: definizioni, rappresentazione in memoria. | [CLRS]: appendice B.4, cap 22: 22.1 lavagna video |
28/04/2020 | Laboratorio: Alberi binari di ricerca. | Slide Esercizio 1 (con verifica 1-bilanciamento) |
29/04/2020 | Grafi: visita in ampiezza (BFS), algoritmo, analisi di complessità, proprietà (senza dimostrazioni), albero BF e algoritmo PRINT-PATH. Grafi: visita in profondità (DFS), algoritmo. | [CLRS]: cap 22: 22.2, 22.3 lavagna video |
30/04/2020 | Grafi: visita in profondità (DFS), analisi di complessità, foresta DF, classificazione degli archi. | [CLRS] cap 22: 22.3, 22.4 (Teorema 22.7, Corollario 22.8, Teorema 22.9, Lemma 22.11) lavagna video |
05/05/2020 | Ordinamento topologico di grafi diretti aciclici. Esempi di problemi su grafi: clique, ciclo hamiltoniano, ciclo euleriano. Esercitazione: progettazione di algoritmi efficienti su grafi. | [CLRS] cap 22: 22.4 (Teorema 22.12) Esercizi su grafi lavagna 1 lavagna 2 video |
05/05/2020 | Laboratorio: simulazione prova d'esame. | Slide |
06/05/2020 | Esercitazione: progettazione di algoritmi efficienti (dizionari, grafi) | Esercizi su dizionari e alberi lavagna altri esercizi svolti su grafi altri esercizi svolti su dizionari video |
07/05/2020 | 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. | [CLRS] cap 15: 15.3. Programmazione Dinamica (note di F. Luccio) lavagna lezione1 lezione2 |
12/05/2020 | Calcolo della Edit Distance con la PD: regola ricorsiva e ricostruzione della soluzione, algoritmo ED. Complessita'. Esempio. | Edit Distance (note di F. Luccio) lavagna lezione |
12/05/2020 | Laboratorio: grafi. | Slide Esercizio 1 (Grafo Bipartito) Esercizio 2 (grafo connesso) |
13/05/2020 | Esercitazione su Programmazione Dinamica | Esercizi sulla Programmazione Dinamica SoluEditDistance lavagna lezione1 lezione2 |
14/05/2020 | Problemi Indecidibili e Problemi Intrattabili. Generazione delle sequenze binarie. Algoritmo enumerativo per il problema dello Zaino. | Calcolabilità The Towers of Hanoi: note di Tom Leighton e Ronitt Rubinfeld, MIT, 2006 [BFL]: generazione delle sequenze binarie e delle permutazioni lavagna video |
19/05/2020 | Generazione delle permutazioni. Teoria della complessità: classi P e NP, certificati, riduzioni, problemi NP-completi. | Le classi P, NP e NPC lucidi Complessità lavagna video |
19/05/2020 | Laboratorio: esercitazione finale | Slide |
20/05/2020 | Esercitazione: Certificati Polinomiali, Algoritmi Enumerativi. | lavagna video |
21/05/2020 | Ricevimento collettivo sostitutivo del secondo compitino |