Docenti: Linda Pagli, Rossano Venturini, Giovanna Rosone, Andrea Farruggia
(Docenti corso B: Anna Bernasconi, Rossano Venturini, Nadia Pisanti, 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.
La lezione del giorno 15/05/2015 (esercitazione) è spostata al 14/05/2014 dalle 14 alle 16 in aula A
Orario delle Lezioni | |||
---|---|---|---|
Martedì | 14-16 | H, M | Laboratorio |
Mercoledì | 11-13 | A | Teoria |
Giovedì | 14-16 | A | Teoria |
Venerdì | 11-13 | A | Teoria |
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 12:00 alle 13:00, ufficio pagli. |
10/06/2015, ore 9:30 | Orali | ufficio pagli | |
12/06/2015, ore 9:30 | Scritto | testo e soluzioni | lista dei risultati| Visione scritti: martedì 16 giugno, dalle 11:00 alle 13:00, ufficio pagli. |
01/07/2015, ore 9:30 | Orali | ufficio pagli | |
03/07/2015, ore 9:30 | Scritto | testo e soluzioni | lista dei risultat Visione scritti: lunedì 6 luglio ore 11-12 ufficio Bernasconi |
14/07/2015, ore 9:30 | Orali | ufficio pagli | |
10/09/2015, ore 14:30 | Scritto | testo e soluzioni | lista dei risultati |
15/09/2015, ore 14:00 | Orali | ufficio pagli | |
11/01/2016, ore 9:00 | Scritto | testo e soluzioni | Risultati: nessun compito è risultato sufficiente. Visione scritti: su appuntamento. |
01/02/2016, ore 9:00 | Scritto | testo e soluzioni | Risultati:lista dei risultati Visione scritti: su appuntamento. |
08/02/2015, ore 10:00 | Orali | ufficio pagli |
Il secondo compitino è riservato solo agli studenti che hanno preso un voto ≥ 18 al primo compitino
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 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 | Concetto di algoritmo, moltiplicazione Egizia e problema delle 12 monete. | 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 | Paradigma del Divide et Impera. Merge: definizione, correttezza e complessità. Merge-Sort: definizione | [CLRS]: cap : 2.3 |
03/03/2015 | Merge-Sort: analisi. Selection sort: correttezza e analisi di complessità. Notazione asintotica: Theta, O-grande, Omega-grande, o-piccolo e w-piccolo. | [CLRS]: cap 3. |
04/03/2015 | Limite inferiore per il problema dell'ordinamento, esempio con 3 elementi, albero di decisione. Esercizi e esempi di notazioni asintotiche | [CLRS]: cap 3. Cap.8 sez.1 |
05/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 |
06/03/2015 | Il problema della ricerca. 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 |
10/03/2015 | Limiti inferiori: tecnica dell'oracolo o avversario, limite inferiore per la determinazione del primo e del secondo. Esercizi di ripasso | Esercizi1oracol.pdf |
11/03/2015 | Metodi di soluzione dell'equazioni di ricorrenza: metodo iterativo, albero di ricorsione, metodo dell'esperto. | [CLRS]: cap 4, sezioni da 4.4 a 4.6 |
12/03/2015 | Laboratorio: Sottoarray di somma massima, intersezione e fusione di array. | Lucidi |
13/03/2015 | Dimostrazione del teorema principale (solo per potenze esatte). Moltiplicazione veloce di interi. Esercizi. | 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 |
24/03/2015 | Heap: definizione, realizzazione implicita come array, proprietà. Code di priorità: definizione, operazioni, realizzazione mediante heap. | [CLRS] cap 6: 6.3, 6.4, 6.5. |
25/03/2015 | Nuove proprietà. Costruzione di un heap in tempo lineare: correttezza e analisi di complessità. | [CLRS] cap 6: 6.1, 6.2, 6.3. |
26/03/2015 | Laboratorio: Quick Sort su interi e su stringhe. Varianti pari&dispari e 3-way partition. | Lucidi QuickSortParziale Partizionamento |
27/03/2015 | HeapSort. Algoritmi di ordinamento: stabilità. Ordinamento di interi in tempo lineare: Counting sort | [CLRS] cap 8: 8.2. |
31/03/2015 | Radix Sort [CLRS] cap.8: 8.3. 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. | |
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 binari di ricerca: definizione, max, min, predecessore, successore, ordinamento. | [CLRS] cap 12: 12.1, 12.2. |
21/04/2015 | Alberi binari di ricerca: inserimento, cancellazione, costruzione e analisi. | [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. | [CLRS] cap 11: 11.4. Dispense Prof. Luccio. Esercizi su dizionari e alberi |
30/04/2015 | Laboratorio: Alberi | Lucidi |
5/05/2015 | Introduzione alla Programmazione Dinamica (calcolo dei numeri di Fibonacci). Il problema dell'“Edit Distance”, definizione, proprietà, regola ricorsiva e ricostruzione della soluzione | programmazione_dinamica edit_distance.pdf |
6/05/2015 | Il problema della sottosequenza comune più lunga (LCS): definizione, proprietà, regola ricorsiva, ricostruzione della soluzione | [CLRS] cap 15: 15.4. |
7/05/2015 | Laboratorio: Tabelle Hash. | Lucidi |
8/05/2015 | LCS: ottimalità della sottostruttura. Stampa LCS iterativo e ricorsivi. 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. | [CLRS] cap 16: 16.2, esercizio 16.2.2. pseudopolinomialità. |
13/05/2015 | Generazione delle sequenze binarie e algoritmo enumerativo per il problema dello Zaino. Introduzione ai grafi e BFS. | [CGGR]: generazione delle sequenze binarie, Esercizi sulla Programmazione Dinamica, [CLRS] cap 22: 22.1, 22.2. |
14/05/2015 | Esercitazione: coda implementata con array, visita in ampiezza di un albero binario, esercizi sulla Programmazione Dinamica | [CLRS] cap 10: 10.1.Soluzioni |
14/05/2015 | Laboratorio: Simulazione della prova di laboratorio. | |
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. | calcolabilità |
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. |