Docenti: Linda Pagli, Rossano Venturini
(Docenti corso B: Anna Bernasconi, Rossano Venturini )
Assistente: Andrea Farruggia
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ì | 11-13 | B | Teoria |
Mercoledì | 11-13 | B | Teoria |
Giovedì | 16-18 | 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 |
---|---|---|---|
02/04/2014, ore 09 | Primo Compitino | risprimocomp.pdf | |
02/04/2014, ore 09 | Secondo Compitino | risalg2-4-2014.pdf | |
28/05/2014, ore 09 | Appello Straordinario | ||
09/06/2014, ore 11.00 | Scritto | algo1_090614.pdf | |
08/07/2014, ore 9.00 | Scritto | algo1_08072014.pdf, Soluzioni | risalg8-7-2014.pdf |
08/09/2014, ore 9.30 | Scritto | algo1_08092014.pdf, Soluzioni | risalg8-9-2014.pdf |
04/11/2014, ore 9.00 | Scritto | algo1_04112014.pdf | Risultati. Visione scritti: mercoledì 5 novembre, ore 9:30 nel mio ufficio. Orali: su appuntamento. |
14/01/2015, ore 9.00 | Scritto | algo1_14012015.pdf,algo140115sol.pdf | Risultati. Visione scritti: giovedì 15 gennaio, ore 11-13 ufficio Bernasconi. Orali: 22 gennaio ore 9.30 ufficio Pagli. |
12/02/2015, ore 9.00 | Scritto | algo1_12020215.pdf | Risultati. Visione scritti e Orali: 19 gennaio ore 11 ufficio Pagli. |
Prossime date per le prove di laboratorio:
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 | |
---|---|---|---|
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 | Concetto di algoritmo, moltiplicazione Egizia e 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, 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 | Esempi di tasso di crescita asintotico. Array di dimensione variabile. Selection Sort, proprietà e complessità al caso ottimo, medio e pessimo. | [CGGR]: cap. 1. | |
04/03/2014 | InsertionSort, analisi e complessità. Limiti inferiori: tecnica della dimensione dell'input, tecnica degli eventi contabili, tecnica dell'albero delle decisioni. Esempi: algoritmo del torneo e del doppio torneo. | [CGGR]: cap. 1 limiti inferiori | |
05/03/2014 | Tecnica dell'oracolo per la determinazione del limite inferiore al problema del doppio torneo. Limite inferiore per il problema della ricerca, Ricerca Binaria Ricorsiva, Divide et impera. | [CGGR]: cap. 3 par.3.oracolo | |
06/03/2014 | Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. Puzzle: L'intero mancante | Lucidi | |
07/03/2014 | Ordinamento ottimo: MergeSort, algoritmo e analisi. Esecizi. | [CGGR]: cap. 3 par.1. | |
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à. Heap di massimo: definizione, proprietà e rappresentazione in memoria. Operazioni Enqueue e Dequeue. | [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 | |
21/03/2014 | Simulazione di Enqueue e Dequeue. HeapSort: definizione e analisi. | [CGGR]: cap 2. | |
25/04/2013 | 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). | ||
08/04/2014 | Esercitazione: Correzione del primo compitino | ||
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 | Alberi: definizioni algoritmi e visite. Algoritimi ricorsivi su alberi binari | [CGGR]: par.3.8 | |
15/04/2014 | Programmazione Dinamica, ricostruzione della soluzione dell'Edit Distance; Problema dell' Approximate String Matching e della LCS (Sottosequenza di Lunghezza Massima) | [CGGR]:cap 6. | |
16/04/2014 | Programmazione Dinamica: Partizione e Zaino. Complessità Pseudopolinomiale | [CGGR]:cap 6. | |
17/04/2014 | Laboratorio: Liste | Lucidi | |
30/04/2014 | Programmazione dinamica: Zaino. Dizionari: alberi binari di ricerca, operazioni di ricerca e inserzione. | [CGGR]:cap 6 e cap.4 | |
02/05/2014 | Alberi binari di ricerca; cancellazioni. Alberi bilanciati in altezza: alberi di Fibonacci, alberi AVL. Relazione logaritmica tra altezza e numero di nodi. Esempi di rotazioni | [CGGR]: cap.4 | |
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 soluzioni | |
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/2013 | 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. | [CGGR] prologo; [CGGR]: cap 8.kclique-_sat.pdf | |
21/05/2014 | Esercitazione: progettazione di algoritmi efficienti su grafi. | ||
22/05/2014 | Laboratorio: Simulazione prova d'esame | ||
27/05/2014 | Esercitazione: generazione di combinazioni e algoritmi di verifica. | ||
28/05/2014 | Seconda prova di verifica intermedia. |