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 25 settembre 2018 al 19 dicembre 2018

Le lezioni si terranno martedì 14.00-17.00 e mercoledì 10.00-13.00 in aula 7, presso la sede di Latina, in via A. Doria 3

Ricevimento studenti: per appuntamento, inviare un'email.

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 Martedì Mercoledì
24-30/09/2018 Inizio corso. Introduzione agli algoritmi e loro costo. Numeri di Fibonacci.
[T1] 1.1-1.4 		Notazione asintotica O-grande, Omega-grande, Theta-grande. Esempi. Limitazione inferiore e superiore al costo di un algoritmo. Teorema sull'andamento asintotico di un polinomio con dimostrazione [Slide e appunti]. Esercizi sulla notazione asintotica [Slide e appunti].
[T1] 1.5 - 1.7, 1.10, 2.1 - 2.2, 2.3.
1-7/10/2018 Metodi di analisi (caso peggiore, caso migliore, caso medio). Ricerca sequenziale iterativa: descrizione e analisi. Ricerca binaria iterativa: descrizione e analisi. Soluzione di equazioni di ricorrenza: metodo dell'albero della ricorsionee e metodo della sostituzione. Principio di induzione matematica ed esempio di applicazione (formula di Gauss per la somma dei primi n interi) [Slide e appunti].
[T1] 2.4 - 2.5.1, 2.5.2. 		Strategia Divide et Impera. Soluzione di equazioni di ricorrenza: teorema Master con dimostrazione. Esempi di applicazione del teorema Master.
[T1] 2.5.3.
8-14/10/2018 Introduzione ai tipi di dato astratto. Il tipo di dato Dizionario, Pila e Coda. Tecniche di rappresentazione dei dati. Implementazioni indicizzate e collegate di Dizionario e Pila. [Slide e appunti]
[T1] Cap.3 fino a 3.2 incluso. 		Tipo di dato Albero. Rappresentazioni indicizzate di alberi: vettore dei padri; vettore posizionale. Rappresentazioni collegate di alberi: lista di figli; primo figlio e fratello successivo. Visite di alberi: algoritmo di visita generica, con dimostrazione di terminazione, costo e correttezza.
[T1] 3.3.3, "Visita in profondità" esclusa.
15-21/10/2018 Visite di alberi (descrizione, pseudocodice, analisi): in profondità iterativa e ricorsiva, in ampiezza. Il problema dell'ordinamento. L'approccio incrementale. Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): SelectionSort, InsertionSort, BubbleSort. Esercizi.
[T1] 3.3.3 da "Visita in profondità", 4.2. 		Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): HeapSort. Introduzione agli algoritmi con approccio divide ed impera: MergeSort. [T1] 4.3.
22-28/10/2018 Algoritmi con approccio divide ed impera (descrizione, pseudocodice, analisi): MergeSort, QuickSort.
[T1] 4.4 - 4.5. 		Dimostrazione del lower bound per ordinamento basato su confronti. Algoritmi di ordinamento di interi (descrizione, pseudocodice, analisi): IntegerSort, BucketSort, RadixSort.
[T1] 4.1, 4.6, 4.7.
29/10-04/11/2018 Lezione cancellata per allerta meteo. Il problema della ricerca. Alberi binari di ricerca (BST). Introduzione agli alberi AVL. Alberi AVL: analisi della profondità (dimostrazione).
[T1] 6.1, 6.2, fino a 6.2.1 escluso (dimostrazione su appunti e slide).
05-11/11/2018 Alberi AVL: rotazioni, ricerca, inserimento e cancellazione; analisi del costo delle operazioni.
[T1] 6.2.2 e 6.2.3.
12-18/11/2018 Tabelle ad accesso diretto. Introduzione alle tabelle hash: generalità, esempi, funzioni hash, uniformità semplice, collisioni.
[T1] 7.1, 7.2. 		Tabelle hash: risoluzione delle collisioni mediante liste di collisione e indirizzamento aperto; scansione lineare e hashing doppio; costo nel caso peggiore e nel caso medio.
[T1] 7.3.
19-25/11/2018 Grafi: generalità e 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.
[T1] 11.1 - 11.2. 		Grafi, algoritmi di visita: generico, in ampiezza, in profondità (iterativo e ricorsivo).
[T1] 11.3.
26/11 - 2/12/2018 La relazione di raggiungibilità, componenti connesse e fortemente connesse, calcolo delle componenti connesse e fortemente connesse. Visita di grafi non connessi. Minimo albero ricoprente, definizione e proprietà. Regola del ciclo. Regola del taglio. Algoritmo generico.
[T1] 11.4 - 11.5 (escluso 11.5.2). capitolo 12, fino a 12.2 (escluso). 		Dimostrazione di terminazione e correttezza dell'algoritmo generico per il calcolo del minimo albero ricoprente. 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.
3-9/12/2018 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.
[T1] capitolo 13, fino a 13.2. 		Algoritmo di Bellman e Ford per il calcolo delle distanze (descirizione e analisi). 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 (descrizioner e analisi).
[T1] capitolo 13, fino a 13.5 (escluso 13.5.1).
10-16/12/2018 Esercizi d'esame. Esercitazione al calcolatore.
17-23/12/2018 Esercizi d'esame. Fine corso. -

Esami

Modalità d'esame

L'esame consiste in una prova scritta della durata di 2 ore, 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 ritenga necessario, potrà convocare gli studenti per una discussione dell'elaborato e per un'evenutale prova orale integrativa.
È inoltre prevista una prova preliminare all'elaboratore, della durata di 2 ore, da svolgere in data unica. La partecipazione è opzionale; il voto ottenuto (massimo 6) sarà sommato al voto ottenuto nella prima prova d'esame sostenuta. È possibile beneficiare del voto della prova preliminare solo negli appelli dell'A.A. 2018/2019.

Appelli d'esame

Saranno pubblicati a breve. (Per registrarsi all'esame, consultare InfoStud in prossimità dell'appello d'interesse.)