Indice

Algoritmica e Laboratorio - Corso A

Anno accademico 2017/2018

Informazioni Generali

Docenti Teoria/Esercitazioni: Paolo Ferragina e Giuseppe Prencipe (corso A) e Linda Pagli (corso B)

Docenti Laboratorio: Anna Bernasconi, Alina Sirbu, 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: Ferragina lunedì 14-16 e su appuntamento. Eventuali variazioni di orario sulle lezioni e/o ricevimento, o comunicazioni sul corso verranno segnalate tramite Twitter all'account @FerraginaTeach

Nel periodo estivo si segnalano i seguenti ricevimenti del Prof. Ferragina: 4 giugno ore 15:30, 14 giugno ore 9, 18 giugno ore 14.30.

Ricevimento studenti Prencipe: Venerdì dalle ore 11:00 alle ore 13:00

Registro delle lezioni: si tratta del registro ufficiale che riporta quanto indicato nel seguito.

Orario Lezioni

Orario delle Lezioni
Lunedì 9-11 aula E Teoria
Martedì 16-18 aule H-I-M Laboratorio
Mercoledì 11-13 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

L'esame consiste di tre prove:

Per avere una idea della tipologia delle prove, si consultino i testi degli anni scorsi.

Data Tipo Prova Documento
04/04/18 Primo Compitino testo1 e testo2, soluzione. Lista dei risultati (solo quelli che hanno riportato una votazione >=17 e sono quindi ammessi al secondo compitino). Mancando di matricola, in quanto non registrati, si segnalano anche Bertolucci Simone 24, Dardanis Nicola 23, Morini Virginia 17.
Per la correzione e visione del compito: mercoledì 11 aprile, Aula G, ore 17:00
30/05/18 Secondo Compitino testo, soluzione, lista dei risultati (solo quelli che hanno riportato una votazione >=18).
Per la correzione e visione del compito: Aula C, martedì 5 giugno, ore 9:00.
La prova orale e la prova di laboratorio possono essere sostenute in qualunque appello secondo le regole su indicate. L'aumento +2 al voto di media (valido solo per i compitini) viene perso se si decide di sostenere la prova orale, la quale è quindi facoltativa per chi ha passato i compitini, ma può portare a un incremento max di 4 punti. La registrazione del voto, dopo aver passato anche la prova di laboratorio, può avvenire in qualunque appello. La visione dei compiti è possibile durante l'orario di ricevimento: 4 giugno ore 15:30, 14 giugno ore 9, 18 giugno ore 14.30.
22/06/18 Primo Appello testo, soluzione, lista dei risultati (solo quelli che hanno riportato una votazione >=18).
Per la correzione e visione del compito: Aula C, lunedì 25 giugno, ore 17:00.
La prova orale e la prova di laboratorio possono essere sostenute in qualunque appello secondo le regole su indicate. L'aumento +2 al voto dello scritto viene perso se si decide di sostenere la prova orale, la quale è quindi facoltativa e può portare a un incremento max di 4 punti. La registrazione del voto, dopo aver passato anche la prova di laboratorio, può avvenire in qualunque appello o ricevimento del docente.
13/07/18
ore 9-11
Secondo appello testo, soluzione, lista dei risultati.
04/09/18
ore 9-11
Terzo appello testo, risultati.
Gli studenti interessati a sostenere la prova orale (opzionale) devono inviare un'email al docente.
La registrazione del voto (avendo superato anche il laboratorio) e l'orale (opzionale) possono avvenire in qualunque appello. L'aumento +2 al voto dello scritto viene perso se si decide di sostenere la prova orale, la quale è quindi facoltativa e può portare a un incremento max di 4 punti. La prossima data utile per orale/registrazione è lunedì 17 settembre, ore 14.30, studio Ferragina. La correzione e visione del compito può avvenire lunedì 10 settembre, ore 14.30, studio Ferragina.
21/01/19 Quarto appello testo, risultati (solo per quelli che hanno riportato un voto >= 16, che possono svolgere la prova di laboratorio.).
La correzione e visione dei compiti avverrà giovedì 24 gennaio 2019, ore 11.00, studio Prof.ssa Pagli.
La prossima data utile per la registrazione del voto è giovedì 24 gennaio 2019, ore 9:00, aula C con il Prof. Ferragina.
La registrazione del voto (avendo superato anche il laboratorio) e l'orale (facoltativo) possono avvenire in qualunque appello. L'aumento +2 al voto dello scritto viene attribuito automaticamente alla registrazione del voto, ma esso viene perso se si decide di sostenere la prova orale, la quale è facoltativa e può portare a un incremento max di 4 punti. Gli studenti interessati a sostenere la prova orale devono inviare un'email al docente Prof. Ferragina.

Libri di testo

Per il laboratorio, un testo fra:

Materiale per il Laboratorio

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
19/02/2018 Questioni organizzative: pagina web, canale twitter, 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 12 monete
20/02/2018 Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Cap. 2-3, 7.1-7.4 di [KR]. Slide
21/02/2018 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
Slide
23/02/2018 Esercitazione sulla notazione asintotica
26/02/2018 Selection sort versus Insertion sort: correttezza e complessità asintotica al caso pessimo e al caso ottimo. CLRS: Sezione 2.1 e 2.2.
27/02/2018 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
28/02/2018 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.
02/03/2018 MergeSort: algoritmo, correttezza e analisi di complessità (metodo iterativo e albero di ricorsione). [CLRS] cap 2: 2.3; cap 4: 4.4.
05/03/2018 Lezione non tenuta per sospensione elettorale
06/03/2018 Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante Slide
07/03/2018 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].
Slide.
09/03/2018 Enunciato del Teorema dell'esperto, con esempi. Dimostrazione del Teorema dell'esperto per il caso delle potenze. [CLRS] cap 4: 4.5 e 4.6.1 (dimostrazione per potenze esatte)
12/03/2018 Esercizi sul Teorema dell'esperto. Algoritmo della Ricerca Binaria e della Moltiplicazione veloce con analisi della complessità. (Studiare anche prodotto veloce tra matrici.) [CLRS] con esercizi. Note di F. Luccio su moltiplicazione interi e matrici.
13/03/2018 Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. Slide
14/03/2018 Esercizi sul Teorema dell'esperto. Slides
16/03/2018 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
19/03/2018 Limiti inferiori alla complessità di un problema: dimensione dell'input, eventi contabili e albero di decisione. Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo medio lineare. Note di F. Luccio su limiti inferiori. [CLRS] cap 8: 8.1.
[CLRS] cap 9: 9.1, 9.2 (leggere analisi al caso medio dalla seguente nota).
20/03/2018 Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Slide
21/03/2018 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à. L'algoritmo Heapsort. [CLRS] cap 6: 6.1 - 6.4.
22/03/2018 Code di priorità: definizione, operazioni, realizzazione mediante heap. [CLRS] cap 6: 6.5.
26/03/2018 Esercitazione su ordinamento e Heap. Esercizi (heap)
27/03/2018 Laboratorio: Qsort e ripasso delle struct.Slide
28/03/2018 Esercitazione pre-compitino Esercizi svolti: lavagna 1, lavagna 2.
11/04/2018 Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. [CLRS] cap 8: 8.2, 8.3.
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.
13/04/2018 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.
16/04/2018 Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica, doppio hashing. [CLRS] cap 11: 11.4.
17/04/2018 Laboratorio: Esercizi d'esame: qsort e struct.Slide
18/04/2018 Alberi e alberi binari: Definizione e memorizzazione. Dizionari: realizzazione con alberi binari di ricerca; interrogazioni (minimo, massimo, successore, predecessore); inserimento e cancellazione. Analisi della loro complessità in tempo. [CLRS] cap 10: 10.4. cap 12: 12.1, 12.2, 12.3.
20/04/2018 Visita di alberi binari di ricerca: Pre/in/post visita e loro applicazioni. Algoritmi ricorsivi su alberi binari. Esercizi sugli alberi binari di ricerca. Esercizi su alberi, Esercizi su dizionari e alberi, lavagna 3.
23/04/2018 Alberi 2-3: definizione, conteggio numero di nodi e foglie (con dimostrazione). Dizionari: realizzazione con alberi 2-3 (ricerca; inserimento; cancellazione). [DFI]: alcune pagine (no sezione B-alberi),
24/04/2018 Laboratorio: Liste monodirezionali e bidirezionali. SlideEsercizio 1 in aula.
27/04/2018 Generazione delle sequenze binarie. Generazione delle permutazion. Esempi. [CGGR]: alcune note su generazione binarie e permutazioni
30/04/2018 Esercizi su alberi binari
02/05/2018 Esercizi su alberi hash, genera binarie/permutazioni
04/05/2018 Grafi: definizioni, rappresentazione di grafi in memoria, esempi di problemi su grafi. Il problema del ciclo euleriano e il problema del ciclo hamiltoniano: definizioni, e considerazioni computazionali. Teorema di Eulero. Alcune note su ciclo euleriano e hamiltoniano. [CLRS]: appendice B.4, cap 22: 22.1.
07/05/2017 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 .
08/05/2018 Laboratorio: Alberi binari di ricerca. Slide
09/05/2017 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
11/05/2017 Lezione non tenuta, ma qui a fianco trovate esercizi da svolgere/svolti su alberi e tabelle hash. Testo 1 (no ex 2-3 albero) e testo 2
14/05/2018 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. [CLRS] cap 15: 15.4. Note del Prof. Luccio. Esercizi sulla Programmazione Dinamica
15/05/2018 Laboratorio: Tabelle hash. Slide Esercizio 1 in aula
16/05/2018 Il problema della sequenza ottima di moltiplicazioni di matrici. Il problema della ricerca approssimata di un pattern in un testo. Il problema della determinazione della Longest Common Subsequence. Edit Distance (dispense Prof. Luccio)
18/05/2018 Esercitazione sui grafi.
21/05/2018 Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino (intero e frazionario). Algoritmi pseudopolinomiali. Il problema dello scheduling delle attivita'. [CLRS] cap 16: 16.2, Il problema dello zaino intero e frazionario.. esercizio 16.2.2 (algoritmo PD per lo Zaino). pseudopolinomialità
22/05/2018 Laboratorio: Simulazione prova di esame.
23/05/2018 Teoria della complessità: le classi P e NP, ed NP-completi. Esempio di riduzione da SAT a Clique. Su P vs NP si consultino: nota 1 e nota 2, quest'ultima nelle pagine 4-6. Per la dimostrazione di NPC per Clique si vedano pag 1-3 di nota 3
25/05/2018 Esercizi su Programmazione Dinamica soluzioni.altri esercizi.
28/05/2018 Esercizi su NPC e grafi
29/05/2018 Laboratorio: Grafi. Slide