Docente: Linda Pagli
Impegno: 12 CFU di cui 9 teoria/esercitazioni e 3 Laboratorio.
Semestre: secondo.
Ricevimento studenti: dopo ogni lezione e su appuntamento.
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.
Orario delle Lezioni | |||
---|---|---|---|
Martedì | 14-16 | A | Teoria |
Mercoledì | 9-11 | A | Teoria |
Giovedì | 16-18 | 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 |
---|---|---|---|
07/06/2012, ore 09.30 | Scritto | algo1_07062012.pdf | lista dei risultati. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà Mercoledì 13 Giugno alle ore 9 nelle aule H e M; è possibile anche sostenere la prova in altro appello. L'orale sarà il 22 Giugno, alle ore 10 (studio Pagli) |
13/06/2012, ore 09.00 | Laboratorio | Testo e input | |
26/06/2012, ore 14.30 | Scritto | algo1_26062012.pdf | lista dei risultati. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà Venerdì 29 Giugno alle ore 9:30 nelle aule H e M. Chi non ha superato lo scritto non è ammesso alla prova di laboratorio. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. L'orale sarà il 6 luglio alle ore 10 (studio Pagli). Un numero limitato di studenti potrà sostenere l'orale venerdì alle 11 subito dopo la prova di laboratorio, sempre nell'ufficio Pagli. |
29/06/2012, ore 09.30 | Laboratorio | Testo e input | |
11/07/2012, ore 09.30 | Scritto | algo1_11072012.pdf | lista dei risultati. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà venerdì 13 luglio alle ore 9:00 nelle aule H e M. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per venerdì 13 dopo la prova di laboratorio oppure il 19 luglio alle 10 ufficio Pagli. |
13/07/2012, ore 09.00 | Laboratorio | Testo e input | |
11/09/2012, ore 15 | Scritto | algo1_11092012.pdf | lista dei risultati. Coloro che hanno superato lo scritto devono sostenere la prova di laboratorio. Tale prova si svolgerà il 13 settembre alle ore 9:30 nelle aule H e M. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per il 13 alle 15 oppure il 21 settembre alle 10 ufficio Pagli. |
13/09/2012, ore 09.30 | Laboratorio | Testo e input | |
15/01/2013, ore 9.30 | Scrittoalgo1_150113.pdf | risalg15-01-2013.pdf | Coloro che hanno superato lo scritto con un voto ≥16, possono sostenere la prova di laboratorio. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per il giorno 23 gennaio alle 9.30 nell'ufficio Pagli oppure il 5 febbraio alle 10 (aula A). |
18/01/2013, ore 09.30 | Laboratorio | Testo e input | |
5/02/2013, ore 9.30 | Scrittoalgo1_050213.pdf | risalg5-02-2013.pdf | Coloro che hanno superato lo scritto con un voto ≥17, possono sostenere la prova di laboratorio. Coloro che hanno superato scritto e laboratorio sono ammessi all'orale. Le prove orali sono fissate per il giorno 11 febbraio alle 9.30 oppure il 14 febbraio alle 9.30 nell'ufficio Pagli. |
08/02/2013, ore 09.30 | Laboratorio | Testo |
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 |
---|---|---|
21/02/2012 | Introduzione al corso. Moltiplicazione Egizia. Nozioni di Algoritmo, Problema, Limite Inferiore. Analisi di un problema semiserio | appunti |
22/02/2012 | Definizioni: problema, istanza, dimensione. Problemi indecidibili, il problema della fermata. Problemi intrattabili: le torri di Hanoi, algoritmo, analisi del numero di mosse. Crescita esponenziale. | Libro [CGG] cap.1 |
23/02/2012 | Laboratorio: Editing e compilazione. Richiami di linguaggio C: Istruzioni varie e operatori, array, printf e scanf. | Cap. 2-3, 7.1-7.4 di [KR]. Lucidi |
24/02/2012 | Laboratorio: Ripasso e esercizi su funzioni e puntatori. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi Soluzioni |
28/02/2012 | Definizione classi P, NP, NP-completi, EXPTIME. Esempio di problema in NP: il Sudoku, algoritmo esponenziale. Il certificato polinomiale. | Libro [CGG] cap.1 |
29/02/2012 | Nozione di Riduzione Polinomiale. Esempi di problemi NPC: Problema SAT, Ciclo Hamiltoniano, k-clique. Esempio di riduzione: SAT - k-Clique. | Una riduzione (K-clique). |
01/03/2012 | Laboratorio: Puntatori, funzioni e passaggio parametri. | Sez. 4.1-4.5 e 5.1-5.5 di [KR]. Lucidi Soluzioni |
02/03/2012 | Laboratorio: Allocazione dinamica della memoria (malloc) e stringhe. | Lucidi Soluzioni |
06/03/2012 | 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. Considerazioni genrali su algortimi ricorsivi. | Libro [CGG] cap.1 |
07/03/2012 | Il modello RAM. Selection Sort e Insertion Sort: proprietà e complessità. Valutazione complessità asintotica al caso ottimo e pessimo. | Formule utili |
08/03/2012 | Laboratorio: Sottoarray di somma massima. Redirezione dell'input e timing di un programma. | Lucidi TestFile Soluzioni Libro [CGG] Sez.2.3 |
09/03/2012 | Limiti inferiori: tecnica della dimensione dell'input, tecnica dell'albero delle decisioni e dell'oracolo. Esempi: primo e secondo, ordinamento. Algoritmo del torneo e del doppio torneo. | limiti inferiori |
13/03/2012 | Il problema della ricerca: limite inferiore, ricerca binaria iterativa e ricorsiva, rango. Analisi. Equazioni di ricorrenza. Paradigma Divide et Impera. | Libro [CGG] Sez.2.4 e 2.5 |
14/03/2012 | Equazioni di ricorrenza; Teorema principale; Esempi di applicazioni del teorema. | ricorrenze |
15/03/2012 | Laboratorio: Insertion Sort su interi e stringhe. Ricerca Binaria. L'intero mancante. | Lucidi Esercizi Soluzioni |
16/03/2012 | Moltiplicazione rapida, analisi. Un algoritmo ottimo di ordinamento di tipo Divide et Impera: MergeSort. | Libro [CGG] Sez.2.5.2 e 2.5.3 |
20/03/2012 | Moltiplicazione rapida di matrici, analisi. Esercizi su algortimi ricorsivi di tipo Divide et Impera e calcolo della complessità. | Libro [CGG] Sez.2.6.1 |
21/03/2012 | Ordinamento per distribuzione, Quick Sort, analisi del caso medio su istanze equiprobabili. Equazioni di ricorrenza non bilanciate, Quick Select per la selezione del k-esimo elemento. | Libro [CGG] Sez.2.5.4 + Errata corrige del paragrafo |
22/03/2012 | Laboratorio: Quick Sort su interi e su stringhe. Varianti (pari&dispari, 3-way partition). La scala e cavalli. | Esercizi Quicksort parziale La scala testfile Soluzioni |
23/03/2012 | Code di priorità. Definizione di Heap, operazioni Enqueue, Dequeue e Read per un Heap di massimo, Complessità. Allocazione implicita in array. Riorganizza Heap. | Libro [CGG] Sez.8.1 e 8.2 |
27/03/2012 | Code di priorità. Creazione dell'Heap in tempo lineare, Heap Sort, analisi. Introduzione alla Programmazioen Dinamica | Libro [CGG] Sez.8.2.3 Programmazione Dinamica |
28/03/2012 | Algoritmi di programmazione dinamica per l'Edit Distance e la Longest Common Subsequence. Analisi e ricostruzione delle soluzioni | Libro [CGG] Sez.2.7 e 2.7.1 |
29/03/2012 | Laboratorio: Funzione qsort. Esercizi su stringhe e diversi ordinamenti. Il pirellone. | Lucidi Esercizi Soluzioni |
30/03/2012 | Esercitazione scritta. Discussione e soluzione durante la lezione del 17/4. | esercitazione_scritta |
12/04/2012 | Laboratorio: Esercizi con le struct e qsort. Elemento maggioritario e due uova. | Lucidi Esercizi Soluzioni |
13/04/2012 | Counting Sort e Radix Sort. | [CLR] cap. 8 |
17/04/2012 | Esercitazione. Discussione e soluzione della esercitazione scritta del 12/04/2012 | |
18/04/2012 | Programmazione dinamica per problemi difficili: Partizione e Zaino. Pseudopolinomialità. | Libro [CGG] Sez.2.7.2, 2.7.3 e 2.7.4 |
19/04/2012 | Laboratorio: Esercizi liste. Ciclo in una lista. | Lucidi Esercizi Soluzioni |
20/04/2012 | Definizione di problemi NP-hard. Riduzione polinomiale da Partizione a Zaino. Algoritmo di programmazione dinamica per Zaino. Introduzione alle strutture con puntatori: liste e alberi. | Libro [CGG] Sez. 9.1 e 9.2.4 |
24/04/2012 | Trasformazione da albero ordinato a albero binario. Allocazione in memoria di alberi binari. Alberi binari di ricerca e operazioni del dizionario | Libro [CGG] Sez. 4.1 e 4.3 e 4.3.1 Sez 5.1, 5.2, 5.4.1 |
26/04/2012 | Laboratorio: Esercizi alberi binari di ricerca. Orco e hobbit. | Lucidi Esercizi Soluzioni |
27/04/2012 | Alberi binari di ricerca bilanciati in altezza. Alberi AVL, alberi di Fibonacci come caso pessimo. Altezza logaritmica degli AVL. Operazione di inserzione, rotazioni semplice e doppia. | Libro [CGG] Sez. 5.4.2 La formula di Binet |
02/05/2012 | Alberi AVL: cancellazione. Tabelle hash, funzioni hash, organizzazione con liste di trabocco, analisi. Open hash: scansione lineare, agglomerati. | Libro [CGG] Sez. 5.3, 5.3.1 |
03/05/2012 | Laboratorio: Esercizi Tabelle Hash. Griglia infetta. | Lucidi Esercizi |
04/05/2012 | Tabelle hash, indirizzamento aperto, scansione lineare: analisi, fenomeno degli agglomerati. Scansione quadratica, Doppio hash. Esempio. | Libro [CGG] Sez. 5.3.2 |
08/05/2012 | Esercitazione su alberi binari. | |
09/05/2012 | Grafi: Definizioni e rappresentazione con matrice di adiacenza e liste di adiacenza | Libro [CGG] Sez. 6.1.1, 6.1.2 |
10/05/2012 | Laboratorio: Simulazione di una prova di esame. | Esercizio |
11/05/2012 | Grafi: Visita BFS, albero BFS, teorema dei cammini minimi; visita DFS, albero DFS e classificazione degli archi. | Libro [CGG] nuova edizione visite.pdf |
15/05/2012 | Grafi orientati aciclici: Ordinamento Topologico. Il problema del routing. Grafi pesati con pesi positivi: algoritmo di Dijstra per i cammini minimi. | Libro [CGG] Sez. 7.5.1, 8.3, 8.3.1 |
16/05/2012 | Algoritmo di Dijstra: esempio completo, dimostrazione di correttezza, analisi con implementazione di coda a Heap. | Libro [CGG] Sez. 8.3.2 e 8.2.2 |
17/05/2012 | Richiami sulle tabelle hash. Studio di una legge di scansione quadratica, eliminazione con spostamento nell'open hash a scansione lineare. Esempi di applicazioni delle tecniche di hashing. | |
18/05/2012 | Problema del minimo albero di copertura. Algortimo di Kruskal. Union-Find con liste disgiunte. | Libro [CGG] Sez. 8.4.1, 8.4.2 e 3.4.1 |
22/05/2012 | Problema del minimo albero di copertura. Algortimo di Jarnik-Prim, complessità, esempi. | Libro [CGG] Sez. 8.4.3 |
23/05/2012 | Esercitazione su grafi | |
24/05/2012 | Esercitazione di riepilogo |