SAPIENZA Università di Roma

Laurea in Ingegneria dell'Informazione - sede di Latina

Algoritmi e Strutture Dati (6 CFU)

Prof. Fabio Patrizi

Informazioni Generali

Il corso introduce gli algoritmi e le strutture dati utilizzate nella risoluzione di problemi fondamentali, presentando principi e tecniche che ne permettono l'analisi sistematica. L'obiettivo è fornire allo studente gli strumenti per progettare soluzioni algoritmiche corrette ed efficienti ed individuare, in presenza di varie alternative, la soluzione più adatta ad un problema.

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.

Programma d'esame

News

Materiale Didattico

Libro di Testo

[T1] C. Demetrescu, I. Finocchi, G. F. Italiano: Algoritmi e strutture dati, McGraw-Hill, seconda edizione (sito web)

Slides

Diario delle Lezioni

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. -

Esami

Modalità d'esame

L'esame consiste in una prova scritta della durata di 2h, che include esercizi e domande di teoria. Il numero complessivo dei quesiti varia tra 4 e 6, a seconda della difficoltà. Laddove il docente lo ritenesse necessario, potrà convocare gli studenti per una discussione dell'elaborato e per un'evenutale prova orale integrativa.

Appelli d'esame