Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
informatica:all-b:start [29/05/2019 alle 14:18 (5 anni fa)] – [Registro delle Lezioni] anna bernasconi | informatica:all-b:start [02/11/2023 alle 11:16 (11 mesi fa)] (versione attuale) – [Modalità di esame attuali e Appelli di Esame] Nadia Pisanti |
---|
| |
| |
===== Anno accademico 2018/2019 ===== | ===== Anno accademico 2019/2020 __e successivi__ ===== |
| |
| Questo corso non e' piu' erogato per cambio ordinamento: questa pagine contiene tuttavia tutte le informazioni per sostenere l'esame per gli iscritti al vecchio ordinamento. |
| |
| |
| |
| |
| **Docenti Teoria/Esercitazioni:** [[http://pages.di.unipi.it/pisanti/|Nadia Pisanti]], [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]] |
| |
| **Docenti Laboratorio:** [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]], [[http://pages.di.unipi.it/pibiri/|Giulio Pibiri]], [[http://pages.di.unipi.it/rossano/|Rossano Venturini]] |
| |
**Docenti Teoria/Esercitazioni:** [[http://www.di.unipi.it/~pagli/|Nadia Pisanti]], [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]] | |
| |
**Docenti Laboratorio:** [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]], [[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. | **Impegno:** 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. |
**Semestre:** secondo. | **Semestre:** secondo. |
| |
| **A.A. 2019-2020: La didattica frontale e' stata sospesa dal 5 Marzo 2020.** \\ |
| Di conseguenza, le lezioni teoriche dal 5 Marzo sono state svolte on-line e registrate e sono disponibili per gli studenti mediante link in questa pagina web nella sezione "Registro delle Lezioni". Nella stessa sezione, per tutte le lezioni e' disponibile una versione .pdf della lavagna. \\ |
| |
| |
| |
===== AVVISO ===== | |
| |
Questa settimana il ricevimento collettivo con gli studenti counselor si terra' **venerdì 3 maggio, 11-13** nella sala riunioni EST del dipartimento di Informatica. | |
| |
La lezione del giorno 16/4/2019 prevista dalle 11 alle 13 non avrà luogo a causa dell'indisponibilità delle Aule del Polo Didattico Fibonacci, occupate per il concorso per la specializzazione all’insegnamento di sostegno nelle scuole. | |
| |
**I laboratori del 16/4 avranno luogo regolarmente.** Tuttavia, l'Ateneo chiede agli studenti la cortesia di stazionare il meno possibile nei corridoi prima e dopo la lezione. | |
| |
===== Ricevimento Collettivo con i Counselor ===== | |
| |
A partire dal 13 Marzo, ogni Mercoledi' 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/1FAIpQLSe9YHV8NtwnsNsymVLGuUhoToT5ohH_xk-AjNvpvrk9vAV9mQ/viewform|Feedback per il Counseling]] | |
| |
[[https://github.com/DrDav/Algo1819/|Materiale didattico di supporto per il laboratorio (preparato dai counselor)]] | |
===== Anni accademici precedenti ===== | ===== Anni accademici precedenti ===== |
| |
| * [[.algoB_19:|A.A. 2018/2019]] |
* [[.algoB_18:|A.A. 2017/2018]] | * [[.algoB_18:|A.A. 2017/2018]] |
* [[.algoB_17:|A.A. 2016/2017]] | * [[.algoB_17:|A.A. 2016/2017]] |
* [[.algoB_16:|A.A. 2015/2016]] | * [[.algoB_16:|A.A. 2015/2016]] |
| |
===== Gruppi Laboratorio ===== | |
^ Gruppo ^ Aula e orario ^ | |
|B1 (da AAA a DE) | Aula H, lunedì 9:00 - 11:00 | | |
|B2 (da DEA a MAN) | Aula M, martedì 14:00 - 16:00 | | |
|B3 (da MAO a ZZZ) | Aula H, martedì 14:00 - 16:00 | | |
| |
| |
| |
| |
| |
===== Orario Lezioni ===== | |
| |
| |
^ Orario delle Lezioni ^^^^ | |
|Lunedì | 9-11 | H | Laboratorio (gruppo B1) | | |
|Martedì | 11-13 | E | Teoria | | |
|Martedì | 14-16 | H, M | Laboratorio (gruppi B2 e B3) | | |
|Mercoledì | 14-16 | E | Teoria | | |
|Giovedì | 9-11 | E | Teoria | | |
| |
| |
| |
Si pregano gli studenti che dispongono di un portatile di portarlo **in Laboratorio**. | |
| |
===== Obiettivi del Corso ===== | ===== Obiettivi del Corso ===== |
| |
---- | ---- |
===== Modalità e Appelli di Esame===== | ===== Modalità di esame attuali e Appelli di Esame ===== |
| |
L'esame consiste di due prove obbligatorie e una facoltativa: | |
| |
* Una prova scritta (obbligatoria) 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. | L'esame consiste in due prove obbligatorie che possono essere sostenute anche in appelli diversi: |
* Una prova in laboratorio (obbligatoria) 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 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 nelle date indicate sul portale esami di ateneo, e sara’ validata da un colloquio orale immediatamente successivo. Tale prova è da intendersi come un **test di idoneità** e l'__iscrizione__ deve essere fatta sul __portale esami__. |
* Una prova orale (facoltativa) sul programma del corso, la cui valutazione finale è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta. | * 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; le date sono indicate in questa pagina web e l'__iscrizione__ è da farsi __via mail__ entro le scadenza indicate per ogni data. |
* Le prove possono essere sostenute in appelli diversi. | * La prova orale puo' essere sostenuta da chiunque, anche senza aver superato il laboratorio. |
* La prova di laboratorio puo' essere sostenuta solo dopo aver superato la prova scritta. | * Precisazioni (a grande richiesta): |
* Se la prova di laboratorio non vine esuperata puo' essere ripetuta senza ripetere lo scritto, ma **SE LA PROVA DI LABORATORIO NON VIENE SUPERATA PER DUE VOLTE CONSECUTIVE, OCCORRE RIPETERE ANCHE LO SCRITTO. ** | * Se la prova orale non viene superata, occorre ripetere soltanto quella. |
* La prova orale e' facoltativa (salvo eccezioni motivate dal docente), puo' essere sostenuta solo dopo aver superato la prova scritta e la prova di laboratorio, e puo' dar luogo ad un incremento massimo di 4 punti rispetto al voto dello scritto. Se lo studente non intende sostenere la prova orale, ne' il docente ritiene che debba sostenerla, puo' registrare il voto dello scritto incrementato di 2 punti. | * Se la prova di laboratorio non viene superata, occorre ripetere soltanto quella. |
* Se la prova orale non viene superata, occorre ripetere soltanto quella. | * Ovvero: chi supera una prova (scritta o di laboratorio) non dovra' mai piu' ripeterla: vale per sempre. |
| * Chi avesse gia' superato lo scritto in passato puo' sostenere direttamente la prova di laboratorio (e, se superata, si contatti il docente per la verbalizzazione). |
| |
Per avere una idea della tipologia delle prove, si consultino i testi degli anni scorsi. | 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. |
**Prossime date per la prova scritta:** | |
| |
^ Data ^ Prova ^ Documenti ^ Avvisi ^ | **Le date delle prove di laboratorio sono sul portale esami e l'iscrizione deve avvenire sul portale** |
| 01/04/19 | Primo Compitino | {{:informatica:all-b:algo010419.pdf| Testo }}\\ {{algoritmica-b_-_esito-1ocompitino.pdf| Risultati}} \\ {{solu1compitino.pdf|Soluzione}} | 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 scritta d'esame. | | |
| 03/06/19 | Secondo Compitino | | | |
| |
| **Le date delle prove orali sulla teoria sono le seguenti e l'iscrizione (obbligatoria) deve avvenire per mail nelle modalita' indicate:**\\ |
| |
| Per ogni data sono riportati 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| [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 28/5/2020 | 09:00 | Orale | 6-8 slot: 568019, 600009, 600310, 596431, 599257, 601843 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 29/5/2020 | 09:00 | Orale | 6-8 slot: 491919, 586306, 602549, 582077, 531425, 596363, 598067, 596883 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 01/06/2020 | 09:00 | Orale | 10 slot: 602476, 584603, 583084, 563519, 598215, 578273, 584365| [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 04/06/2020 | 09:00 | Orale | 10 slot: 559768, 561119, 544545, 579633, 509902, 597983, 597287, 560445, 580259 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse \\ APPELLO MAGGIO TERMINATO | |
| | 17/06/2020 | 14:30 | Orale | 10 slot: 516482, 486651, 601241, 584365, 609124| [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 18/06/2020 | 09:00 | Orale | 10 slot: 572351, 589207, 596789, 598793 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 19/06/2020 | 09:00 | Orale | 7 slot: 503317, 525069, 597525, 599427, 578743, 598871 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse \\ APPELLO GIUGNO TERMINATO | |
| | 08/07/2020 | 14:00 | Orale | 10 slot: 575656, 491265, 560141, 596681, 599523, 597415, 599329, 532492, 531889, 407651 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 09/07/2020 | 09:00 | Orale | 9 slot: 465137, 559364, 525069, 597923, 600199, 602056, 543967, 600375, 599253 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 10/07/2020 | 09:00 | Orale | 9 slot: 549045, 598296, 609124, 597455, 577947, 579839, 600035, 584615, 559441 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 14/07/2020 | 14:00 | Orale | 10 slot: 562397, 549963, 522725, 601371, 598871, 562564, 476249, 588157, 545615 | [[https://meet.google.com/dfz-nrtj-vex | 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. | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 03/09/2020 | 09:00 | Orale | 10 slot: 599065, 564777, 597603, 602495, 579271, 579477, 585477, 578287, 597765, 588157 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse \\ APPELLO SETTEMBRE TERMINATO | |
| | 28/10/2020 | 11:00 | Orale | 4 slot: 560353, 563798, 578177, 549963 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 28/10/2020 | 15:00 | Orale | 8 slot: 598375, 597142, 588157 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse \\ APPELLO STRAORDINARIO TERMINATO | |
| | 18/1/2021 | 9:00 | Orale | 8 slot: 597727, 596135, 579151, 600894, 599899 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse | |
| | 19/1/2021 | 9:00 | Orale | 8 slot: 552117, 581465, 588157 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse \\ APPELLO GENNAIO TERMINATO | |
| | 11/2/2021 | 8:30 | Orale | 9 slot: 564755, 588157, 598537, 581147, 562564, 578225, 407651, 597631, 600361 | [[https://meet.google.com/ovz-uzmf-ezo | QUI ]] | Iscrizioni Chiuse | |
| | 11/2/2021 | 15:00 | Orale | 8 slot: 552685, 601717, 597339, 578976, 553015 | [[https://meet.google.com/ovz-uzmf-ezo | QUI ]] | Iscrizioni Chiuse \\ APPELLO FEBBRAIO TERMINATO | |
| | 26/3/2021 | 08:30 | Orale | 10 slot: 502525, 518897, 597179, 597797, 596533, 588157, 583951, 601433, 604487, 580182 | [[https://meet.google.com/ovz-uzmf-ezo | QUI ]] | Iscrizioni Chiuse \\ APPELLO STRAORDINARIO TERMINATO | |
| | 10/6/2021 | 14:30 | Orale | 10 slot: 597797, 583567, 583567, 588157, 597473, 560611, 560659, 604487 | [[https://meet.google.com/ovz-uzmf-ezo | QUI ]] | Iscrizioni Chiuse \\ APPELLO GIUGNO TERMINATO | |
| | 26/7/2021 | 09:00 | Orale | 579821, 518897, 597473, 407651 | [[https://meet.google.com/dfz-nrtj-vex | QUI ]] | Iscrizioni Chiuse \\ APPELLO LUGLIO TERMINATO | |
| | 3/9/2021 | 9:00 | Orale | 10 slot: | [[https://meet.google.com/ovz-uzmf-ezo | QUI ]] | Iscrizioni Chiuse \\ APPELLO SETTEMBRE TERMINATO | |
| | 26/10/2021 | 11:00 | Orale | 5 slot: | [[https://meet.google.com/ovz-uzmf-ezo | QUI ]] | Iscrizioni Chiuse \\ APPELLO STRAORDINARIO TERMINATO | |
| | 14/01/2022 | 09:00 | Orale | 6 slot: 550342, 578177, 600035, 596715, 598771, 583943 | [[https://meet.google.com/ovz-uzmf-ezo | QUI ]] | Iscrizioni Chiuse \\ APPELLO GENNAIO TERMINATO | |
| | 12/04/2022 | 16:00 | Orale | 6 slot: 604825, 578463, 561655, 577925, 601564 | [[https://meet.google.com/ovz-uzmf-ezo | QUI ]] | Iscrizioni Chiuse \\ APPELLO STRAORDINARIO TERMINATO | |
| | 11/05/2022 | 9:00 | Orale | 6 slot: 602065, 578463 | [[https://meet.google.com/ovz-uzmf-ezo | QUI ]] | Iscrizioni Chiuse | |
| | 19/05/2022 | 15:00 | Orale | 2 slot: 604825, 561655 | Ufficio Prof.ssa Pisanti | Iscrizioni Chiuse \\ APPELLO MAGGIO TERMINATO | |
| | 09/06/2022 | 09:00 | Orale | 4 slot: 537366, 584367, 407651 | Ufficio Prof.ssa Pisanti | Iscrizioni Chiuse \\ APPELLO GIUGNO TERMINATO | |
| | 26/07/2022 | 15:00 | Orale | 6 slot: 578463, 407651, 598075 | Ufficio Prof.ssa Pisanti | Iscrizioni Chiuse \\ APPELLO LUGLIO TERMINATO | |
| | 2/09/2022 | 09:00 | Orale | 6 slot: 407651, 578463 | Ufficio Prof.ssa Pisanti | Iscrizioni Chiuse \\ APPELLO SETTEMBRE TERMINATO | |
| | 3/11/2022 | 11:00 | Orale | 8 slot: 577925, 601564, 598075, 561655, 407651, 578463, 603449, 604263 | Ufficio Prof.ssa Pisanti | Iscrizioni Chiuse \\ APPELLO NOVEMBRE TERMINATO | |
| | 6/12/2022 | 09:00 | Orale | 8 slot: 577925, 601564, 578463, 407651, 605011, 598075 | Ufficio Prof.ssa Pisanti| Iscrizioni Chiuse \\ APPELLO DICEMBRE TERMINATO | |
| | 3/2/2023 | 14:30 | Orale | 8 slot: 407651, 578463, 577925, 601564 | Ufficio Prof.ssa Pisanti | Iscrizioni chiuse \\ APPELLO FEBBRAIO TERMINATO | |
| | 4/4/2023 | 09:00 | Orale | 8 slot: 597683, 599469 | Ufficio Prof.ssa Pisanti | Iscrizioni chiuse \\ APPELLO APRILE TERMINATO | |
| | 7/6/2023 | 09:00 | Orale | 8 slot: | Ufficio Prof.ssa Pisanti | Iscrizioni chiuse \\ APPELLO GIUGNO TERMINATO | |
| | 31/7/2023 | 09:00 | Orale | 8 slot: 252011, 599469, 598825, 407651 | Ufficio Prof.ssa Pisanti | Iscrizioni chiuse \\ APPELLO LUGLIO TERMINATO | |
| | 7/8/2023 | 15:00 | Orale | 3 slot: 407651 | Ufficio Prof.ssa Pisanti | Iscrizioni chiuse \\ APPELLO AGOSTO TERMINATO | |
| | 12/9/2023 | 14:00 | Orale | 5 slot: 252011 | Ufficio Prof.ssa Pisanti | Iscrizioni Chiuse \\ APPELLO SETTEMBRE TERMINATO | |
| | 3/11/2023 | 09:00 | Orale | 5 slot: | Ufficio Prof.ssa Pisanti | Iscrizioni Chiuse \\ APPELLO NOVEMBRE TERMINATO | |
| |
| | Da Dicembre 2023, chi volesse sostenere l'esame della parte teorice del Corso di Algoritmica e Laboratorio vecchio ordinamento, puo' farlo su appuntamento scrivendo una mail alla prof. Nadia Pisanti <nadia.pisanti@unipi.it> indicando nome, cognome e numero di matricola.| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
**Prossime date per la prova di laboratorio:** | |
| |
^ Data ^ Ora ^ Aule ^ | |
| |
| |
**Prossime date per le prove orali:** | |
^ Data ^ Ora ^ Aula ^ Note ^ | |
===== Libri di testo ===== | ===== Libri di testo ===== |
| |
* **__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. | * **__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. | * **__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/]] | * [[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/]] |
| |
| |
| |
- Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort. | - Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort. |
- Ordinamento di interi: Counting sort, Radix Sort. | - Ordinamento di interi: Counting sort, Radix Sort. |
- Ordinamento di stringhe: ''qsort''-based. | - Programmazione dinamica: Fibonacci, Edit Distance e Zaino |
- Sottosequenza di somma massima. | |
- Programmazione dinamica: LCS, Partizione e Zaino | |
- Algoritmi randomizzati: Quicksort. | - Algoritmi randomizzati: Quicksort. |
- Cenni di trattabilità (P, NP, NPC, EXP-TIME). | - Cenni di trattabilità (P, NP, NPC, EXP-TIME). |
- Generazione di combinazioni e permutazioni | - Generazione di combinazioni e permutazioni |
- Analisi ammortizzata: doubling di array, contatore binario, k ricerche. | - Analisi ammortizzata: doubling di array, contatore binario, k ricerche. |
- Dizionari: Alberi bilanciati (Alberi 2-3), Tabelle hash (liste di trabocco e indirizzamento aperto). | - Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto). |
- Alberi: rappresentazione e visite. | - Alberi: rappresentazione e visite. |
- Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico. | - Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico. |
- Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse. | - Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse. |
- Grafi III: Minimum Spanning Tree e Shortest Path. | - Grafi III: Minimum Spanning Tree e Shortest Path. |
| |
| |
===== Registro delle Lezioni ===== | ===== Registro delle Lezioni ===== |
| |
^ Data ^ Argomento ^ Rif. Biblio ^ | ^ Data ^ Argomento ^ Rif. Biblio ^ |
| 18/02/2019 19/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}} | | | 18/02/2020 | Nozioni di Problema, Algoritmo, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete.|{{:informatica:all-b:12monete.pdf|12 monete}} \\ {{https://drive.google.com/file/d/1_4hkrDoyt43qvhjN6gAylB8DfHNf9f_a/view?usp=sharing | lavagna }} | |
| 19/02/2019 | Nozioni di Problema, Algoritmo, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete.|{{: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/2019 | 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.| | | 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. \\ {{https://drive.google.com/file/d/118D_PtjyijLkPfYdsDdSstZGYG0CiDwB/view?usp=sharing | lavagna }} | |
| 21/02/2019 | Insertion sort: analisi di complessità al caso ottimo e pessimo. Invariante di ciclo e dimostrazione di correttezza. Selection sort: pseudocodice, esempio, e analisi di complessità. | [CLRS] cap 2.2.| | | 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. \\ {{https://drive.google.com/file/d/1zsjob55eVJASw9wknkjvcuwh0lhW0CU0/view?usp=sharing | lavagna }}| |
| 25/02/2019 26/02/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}} | | | 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. \\ {{:informatica:all-b:TCScheat.pdf|TCS cheat sheet}} \\ {{https://drive.google.com/file/d/1FK5N546oRtklqH5GUaNEuSm069RsAZkF/view?usp=sharing | lavagna}}| |
| 26/02/2019 | Esercitazione: Invariante di ciclo di SelectionSort, Ricerca Sequenziale e Binaria, Vettore Unimodulare. Per casa: Problema delle 9 monete, sorting di vettore binario in loco. | | | | 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/2019 | 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. {{:informatica:all-b:TCScheat.pdf|TCS cheat sheet}} | | | 26/02/2020 | Esercitazione: Problema delle 9 monete. Ricerca Sequenziale e Ricerca Binaria. Esercizi sulla notazione asintotica. Sorting di vettore binario in loco. | {{https://drive.google.com/file/d/1I7v6Uy1cFM8Vqmy67fGil65eSx3Gielg/view?usp=sharing | lavagna}} | |
| 28/02/2019 | 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.| | | 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. \\ {{https://drive.google.com/file/d/1WyMF1KeiTGQVVs_2D-XwpwWj0dferht6/view?usp=sharing| lavagna}}| |
| 04/03/2019 05/03/2019 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} | | | 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. \\ {{https://drive.google.com/file/d/1Qho7jOs8m9SpJ6MR1UG_73mIS-Xynuze/view?usp=sharing | lavagna}}| |
| 05/03/2019 | MergeSort: algoritmo, correttezza, analisi di complessità (metodo iterativo e albero di ricorsione). Esempio. | [CLRS] cap 2: 2.3, cap 4: 4.3 e 4.4.| | | 03/03/2020 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} | |
| 06/03/2019 | Esercitazione: soluzione esercizi dati per casa. Mergeinsort. Altri esercizi su vettori. | | | | 04/03/2020 | Esercitazione: Algoritmi come tecnologia. Vettore Unimodulare. Mergeinsort. Altri esercizi su vettori: cerca i tale che A[i]=i; cerca uguali, sommak. | {{https://drive.google.com/file/d/1fZkzlxHLJYakJobAC4jaBLKGElnLP4ZP/view?usp=sharing | lavagna}} | |
| 07/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. [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/limitiinf.pdf | Note di F. Luccio]] su limiti inferiori. | | | 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 | |
| 11/03/2019 12/03/2019 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-a:lezione4.pdf|Slide}} | | | 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. \\ {{:informatica/all-b/limitiinf.pdf | Note di F. Luccio}} su limiti inferiori. \\ {{ https://drive.google.com/file/d/1A0bdhCBUKXd_kMn2BZ8pmr7x84Lps4ix/view?usp=sharing | lavagna1 }} {{https://drive.google.com/file/d/1yt-NIGt9ulBle18A3mJtyRjUbcIM9Y0C/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/1m5vY2R4nRS-_GiBKxWofphUG9aijNK0y/view?usp=sharing | lavagna2}} {{ https://drive.google.com/file/d/1heyLkgxRFQUZX1231TkTMMDoWSU_zOnp/view?usp=sharing | lezione2}} | |
| 12/03/2019 | 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) | | | 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) \\ {{ https://drive.google.com/file/d/1tA4eZxGNCWIeHQaZdkEUlHPYjp8Bgbkc/view?usp=sharing | lavagna1 }} {{ |
| 13/03/2019 | Relazioni di ricorrenza di ordine k. Esercizitazione sul Teorema dell'esperto: algoritmo della Moltiplicazione veloce con analisi della complessità. (Studiare anche prodotto veloce tra matrici.) | {{:informatica:all-a:Ricorrenze.pdf| Ricorrenze}} (dispensa Prof.Luccio: leggere introduzione, sezioni 1 e 3, saltando la sezione 2). {{ :informatica:all-a:prodotto_interi_e_matrici.pdf |moltiplicazione interi e matrici}} (note Prof.Luccio). | | https://drive.google.com/file/d/1YoZxaEI0Sdn9SYCqLEAEK-15ixVPprEB/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/1_5fEb5msPOiXabu6U758pz6CeZdNho6d/view?usp=sharing | lavagna2}} {{ https://drive.google.com/file/d/1sin3N7bMlyFl_fWdAxBDFXJbxzAILsb1/view?usp=sharing | lezione2}} | |
| 16/03/2019 | Quicksort: descrizione intuitiva, pseudo-codice, correttezza e complessita' di Partition. Correttezza di Quicksort. Esempi. | [CLRS] cap 7 | | | 10/03/2020 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-a:lezione4.pdf|Slide}} | |
| 18/03/2019 19/03/2019| **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5.pdf |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. | {{:informatica:all-a:Ricorrenze.pdf| Ricorrenze}} (dispensa Prof.Luccio: leggere introduzione, sezioni 1 e 3, saltando la sezione 2). {{ :informatica:all-a:prodotto_interi_e_matrici.pdf | moltiplicazione interi e matrici}} (note Prof.Luccio). \\ {{ https://drive.google.com/file/d/1yP5gCRgclSpSlRplSghEs_96Ch4uyWgL/view?usp=sharing | lavagna1 }} {{ https://drive.google.com/file/d/1QjSMlTpxmYJmbUDoevQJrJ8YskAThK-9/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/1_2ZAGKz5OkPvhXwL83Z49B5Hds0EvYtP/view?usp=sharing | lavagna2}} {{ https://drive.google.com/file/d/1DCZMo2DSyljivBz0MFEYaODFsM2g2nB5/view?usp=sharing | lezione2}} | |
| 19/03/2019 | Quicksort: analisi della complessità al caso pessimo, al caso ottimo e al caso medio. Versione randomizzata, e analisi della complessità. | [CLRS] cap 7 | | | 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 \\ {{https://drive.google.com/file/d/1iRRxtcNUMpdSEgVbZhLqjRYjX8dgAGBX/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1PIaGnOnkmlEBbmefi5MK6HcULaESFXCH/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/1l2EUIvUFGm8eAfrcqspPmVuXMxAYccOC/view?usp=sharing | lezione2}} | |
| 20/03/2019 | La struttura dati Heap: definizione, realizzazione implicita come array, proprieta', costruzione (BuildHeap) con Max-Heapify. Analisi della complessità e correttezza di MaxHeapify. | [CLRS] cap 6: 6.1, 6.2, 6.3.| | | 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 \\ {{https://drive.google.com/file/d/1dNB0iC9MYevAXN1slw0qMXEq4b-V9L_U/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1r3f1F5HRqJjAfQQz8ytbuB5LKegeaZZV/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/1jZnhaJ6kMXJWs0vFvXkAN0hEh7NdPV7u/view?usp=sharing | lezione2}} | |
| 21/03/2019 | Analisi della complessità e correttezza di BuildHeap. L'algoritmo Heapsort. Esercizi sull'Heap. Code di priorità, operazioni, definizione e realizzazione mediante heap. | [CLRS] cap 6: 6.3, 6.4., 6.5 | | | 17/03/2020| **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5.pdf |Slide}}| |
| 25/03/2019 26/03/2019 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-a:lezione6.pdf|Slide}} | | | Lezione prevista il 18/03/2020 | Esercitazione. Esercizi di ripasso su QuickSort, equazioni di ricorrenza e ordinamento | {{https://drive.google.com/file/d/1KXyO3zGH09PidnRFRkxqmGn9Asi4CvT1/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1DQWr5mdttMVddEANF6EqYPOzvaFi3MLV/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/1zsVpkbQ-TKX5f0e9H0J-6ywYhijScQKl/view?usp=sharing | lezione2}} | |
| 26/03/2019 | Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. | [CLRS] cap 8: 8.2, 8.3. | | | 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. \\ {{https://drive.google.com/file/d/1YU_w-3-vsB2g6oJ_mo5gB_7Eh3EiO8Jl/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/16-I1-h-7Xqak6i6PjsT7ERAdKTLshB0b/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/1NahzJWpwUl4naUvH4L-1pzNtIMP0s5xs/view?usp=sharing | lezione2}} | |
| 27/03/2019 | Esercitazione. Esercizi di ripasso su Divide et Impera, equazioni di ricorrenza e ordinamento .| | | | 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. \\ {{ https://drive.google.com/file/d/1rDzdUqh7bUyOdLjVwaw-SETq4TgTgEVT/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1NQelyh_EEIBfUD4A06KzmnU3sW5j_oDD/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/1EDlTFORgrS8tultvDpJvYiXbpcwnwiwh/view?usp=sharing | lezione2}} {{ https://drive.google.com/file/d/1cQ-PLJyL7y667xxw7qvQYS7Qj83uLCR4/view?usp=sharing | lezione3}}| |
| 28/03/2019 | Esercitazione. Esercizi di ripasso su QuickSort e su heap e heapsort. | | | | 24/03/2020 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-a:lezione6.pdf|Slide}} | |
| 01/04/2019 | **PRIMA VERIFICA INTERMEDIA** Corso B 11-13| | | | 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. \\ {{ https://drive.google.com/file/d/17_xa1EIfw8-xSVYDrbnnz30k4xIF51eH/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1e7PQXc7dH54FtouvS3wPutOpR3YRrsNd/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/124pgDa6REaw0X2Ed06BNnPMfD387KMQD/view?usp=sharing | lezione2}} | |
| 08/04/2019 09/04/2019 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} | | | Lezione prevista il 26/03/2019 | Radix sort. Esercitazione su Divide et Impera, su heap e Heapsort. | cap 8: 8.3. \\ {{ https://drive.google.com/file/d/18m5p_A4epTr-un3K6ml1XAmdAt5jpvbm/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1BVpYrZEGKxsd9iY4VecXHAxoFpV0i454/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/1tYywsyBcT1RRq_GQGIwqC75otNE3MhBc/view?usp=sharing | lezione2}} {{ https://drive.google.com/file/d/10C4oPRhaGcUROtM5TABiyCAJZnznRANY/view?usp=sharing | CORREZIONE ESERCIZIO DATO PER CASA}} | |
|9/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.2, 11.2, 11.3, 11.3.1. {{https://drive.google.com/file/d/1ve9JkUNGV4plfsRH3G1PV5Y3MDgRPvLD/view?usp=sharing|lavagna}} | | | 31/03/2020 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} | |
|10/04/2019 | Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica. |[CLRS] cap 11: 11.4. {{https://drive.google.com/file/d/18kO8NoyjedvR8iucUICP7CrhW5FsOFAl/view?usp=sharing|lavagna}} | | | 01/04/2020 \\ COMPITINO ANNULLATO \\ {{https://didattica.di.unipi.it/prove-di-verifica-intermedia-annullamento | avviso}} | A SOSTITUZIONE DEL COMPITINO QUALE MOMENTO DI AUTOVALUTAZIONE SVOLGETE \\ IL PRIMO COMPITINO DEL {{:informatica:all-b:algo010419.pdf| 2019 }} E QUELLO DEL {{informatica:all-b:algo_040418_versione_1_.pdf | 2018}} \\ **BUON LAVORO!** | SEGUONO DUE ESERCITAZIONI EXTRA CON LO SVOLGIMENTO REGISTRATO DEGLI STESSI | |
|11/04/2019 | Tabelle hash a indirizzamento aperto: doppio hash. Alberi e alberi binari: visite.|[CLRS] cap 11: 11.4, cap 10: 10.4. {{https://drive.google.com/file/d/16EuMhxkIgzk7cd9SptyVQfwbsEPvl1z0/view?usp=sharing|lavagna}} {{ :informatica:all-b:EserciziHash.pdf | Esercizi (hash)}} {{ :informatica:all-b:SoluzioniHash.pdf | Soluzioni (hash)}} | | | 01/04/2020 | Esercizitazione: svolgimento Primo Compitino 2019 | PROVATE **DAVVERO** A SVOLGERLO PRIMA DI VISIONARNE LA SOLUZIONE!! \\ {{ https://drive.google.com/file/d/1X8kztByGGMFGT8zdNKtMIhnppF4YLtPG/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1N1ZatIQUY5DVhVmPlF14EAWpmRzL7Ny7/view?usp=sharing | lezione }} | |
| 15/04/2019 16/04/2019 | **Laboratorio**: Liste monodirezionali e bidirezionali. LUNEDI' gruppo B1, MARTEDI' gruppi B2 e B3| {{ :informatica:all-a:lezione8-1415.pdf |Slide}}| | | 02/04/2020 | Esercizitazione: svolgimento Primo Compitino 2018 | PROVATE **DAVVERO** A SVOLGERLO PRIMA DI VISIONARNE LA SOLUZIONE!! \\ {{ https://drive.google.com/file/d/1FfwzmVG9CWF8e3SYjUyfQOHCAR3EbXWT/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1J1sQXhcjJRF1KraL3eRDybcX8SZOH_TE/view?usp=sharing | lezione1 }} {{ https://drive.google.com/file/d/1_wrn4j_DwiIHrCpXPIHoLWJYpiz5zZgP/view?usp=sharing | lezione2 }}| |
|16/04/2019 | **LEZIONE NON TENUTA** a causa dell'indisponibilità delle Aule del Polo Didattico Fibonacci, occupate per il concorso per la specializzazione all’insegnamento di sostegno nelle scuole. || | | 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) \\ [[https://drive.google.com/file/d/1xLj_Mx4RgS3EyIEcROL0Jvmj1aW1XTUV/view?usp=sharing| lavagna]] [[https://drive.google.com/file/d/1bzMLLRI3VQuOlvF3Ds8coFQypsN6WICq/view?usp=sharing|video]]| |
|17/04/2019 | Algoritmi ricorsivi su alberi binari. Dizionari: realizzazione con alberi binari di ricerca (interrogazioni: ricerca, minimo, massimo, successore, predecessore). |[CLRS] cap 12: 12.1, 12.2. [CGGR]: {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}} {{https://drive.google.com/file/d/1cwv8n6cKTC9DLJHJhIiERxy-TTv__V6h/view?usp=sharing|lavagna}} | | | 07/04/2020 | **Laboratorio**: Liste monodirezionali e bidirezionali. | {{ :informatica:all-a:lezione8-1415.pdf |Slide}}| |
| 29/04/2019 30/04/2019 | **Laboratorio**: Tabelle Hash. LUNEDI' gruppo B1, MARTEDI' gruppi B2 e B3| {{ :informatica:all-b:lezionehash.pdf |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) \\ [[https://drive.google.com/file/d/1WYXLGzWyxxO6sx2Glexqs7yiCjfxBVUN/view?usp=sharing| lavagna]] [[https://drive.google.com/file/d/1uKCvH-bMVG0gceL8TXYxQuI1Z049z3Bu/view?usp=sharing|video]] | |
|30/04/2019 | Dizionari: realizzazione con alberi binari di ricerca (inserimento e cancellazione). Correzione della prima prova di verifica intermedia. |[CLRS] cap 12: 12.3 {{https://drive.google.com/file/d/1Se297vYwiGO3Q26KmKkcQOKwMdSKsQzE/view?usp=sharing|lavagna}} | | | 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 \\ [[https://drive.google.com/file/d/1lmGFRKd5n_WyYBCY8nRVoT3FfTbkmN7Y/view?usp=sharing| lavagna]] [[https://drive.google.com/file/d/1yk94i5m5TeCqMbD-ppXE0Ps74rBDVcGB/view?usp=sharing|video]]| |
| 02/05/2019 | **Esercitazione**: Esercizi su alberi binari e alberi binari di ricerca.| {{ :informatica:all-b:eserciziAlberi2016.pdf | Esercizi (alberi binari)}} {{ :informatica:all-a:ABR2019.pdf | Esercizi (alberi binari di ricerca)}} {{https://drive.google.com/file/d/1SV9gggMdKuQitXNWLDr3ZdKyrDdBY1CH/view?usp=sharing|lavagna}} {{ :informatica:all-b:SoluzioniABABR.pdf | Alcune altre soluzioni}} | | | 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 \\ {{ :informatica:all-b:EserciziHash.pdf|Esercizi (hash)}} {{ :informatica:all-b:SoluzioniHash.pdf| Soluzioni}} \\ [[https://drive.google.com/file/d/1Ex5h-Lz-qaTYLxNH2ngkYvZHgQ2oK5Ja/view?usp=sharing | lavagna]] [[https://drive.google.com/file/d/1xDSKkvrPVQBn_dTHxYPIwx4Q-Ut9DXPz/view?usp=sharing | video]]| |
| 06/05/2019 07/05/2019 | **Laboratorio**: Alberi binari di ricerca. | {{ :informatica:all-a:lezioneabr.pdf |Slide}}| | | 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] {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}} \\ {{ https://drive.google.com/file/d/1cH9vk9tLgLSwY_5ueTpBWUqGakoi5kcj/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/11vgsG7I9v4BsVpghMgSRrlcGyC57SdiG/view?usp=sharing | lezione1 }} {{ https://drive.google.com/file/d/1uGyd5uVjFDdqvpgK-fown0y71nGw-Nw8/view?usp=sharing | lezione2 }}| |
| 07/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}} {{https://drive.google.com/file/d/1iVO5_93fYfhQ55L1Oy4LEh1NojChmEeF/view?usp=sharing|lavagna}}| | | 21/04/2020 | Alberi Binari di Ricerca | [CLRS] cap 12: 12.1, 12.2. \\ {{ https://drive.google.com/file/d/1UMjsnM3ItY2zp8nYAY_-fD-bAIasxnyc/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1HOOGjxmPKb5B49fBHXjtxXaa_ALvpOFa/view?usp=sharing | lezione1 }} {{ https://drive.google.com/file/d/1clZJh5SukMFwaO4PS9XXNfe_NGijuEZI/view?usp=sharing | lezione2 }} | |
|08/05/2017 | Grafi: definizioni, rappresentazione in memoria. Grafi: visita in ampiezza (BFS), algoritmo.| [CLRS]: appendice B.4, cap 22: 22.1, 22.2 {{https://drive.google.com/file/d/116PqRGAh-SioY2x5abhZEVwIbRhhutBV/view?usp=sharing|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}}| |
|09/05/2017 | Grafi: visita in ampiezza (BFS), analisi di complessità, proprietà, albero BF e algoritmo PRINT-PATH. Grafi: visita in profondità (DFS), algoritmo, analisi di complessità, foresta DF.| [CLRS]: cap 22: 22.2, 22.3 {{https://drive.google.com/file/d/1VDU2GFKTGVFECSpiYVcd1A3Mc2LfA1-u/view?usp=sharing|lavagna}} | | | 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]: {{:informatica:all-b:AVL.pdf|Alberi AVL}}, {{:informatica:all-b:rotazioniavl.pdf| rotazioni}}\\ [[https://drive.google.com/file/d/1V15xz88NRz_0k10mmiST_syZWzx9L9JV/view?usp=sharing | lavagna]] [[https://drive.google.com/file/d/1Ge9wEE4sQ8cmDXu55N_sRXsehD-vmIF0/view?usp=sharing | video]]| |
| 13/05/2019 14/05/2019 | **Laboratorio**: Grafi. | {{ :informatica:all-b:lezionegrafi.pdf |Slide}} {{{:informatica:all-b/grafo_bipartito.pdf|Esercizio1}}| | | 23/04/2020 | Esercitazione | {{ informatica:all-b:eserciziAlberi2016.pdf | Esercizi su Alberi Binari}} \\ {{ :informatica:all-a:ABR2019.pdf | Esercizi su Alberi Binari di Ricerca}} \\ {{ https://drive.google.com/file/d/18lSquxfExD4MMdyhVwIOjvnNv34TeH5g/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1083hEBkEO0knJ1XUlpMUDanHTUpyZOIp/view?usp=sharing | lezione1 }} {{ https://drive.google.com/file/d/1ecvK8Ita3eJ5bMwCpvqapZDIHL5D_QPp/view?usp=sharing | lezione2 }} | |
| 14/05/2019 | Grafi: visita in profondità (DFS), classificazione degli archi, ordinamento topologico di grafi diretti aciclici.|[CLRS] cap 22: 22.3, 22.4. {{https://drive.google.com/file/d/15brzf2VC7VeePXq_0pqVC18u7uBvm-hq/view?usp=sharing|lavagna}}| | | 28/04/2020 | Grafi: definizioni, rappresentazione in memoria. | [CLRS]: appendice B.4, cap 22: 22.1 \\ [[https://drive.google.com/file/d/1ngJ-80KDtnC5Xm5-kSI8g7C0nsgOIqIe/view?usp=sharing | lavagna]] [[https://drive.google.com/file/d/1n0EjCU4QP-vG5upxZcXEy44IKXdBcOV-/view?usp=sharing | video]]| |
| 15/05/2019 | Esempi di problemi su grafi: clique, ciclo hamiltoniano, ciclo euleriano. **Esercitazione**: progettazione di algoritmi efficienti su grafi.|{{:informatica:all-b:esercizigrafi19.pdf|Esercizi}} {{https://drive.google.com/file/d/1sw6hl-u6HtqIhmcMuduEparHkDR4MsrZ/view?usp=sharing|lavagna}} {{https://drive.google.com/file/d/183NuU0VQ6Kl0buwu9zemOOEjrmcgPgpx/view?usp=sharing|altre soluzioni}}| | | 28/04/2020 | **Laboratorio**: Alberi binari di ricerca. | {{ :informatica:all-a:lezioneabr.pdf |Slide}} \\ {{:informatica:all-b:EsercizioABRAVL.pdf |Esercizio 1 (con verifica 1-bilanciamento)}}| |
| 16/05/2019 | Problemi indecidibili e problemi intrattabili. Generazione delle sequenze binarie e delle permutazioni. | {{{:informatica:all-b/calc2019.pdf|Calcolabilità}} {{ :informatica:all-b:thetowersofhanoi.pdf | The Towers of Hanoi: note di Tom Leighton e Ronitt Rubinfeld, MIT, 2006}} {{:informatica:all-b:binperm.pdf |[BFL]: generazione delle sequenze binarie e delle permutazioni}} [[https://www.youtube.com/watch?v=Q4gTV4r0zRs|Time with class! Let's count!]] {{https://drive.google.com/file/d/1A151G5JNmxyWpWIgyJXpJtCZSKt2EzJZ/view?usp=sharing|lavagna}}| | | 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 \\ [[https://drive.google.com/file/d/1eHEuo9g0fSWzBkFRyei9LrplHbF31arH/view?usp=sharing | lavagna ]][[https://drive.google.com/file/d/1N_Iir8z7zdlo3IDdVsuP8R6JmBzbBhjP/view?usp=sharing | video]]| |
| 20/05/2019 21/05/2019 | **Laboratorio**: Simulazione prova di esame.|{{ :informatica:all-b:solgrafi.pdf |Slide}} | | | 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)\\ [[https://drive.google.com/file/d/1S-cTui7X0JWj5thOlCupV8JHRTS06JiE/view?usp=sharing | lavagna ]][[https://drive.google.com/file/d/1PL4cfUa2G9m8AtkfWsQHOxZdcdZ_OQ1P/view?usp=sharing | video]]| |
| 21/05/2017 | 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. |{{:informatica:all-b:PD.pdf|Programmazione Dinamica (note di F. Luccio)}} \\ [CLRS] cap 15: 15.3.| | | 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) \\ {{:informatica:all-b:esercizigrafi19.pdf|Esercizi su grafi}} [[https://drive.google.com/file/d/11QjT8K8oZ8OAhkaG0Yfqj-f5IG8yqZ_P/view?usp=sharing | lavagna 1]] [[https://drive.google.com/file/d/1rZZBWNDnzXpYxspmKRi6JmKy7g-nXo31/view?usp=sharing | lavagna 2]] [[https://drive.google.com/file/d/1I7Ievwuz41CMlBYiGgr07xAnkwRB5Uwl/view?usp=sharing | video]]| |
| 22/05/2018 | Calcolo della Edit Distance con la PD: regola ricorsiva e ricostruzione della soluzione, algoritmo ED. Complessita'. Esempio.|{{:informatica:all-b:ED.pdf|Edit Distance (note di F. Luccio)}}. | | | 05/05/2020 | **Laboratorio**: simulazione prova d'esame. | {{ :informatica:all-a:SolAlberi.pdf |Slide}} | |
| 23/05/2018 | Il problema dello Zaino: Tecnica Greedy e Programmazione Dinamica. Algoritmo enumerativo per il problema dello zaino basato su genera binarie. Algoritmi pseudopolinomiali. | [CLRS] cap 16: 16.2,\\ {{:informatica:all-b:ZainoPD.pdf|Algoritmo PD per lo Zaino}}.\\ [CGGR]: {{:informatica:all-b:pseudo.pdf |pseudopolinomialità}}. | | | 06/05/2020 | **Esercitazione**: progettazione di algoritmi efficienti (dizionari, grafi)| {{:informatica:all-b:DizAlberi2019.pdf|Esercizi su dizionari e alberi}} \\ [[https://drive.google.com/file/d/1mUxUQXo_34oDXW5f6f8l2A_Ibp4SFvLj/view?usp=sharing|lavagna]] [[https://drive.google.com/file/d/1fIJBVYWcp1QeTjcwiQoTBP-mQbth1hRa/view?usp=sharing|altri esercizi svolti su grafi]] [[https://drive.google.com/file/d/1RSoz_SrcMxc0c2DGRk-XY2rx0UfhhBE8/view?usp=sharing|altri esercizi svolti su dizionari]] [[https://drive.google.com/file/d/1nzrGx3xtXERDT6wQReK2KCz7vQk5WJGK/view?usp=sharing | video]] | |
| 28/05/2018 | Teoria della complessità: le classi P e NP, i problemi NP-completi. |[BFL]: {{ :informatica:all-b:p-np.pdf | Le classi P, NP e NPC}} \\ {{ :informatica:all-b:p-np-slides.pdf | Lucidi P-NP}} \\ [CLRS] cap 34 | | | 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. \\ {{:informatica:all-b:PD.pdf|Programmazione Dinamica (note di F. Luccio)}} \\ {{ https://drive.google.com/file/d/1UIFEQfVoeJ5whBPjozpxh39_ZaHsQgZ_/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1zY-9kfwOGJHd69-reB6d-eQfki-iCoZE/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/172WAbI9qfrVHK5IoCMDYX77asAfYUHom/view?usp=sharing | lezione2}} | |
| 28/05/2018 | {{ :informatica:all-b:testset.zip |}} | | | 12/05/2020 | Calcolo della Edit Distance con la PD: regola ricorsiva e ricostruzione della soluzione, algoritmo ED. Complessita'. Esempio. | {{:informatica:all-b:ED.pdf|Edit Distance (note di F. Luccio)}} \\ {{https://drive.google.com/file/d/12ew3t8JYjf6LBUgUiQMI4SSrbmu-bEg4/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1Is_kLNIf_BnrQSl_6XladtYL57iVaHYJ/view?usp=sharing | lezione}} | |
| 30/05/2019 | **Esercitazione**: progettazione di algoritmi efficienti (dizionari e alberi)..|{{:informatica:all-b:DizAlberi2019.pdf|Esercizi}} | |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)}}| |
| | 13/05/2020 | Esercitazione su Programmazione Dinamica | {{ :informatica:all-b:eserciziprogdinamica.pdf | Esercizi sulla Programmazione Dinamica}} \\ {{:informatica:all-b:ExEditDistance.pdf| SoluEditDistance }} \\ {{ https://drive.google.com/file/d/1T7DwCTQRFzPdEQ4XafDIpjrcSEyY-Zg2/view?usp=sharing | lavagna }} {{ https://drive.google.com/file/d/1Skk7jEc4XG5SD3k3L51VNFomLZOXurbm/view?usp=sharing | lezione1}} {{ https://drive.google.com/file/d/189knZtcS_9zJdhdVL3v77eU_PefgSJZA/view?usp=sharing | lezione2}} | |
| | 14/05/2020 | Problemi Indecidibili e Problemi Intrattabili. Generazione delle sequenze binarie. Algoritmo enumerativo per il problema dello Zaino. |{{:informatica:all-b/calc2020breve.pdf|Calcolabilità}} {{ :informatica:all-b:thetowersofhanoi.pdf | The Towers of Hanoi: note di Tom Leighton e Ronitt Rubinfeld, MIT, 2006}} {{:informatica:all-b:binperm.pdf |[BFL]: generazione delle sequenze binarie e delle permutazioni}} [[https://drive.google.com/file/d/11Lnat6K34uh9P9PjLV9f3TbkSmzpyc0a/view?usp=sharing | lavagna ]] [[https://drive.google.com/file/d/1Ibqd-WCmDWdQ2v_6x_U8wp-Jd3upLTNB/view?usp=sharing| video ]]| |
| | 19/05/2020 | Generazione delle permutazioni. Teoria della complessità: classi P e NP, certificati, riduzioni, problemi NP-completi.| {{ :informatica:all-b:p-np.pdf | Le classi P, NP e NPC}} {{:informatica:all-b/PNP2020.pdf| lucidi Complessità}} \\ [[https://drive.google.com/file/d/1_zUDBRYhkmgbn7wO-IWcq2ifv4shuTpV/view?usp=sharing | lavagna ]] [[https://drive.google.com/file/d/1BgwIvrumv6kl9NhyR1T4JI-GGnNfbxET/view?usp=sharing | video]]| |
| |19/05/2020 | **Laboratorio**: esercitazione finale | {{ :informatica:all-b:solgrafi.pdf |Slide}}| |
| | 20/05/2020 | **Esercitazione**: Certificati Polinomiali, Algoritmi Enumerativi. | [[https://drive.google.com/file/d/1OEAFVV0haXTh1-qmeNOyeLq-8u6t8Wgq/view?usp=sharing | lavagna ]] [[https://drive.google.com/file/d/1nqcASp20gTrYM4RA2o0ctdnbVFY_FKiP/view?usp=sharing | video]]| |
| | 21/05/2020 | Ricevimento collettivo sostitutivo del secondo compitino | | |