Questa è una vecchia versione del documento!
Docenti: Anna Bernasconi, Rossano Venturini, Nadia Pisanti, Andrea Farruggia
(Docenti corso A: Linda Pagli, Rossano Venturini, Giovanna Rosone, 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.
Orario delle Lezioni | |||
---|---|---|---|
Martedì | 11-13 | B | Teoria |
Mercoledì | 11-13 | B | Teoria |
Giovedì | 14-16 | H,M | Laboratorio |
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 |
---|---|---|---|
14/04/2015, ore 11.00 | Scritto (primo compitino) | algo1_140415.pdf | lista dei risultati. |
29/05/2015, ore 9.00 | Scritto (secondo compitino) | testo e soluzioni | lista dei risultati. Visione scritti: martedì 3 giugno, dalle 14:30 alle 15:30, ufficio Bernasconi. |
12/06/2015, ore 9:30 | Scritto | testo e soluzioni | lista dei risultati. Visione scritti: lunedì 15 giugno, dalle 14:30 alle 15:30, ufficio Bernasconi. |
03/07/2015, ore 9:30 | Scritto | testo e soluzioni | lista dei risultati. Visione scritti: lunedì 6 luglio, dalle 11:00 alle 12:00, ufficio Bernasconi. |
10/09/2015, ore 14:30 | Scritto | testo e soluzioni | lista dei risultati. Visione scritti: lunedì 14 settembre, dalle 10:00 alle 11:00, ufficio Bernasconi. Orali: mercoledì 16 settembre, ore 9:15, ufficio Bernasconi |
11/01/2016, ore 9:00 | Scritto | testo e soluzioni | lista dei risultati. Visione scritti: mercoledì 13 gennaio, dalle 11:00 alle 12:00, ufficio Bernasconi. Orali: martedì 19 gennaio, ore 9:00, ufficio Bernasconi, oppure su appuntamento |
01/02/2016, ore 9:00 | Scritto | testo e soluzioni | lista dei risultati. Visione scritti: giovedì 4 febbraio, dalle 9:00 alle 10:00, ufficio Bernasconi. Orali: giovedì 4 febbraio, ore 10:00, ufficio Bernasconi, oppure su appuntamento |
Prossime date per le prove di laboratorio:
Data | Ora | Aule | Documento |
---|---|---|---|
04/06/2015 | 9:00 | H-M-I | Testo TestSet |
22/06/2015 | 9:00 | H-M-I | Testo |
09/07/2015 | 9:00 | H-M-I | |
15/09/2015 | 9:00 | H-M-I | |
06/11/2015 | 10:00 | M | Appello straordinario |
13/01/2016 | 9:00 | H-M-I | |
03/02/2016 | 9:00 | H-M-I |
Prossime date per le prove orali:
Data | Ora | Aula |
---|---|---|
venerdì 5/06/2015 | 9:30 | aula A1 |
mercoledì 10/06/2015 | 9:30 | ufficio Bernasconi |
martedì 16/06/2015 | 9:30 | ufficio Bernasconi |
martedì 23/06/2015 | 9:30 | ufficio Bernasconi |
lunedì 29/06/2015 | 9:30 | ufficio Bernasconi |
venerdì 10/07/2015 | 9:30 | ufficio Bernasconi |
giovedì 23/07/2015 | 15:00 | ufficio Bernasconi |
mercoledì 16/09/2015 | 9:15 | ufficio Bernasconi |
martedì 19/06/2015 | 9:00 | ufficio Bernasconi |
martedì 4/02/2016 | 10:00 | ufficio Bernasconi |
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 |
---|---|---|
24/02/2015 | Nozioni di Problema, Algoritmo, Limite Inferiore. Analisi di un problema semiserio: il problema delle 12 monete. Moltiplicazione Egizia. | 12 monete |
25/02/2015 | 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. |
26/02/2015 | Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. Funzioni e puntatori. | Cap. 2-3, Sez. 4.1-4.5, 5.1-5.5 e 7.1-7.4 di [KR]. Lucidi |
27/02/2015 | Selection sort: correttezza e analisi di complessità. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. | [CLRS] cap 3. |
3/03/2015 | Paradigma del Divide et Impera. MergeSort: algoritmo, correttezza e analisi di complessità. | [CLRS] cap 2: 2.3. |
4/03/2015 | Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero di decisione. Esempi: algoritmo del torneo e del doppio torneo, albero di decisione per l'insertion sort su tre elementi. | [CLRS] cap 8: 8.1. limiti inferiori Il problema del torneo |
5/03/2015 | 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 |
6/03/2015 | Limite inferiore per l'ordinamento per confronti. Il problema della ricerca: ricerca sequenziale e ricerca binaria. | [CLRS] cap 8: 8.1. |
10/03/2015 | Esercitazione: progettazione di algoritmi e analisi di complessità. | Esercizi (divide et impera, ricerca, ordinamento) |
11/03/2015 | Relazioni di ricorrenza: metodo dell'albero di ricorsione, metodo dell'esperto (Teorema principale) con esempi di applicazione. | [CLRS] cap 4: 4.4, 4.5. |
12/03/2015 | Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante | Lucidi |
13/03/2015 | Dimostrazione del teorema principale (solo per potenze esatte). Moltiplicazione veloce di interi e matrici. | [CLRS] cap 4: 4.2, 4.6.1. Moltiplicazione veloce di interi (Prof. Grossi) |
17/03/2015 | Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato. | [CLRS] cap 7: 7.1, 7.2, 7.3. |
18/03/2015 | Quicksort randomizzato: analisi della complessità nel caso medio. Statistiche d'ordine: algoritmo Randomized-Select per la selezione dell'i-esimo elemento più piccolo in tempo atteso lineare. | [CLRS] cap 7: 7.4.2, cap 9: 9.1, 9.2 (senza analisi nel caso medio). Numero di confronti di Randomized-Quicksort (Prof. Luccio) |
19/03/2015 | Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | Lucidi |
20/03/2015 | Esercitazione: progettazione di algoritmi e analisi di complessità. | Esercizi (divide et impera, ricorrenze, ordinamento) |
24/03/2015 | Heap: definizione, realizzazione implicita come array, proprietà, conservazione della proprietà di heap, costruzione. | [CLRS] cap 6: 6.1, 6.2, 6.3. |
25/03/2015 | 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. |
26/03/2015 | Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | Lucidi QuickSortParziale Partizionamento |
27/03/2015 | Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort e Radix sort. | [CLRS] cap 8: 8.2, 8.3. |
31/03/2015 | Esercitazione: progettazione di algoritmi e analisi di complessità. | Esercizi (heap) |
1/04/2015 | Esercitazione: progettazione di algoritmi e analisi di complessità. | |
2/04/2015 | Laboratorio: Qsort e ripasso delle struct. | Lucidi |
14/04/2015 | Prima prova di verifica intermedia. | lista dei risultati |
15/04/2015 | Correzione della prima prova di verifica intermedia. Alberi binari: visite, algoritmi ricorsivi su alberi binari. | [CLRS] cap 10: 10.4. [CGGR]: Algoritmi ricorsivi su alberi binari |
16/04/2015 | Laboratorio: Esercizi d'esame: qsort e struct. | Lucidi |
17/04/2015 | Alberi: memorizzazione binarizzata. Dizionari: realizzazione con alberi binari di ricerca (ricerca, minimo, massimo, successore). | [CLRS] cap 10: 10.4, cap 12: 12.1, 12.2. |
21/04/2015 | Dizionari: realizzazione con alberi binari di ricerca (inserimento e cancellazione). | [CLRS] cap 12: 12.3. |
22/04/2015 | 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. |
23/04/2015 | Laboratorio: Liste. | Lucidi |
24/04/2015 | Esercitazione: progettazione di algoritmi efficienti su alberi binari, ABR e AVL. | EserciziAB |
28/04/2015 | 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. |
29/04/2015 | 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 |
30/04/2015 | Laboratorio: Alberi. | Lucidi |
5/05/2015 | 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. |
6/05/2015 | LCS: ricostruzione della soluzione, algoritmi LCS-LENGTH e PRINT-LCS. Il problema della Edit Distance: definizione, regola ricorsiva e ricostruzione della soluzione. | [CLRS] cap 15: 15.4. Edit Distance (dispense Prof. Luccio). |
7/05/2015 | Laboratorio: Tabelle Hash. | Lucidi |
8/05/2015 | Edit Distance: algoritmi ED e ALLINEA. Apparizioni approssimate di una sequenza in un testo (cenni). Esercitazione: progettazione di algoritmi efficienti (dizionari e alberi). | Esercizi su dizionari e alberi Soluzioni |
12/05/2015 | 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à. |
13/05/2015 | Grafi: definizioni, rappresentazione di grafi in memoria, visita in ampiezza (BFS). | [CLRS]: appendice B.4, cap 22: 22.1, 22.2. |
14/05/2015 | Laboratorio: Simulazione della prova di laboratorio. | |
15/05/2015 | Visita in ampiezza di un grafo: algoritmo BFS e analisi di complessità, albero di visita in ampiezza e algoritmo PRINT-PATH, esplorazione di un grafo con insieme di vertici non noto. Implementazione di una coda su array. Esercitazione: esercizi sulla Programmazione Dinamica. | [CLRS] cap 22: 22.2 (senza dimostrazioni), cap 10: 10.1. Esercizi sulla Programmazione Dinamica Soluzioni |
19/05/2015 | Grafi: visita in profondità (DFS); classificazione degli archi; ordinamento topologico di grafi diretti aciclici. | [CLRS] cap 22: 22.3, 22.4. |
20/05/2015 | Esercitazione: progettazione di algoritmi efficienti su grafi. | Esercizi |
21/05/2015 | Laboratorio: Soluzione della prova di laboratorio della scorsa settimana. | soluzione |
22/05/2015 | Introduzione alla computabilità, problemi indecidibili. Il problema dell'arresto. Le classi di complessità P e NP: introduzione. | Lucidi |
26/05/2015 | Teoria della complessità: classe P; nozione di certificato polinomiale e classe NP; nozione di riduzione polinomiale; problemi NP-completi. Esempi: problema del ciclo euleriano; generazione di tutte le permutazioni e problema del ciclo hamiltoniano; riduzione SAT - Clique. | [CLRS] cap 34: 34.1. Lucidi Generazione delle permutazioni e problema del ciclo hamiltoniano. |
29/05/2015 | Seconda prova di verifica intermedia. |