Indice

Algoritmica e Laboratorio - Corso B

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.

Informazioni Generali

Docenti Teoria/Esercitazioni: Nadia Pisanti, Anna Bernasconi

Docenti Laboratorio: Anna Bernasconi, Giulio Pibiri, Rossano Venturini

Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio. Il corso consiste ogni settimana di tre lezioni di didattica frontale in aula e di una esercitazione in laboratorio nella quale le nozioni apprese in classe verranno sperimentate realizzando in C gli algoritmi corrispondenti.

Semestre: secondo.

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.

Anni accademici precedenti

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à di esame attuali e Appelli di Esame

L'esame consiste in due prove obbligatorie che possono essere sostenute anche in appelli diversi:

Istruzioni piu’ dettagliate verranno fornite via mail agli iscritti alle prove. Per questo motivo, e per la necessita’ nelle nuove condizioni di organizzare al meglio le prove, l’iscrizione e’ tassativamente obbligatoria.

Le date delle prove di laboratorio sono sul portale esami e l'iscrizione deve avvenire sul portale

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 QUI Iscrizioni Chiuse
28/5/2020 09:00 Orale 6-8 slot: 568019, 600009, 600310, 596431, 599257, 601843 QUI Iscrizioni Chiuse
29/5/2020 09:00 Orale 6-8 slot: 491919, 586306, 602549, 582077, 531425, 596363, 598067, 596883 QUI Iscrizioni Chiuse
01/06/2020 09:00 Orale 10 slot: 602476, 584603, 583084, 563519, 598215, 578273, 584365 QUI Iscrizioni Chiuse
04/06/2020 09:00 Orale 10 slot: 559768, 561119, 544545, 579633, 509902, 597983, 597287, 560445, 580259 QUI Iscrizioni Chiuse
APPELLO MAGGIO TERMINATO
17/06/2020 14:30 Orale 10 slot: 516482, 486651, 601241, 584365, 609124 QUI Iscrizioni Chiuse
18/06/2020 09:00 Orale 10 slot: 572351, 589207, 596789, 598793 QUI Iscrizioni Chiuse
19/06/2020 09:00 Orale 7 slot: 503317, 525069, 597525, 599427, 578743, 598871 QUI Iscrizioni Chiuse
APPELLO GIUGNO TERMINATO
08/07/2020 14:00 Orale 10 slot: 575656, 491265, 560141, 596681, 599523, 597415, 599329, 532492, 531889, 407651 QUI Iscrizioni Chiuse
09/07/2020 09:00 Orale 9 slot: 465137, 559364, 525069, 597923, 600199, 602056, 543967, 600375, 599253 QUI Iscrizioni Chiuse
10/07/2020 09:00 Orale 9 slot: 549045, 598296, 609124, 597455, 577947, 579839, 600035, 584615, 559441 QUI Iscrizioni Chiuse
14/07/2020 14:00 Orale 10 slot: 562397, 549963, 522725, 601371, 598871, 562564, 476249, 588157, 545615 QUI Iscrizioni Chiuse
APPELLO LUGLIO TERMINATO
02/09/2020 09:00 Orale 10 slot: 562564, 609652, 600463, 598992, 566765, 598631, 578225, 559881;
ore 14:30 605553.
QUI Iscrizioni Chiuse
03/09/2020 09:00 Orale 10 slot: 599065, 564777, 597603, 602495, 579271, 579477, 585477, 578287, 597765, 588157 QUI Iscrizioni Chiuse
APPELLO SETTEMBRE TERMINATO
28/10/2020 11:00 Orale 4 slot: 560353, 563798, 578177, 549963 QUI Iscrizioni Chiuse
28/10/2020 15:00 Orale 8 slot: 598375, 597142, 588157 QUI Iscrizioni Chiuse
APPELLO STRAORDINARIO TERMINATO
18/1/2021 9:00 Orale 8 slot: 597727, 596135, 579151, 600894, 599899 QUI Iscrizioni Chiuse
19/1/2021 9:00 Orale 8 slot: 552117, 581465, 588157 QUI Iscrizioni Chiuse
APPELLO GENNAIO TERMINATO
11/2/2021 8:30 Orale 9 slot: 564755, 588157, 598537, 581147, 562564, 578225, 407651, 597631, 600361 QUI Iscrizioni Chiuse
11/2/2021 15:00 Orale 8 slot: 552685, 601717, 597339, 578976, 553015 QUI Iscrizioni Chiuse
APPELLO FEBBRAIO TERMINATO
26/3/2021 08:30 Orale 10 slot: 502525, 518897, 597179, 597797, 596533, 588157, 583951, 601433, 604487, 580182 QUI Iscrizioni Chiuse
APPELLO STRAORDINARIO TERMINATO
10/6/2021 14:30 Orale 10 slot: 597797, 583567, 583567, 588157, 597473, 560611, 560659, 604487 QUI Iscrizioni Chiuse
APPELLO GIUGNO TERMINATO
26/7/2021 09:00 Orale 579821, 518897, 597473, 407651 QUI Iscrizioni Chiuse
APPELLO LUGLIO TERMINATO
3/9/2021 9:00 Orale 10 slot: QUI Iscrizioni Chiuse
APPELLO SETTEMBRE TERMINATO
26/10/2021 11:00 Orale 5 slot: QUI Iscrizioni Chiuse
APPELLO STRAORDINARIO TERMINATO
14/01/2022 09:00 Orale 6 slot: 550342, 578177, 600035, 596715, 598771, 583943 QUI Iscrizioni Chiuse
APPELLO GENNAIO TERMINATO
12/04/2022 16:00 Orale 6 slot: 604825, 578463, 561655, 577925, 601564 QUI Iscrizioni Chiuse
APPELLO STRAORDINARIO TERMINATO
11/05/2022 9:00 Orale 6 slot: 602065, 578463 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 [dot] pisanti [at] unipi [dot] it indicando nome, cognome e numero di matricola.

Libri di testo

Per il laboratorio, un testo fra:

Materiale per il Laboratorio

Programma del corso

  1. Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
  2. Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
  3. Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
  4. Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
  5. Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
  6. Ordinamento di interi: Counting sort, Radix Sort.
  7. Programmazione dinamica: Fibonacci, Edit Distance e Zaino
  8. Algoritmi randomizzati: Quicksort.
  9. Cenni di trattabilità (P, NP, NPC, EXP-TIME).
  10. Generazione di combinazioni e permutazioni
  11. Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
  12. Dizionari: Alberi bilanciati (AVL), Tabelle hash (liste di trabocco e indirizzamento aperto).
  13. Alberi: rappresentazione e visite.
  14. Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
  15. Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
  16. Grafi III: Minimum Spanning Tree e Shortest Path.

Registro delle Lezioni

Data Argomento Rif. Biblio
18/02/2020 Nozioni di Problema, Algoritmo, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete.12 monete
lavagna
18/02/2020 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Slide
19/02/2020 12 monete (continua). Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo, al caso ottimo e al caso medio. Insertion sort: descrizione, pseudocodice, esempio. [CLRS] cap 1, cap 2: 2.1, 2.2.
lavagna
20/02/2020 Insertion sort: analisi di complessità al caso ottimo e pessimo. Invariante di ciclo e dimostrazione di correttezza. Selection Sort: pseudocodice, esempio, enunciato dell'invariante di ciclo (da dimostrare a casa). [CLRS] cap 2.2.
lavagna
25/02/2020 Complessita' di Selection Sort. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. Caso ottimo e caso pessimo con la notazione asintotica. [CLRS] cap 3.
TCS cheat sheet
lavagna
25/02/2020 Laboratorio: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Slide
26/02/2020 Esercitazione: Problema delle 9 monete. Ricerca Sequenziale e Ricerca Binaria. Esercizi sulla notazione asintotica. Sorting di vettore binario in loco. lavagna
27/02/2020 Paradigma del Divide et Impera: descrizione del paradigma, alberi di ricorsione, dimostrazione di correttezza mediante induzione. Esempi (min-max e potenza ennesima). MergeSort: cenno. [CLRS] cap 2: 2.3, cap 4: introduzione.
lavagna
03/03/2020 MergeSort: descrizione algoritmo, correttezza, analisi di complessità (con metodo iterativo e con albero di ricorsione). Esempio. [CLRS] cap 2: 2.3, cap 4: 4.3 e 4.4.
lavagna
03/03/2020 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante Slide
04/03/2020 Esercitazione: Algoritmi come tecnologia. Vettore Unimodulare. Mergeinsort. Altri esercizi su vettori: cerca i tale che A[i]=i; cerca uguali, sommak. lavagna
Da qui in poi le lezioni del corso teorico sono registrate Ogni lezione ha una parte1 e una parte2, e per ciascuna di esse e' disponibile un file lavagna, e un file lezione Il file lavagna* e' un .pdf
Il file lezione* e' un .mp4
ATTENZIONE: PER AVERE L'AUDIO
IL VIDEO DEVE ESSERE SCARICATO
Lezione prevista il 05/03/2019 Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Limite inferiore per l'ordinamento per confronti. [CLRS] cap 8: 8.1.
Note di F. Luccio su limiti inferiori.
lavagna1 lezione1 lavagna2 lezione2
Lezione prevista il 10/03/2020 Enunciato del Teorema dell'esperto, con esempi. Dimostrazione del Teorema dell'esperto per il caso delle potenze esatte. [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte)
lavagna1 lezione1 lavagna2 lezione2
10/03/2020 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Slide
Lezione prevista il 11/03/2020 Relazioni di ricorrenza di ordine k. Esercizi sul Teorema dell'esperto. Algoritmo della Moltiplicazione veloce con analisi della complessità. Prodotto tra matrici. Ricorrenze (dispensa Prof.Luccio: leggere introduzione, sezioni 1 e 3, saltando la sezione 2). moltiplicazione interi e matrici (note Prof.Luccio).
lavagna1 lezione1 lavagna2 lezione2
Lezione prevista il 12/03/2020 Quicksort: descrizione intuitiva, pseudo-codice, correttezza di Partition. Correttezza di Quicksort. Esempi di Partition e di QuickSort. [CLRS] cap 7
lavagna lezione1 lezione2
Lezione prevista il 17/03/2020 Complessita' di Partition, Correttezza di Quicksort. Analisi della complessità di Quicksort al caso pessimo, al caso ottimo e al caso medio. Versione randomizzata, e analisi della complessità. [CLRS] cap 7
lavagna lezione1 lezione2
17/03/2020 Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Slide
Lezione prevista il 18/03/2020 Esercitazione. Esercizi di ripasso su QuickSort, equazioni di ricorrenza e ordinamento lavagna lezione1 lezione2
Lezione prevista il 19/03/2020 Correzione esercizi dati per casa. La struttura dati Heap: definizione, realizzazione implicita come array, proprieta'. [CLRS] cap 6: 6.1.
lavagna lezione1 lezione2
Lezione prevista il 24/03/2020 Costruzione (BuildHeap) con Max-Heapify. Analisi della complessità e correttezza di MaxHeapify. Analisi della complessità e correttezza di BuildHeap. L'algoritmo Heapsort. Esempio. [CLRS] cap 6: 6.2, 6.3, 6.4.
lavagna lezione1 lezione2 lezione3
24/03/2020 Laboratorio: Qsort e ripasso delle struct.Slide
Lezione prevista il 25/03/2019 Code di priorità, operazioni, definizione e realizzazione mediante heap. Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort. [CLRS] cap 6: 6.5. cap 8: 8.2.
lavagna lezione1 lezione2
Lezione prevista il 26/03/2019 Radix sort. Esercitazione su Divide et Impera, su heap e Heapsort. cap 8: 8.3.
lavagna lezione1 lezione2 CORREZIONE ESERCIZIO DATO PER CASA
31/03/2020 Laboratorio: Esercizi d'esame: qsort e struct.Slide
01/04/2020
COMPITINO ANNULLATO
avviso
A SOSTITUZIONE DEL COMPITINO QUALE MOMENTO DI AUTOVALUTAZIONE SVOLGETE
IL PRIMO COMPITINO DEL 2019 E QUELLO DEL 2018
BUON LAVORO!
SEGUONO DUE ESERCITAZIONI EXTRA CON LO SVOLGIMENTO REGISTRATO DEGLI STESSI
01/04/2020 Esercizitazione: svolgimento Primo Compitino 2019 PROVATE DAVVERO A SVOLGERLO PRIMA DI VISIONARNE LA SOLUZIONE!!
lavagna lezione
02/04/2020 Esercizitazione: svolgimento Primo Compitino 2018 PROVATE DAVVERO A SVOLGERLO PRIMA DI VISIONARNE LA SOLUZIONE!!
lavagna lezione1 lezione2
07/04/2020 Dizionari: realizzazione con tabelle a indirizzamento diretto e con tabelle hash; funzioni hash (metodo della divisione e metodo iterativo); gestione delle collisioni mediante concatenamento (analisi al caso pessimo e medio). [CLRS] cap 11: 11.2, 11.2, 11.3, 11.3.1 (teoremi 11.1 e 11.2)
lavagna video
07/04/2020 Laboratorio: Liste monodirezionali e bidirezionali. Slide
08/04/2020 Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). [CLRS] cap 11: 11.4 (teoremi 11.6 e 11.8, corollario 11.7)
lavagna video
09/04/2020 Tabelle hash a indirizzamento aperto: Scansione lineare, scansione quadratica, doppio hash. Alberi e alberi binari: definizioni e rappresentazione in memoria. [CLRS] cap 11: 11.4
lavagna video
15/04/2020 Alberi e alberi binari: visite. Alberi cardinali, alberi ordinali e notazione binarizzata.
Esercitazione: esercizi su dizionari e tabelle hash.
[CLRS] cap 10: 10.4
Esercizi (hash) Soluzioni
lavagna video
16/04/2020 Algoritmi Ricorsivi su Alberi Binari: schema generale D&I su alberi. Alberi Binari Completamente Bilanciati. Algoritmi ricorsivi per trovare: dimensione, altezza, ABCB, nodi cardine, nodi centrali. [CGGR] Algoritmi ricorsivi su alberi binari
lavagna lezione1 lezione2
21/04/2020 Alberi Binari di Ricerca [CLRS] cap 12: 12.1, 12.2.
lavagna lezione1 lezione2
21/04/2020 Laboratorio: Tabelle Hash. Slide
Esercizio 1 Esercizio 2
22/04/2020 Alberi AVL: definizione, alberi di Fibonacci, dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni; cancellazione: cenni). [CGGR]: Alberi AVL, rotazioni
lavagna video
23/04/2020 Esercitazione Esercizi su Alberi Binari
Esercizi su Alberi Binari di Ricerca
lavagna lezione1 lezione2
28/04/2020 Grafi: definizioni, rappresentazione in memoria. [CLRS]: appendice B.4, cap 22: 22.1
lavagna video
28/04/2020 Laboratorio: Alberi binari di ricerca. Slide
Esercizio 1 (con verifica 1-bilanciamento)
29/04/2020 Grafi: visita in ampiezza (BFS), algoritmo, analisi di complessità, proprietà (senza dimostrazioni), albero BF e algoritmo PRINT-PATH. Grafi: visita in profondità (DFS), algoritmo. [CLRS]: cap 22: 22.2, 22.3
lavagna video
30/04/2020 Grafi: visita in profondità (DFS), analisi di complessità, foresta DF, classificazione degli archi. [CLRS] cap 22: 22.3, 22.4 (Teorema 22.7, Corollario 22.8, Teorema 22.9, Lemma 22.11)
lavagna video
05/05/2020 Ordinamento topologico di grafi diretti aciclici. Esempi di problemi su grafi: clique, ciclo hamiltoniano, ciclo euleriano.
Esercitazione: progettazione di algoritmi efficienti su grafi.
[CLRS] cap 22: 22.4 (Teorema 22.12)
Esercizi su grafi lavagna 1 lavagna 2 video
05/05/2020 Laboratorio: simulazione prova d'esame. Slide
06/05/2020 Esercitazione: progettazione di algoritmi efficienti (dizionari, grafi) Esercizi su dizionari e alberi
lavagna altri esercizi svolti su grafi altri esercizi svolti su dizionari video
07/05/2020 Introduzione alla Programmazione Dinamica (PD). Calcolo dei numeri di Fibonacci. Requisiti di un problema su cui applicare la PD a confronto con il paradigma Divide et Impera. Il problema della Edit Distance: definizione. [CLRS] cap 15: 15.3.
Programmazione Dinamica (note di F. Luccio)
lavagna lezione1 lezione2
12/05/2020 Calcolo della Edit Distance con la PD: regola ricorsiva e ricostruzione della soluzione, algoritmo ED. Complessita'. Esempio. Edit Distance (note di F. Luccio)
lavagna lezione
12/05/2020 Laboratorio: grafi. Slide Esercizio 1 (Grafo Bipartito) Esercizio 2 (grafo connesso)
13/05/2020 Esercitazione su Programmazione Dinamica Esercizi sulla Programmazione Dinamica
SoluEditDistance
lavagna lezione1 lezione2
14/05/2020 Problemi Indecidibili e Problemi Intrattabili. Generazione delle sequenze binarie. Algoritmo enumerativo per il problema dello Zaino. Calcolabilità The Towers of Hanoi: note di Tom Leighton e Ronitt Rubinfeld, MIT, 2006 [BFL]: generazione delle sequenze binarie e delle permutazioni lavagna video
19/05/2020 Generazione delle permutazioni. Teoria della complessità: classi P e NP, certificati, riduzioni, problemi NP-completi. Le classi P, NP e NPC lucidi Complessità
lavagna video
19/05/2020 Laboratorio: esercitazione finale Slide
20/05/2020 Esercitazione: Certificati Polinomiali, Algoritmi Enumerativi. lavagna video
21/05/2020 Ricevimento collettivo sostitutivo del secondo compitino