Strumenti Utente

Strumenti Sito


informatica:all-a:start

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

Prossime date per la prova orale:

Gli orali della III sessione si svolgeranno il 10 Luglio:

https://agende.unipi.it/rxv-uhj-ogk

NOTA: il sistema e' in beta testing, quindi segnalate eventuali malfunzionamenti a: giuseppe.prencipe@unipi.it

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

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 compilatore gcc, sono sufficienti per apprendere e testare le varie nozioni algoritmiche e di coding che verranno discusse in Laboratorio. I programmatori più esperti potranno eventualmente utilizzare un framework di sviluppo come Eclipse esteso con il suo plug-in Eclipse C/C++ Development Tooling. Per chi si trova a operare sotto Windows consigliamo di installare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux. Il consiglio è però quello di adoperare la combinazione minimale editor+gcc al fine di non perdersi nei meandri e nelle opzioni dei vari tools (non necessari per il corso), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.
  • Sistema di Autovalutazione: http://algo1920.dijkstra.di.unipi.it/

Programma del corso

  1. Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
  2. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
  3. Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
  4. Divide-et-impera, Relazioni di ricorrenza, Teorema “dell'esperto”.
  5. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
  6. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
  7. Ordinamento di interi: Counting sort, Radix Sort.
  8. Ordinamento di stringhe: qsort-based.
  9. Sottosequenza di somma massima.
  10. Programmazione dinamica: LCS, Partizione e Zaino
  11. Algoritmi randomizzati: Quicksort.
  12. Generazione di combinazioni e permutazioni
  13. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
  14. Dizionari: Alberi bilanciati (Alberi 2-3), Tabelle hash (liste di trabocco e indirizzamento aperto).
  15. Alberi: rappresentazione e visite.
  16. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  17. Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
  18. 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: MergeInsertionSortEs 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-CompletezzaPvsNP
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
informatica/all-a/start.txt · Ultima modifica: 14/07/2020 alle 17:01 (4 settimane fa) da Giuseppe Prencipe