| Entrambe le parti precedenti la revisione
Revisione precedente
Prossima revisione
|
Revisione precedente
|
informatica:all-a:start [29/05/2019 alle 15:06 (5 anni fa)]
Linda Pagli [Registro delle Lezioni] |
informatica:all-a:start [27/04/2022 alle 06:10 (2 anni fa)] (versione attuale)
anna bernasconi [Modalità e Appelli di Esame] |
| |
| |
| ===== Anno accademico 2018/2019 ===== | ===== 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 ===== | ===== Informazioni Generali ===== |
| |
| **Docenti Teoria/Esercitazioni:** [[http://sbrinz.di.unipi.it/~peppe/|Giuseppe Prencipe]] e [[http://www.di.unipi.it/~pagli/|Linda Pagli]] ([[informatica:all-a:start|corso A]]) | **Docenti 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]], | **Docenti Laboratorio:** [[http://pages.di.unipi.it/bernasconi/|Anna Bernasconi]], [[http://hpc.isti.cnr.it/~nardini/|Franco Maria Nardini]], |
| [[http://pages.di.unipi.it/desensi/|Daniele De Sensi]] | |
| [[http://pages.di.unipi.it/rossano/|Rossano Venturini]] | [[http://pages.di.unipi.it/rossano/|Rossano Venturini]] |
| |
| |
| **Semestre:** secondo. | **Semestre:** secondo. |
| |
| **Ricevimento studenti** Prencipe: Martedì dalle ore 11:00 alle ore 13:00 (o su appuntamento) | |
| |
| **Ricevimento studenti:** Pagli: su appuntamento, scrivere a linda.pagli@unipi.it | **Ricevimento studenti:** Pagli: su appuntamento, scrivere a linda.pagli@unipi.it |
| |
| **Registro delle lezioni:** si tratta del [[https://unimap.unipi.it/registri/dettregistriNEW.php?re=3290010::::&ri=080240|registro ufficiale]] che riporta quanto indicato nel seguito. | **Ricevimento studenti** Prencipe: Martedì dalle ore 11:00 alle ore 13:00 (o su appuntamento) |
| |
| ===== NEW: Ricevimento Collettivo con i Counselor !!!! ===== | **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. |
| |
| A partire dal 13 Marzo, ogni Martedi' dalle 11 alle 13 nella Sala Riunioni Est del Dipartimento di Informatica si terra' un ricevimento collettivo delle attivita' di Laboratorio tenuto dai quattro studenti counselor assegnati a questo corso. | |
| |
| [[https://docs.google.com/forms/d/e/1FAIpQLScwAWf_UnsXKJ0hfdVb20vYA5KpxtkC0L_IQq5J1X75GfQHig/viewform|Feedback per il Counseling.]] | |
| |
| [[https://github.com/DrDav/Algo1819/|Materiale didattico di supporto per il laboratorio (preparato dai counselor)]] | |
| |
| | **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 ===== | ===== Anni accademici precedenti ===== |
| | * [[.all19:|A.A. 2018/2019]] |
| * [[.all18:|A.A. 2017/2018]] | * [[.all18:|A.A. 2017/2018]] |
| * [[.all17:|A.A. 2016/2017]] | * [[.all17:|A.A. 2016/2017]] |
| |
| ===== Gruppi Laboratorio ===== | ===== 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 ^ | ^ Gruppo ^ Aula e orario ^ |
| |A1 (da AA a DE) | Aula H, martedì 16:00 - 18:00| | |A1 | Aula H, martedì 11:00 - 13:00| |
| |A2 (da DI a NA) | Aula M, martedì 16:00 - 18:00| | |A2 | Aula M, martedì 11:00 - 13:00| |
| |A3 (da NE a ZZ) | Aula M, venerdì 14:00 - 16: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 Lezioni ===== |
| |
| ^ Orario delle Lezioni ^^^^ | ^ Orario delle Lezioni ^^^^ |
| | Lunedì | 9-11 | aula E | Teoria | | | Lunedì | 11-13 | aula E | Teoria | |
| | Martedì | 16-18 | aule H-I-M | Laboratorio | | | Martedì | 11-13 | aule H-I-M | Laboratorio | |
| | Mercoledì | 11-13 | aula E | Teoria | | | Giovedì | 16-18 | aula E | Teoria | |
| | Venerdì | 9-11 | aula E | Teoria | | | Venerdì | 9-11 | aula E | Teoria | |
| | Venerdì |14-16 | aula M | Laboratorio | | |
| | |
| |
| ===== Obiettivi del Corso ===== | ===== Obiettivi del Corso ===== |
| ===== Modalità e Appelli di Esame===== | ===== Modalità e Appelli di Esame===== |
| | |
| L'esame consiste di tre prove: | MODALITA’ DI ESAME PER GLI STUDENTI DELLA LAUREA TRIENNALE |
| |
| * Una prova scritta con esercizi atti a valutare l'apprendimento delle nozioni teoriche e la capacità di "problem solving" dello studente. Tale prova viene valutata in trentesimi, e si intende superata se la valutazione è maggiore o uguale a 18. | L'esame degli appelli estivi consistono in due prove obbligatorie: |
| * Una prova in laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi su array, liste, alberi e grafi. Tale prova è da intendersi come un __test di idoneità__. | |
| * Una prova orale sul programma del corso, la cui valutazione è in trentesimi e tiene in considerazione il risultato riportato dallo studente nella prova scritta. | |
| * Le prove possono essere sostenute in appelli diversi. | |
| * La prova orale e quella di laboratorio possono essere sostenute in qualunque ordine, ma solo dopo aver superato la prova scritta. | |
| * Se la prova orale non viene superata, occorre ripetere soltanto quella. | |
| * Se la prova di laboratorio non viene superata per due volte consecutive, occorre ripetere tutte le prove già sostenute. | |
| * La registrazione del voto di esame potrà essere effettuata soltanto dopo che tutte e tre prove sono state superate con successo, e questo potrà avvenire in **qualunque appello durante la prova orale**. | |
| |
| | * 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. |
| |
| 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. **Attenzione**: la scadenza per iscriversi non sara’ molto a ridosso delle prove d’esame, controllate l'apposito portale.\\ |
| **Prossime date per la prova scritta:** | |
| |
| ^ Data ^ Tipo Prova ^ Documenti ^ Avvisi ^ | DATA SCIENCE STUDENTS: PLEASE CONTACT ANY OF THE PROFESSORS FOR INSTRUCTIONS |
| | 01/04/19 | Primo Compitino | {{:informatica:all-a:algo010419-a.pdf|testo}}| {{informatica:all-a:votiesami.pdf|Risultati}} corso A. Correzione e visione dei compiti: lezione di lunedì 8 Aprile 2019. Coloro che devono ancora assolvere gli OFA possono sostenere il compitino come test di autovalutazione, ma l'esito della loro prova non puo' essere considerato valevole come (semi)prova d'esame. | | |
| | 01/04/19 | Appello Straordinario | {{:informatica:all-a:algo010419.pdf|testo}} |{{ :informatica:all-a:ris1_4_2019.docx |Risultati}} corso A e corso B. Sono ammessi all'esame di laboratorio gli studenti con voto ≥16. Per visione dei compiti lunedì 8 alle 12 ufficio Pagli.| | |
| | 03/06/19 | Secondo Compitino | | | |
| |
| | **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 ===== | ===== Registrazioni delle Lezioni ===== |
| [[http://sbrinz.di.unipi.it/peppe/AlgoLezioniVideo/]] | [[http://sbrinz.di.unipi.it/peppe/AlgoLezioniVideo/AlgoLezioniVideo2020]] |
| |
| ===== 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/]] |
| | |
| |
| |
| |
| ^ Data ^ Argomento ^ Rif. Biblio ^ | ^ Data ^ Argomento ^ Rif. Biblio ^ |
| | 18/02/2019 | Questioni organizzative: pagina web, laboratori, ricevimento studenti e modalità di esame.\\ Introduzione al corso: nozione di algoritmo, problema, dimensione dell'input, limite inferiore/superiore alla complessità di un problema/algoritmo. Analisi di un problema semiserio: il problema delle 3, 4, 5 e 12 monete. | Capitolo 1 del CLRS, e [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/12monete.pdf | 12 monete]] | | | 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]] | |
| | 19/02/2019 22/02/2019| **Laboratorio:** Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. {{ :informatica:all-a:lezione1.pdf |Slide}} | | | 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: caso pessimo, caso ottimo e caso medio. Notazione asintotica: O-grande, Omega e Theta, o-piccolo e omega-piccolo. | CLRS: Capitolo 3\\ [[https://www.dropbox.com/s/r4u3xf0avjrzyhz/20180221_ClassiComplessita.pdf?dl=0|Slide]] | | | 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. | |
| | 22/02/2019 | Esercitazione: Notazione asintotica. SelectionSort, algoritmo, complessità. | {{:informatica:all-b:TCScheat.pdf|TCS cheat sheet}} | | | 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.| | |
| | 25/02/2019 | InsertionSort: algoritmo, correttezza e complessita'. | | | | 24/02/2020 | MergeSort: algoritmo, correttezza e analisi di complessità del Merge. | [CLRS] cap 2: 2.3; cap 4: 4.4. Consultare [FL]. | |
| | 26/02/2019 01/03/2019| **Laboratorio**: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. {{ :informatica:all-a:Lezione2.pdf |Slide}} | | | 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 | Paradigma del Divide et Impera: descrizione, pseudo-codice e analisi della complessità in tempo mediante relazioni di ricorrenza. Esempio su calcolo del massimo di un vettore. MergeSort: algoritmo, correttezza e analisi di complessità del Merge. | [CLRS] cap 2: 2.3; cap 4: 4.4. | | | 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]. | |
| |01/03/2019 | Esercitazione. Ricerca Sequenziale, con analisi caso medio, Ricerca Binaria ricorsiva, iterativa, che restituisce il k più a sinistra. Confronti e analisi.| | | | 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) | |
| | 04/03/2019 | Algoritmi polinomiali ed esponenziali: definizione, confronto e caso di PC k-volte più veloce, con considerazioni. Problema della Torre di Hanoi: definizione, risoluzione con algoritmo ricorsivo e valutazione della complessità con relazione di ricorrenza. Pseudo-codice ricorsivo con valutazione della complessità: caso lineare e caso logaritmico. | Consultare [FL].\\ {{ :informatica:all-a:20180307_compl_ric.pdf |Slide}}. | | | 02/03/2020 | Esercitazione: Ordini di grandezza, Ricerca sequenziale e varie versioni ricerca binaria. Analisi complessità|{{ :informatica:all-a:esercitazione_1.pdf |Es 1}} | |
| | 05/03/2019 08/03/2019 | **Laboratorio**: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante| {{ :informatica:all-a:lezione3.pdf |Slide}} | | | 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 | Enunciato del Teorema dell'esperto, con esempi.| | | | 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}} | |
| | 08/03/2019 | Dimostrazione del Teorema dell'esperto per il caso delle potenze. | [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte) | | | 10/03/2020 | **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-a:lezione4.pdf|Slide}} | |
| | 11/03/2019 | Esercizi sul Teorema dell'esperto. Algoritmo della Moltiplicazione veloce di interi e di matrici con analisi della complessità. | [CLRS] con {{ :informatica:all-a:esercizi1-2017.pdf |esercizi}}. Note di F. Luccio su {{ :informatica:all-a:prodotto_interi_e_matrici.pdf |moltiplicazione interi e matrici}}. | | |12/03/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}} | |
| | 12/03/2019 15/03/2019| **Laboratorio**: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | {{:informatica:all-a:lezione4.pdf|Slide}} | | | 13/03/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 | |
| | 13/03/2019 | Quicksort: descrizione intuitiva, pseudo-codice, versione randomizzata, analisi della complessità al caso pessimo, al caso ottimo e al caso medio. Studiare anche Partizione di Hoare (Problema [CLRS] 7.1) e Partizione con elementi uguali (Problema [CLRS] 7.2) | [CLRS] cap 7 | | | 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 |
| | 15/03/2019 | Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Algoritmi per determinare il primo e secondo, algoritmo del doppio torneo.| [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/limitiinf.pdf | Note di F. Luccio]] su limiti inferiori. [CLRS] cap 8: 8.1. | | }}| |
| | 18/03/2019 | Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo medio lineare. La struttura dati Heap: proprietà, esempi, Max-Heapify con analisi della complessità e correttezza. Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. | [CLRS] cap 9: 9.1, 9.2 (leggere analisi al caso medio dalla {{ :informatica:all-a:rand_select_comm.pdf |seguente nota}}).\\ [CLRS] cap 6: 6.1 - 6.4. | | | 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/2019 22/03/2019| **Laboratorio**: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | {{ :informatica:all-b:lezione5.pdf |Slide}}| | | 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/2019 | Heapsort. Code di priorità: definizione, operazioni, realizzazione mediante heap. | [CLRS] cap 6: 6.5. | | | 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. | |
| |22/03/2019 |Esercitazione: problema del mergeInsertionSort, con analisi e limite inferiore. Algoritmi Divide et impera e come trasformazione di ricerca Binaria (cuspide, trova occorrenze)|{{:informatica:all-a:ricercabinariasin.pdf|ricerca binaria sinistra}} | | | 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.| |
| |25/03/2019 | Esercizi Master Theorem.| {{ :informatica:all-a:20180314_esercizimasterth.pdf |Slides}} | | | 24/03/2020 | **Laboratorio**: Qsort e ripasso delle struct.|{{:informatica:all-a:lezione6.pdf|Slide}} | |
| | 26/03/2019 29/03/2019 | **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. | |
| | 27/03/2019 |Esercitazione: calcolo della potenza di a alla n con O(log n) moltiplicazioni; trova due elementi a somma k, limite inferiore con albero di decisione, algoritmo lineare; Intersezione di due insiemi con e senza ordinamento;| | | |
| | 29/03/2019 |Esercitazione: esercizi di ripasso su QuickSort, MergeSort, Heap e HeapSort | | | |
| | 08/04/2019 | Correzione prima prova di verifica intermedia. | | | |
| | 9/04/2018 12/04/2019 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} | | |
| | 10/04/2019 | Dizionari: realizzazione con tabelle a indirizzamento diretto e con tabelle hash; funzioni hash (metodo della divisione e metodo iterativo); gestione delle collisioni mediante concatenamento (analisi al caso pessimo e medio). |[CLRS] cap 11: 11.1, 11.2, 11.3, 11.3.1, 11.3.2. | | |
| | | Si invitano gli studenti a studiare il Capitolo 10 [CLRS] per ripassare le nozioni di Pila, Coda e Lista, e algoritmi su queste strutture dati elementari. | | | | | Si invitano gli studenti a studiare il Capitolo 10 [CLRS] per ripassare le nozioni di Pila, Coda e Lista, e algoritmi su queste strutture dati elementari. | | |
| | 12/04/2019 | Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. | [CLRS] cap 8: 8.2, 8.3. | | | 27/03/2020 |Esercitazione. Dimostrazioni per induzione su alberi binari. Simulazione di HeapSort. Equazioni di ricorrenza| {{ :informatica:all-a:ese3.pdf |lavagna}} | |
| | 15/04/2019 | Alberi e alberi binari: Definizione e memorizzazione. Interrogazioni (minimo, massimo, successore, predecessore); inserimento e cancellazione. Analisi della loro complessità in tempo. Visita di alberi binari di ricerca: Visite Anticipata/Simmetrica/Posticipata. | [CLRS] cap 10: 10.4. cap 12: 12.1, 12.2, 12.3. | | | 30/03/2020 | Esercitazione scritta | | |
| | 16/04/2019 | **Laboratorio**: Liste monodirezionali e bidirezionali. MARTEDI' GRUPPI A1, A2 e A3| {{ :informatica:all-a:lezione8-1415.pdf |Slide}}| | | 31/03/2020 | **Laboratorio**: Esercizi d'esame: qsort e struct.|{{ :informatica:all-b:lezione7.pdf |Slide}} | |
| | 17/04/2019 | Esercitazione: Algoritmi ricorsivi su alberi binari, dimensione, altezza, controlo perfettamente bilanciato, nodi cardine. Esempio di open hash con scansione lineare quadratica e doppio hash. | [CGGR]: {{:informatica:all-b:alberibinari.pdf|Algoritmi ricorsivi su alberi binari}} {{ :informatica:all-b:eserciziAlberi2016.pdf | Esercizi (alberi binari)}} | | | 02/04/2020 | Esercitazione. Esercizi vari su Heap e HeapSort.| {{ :informatica:all-a:eser4.pdf |lavagna}} | |
| | 29/04/2019 | Grafi: definizioni, rappresentazione di grafi in memoria. Grafi: visita in ampiezza (BFS), algoritmo e analisi di complessità e correttezza, albero di visita in ampiezza e algoritmo PRINT-PATH.| [CLRS] cap 22: 22.2 con lem/teo/cor da 22.1 a 22.5. [CLRS]: appendice B.4 | | | 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}} | |
| | 30/04/2019 03/05/2019 | **Laboratorio**: Tabelle Hash. MARTEDI' gruppi A1 e A2, VENERDI' gruppo A3| {{ :informatica:all-b:lezionehash.pdf |Slide}}| | | 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}} | |
| | 03/05/2019 | **Esercitazione**: Alberi binari di ricerca. | {{ :informatica:all-a:ABR2019.pdf | Esercizi (alberi binari di ricerca)}} {{https://drive.google.com/file/d/1Yq-VYzzbhUwx-SAKshPz3x_oN7Si8lFI/view?usp=sharing|lavagna}}| | | 07/04/2020 | **Laboratorio**: Liste monodirezionali e bidirezionali. | {{ :informatica:all-a:lezione8-1415.pdf |Slide}}|. |
| | 06/05/2019 | Grafi: visita in profondità (DFS), analisi di complessità e correttezza, classificazione degli archi; ordinamento topologico di grafi diretti aciclici.| [CLRS] cap 22: 22.3, 22.4 con lem/teo/cor 22.7, 22.8 e 22.9 | | | 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}}| |
| | 07/05/2019 10/05/2019 | **Laboratorio**: Alberi binari di ricerca. | {{ :informatica:all-a:lezioneabr.pdf |Slide}}| | | 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}}| |
| | 08/05/2019 | Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Inefficienza degli algoritmi ricorsivi su sottoinsiemi di dati con alta sovrapposizione: esempi sui numeri di Fibonacci e sui coefficienti binomiali. Il problema del taglio della corda. Il problema del calcolo dei Coefficienti Binomiali. |[CLRS] cap 15: 15.4. [[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/pd.pdf|Note del Prof. | | 17/04/2020 | Esercitazione. alberi binari, alberi binarizzati, inserzioni in albero AVL. |{{ :informatica:all-a:lez17aprile.pdf |lavagna}} | |
| Luccio]]. {{:informatica:all-b:esercizipd.pdf|Esercizi sulla Programmazione Dinamica}} | | | 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}}| |
| | 10/05/2019| Alberi AVL: definizione, alberi di Fibonacci, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni; cancellazione: cenni).| [CGGR]: {{:informatica:all-b:AVL.pdf|Alberi AVL}}, {{:informatica:all-b:rotazioniavl.pdf| rotazioni}} | | | 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}} | |
| | 13/05/2019 | Il problema della sequenza ottima di moltiplicazioni di matrici. Il problema della determinazione della Longest Common Subsequence. Il problema dello zaino 0-1. | {{:informatica:all-b:ED.pdf|Edit Distance (dispense Prof. Luccio)}} | | | 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}} | |
| | 14/05/2019 17/05/2019 | **Laboratorio**: Grafi. | {{ :informatica:all-b:lezionegrafi.pdf |Slide}} {{:informatica:all-a:grafobip.pdf|Esercizio 1}}| | | 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}} | |
| | 15/05/2019 | **Esercitazione**: progettazione di algoritmi efficienti su grafi.|{{:informatica:all-b:esercizigrafi19.pdf|Esercizi}}| | | 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. |
| | 17/05/2019 | **Esercitazione**: esempi di algoritmi programmazione dinamica, Zaino e Edit Distance|[[http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/pd.pdf|Note di F. | Luccio]].{{ :informatica:all-a:lez27aprile.pdf |lavagna}} | |
| Luccio]]| | | 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}}| |
| | 20/05/2019 | Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino frazionario. Algoritmi pseudopolinomiali. Il problema dello scheduling delle attivita'. Partizione di un insieme di interi. Edit Distance. Come passare l'esame (problema di programmazione dinamica!). Data Center. | [CLRS] cap 16: 16.2, {{:informatica:all-a:ProblemaZaino_pubblicato.pdf|Il problema dello zaino intero e frazionario.}} {{:informatica:all-b:ZainoPD.pdf|esercizio 16.2.2 (algoritmo PD per lo Zaino)}}. {{:informatica:all-b:pseudo.pdf |pseudopolinomialità}} | | | 30/04/2020 |Esercitazione. Esercizi di Programmazione Dinamica. |{{ :informatica:all-a:algo1_090614.pdf | esercizio 3}} {{ :informatica:all-a:esercizipd.pdf | scacchiere}} | |
| | 21/05/2019 24/05/2019 | **Laboratorio**: Simulazione prova di esame. |{{ :informatica:all-b:solgrafi.pdf |Slide}} | | | 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 }}| |
| | 22/05/2019 | Teoria della complessità: le classi P e NP, ed NP-completi. Esempio di riduzione da SAT a Clique. | Su P vs NP si consultino: {{ :informatica:all-a:p-np.pdf |nota 1}} e {{ :informatica:all-a:altre_note.pdf |nota 2}}, quest'ultima nelle pagine 4-6. Per la dimostrazione di NPC per Clique si vedano pag 1-3 di {{ :informatica:all-a:p-np_e_k-clique.pdf |nota 3}} | | | 05/05/2020 | **Laboratorio**: simulazione prova d'esame.|{{ :informatica:all-a:SolAlberi.pdf |Slide}} | |
| | 24/05/2019 | Esercitazione: Genera binarie, Genera permutazioni, Scacchiera, Problema dell'Imbalance su alberi binari. | | | | 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}}| |
| | 29/05/2019 | Esercitazione: Algoritmo enumerativo per TSP. Verifica polinomiale per Vertex Cover. Problemi di ripasso | | | |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}} | |
| | |
