Docenti: Anna Bernasconi, Rossano Venturini
(Docenti corso A: Linda Pagli, Rossano Venturini)
Assistente: Roberto Santoro
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 | A | Teoria |
Mercoledì | 11-13 | A | Teoria |
Giovedì | 14-16 | H,M | Laboratorio |
Venerdì | 11-13 | A | 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 |
---|---|---|---|
02/04/2014, ore 11.00 | Scritto (primo compitino) | algo1_020414.pdf | |
28/05/2014, ore 11.00 | Scritto (secondo compitino) | algo1_28052014.pdf | |
09/06/2014, ore 11.00 | Scritto | algo1_090614.pdf | |
08/07/2014, ore 9:30 | Scritto | algo1_08072014.pdf, Soluzioni | |
08/09/2014, ore 9.30 | Scritto | algo1_08092014.pdf, Soluzioni | |
04/11/2014, ore 9.00 | Scritto | algo1_04112014.pdf | |
14/01/2015, ore 9.00 | Scritto | algo1_14012015.pdf,algo140115sol.pdf | |
12/02/2015, ore 9.00 | Scritto | algo1_12020215.pdf | Risultati. Visione scritti: lunedì 16 febbraio, ore 12-13 ufficio Bernasconi. Orali: 18 febbraio, ore 10, ufficio Bernasconi (oppure su appuntamento). |
Prossime date per le prove di laboratorio:
Data | Ora | Aule | Documento |
---|---|---|---|
13/06/2014 | 9:00 | H, I, M | Testo 1 Testo 2 Test1 Test2 |
27/06/2014 | 9:00 | H, I, M | Testo Test |
16/07/2014 | 9:00 | H, I, M | Testo Test |
15/09/2014 | 9:00 | H, I, M | Testo e test |
06/11/2014 | 9:00 | I, M | Testo e test |
16/01/2015 | 9:00 | H, I, M | Testo e test |
17/02/2015 | 9:00 | H, I, M |
Prossime date per le prove orali:
Data | Ora | Aula |
---|---|---|
03/06/2014 | 9:15 | aula A1 |
16/06/2014 | 9:15 | aula B |
30/06/2014 | 9:15 | ufficio Bernasconi |
10/07/2014 | 9:30 | ufficio Bernasconi |
16/07/2014 | 11:00, 14:00 | ufficio Bernasconi |
24/07/2014 | 14:00 | ufficio Bernasconi |
16/09/2014 | 9:30 | ufficio Bernasconi |
20/01/2015 | 10:00 | ufficio Bernasconi |
18/02/2015 | 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 suggeriamo il compilatore e il debugger disponibili con MinGW, e consigliamo di istallare i 3 componenti suddetti secondo la sequenza: Eclipse-MinGW-CDevTool. Oppure istallare una macchina virtuale, come VirtualBox, con una qualunque distribuzione Linux sopra. 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 |
---|---|---|
18/02/2014 | Introduzione al corso: intervento del Prof. Roberto Grossi. | |
19/02/2014 | Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. Lucidi Istruzioni per testing |
20/02/2014 | Laboratorio: Funzioni e puntatori. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi |
21/02/2014 | Nozioni di Algoritmo, Problema, Limite Inferiore. Moltiplicazione Egizia. Analisi di un problema semiserio: il problema delle 12 monete. | 12 monete |
25/02/2014 | Modello RAM e complessità computazionale di un algoritmo in tempo e spazio, al caso pessimo e caso medio. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo, con esempi. | Notazione asintotica (dispensa Prof. Luccio); [CGGR]: introduzione; Formule utili |
26/02/2014 | Laboratorio: Puntatori, Array, e stringhe. Uso di Valgrind. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi |
27/02/2014 | Laboratorio: Allocazione dinamica della memoria. | Lucidi |
28/02/2014 | Array di dimensione variabile. Selection Sort e Insertion Sort: proprietà e complessità al caso ottimo, medio e pessimo. | [CGGR]: cap. 1. |
04/03/2014 | Algoritmi di ordinamento stabili. Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero delle decisioni. Esempi: algoritmo del torneo e del doppio torneo. | limiti inferiori |
05/03/2014 | Limite inferiore per l'ordinamento per confronti. Il problema della ricerca: ricerca binaria ricorsiva: analisi. Paradigma Divide et Impera. Un algoritmo ottimo di ordinamento di tipo Divide et Impera: MergeSort. | [CGGR]: pag 56, cap 3. |
06/03/2014 | Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante | Lucidi |
07/03/2014 | Esercitazione: progettazione di algoritmi e analisi di complessità. | |
11/03/2014 | Relazioni di ricorrenza: Teorema principale (con dimostrazione) ed esempi di applicazione. | Ricorrenze (dispensa Prof. Luccio). |
12/03/2014 | Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato: analisi al caso medio. | [CGGR]: cap 3 e cap 5. |
13/03/2014 | Laboratorio: Selection Sort, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | Lucidi |
14/03/2014 | Selezione dell'elemento di rango r in un array (QuickSelect). Moltiplicazione veloce di interi e matrici. | [CGGR]: cap 3 e cap 5. |
18/03/2014 | Esercitazione: progettazione di algoritmi e analisi di complessità. | Esercizi |
19/03/2014 | Code con priorità: definizione, operazioni Empty, Enqueue, Dequeue, First. Heap di massimo: definizione, proprietà e rappresentazione in memoria (allocazione implicita in un array). | [CGGR]: cap 2. |
20/03/2014 | Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. Puzzle: La scala e Corsa di cavalli | Lucidi QuickSortParziale Partizionamento |
24/03/2014 | Heap di massimo: implementazione delle operazioni Enqueue, First, Dequeue. HeapSort: definizione e analisi. | [CGGR]: cap 2. |
25/03/2014 | Ordinamento di interi: Counting sort e Radix Sort. | [CLR] cap. 8 |
26/03/2014 | Esercitazione: progettazione di algoritmi e analisi di complessità. | |
27/03/2014 | Laboratorio: Qsort e ripasso delle struct | Lucidi |
28/03/2014 | Esercitazione: progettazione di algoritmi e analisi di complessità (heap, numeri di Fibonacci). | |
02/04/2014 | Prima prova di verifica intermedia. | |
08/04/2014 | Algoritmi per il calcolo dei numeri di Fibonacci. Correzione della prima prova di verifica intermedia. | |
09/04/2014 | Introduzione alla Programmazione Dinamica. Distanza tra due stringhe (Edit Distance). | Programmazione dinamica (dispensa Prof. Luccio) ; [CGGR]: cap 6. |
10/04/2014 | Laboratorio: Esercizi d'esame: qsort e struct | Lucidi |
11/04/2014 | Programmazione Dinamica: Longest Common Subsequence, Partizione di un insieme di interi. | [CGGR]: cap 6. |
15/04/2014 | Algoritmi pseudopolinomiali. Tecnica Greedy e Programmazione Dinamica: il problema dello Zaino. | [CGGR]: cap 6. Esercizi |
16/04/2014 | Alberi binari: visite, algoritmi ricorsivi su alberi binari. Alberi cardinali. Alberi ordinali: memorizzazione binarizzata. | [CGGR]: cap 1, cap 3. |
17/04/2014 | Laboratorio: Liste | Lucidi |
30/04/2014 | Dizionari: realizzazione con alberi binari di ricerca. Alberi AVL: definizione. | [CGGR]: cap 4. |
02/05/2014 | Alberi binari 1-bilanciati: alberi di Fibonacci; dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni). | [CGGR]: cap 4; lucidi. |
06/05/2014 | Alberi AVL: esempio di inserimento con rotazioni, cancellazione: cenni. Introduzione alle tabelle hash. | [CGGR]: cap 4. |
07/05/2014 | Dizionari: realizzazione con tabelle hash (con liste di trabocco e a indirizzamento aperto). | [CGGR]: cap 4. |
07/05/2014 | Esercitazione: progettazione di algoritmi di programmazione dinamica per problemi su scacchiera. | EserciziPD: soluzioni |
08/05/2014 | Laboratorio: Alberi | Lucidi |
09/05/2014 | Esercitazione: progettazione di algoritmi efficienti su alberi binari, ABR e AVL. | EserciziAB |
13/05/2013 | Grafi: definizioni, rappresentazione di grafi in memoria. | [CGGR]: cap 7. |
14/05/2013 | Grafi: visita in ampiezza e in profondità; classificazione degli archi. | [CGGR]: cap 7. |
14/05/2013 | Esercitazione: progettazione di algoritmi efficienti (dizionari e alberi). | Esercizi, soluzioni. |
15/05/2014 | Laboratorio: Tabelle Hash | Lucidi |
16/05/2014 | Ordinamento topologico di un grafo diretto aciclico (DAG): algoritmo e analisi. | [CGGR]: cap 7. |
20/05/2014 | Problemi indecidibili: il problema della fermata. Problemi intrattabili: le torri di Hanoi (algoritmo, analisi del numero di mosse); generazione delle stringhe binarie. | [CGGR] prologo. |
21/05/2014 | Generazione di tutte le permutazioni. Le classi di complessità P e EXP. Il certificato polinomiale e la classe NP. Nozione di Riduzione Polinomiale. Problemi NP-completi. Esempio di riduzione: SAT - Clique. | [CGGR] prologo, cap 8; Lucidi. |
21/05/2014 | Esercitazione: progettazione di algoritmi efficienti su grafi. | Esercizi e soluzioni |
22/05/2014 | Laboratorio: Simulazione prova d'esame | |
27/05/2014 | Esercitazione: certificati polinomiali e algoritmi di verifica. | |
28/05/2014 | Seconda prova di verifica intermedia. |