Docenti: Anna Bernasconi, Rossano Venturini
(Docenti corso A: Linda Pagli, Giuseppe Prencipe)
Assistente: Diego Ceccarelli
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ì | 9-11 | B | Teoria |
Mercoledì | 11-13 | B | Teoria |
Giovedì | 16-18 | 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 |
---|---|---|---|
03/04/2013, ore 11.00 | Scritto (primo compitino) | algo1_030413.pdf | |
30/05/2013, ore 9.00 | Scritto (secondo compitino) | algo1_300513sol.pdf | |
12/06/2013, ore 9.00 | Scritto | algo1_120613.pdf, soluzioni | |
12/07/2013, ore 9.00 | Scritto | algo1_120713.pdf | |
9/09/2013, ore 15.00 | Scritto | algo1_090913.pdf | |
4/11/2013, ore 14.00 | Scritto | algo1_041113.pdf | |
21/01/2014, ore 9.30 | Scritto | Testo e soluzioni | |
7/02/2014, ore 9.30 | Scritto | Testo |
Prossime date per le prove di laboratorio:
Data | Ora | Aule | Documento |
---|---|---|---|
11/06/2013 | 9:30 | H e M | Testo TestSet |
14/06/2013 | 9:30 | H e M | Testo TestSet |
16/07/2013 | 9:30 | H e M | Testo TestSet |
12/09/2013 | 9:30 | H e M | Testo |
08/11/2013 | 10:30 | H e M | Testo |
24/01/2014 | 9:30 | H e M | Testo |
11/02/2014 | 9:30 | H e M |
Prossime date per le prove orali:
Data | Ora | Aula |
---|---|---|
14/06/2013 | 9:30 | aula B |
19/06/2013 | 9:00 | aula A1 |
27/06/2013 | 9:30 | nel mio studio |
17/07/2013 | 9:00 | aula C1 |
13/09/2013 | 9:30 | aula C |
17/09/2013 | 9:30 | aula L1 |
27/01/2014 | 9:30 | nel mio studio |
13/02/2014 | 9:30 | nel mio studio |
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 AIL), per concentrarsi soltanto sugli aspetti di coding degli algoritmi.qsort
-based.Data | Argomento | Rif. Biblio |
---|---|---|
19/02/2013 | Introduzione al corso. Moltiplicazione Egizia. Nozioni di Algoritmo, Problema, Limite Inferiore. Analisi di un problema semiserio. | appunti |
20/02/2013 | Laboratorio: Editing e compilazione. Richiami di linguaggio C: Costrutti, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. Lucidi Sito Esercitazioni |
21/02/2013 | Laboratorio: Ripasso e esercizi su funzioni e puntatori. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi |
22/02/2013 | Problemi indecidibili, il problema della fermata. Problemi intrattabili: le torri di Hanoi, algoritmo, analisi del numero di mosse. Crescita esponenziale. | Lucidi; [CGGR] prologo; [CGG] cap. 1 |
27/02/2013 | Laboratorio: Funzioni e passaggio dei parametri. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi |
28/02/2013 | Laboratorio: Allocazione dinamica della memoria (malloc) e stringhe. | Lucidi |
01/03/2013 | Il metodo algoritmico (intervento di Pilu Crescenzi). Generalizzazione del problema delle Torri di Hanoi e crescita polinomiale. Algoritmi polinomiali. Le classi di problemi P ed EXP. | [CGGR] prologo; [CGG] cap. 1 |
05/03/2013 | Rappresentazione degli elementi di un insieme con vettore di appartenenza. Generazione di tutte le stringhe binarie, applicazione a PARTITION. Generazione di tutte le permutazioni, applicazione a HAMILTONIAN CYCLE. Esempi di certificati polinomiali. Il Sudoku. La classe NP. | [CGGR]: prologo; pag 185 e 211 (solo definizione di Partition e Hamiltonian Cycle) [CGG]: cap. 1; pag 75 e 207 (solo definizione di Partition e Hamiltonian Cycle) |
06/03/2013 | Il certificato polinomiale e la classe NP. Nozione di Riduzione Polinomiale. Problemi NP-completi. Il Problema SAT. Esempio di riduzione: SAT - Clique. | [CGGR]: prologo; [CGG]: cap. 1; Lucidi |
07/03/2013 | Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. | File di test per intersezione File di test per sottoarray di somma massima |
08/03/2013 | 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; [CGG]: cap. 1; Esercizi; Formule utili |
12/03/2013 | Array di dimensione variabile. Selection Sort e Insertion Sort: proprietà e complessità al caso ottimo, medio e pessimo. | [CGGR]: cap. 1; [CGG]: cap. 2; lavagna. |
13/03/2013 | Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero delle decisioni. Esempi: algoritmo del torneo e del doppio torneo, ordinamento per confronti, ricerca. | limiti inferiori; [CGGR]: pag. 56; [CGG]: pag 46; lavagna |
14/03/2013 | Laboratorio: Sottoarray di somma massima lineare, Insertion Sort su interi e stringhe, ricerca binaria su stringhe. | Lucidi sottoarray somma massima Lucidi Array Stringhe Puzzle: L'intero mancante |
15/03/2013 | Soluzione degli esercizi proposti: generazione di tutti i sottoinsiemi di k elementi. Algoritmo di soluzione e verifica della k-clique. Algoritmo per il problema della Subset-Sum. | Soluzioni |
19/03/2013 | Il problema della ricerca: ricerca binaria ricorsiva; Analisi. Paradigma Divide et Impera. Un algoritmo ottimo di ordinamento di tipo Divide et Impera: MergeSort. | [CGGR]: cap 3; [CGG]: cap. 2; lavagna |
20/03/2013 | Quicksort: proprietà e analisi della complessità nel caso ottimo e pessimo. Quicksort randomizzato: analisi al caso medio. | [CGGR]: cap 3 e cap 5; [CGG]: cap. 2; lavagna |
21/03/2013 | Laboratorio: Quick Sort su interi e su stringhe. Varianti (pari&dispari, 3-way partition). | Quicksort parziale Pseudocodice Distribuzione Puzzle: la scala e cavalli |
22/03/2013 | Relazioni di ricorrenza: Teorema principale (con dimostrazione) ed esempi di applicazione. | ricorrenze.pdf; lavagna; Esercizi |
26/03/2013 | Moltiplicazione veloce di interi e matrici. Esercitazione: progettazione di algoritmi e analisi di complessità. | [CGGR]: cap 3; [CGG]: cap. 2; lavagna |
27/03/2013 | Selezione dell'elemento di rango r in un array (QuickSelect). Esercitazione: progettazione di algoritmi e analisi di complessità. | [CGGR]: cap 3 e cap 5; [CGG]: cap. 2; lavagna |
28/03/2013 | Laboratorio: Qsort e ripasso delle struct | Lucidi qsort Lucidi struct Puzzle: Pirellone |
3/04/2013 | Prima prova di verifica intermedia. | |
9/04/2013 | Correzione della prima prova di verifica intermedia. Code con priorità, Heap come albero binario completo a sinistra, relazione tra numero di nodi e altezza. | [CGGR]: cap 2 ; [CGG]: cap. 8; lavagna |
10/04/2013 | Operazioni Enqueue, First, Dequeue per un Heap di massimo. Complessità. Allocazione implicita in array. HeapSort. | [CGGR]: cap 2 ; [CGG]: cap. 8; lavagna |
11/04/2013 | Laboratorio: Esercizi d'esame: qsort e struct | Puzzle: Elemento maggioritario |
12/04/2013 | Ordinamento di interi: Counting sort e Radix Sort. Introduzione alla Programmazione Dinamica. | [CLR] cap. 8; Programmazione dinamica (dispensa Prof. Luccio) ; [CGGR]: cap 6; [CGG]: cap 2; lavagna |
16/04/2013 | Programmazione Dinamica: Edit Distance, Longest Common Subsequence (introduzione al problema). | Programmazione dinamica (dispensa Prof. Luccio); [CGGR]: cap 6; [CGG]: cap 2; lavagna |
17/04/2013 | Programmazione Dinamica: Longest Common Subsequence, Partizione di un insieme di interi. | [CGGR]: cap 6; [CGG]: cap 2; lavagna |
18/04/2013 | Laboratorio: Liste | Lucidi Puzzle: Ciclo in una lista |
19/04/2013 | Programmazione Dinamica: Il problema dello Zaino. Pseudopolinomialità. Esercizi sulla programmazione dinamica. | [CGGR]: cap 6; [CGG]: cap 2; lavagna, Esercizi |
23/04/2013 | Alberi binari: visite, algoritmi ricorsivi su alberi binari. Alberi cardinali. Alberi ordinali: memorizzazione binarizzata. Dizionari. | [CGGR]: cap 1, cap 3, cap 4; [CGG]: cap 4, cap 5; lavagna |
24/04/2013 | Dizionari: realizzazione con alberi binari di ricerca. Alberi AVL: definizione, alberi di Fibonacci. | [CGGR]: cap 4; [CGG]: cap 5; lavagna |
26/04/2013 | Esercitazione: operazione DecreaseKey in un heap; simulazione di un algoritmo di programmazione dinamica per il problema dello Zaino. Progettazione di algoritmi di programmazione dinamica per problemi su scacchiera. | ese26-4-2012.pdf |
30/04/2013 | Alberi binari 1-bilanciati: dimostrazione di altezza logaritmica nel numero di nodi. Dizionari: realizzazione con alberi AVL (ricerca; inserimento: rotazioni; cancellazione: cenni). | [CGGR]: cap 4; [CGG]: cap 5; lavagna |
02/05/2013 | Laboratorio: Alberi | Lucidi Puzzle: Orco e Hobbit |
03/05/2013 | Esercitazione: progettazione di algoritmi efficienti su alberi binari, ABR e AVL. | Esercizi Alcune soluzioni |
07/05/2013 | Dizionari: funzioni hash, realizzazione del dizionario con tabelle hash con liste di trabocco e a indirizzamento aperto. | [CGGR]: cap 4; [CGG]: cap 5; lavagna |
08/05/2013 | Tabelle hash a indirizzamento aperto: analisi al caso medio; scansione lineare, quadratica, doppio hash. | [CGGR]: cap 4; [CGG]: cap 5; tabelle hash (dispensa Prof. Luccio); lavagna |
09/05/2013 | Laboratorio: Tabelle Hash | Lucidi Puzzle: Griglia infetta |
10/05/2013 | Grafi: definizioni, rappresentazione di grafi in memoria; visita in ampiezza. | [CGGR]: cap 7; [CGG]: cap 6; lavagna |
14/05/2013 | Visita in ampiezza di un grafo: analisi e proprietà. Visita in profondità. Ordinamento topologico di un grafo diretto aciclico. | [CGGR]: cap 7; [CGG]: cap 6; lavagna |
15/05/2013 | Ordinamento topologico di un DAG: algoritmo e analisi. Ricerca di cammini minimi su grafi pesati: algoritmo di Dijkstra. | [CGGR]: cap 7; [CGG]: cap 6,8; lavagna |
16/05/2013 | Laboratorio: Simulazione della prova di laboratorio | Testo Input Codice sottoposto |
17/05/2013 | Algoritmo di Dijkstra: simulazione, correttezza e analisi. | [CGGR]: cap 7; [CGG]: cap 8; lavagna |
21/05/2013 | Liste per insiemi disgiunti (Union-Find). Problema della ricerca del minimo albero di copertura: Algoritmo di Kruskal. | [CGGR]: cap 5, 7; [CGG]: cap 3, 8; lucidi; lavagna |
22/05/2013 | Esercitazione: progettazione di algoritmi efficienti su grafi. | lavagna |
23/05/2013 | Laboratorio: Lezione facoltativa su comandi da terminale in aula H dalle 14:00 alle 16:00 | |
24/05/2013 | Esercitazione di riepilogo. | lavagna |
30/05/2013 | Seconda prova di verifica intermedia. |