Indice
Algoritmica e Laboratorio - Corso A
Anno accademico 2019/2020
IMPORTANTE
A partire dal 9 marzo Le lezioni si svolgeranno telematicamente nelle ore previste dall'orario.
Per partecipare accedere all'URL:
http://unipi.it/corsionline ed eseguire le istruzioni della guida per partecipare alle lezioni su Teams di Microsoft.
Il ricevimento studenti sarà fatto via mail, oppure via Skype su appuntamento.
Informazioni per le lezioni di laboratorio
Le lezioni di laboratorio si svolgeranno on line (streaming), a partire da martedì 10 marzo alle ore 11 sulla piattaforma Meet di Google.
Attenzione: le lezioni non saranno registrate. Seguitele rispettando gli orari del corso.
Gli studenti del corso di laurea in Informatica sono pregati di collegarsi (il martedi alle ore 11) utilizzando questo link
Gli studenti del corso di laurea in Data Science sono pregati di collegarsi (il martedi alle ore 11) utilizzando questo link
Gruppo Telegram con gli assistenti di laboratorio: link
Informazioni Generali
Docenti Teoria/Esercitazioni: Linda Pagli e Giuseppe Prencipe (corso A)
Docenti Laboratorio: Anna Bernasconi, Franco Maria Nardini, Rossano Venturini
Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. Il corso consiste ogni settimana di 3 lezioni di didattica frontale in aula e di 1 esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.
Semestre: secondo.
Ricevimento studenti: Pagli: su appuntamento, scrivere a linda.pagli@unipi.it
Ricevimento studenti Prencipe: Martedì dalle ore 11:00 alle ore 13:00 (o su appuntamento)
Ricevimento studenti Bernasconi: Mercoledì, dalle 9 alle 11, sulla piattaforma Meet di Google. Ricevo inoltre via Skype su appuntamento. Tramite mail avverrà lo scambio dei contatti skype e l'accordo sul giorno e sull'orario.
Registro delle lezioni: si tratta del registro ufficiale che riporta quanto indicato nel seguito.
Anni accademici precedenti
Gruppi Laboratorio
NEWS: Starting from Tuesday March 3rd, the Python Lab slot dedicated to Data Science Master Degree students is anticipated at 11:00-13:00 (still in class-room I). Therefore Data Science students should head to that time slot, while first year students are now allowed to attend the C Lab class at 14:00 even in classroom I.
Gruppo | Aula e orario |
---|---|
A1 | Aula H, martedì 11:00 - 13:00 |
A2 | Aula M, martedì 11:00 - 13:00 |
A3 (Riservata a studenti della LM in Data Science - Dedicated to Data Science Master students) | Aula I, martedì 11:00 - 13:00 |
Orario Lezioni
Orario delle Lezioni | |||
---|---|---|---|
Lunedì | 11-13 | aula E | Teoria |
Martedì | 11-13 | aule H-I-M | Laboratorio |
Giovedì | 16-18 | aula E | Teoria |
Venerdì | 9-11 | aula E | Teoria |
Obiettivi del Corso
L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.
Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.
Modalità e Appelli di Esame
MODALITA’ DI ESAME PER GLI STUDENTI DELLA LAUREA TRIENNALE
L'esame degli appelli estivi consistono in due prove obbligatorie:
- Una prova di Laboratorio che verifica la capacità dello studente di realizzare in C gli algoritmi di base visti in classe, risolvendo semplici problemi. La prova avra’ luogo sulla consueta piattaforma d’esame accessibile via browser, e sara’ validata da un colloquio orale immediatamente successivo. Tale prova è da intendersi come un test di idoneità.
- Una prova orale sul programma del corso la cui valutazione finale è in trentesimi, atta a valutare l'apprendimento delle nozioni teoriche e la capacità di “problem solving” dello studente.
- La prova orale puo' essere sostenuta solo dopo aver superato la prova di Laboratorio.
- Le prove possono essere sostenute in appelli diversi.
- Se la prova orale non viene superata, occorre ripetere soltanto quella.
Istruzioni piu’ dettagliate verranno fornite via mail agli iscritti alle prove. Per questo motivo, e per la necessita’ nelle nuove condizioni di organizzare al meglio le prove, l’iscrizione e’ tassativamente obbligatoria. Attenzione: la scadenza per iscriversi non sara’ molto a ridosso delle prove d’esame, controllate l'apposito portale.
DATA SCIENCE STUDENTS: PLEASE CONTACT ANY OF THE PROFESSORS FOR INSTRUCTIONS
Prossime date per la prova di Laboratorio:
Data | Tipo Prova | Documenti | Aula Virtuale |
---|---|---|---|
26/5/2020 | 09:00 | Laboratorio | |
16/6/2020 | 09:00 | Laboratorio | |
07/07/2020 | 09:00 | Laboratorio | |
01/09/2020 | 09:00 | Laboratorio | |
11/01/2021 | 14:00 | Laboratorio | QUI |
01/02/2021 | 14:00 | Laboratorio | QUI |
22/03/2021 | 14:30 | Laboratorio | QUI |
8/06/2022 | 9:00 | Laboratorio | 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. | QUI | Sul portale di iscrizione esami entro il 21/5 |
16/6/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 14/06/2020 all'indirizzo email rossano.venturini@unipi.it. | QUI | Sul portale di iscrizione esami entro il 11/6 |
7/7/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 5/7/2020 all'indirizzo email rossano.venturini@unipi.it. | QUI | Sul portale di iscrizione esami entro il 2/7/2020 |
1/9/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 30/8/2020 all'indirizzo email rossano.venturini@unipi.it. | QUI | Sul portale di iscrizione esami entro il 27/8/2020 |
27/10/2020 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 25/10/2020 all'indirizzo email rossano.venturini@unipi.it. | QUI | Sul portale di iscrizione esami entro il 19/10/2020 |
11/01/2021 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 09/01/2021 all'indirizzo email rossano.venturini@unipi.it. | QUI | |
01/02/2021 | 14:00 | Laboratorio in Python | Gli studenti che partecipano all'esame sono tenuti a inviare i notebook con le soluzioni entro il 30/01/2021 all'indirizzo email rossano.venturini@unipi.it. | QUI | Nota: Se la data dell'esame coincide con quella di altri esami, inviatemi un'email per concordare un'altra data. |
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. | QUI | Nota: Se la data dell'esame coincide con quella di altri esami, inviatemi un'email per concordare un'altra data. |
Registrazioni delle Lezioni
Libri di testo
- [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, Terza edizione, 2010.
- [DFI] C. Demetrescu, I. Finocchi, G. Italiano. Algoritmi e strutture dati. McGraw-Hill, Seconda edizione, 2008. Solo pagine 161-165.
- [FL] P. Ferragina, F. Luccio. Il Pensiero Computazionale: dagli algoritmi al coding. Il Mulino, 2017. Solo pagine 64-65, Capitolo 7 e Capitolo 10.
Per il laboratorio, un testo fra:
- [KR] B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2008.
- [KP] A. Kelley, I. Pohl. C: Didattica e Programmazione, Addison-Wesley, quarta edizione, 2004.
Materiale per il Laboratorio
- Prerequisito: Conoscenza approfondita della programmazione C per ciò che concerne gli operatori (aritmetici e relazionali), il flusso del controllo (If-then-else, while, for), le funzioni, gli array, i puntatori, le stringhe e l'allocazione dinamica della memoria. Quindi i capitoli 1-5 del libro “Il Linguaggio C”, B.W. Kernighan e D.M. Ritchie, Pearson-Prentice Hall, seconda edizione, 2008.
- Strumenti per la programmazione: Un editore testuale (tipo
Emacs
), e il compilatoregcc
, sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di coding che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come Eclipse esteso con il suo plug-in Eclipse C/C++ Development Tooling. Per chi si trova a operare sotto Windows consigliamo di installare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux. Il consiglio è però quello di adoperare la combinazione minimaleeditor+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://algo1920.dijkstra.di.unipi.it/
Programma del corso
- Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
- Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
- Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
- Divide-et-impera, Relazioni di ricorrenza, Teorema “dell'esperto”.
- Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
- Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
- Ordinamento di interi: Counting sort, Radix Sort.
- Ordinamento di stringhe:
qsort
-based. - Sottosequenza di somma massima.
- Programmazione dinamica: LCS, Partizione e Zaino
- Algoritmi randomizzati: Quicksort.
- Generazione di combinazioni e permutazioni
- Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
- Dizionari: Alberi bilanciati (Alberi 2-3), Tabelle hash (liste di trabocco e indirizzamento aperto).
- Alberi: rappresentazione e visite.
- Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
- Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
- Grafi III: Minimum Spanning Tree e Shortest Path.
Registro delle Lezioni
Data | Argomento | Rif. Biblio |
---|---|---|
17/02/2020 | Questioni organizzative: pagina web, laboratori, ricevimento studenti e modalità di esame. Introduzione al corso: nozione di algoritmo, problema, dimensione dell'input, limite inferiore/superiore alla complessità di un problema/algoritmo. Analisi di un problema semiserio: il problema delle 12 monete. | Capitolo 1 del CLRS, e 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]. Slide |
20/02/2020 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio: caso pessimo, caso ottimo e caso medio. Notazione asintotica: O-grande, Omega e Theta, o-piccolo e omega-piccolo. | CLRS: Capitolo 3. |
21/02/2020 | InsertionSort: algoritmo, correttezza e complessita'. SelectionSort (correttezza e analisi sul libro di testo). Paradigma del Divide et Impera: descrizione, pseudo-codice e analisi della complessità in tempo mediante relazioni di ricorrenza. Esempio su calcolo del massimo e minimo di un vettore. | |
24/02/2020 | MergeSort: algoritmo, correttezza e analisi di complessità del Merge. | [CLRS] cap 2: 2.3; cap 4: 4.4. Consultare [FL]. |
25/02/2020 | Laboratorio: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Slide |
27/02/2020 | Algoritmi polinomiali ed esponenziali: definizione, confronto e caso di PC k-volte più veloce, con considerazioni. Problema della Torre di Hanoi: definizione, risoluzione con algoritmo ricorsivo e valutazione della complessità con relazione di ricorrenza. | Consultare [FL]. |
28/02/2020 | Teorema dell'esperto, esempi, e sua dimostrazione per il caso delle potenze. | [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte) |
02/03/2020 | Esercitazione: Ordini di grandezza, Ricerca sequenziale e varie versioni ricerca binaria. Analisi complessità | Es 1 |
03/03/2020 | Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante | Slide |
09/03/2020 | Esercitazione: Ricerca Binaria Sinistra, limiti inferiori al problema della ricerca, problema 2.1 pag. 37 del Cormen: MergeInsertionSort | Es 2 |
10/03/2020 | Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | Slide |
12/03/2020 | Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Algoritmi per determinare il primo e secondo, algoritmo del doppio torneo. | Note di F. Luccio su limiti inferiori. [CLRS] cap 8: 8.1. lavagna |
13/03/2020 | Quicksort: descrizione intuitiva, pseudo-codice, versione randomizzata, analisi della complessità al caso pessimo, al caso ottimo e al caso medio. Studiare anche Partizione di Hoare (Problema [CLRS] 7.1) e Partizione con elementi uguali (Problema [CLRS] 7.2). Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo medio lineare. | [CLRS] cap 7 (leggere analisi al caso medio dalla seguente nota). cap 9: 9.1, 9.2 |
16/03/2020 | Limiti inferiori con la tecnica dell'avversario: problema del primo e secondo. Partizione con elementi uguali (Problema [CLRS] 7.2). Moltiplicazione nel bit model | TCS cheat sheet Note di F. Luccio su moltiplicazione interi e matrici lavagna |
17/03/2020 | Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | Slide |
19/03/2020 | Moltiplicazione Egizia e Moltiplicazione Rapida, Moltiplicazione di matrici: Algoritmo di Strassen. Introduzione alle cose con priorità | lavagna |
20/03/2020 | La struttura dati Heap: proprietà, esempi, Max-Heapify con analisi della complessità e correttezza. Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. Heapsort. | [CLRS] cap 6: 6.1 - 6.5. |
23/03/2020 | Code di priorità: definizione, operazioni, realizzazione mediante heap. Dizionari: realizzazione con tabelle a indirizzamento diretto e con tabelle hash; funzioni hash (metodo della divisione e metodo iterativo); gestione delle collisioni mediante concatenamento (analisi al caso pessimo e medio). Funzioni hash: metodo della divisione. | [CLRS] cap 6: 6.1 - 6.5. cap 11: 11.1, 11.2, 11.3, 11.3.1, 11.3.2. |
24/03/2020 | Laboratorio: Qsort e ripasso delle struct. | Slide |
26/03/2020 | Funzioni hash: metodo della moltiplicazione. Dizionari: realizzazione con tabelle a indirizzamento aperto e analisi di ricerca senza successo e inserimento. Probing lineare, quadratico, e con double hashing. Tabelle hash con stringhe come chiavi. | [CLRS] cap 11: 11.3.2, 11.4. |
Si invitano gli studenti a studiare il Capitolo 10 [CLRS] per ripassare le nozioni di Pila, Coda e Lista, e algoritmi su queste strutture dati elementari. | ||
27/03/2020 | Esercitazione. Dimostrazioni per induzione su alberi binari. Simulazione di HeapSort. Equazioni di ricorrenza | lavagna |
30/03/2020 | Esercitazione scritta | |
31/03/2020 | Laboratorio: Esercizi d'esame: qsort e struct. | Slide |
02/04/2020 | Esercitazione. Esercizi vari su Heap e HeapSort. | lavagna |
03/04/2020 | Esercitazione. Esercizi di simulazione di tabelle hash con diversi metodi gestione delle collisioni. Il problema della cancellazione nell'open hash, uso della marcatura. | lavagna |
06/04/2020 | Definizione di albero, con radice, ordinato k-ario. Algoritmi ricorsivi su alberi binari, dimensione, altezza. Visite, Paradigma generale tipo Divide et Impera, con equazioni di ricorrenza | [CGGR]: Algoritmi ricorsivi su alberi binari lavagna |
07/04/2020 | Laboratorio: Liste monodirezionali e bidirezionali. | Slide |
09/04/2020 | Trasformazione da albero ordinato ad albero binario. Alberi binari di ricerca. Operzioni di ricerca, inserzione, cancellazione, ordinamento, minimo, massimo, predecessore e successore. | [CLRS] cap 12: 12.1, 12.2, 12.3 (senza alg TRASPLANT). lavagna |
16/04/2020 | Alberi bilanciati in altezza: alberi AVL. Studio del caso pessimo: Alberi di Fibonacci. Rotazioni dopo inserzione e cancellazione, esempi. | [CGGR]: Alberi AVL, rotazioni lavagna |
17/04/2020 | Esercitazione. alberi binari, alberi binarizzati, inserzioni in albero AVL. | lavagna |
20/04/2020 | Array di dimensione variabile. Sorting in tempo lineare: Counting Sort e Radix Sort. | [CGGR] par 1.1.3, [CLRS] cap 8: 8.2, 8.3 array variabililavagna |
21/04/2020 | Laboratorio: Tabelle Hash. | Slide Esercizio 1 Esercizio 2 |
23/04/2020 | Esercitazione. Radix Sort, esempi e confronti. Esercizi su alberi binari di ricerca. | Esercizi (alberi binari di ricerca)lavagna |
24/04/2020 | Introduzione alla Programmazione Dinamica. Generazione dei numeri di Fibonacci. Il problema della Longest Common Subsequence. | [CLRS] cap 15: 15.4.lavagna |
27/04/2020 | Programmazione Dinamica. Il problema della Edit Distance | Note del Prof. Luccio.lavagna |
28/04/2020 | Laboratorio: Alberi binari di ricerca. | Slide Esercizio 1 Esercizio AVL |
30/04/2020 | Esercitazione. Esercizi di Programmazione Dinamica. | esercizio 3 scacchiere |
04/05/2020 | Il problema dello Zaino e dello Zaino frazionato. Algoritmo greedy per lo Zaino frazionato. Programmazione Dinamica per lo Zaino. Pseudopolinomialità. Algoritmo brute force per lo Zaino. | [CGGR] par 6.5 lavagna |
05/05/2020 | Laboratorio: simulazione prova d'esame. | Slide |
07/05/2020 | Introduzione ai grafi. Definizioni. Rappresentazione con Matrice e liste di adiacenza. Visita BFS. | [CLRS] cap.22, 22.1 e 22.2 fino a analisi e appendice B4, lavagna |
11/05/2020 | Grafi: albero BFS, Vista DFS, foresta DFS. Etichettamento degli archi. Esempi | [CLRS] cap.22, 22.2 lavagna |
12/05/2020 | Laboratorio: grafi. | Slide Esercizio 1 (Grafo Bipartito) 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 | Esercizi lavagna |
18/05/2020 | Il problema P e NP. Introduzione all'NP-Completezza | PvsNP |
19/05/2020 | Laboratorio: esercitazione finale | 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: nota 1 e nota 2, quest'ultima nelle pagine 4-6. lavagna |
22/05/2020 | Esercitazione: esercizi su grafi, programmazione dinamica, algoritmi enumerativi e verifica polinomiale. | GeneraBinarie e GeneraPermutazioni lavagna |