Docenti: Anna Bernasconi, Rossano Venturini, Nadia Pisanti, Andrea Farruggia
(Docenti corso A: Linda Pagli, Rossano Venturini, Andrea Marino, Andrea Farruggia)
Impegno: 12 CFU.
Codice: 008AA
Periodo: primo anno, secondo semestre.
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.
Le lezioni di laboratorio del 23/2 e del 1/3 si terranno a gruppi riuniti nell'aula B alle 16
Orario delle Lezioni | |||
---|---|---|---|
Martedì | 16-18 | H, I, M | Laboratorio |
Mercoledì | 11-13 | B | Teoria |
Giovedì | 14-16 | B | Teoria |
Venerdì | 11-13 | B | Teoria |
Si pregano gli studenti che dispongono di un portatile di portarlo in Laboratorio.
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.
L'esame consiste di tre prove:
Le prove possono essere sostenute in appelli diversi. Se una prova non viene passata, occorre risostenere soltanto quella.
Per avere una idea della tipologia delle prove, si consultino i testi dell'anno scorso.
Data | Tipo Prova | Documento | Note |
---|---|---|---|
31/03/2016, ore 9:00 | Scritto (primo compitino) | algo1_310316.pdf | lista dei risultati (sono ammessi alla seconda prova di verifica intermedia gli studenti con voto >= 17) |
25/05/2016, ore 9:00 | Scritto (secondo compitino) | Testo e soluzioni | lista dei risultati Visione scritti: lunedì 30 maggio, dalle 14:30 alle 15:30, ufficio Bernasconi. |
27/06/2016, ore 9:00 | Scritto | Testo e soluzioni | lista dei risultati Visione scritti: giovedì 30 giugno, ore 9:30, ufficio Bernasconi. |
13/07/2016, ore 9:00 | Scritto | Testo | lista dei risultati Visione scritti: lunedì 18 luglio, ore 9:15, ufficio Bernasconi. |
05/09/2016, ore 14:00 | Scritto | Testo | lista dei risultati Visione scritti: lunedì 12 settembre, ore 14:00, ufficio Bernasconi. |
23/01/2017, ore 10:00 | Scritto | Testo | lista dei risultati Visione scritti: mercoledì 25 gennaio, dalle ore 11:00 alle ore 13:00, ufficio Bernasconi. |
13/02/2017, ore 9:00 | Scritto | Testo | lista dei risultati Visione scritti: martedì 14 febbraio, dalle ore 11:00 alle ore 12:00, ufficio Bernasconi. |
Prossime date per le prove di laboratorio:
Data | Ora | Aule | Documento | Note |
---|---|---|---|---|
05/04/2016 | 14:00 | H | Appello straordinario riservato a studenti lavoratori e fuori corso | |
09/06/2016 | 9:00 | H,M,I | Appello riservato agli studenti che hanno superato i compitini o appelli precedenti | |
04/07/2016 | 9:00 | H,M,I | ||
25/07/2016 | 9:00 | H,M,I |
Prossime date per le prove orali:
Data | Ora | Aula | Note |
---|---|---|---|
31/05/2016 | 9:00 | N1 | obbligatorio iscriversi (via email) |
1/06/2016 | 9:00 | N1 | obbligatorio iscriversi (via email) |
22/06/2016 | 9:30 | N1 | obbligatorio iscriversi (via email) |
30/06/2016 | 10:00 | ufficio Bernasconi | obbligatorio iscriversi (via email) |
6/07/2016 | 9:30 | ufficio Bernasconi | obbligatorio iscriversi (via email) |
13/07/2016 | 14:00 | ufficio Bernasconi | obbligatorio iscriversi (via email) |
21/07/2016 | 14:00 | ufficio Bernasconi | obbligatorio iscriversi (via email) |
12/09/2016 | 14:15 | ufficio Bernasconi | obbligatorio iscriversi (via email) |
27/01/2017 | 9:30 | ufficio Bernasconi | obbligatorio iscriversi (via email) |
16/02/2017 | 9:30 | ufficio Bernasconi | obbligatorio iscriversi (via email) |
23/02/2017 | 13:30 | ufficio Bernasconi | obbligatorio iscriversi (via email) |
Per il laboratorio, un testo fra:
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.qsort
-based.Data | Argomento | Rif. Biblio |
---|---|---|
23/02/2016 | Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. Lucidi. |
24/02/2016 | Nozioni di Problema, Algoritmo, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete. | 12 monete lavagna |
25/02/2016 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo, al caso ottimo e al caso medio. Insertion sort: correttezza e analisi di complessità al caso ottimo, medio e pessimo. | [CLRS] cap 1, cap 2: 2.1, 2.2. lavagna |
26/02/2016 | Selection sort: correttezza e analisi di complessità. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. | [CLRS] cap 3. TCS cheat sheet lavagna |
1/03/2016 | Laboratorio: Puntatori, Array, e stringhe. Uso di Valgrind. Allocazione dinamica della memoria. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi |
2/03/2016 | Paradigma del Divide et Impera. MergeSort: algoritmo e correttezza. | [CLRS] cap 2: 2.3. lavagna |
3/03/2016 | MergeSort: analisi di complessità. Esercitazione: progettazione di algoritmi e analisi di complessità. | Esercizi (ricerca, ordinamento, divide et impera) lavagna |
4/03/2016 | Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero di decisione. Limite inferiore per l'ordinamento per confronti. | [CLRS] cap 8: 8.1. limiti inferiori lavagna |
8/03/2016 | Laboratorio: Esercizi. | |
9/03/2016 | Limiti inferiori: tecnica degli eventi contabili. Esempi: algoritmo del torneo e del doppio torneo. Relazioni di ricorrenza: metodo dell'esperto (Teorema principale) con esempi di applicazione. Dimostrazione del teorema principale (solo per potenze esatte). | [CLRS] cap 4: 4.5, 4.6.1. Il problema del torneo lavagna |
10/03/2016 | Esercitazione: progettazione di algoritmi e analisi di complessità. | lavagna |
11/03/2016 | Moltiplicazione veloce di interi e matrici. Esercitazione: esercizi sull'applicazione del Teorema Principale. | [CLRS] cap 4: 4.2. Moltiplicazione veloce di interi (appunti del Prof. Grossi) lavagna |
15/03/2016 | Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante | Lucidi |
16/03/2016 | Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato: analisi della complessità nel caso medio. | [CLRS] cap 7: 7.1, 7.2, 7.3, 7.4.2 Numero di confronti di Randomized-Quicksort (Appunti del Prof. Luccio) lavagna |
17/03/2016 | Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo atteso lineare. Esercitazione: progettazione di algoritmi e analisi di complessità. | [CLRS] cap 9: 9.1, 9.2 (senza analisi nel caso medio) Esercizi (divide et impera, ricorrenze, ordinamento) lavagna |
18/03/2016 | Heap: definizione, realizzazione implicita come array, proprietà, conservazione della proprietà di heap, costruzione. | [CLRS] cap 6: 6.1, 6.2. lavagna |
22/03/2016 | Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe, e QuickSort. | Lucidi Lucidi |
23/03/2016 | Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. L'algoritmo Heapsort. Code di priorità: definizione, operazioni, realizzazione mediante heap. | [CLRS] cap 6: 6.3, 6.4, 6.5. lavagna |
24/03/2016 | Esercitazione: Esercizi di preparazione alla prima prova di verifica intermedia. | lavagna |
31/03/2016 | Prima prova di verifica intermedia. | lista dei risultati |
6/04/2016 | Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. | [CLRS] cap 8: 8.2, 8.3. lavagna |
7/04/2016 | Correzione della prima prova di verifica intermedia. Esercitazione: heap. | Esercizi (heap) lavagna |
8/04/2016 | 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. lavagna |
12/04/2016 | Laboratorio: Qsort e ripasso delle struct. | Lucidi |
13/04/2016 | Tabelle hash a indirizzamento aperto (analisi al caso pessimo e medio). Scansione lineare, scansione quadratica, doppio hashing. | [CLRS] cap 11: 11.4. Dispense Prof. Luccio lavagna |
14/04/2016 | Esercitazione: tabelle hash e heap. | Esercizi (heap) lavagna |
15/04/2016 | Alberi e alberi binari: visite, algoritmi ricorsivi su alberi binari, memorizzazione binarizzata. | [CLRS] cap 10: 10.4. [CGGR]: Algoritmi ricorsivi su alberi binari lavagna |
19/04/2016 | Laboratorio: Esercizi d'esame: qsort e struct. | Lucidi |
20/04/2016 | Dizionari: realizzazione con alberi binari di ricerca; interrogazioni (ricerca, minimo, massimo, successore); inserimento e cancellazione. | [CLRS] cap 12: 12.1, 12.2, 12.3. lavagna |
21/04/2016 | Esercitazione: progettazione di algoritmi efficienti su alberi binari e alberi binari di ricerca. | EserciziAB lavagna |
22/04/2016 | 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 |
26/04/2016 | Laboratorio: Liste. | Lucidi |
27/04/2016 | Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva. | [CLRS] cap 15: 15.4. lavagna |
28/04/2016 | LCS: ricostruzione della soluzione, algoritmi LCS-LENGTH e PRINT-LCS. | [CLRS] cap 15: 15.4. lavagna |
29/04/2016 | Esercitazione: progettazione di algoritmi efficienti (dizionari e alberi). | Esercizi su dizionari e alberi Soluzioni lavagna |
3/05/2016 | Laboratorio: Alberi binari di ricerca. | Lucidi |
4/05/2016 | Il problema della Edit Distance: definizione, regola ricorsiva e ricostruzione della soluzione, algoritmi ED e ALLINEA. | Edit Distance (dispense Prof. Luccio). lavagna |
5/05/2016 | Esercitazione: Programmazione Dinamica. | Esercizi sulla Programmazione Dinamica lavagna |
6/05/2016 | Lezione non tenuta causa mancata apertura del Polo Didattico (sciopero dei lavoratori del servizio di portierato) | |
10/05/2016 | Laboratorio: Tabelle Hash. | Lucidi |
11/05/2016 | Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. Algoritmi pseudopolinomiali. Generazione delle sequenze binarie e algoritmo enumerativo per il problema dello zaino. | [CLRS] cap 16: 16.2, esercizio 16.2.2 (algoritmo PD per lo Zaino). [CGGR]: generazione delle sequenze binarie, pseudopolinomialità lavagna |
12/05/2016 | Grafi: definizioni, rappresentazione di grafi in memoria, esempi di problemi su grafi (perfect matching, ciclo hamiltoniano e ciclo euleriano). | [CLRS]: appendice B.4, cap 22: 22.1. lavagna |
13/05/2016 | Grafi: visita in ampiezza (BFS), algoritmo e analisi di complessità, albero di visita in ampiezza e algoritmo PRINT-PATH; esplorazione di un grafo con insieme di vertici non noto; visita in profondità (DFS). | [CLRS] cap 22: 22.2, 22.3 (senza dimostrazioni). lavagna |
17/05/2016 | Laboratorio: Simulazione della prova di laboratorio. | |
18/05/2016 | Grafi: visita in profondità (DFS), analisi di complessità, classificazione degli archi; ordinamento topologico di grafi diretti aciclici. | [CLRS] cap 22: 22.3, 22.4. lavagna |
19/05/2016 | Esercitazione: progettazione di algoritmi efficienti su grafi. | Esercizi lavagna |
20/05/2016 | Introduzione alla computabilità, problemi indecidibili. Il problema dell'arresto. Teoria della complessità: le classi P e NP. | Calcolabilità Complessità |
24/05/2016 | Laboratorio: Simulazione della prova di laboratorio. | |
25/05/2016 | Seconda prova di verifica intermedia. |