Corso impartito dal 5 ottobre 2016 al 21 dicembre 2016
Le lezioni si terranno mercoledì e venerdì dalle 11.00 alle 13.00 in aula 10, presso la sede di Latina, in via A. Doria 3
Ricevimento studenti: Subito prima o dopo le lezioni, presso lo Studio 5 (sede di Latina). Inviare SEMPRE un'email, non più tardi del giorno precedente.
Settimana | Mercoledì | Venerdì |
---|---|---|
3-9/10/2016 | Introduzione agli algoritmi e loro costo. Numeri di Fibonacci. [T1] 1.1-1.4. Esercitazione autoguidata. | Notazione asintotica O-grande, Omega-grande, Theta-grande. Metodi di analisi. Ricerca sequenziale iterativa: descrizione e analisi. Ricerca binaria iterativa e ricorsiva: descrizione e analisi. Soluzione di equazioni di ricorrenza: metodo dell'iterazione. Esempi. [T1] 1.5 - 1.7, 1.10, 2.1 - 2.5.1. Esercitazione autoguidata. |
10-16/10/2016 | Soluzione di equazioni di ricorrenza: metodo della sostituzione. Strategia Divide et Impera. Soluzione di equazioni di ricorrenza: teorema Master (senza dimostrazione) e sue applicazioni. Esempi. Introduzione alle strutture dati elementari: il tipo di dato Dizionario. [T1] 2.5.2 - 2.5.3. Introduzione al Cap.3. | Strutture dati elementari: i tipi di dato Pila e Coda. Tecniche di rappresentazione dei dati: indicizzate e collegate; vantaggi e svantaggi. Rappresentazione collegata di alberi. Algoritmi di visita di alberi binari: generica, profondità, ampiezza (descrizione, implementazione, costo). [T1] Cap.3 escluso 3.3.1. Esercitazione autoguidata. |
17-23/10/2016 | Il problema dell'ordinamento. L'approccio incrementale. Algoritmi (descrizione, pseudocodice, analisi): SelectionSort, InsertionSort, BubbleSort, HeapSort. [T1] 4.2.2 - 4.3. | Esercitazione in laboratorio. |
24-30/10/2016 | Algoritmi incrementali (descrizione, pseudocodice, analisi): MergeSort, QuickSort. Dimostrazione del lower bound per ordinamento con modello di costi basato su confronti. Algoritmi di ordinamento lineari (descrizione, pseudocodice, analisi): IntegerSort. [T1] 4.1, 4.4, 4.5. | Algoritmi di ordinamento lineari (descrizione, pseudocodice, analisi): BucketSort, RadixSort. Il porblema della ricerca. Alberi binari di ricerca (BST). Introduzioni agli alberi AVL. [T1] 4.6, 4.7. 6.1. |
31-6/11/2016 | Esercitazione in laboratorio. | Alberi AVL: rotazioni, ricerca, inserimento e cancellazione; analisi del costo delle operazioni. Tabelle di hash: funzioni hash; collisioni, risoluzione delle collisioni mediante liste di collisione. [T1] 6.2. 7.1, 7.2, 7.3.1. |
7-13/11/2016 | Tabelle di hash: risoluzione delle collisioni mediante indirizzamento aperto; scansione lineare e hashing doppio. Grafi: generalità. [T1] 7.3.2, 11.1. | Grafi: nozioni preliminari. Strutture dati per la rappresentazione di grafi (e costo delle operazioni comuni): lista di archi; liste di adiacenza; liste di incidenza; matrice di adiacenza; matrice di incidenza. Algoritmo di visita generica di un grafo. [T1] 11.2, 11.3 (fino a 11.3.1). |
14-20/11/2016 |
Grafi, algoritmi di visita: generico, in ampiezza, in profondità (iterativo e ricorsivo).
La relazione di raggiungibilità, componenti connesse e fortemente connesse, calcolo
delle componenti connesse e fortemente connesse. Visita di grafi non connessi. [T1] 11.3 - 11.5 (escluso 11.5.2). |
Grafi: minimo albero ricoprente, definizione e proprietà. Regola del ciclo. Regola del taglio. Algoritmi per il calcolo del minimo albero ricoprente (descrizione e analisi di complessità): algoritmo di Kruskal; algoritmo di Prim; algoritmo di Borůvka. [T1] capitolo 12, esclusi 12.2.1 e 12.3.1. |
21-27/11/2016 | Lezione cancellata. | Cammini minimi. Definizione e proprietà. Distanza tra nodi. Algoritmo per il calcolo dei cammini minimi a partire dalle distanze tra i nodi (descrizione e analisi). Albero dei cammini minimi. Algoritmo di Bellman e Ford per il calcolo delle distanze (descirizione e analisi). [T1] capitolo 13, fino a 13.4. |
28/11 - 4/12/2016 | Lezione cancellata. | Lezione cancellata. |
5-11/12/2016 | Ordinamento topologico: definizione e algoritmo per il calcolo (descrizione e analisi). Algoritmo per il calcolo delle distanze in grafi diretti aciclici (descrizione e analisi). Algoritmo di Dijkstra. [T1] 13.4 e 13.5 (escluso 13.5.1). | Facoltà chiusa (ponte Immacolata) |
12-18/12/2016 | Esercitazione d'esame. | Esercitazione d'esame. |
19-21/12/2016 | Esercitazione (d'esame). Fine corso. | - |