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 fondamentali per la risoluzione di problemi d base e i principi e le tecniche che permettono l'analisi sistematica degli algoritmi. L'obiettivo è fornire gli strumenti per progettare soluzioni algoritmiche corrette ed efficienti ed individuare, in presenza di varie alternative, la soluzione più adatta ad un problema.

Orario

Corso impartito nel periodo 27 settembre - 22 dicembre 2023.

Le lezioni si terranno mercoledì 14.00-17.00 in aula 2 e venerdì 9.00-13.00 in aula 6, presso la sede di Latina, in via A. Doria 3.

Svolgimento delle lezioni

Le lezioni si terranno in presenza.

Google Classroom

Per la comunicazione docente-studenti sarà utilizzata la piattaforma Google Classroom (codice registrazione: zg6ah6l).

Ricevimento studenti

Informazioni disponibili qui.

Programma d'esame

Riferimenti bibligrafici:

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

Pubblicate durante il corso.

Esercitazioni

Durante il corso saranno assegnati, tramite Classroom, degli esercizi di programmazione finalizzati alla comprensione degli argomenti trattati e propedeutici alla realizzazione del progetto finale. Gli esercizi non saranno oggetto di valutazione ma ne è fortemente incoraggiato lo svolgimento. Su richiesta, gli esercizi saranno discussi in orario di ricevimento.

Diario delle Lezioni

Settimana Mercoledì Venerdì
25/09-01/10/2023 Introduzione al corso. Introduzione agli algoritmi e loro costo. Numeri di Fibonacci.
[Slide e appunti]. [T1] 1.1-1.4
 Notazione asintotica O-grande, Omega-grande, Theta-grande. Esempi. Teorema sull'andamento asintotico di un polinomio con dimostrazione. Esercizi sulla notazione asintotica. Limitazione inferiore e superiore al costo di un algoritmo. Metodi di analisi (caso peggiore, caso migliore, caso medio).
[Slide e appunti]. [T1] 1.5 - 1.7, 1.10, 2.1 - 2.4
02-08/10/2023 Introduzione ai tipi di dato astratti. Il tipo di dato astratto Dizionario. I tipi di dato astratti Pila e Coda. Tecniche di rappresentazione dei dati: indicizzata e collegata. Implementazione con rappresentazione indicizzata e collegata di Dizionario.
[Slide e appunti]. [T1] 3.1, 3.2
 Implementazione con rappresentazione indicizzata e collegata di Pila e Coda. Introduzione al tipo di dato Albero. Rappresentazioni indicizzate di alberi: vettore dei padri; vettore posizionale. Rappresentazioni collegate di alberi: lista di figli.
[Slide e appunti]. [T1] 3.3, fino a 3.3.3 escluso.
9-15/10/2023 Lezione cancellata. Visite di alberi: algoritmo di visita generica, con dimostrazione di terminazione, costo e correttezza. Visite di alberi (descrizione, pseudocodice, analisi) in profondità iterativa e ricorsiva, in ampiezza. Conteggio del numero dei nodi di un albero (soluzione ricorsiva).
Il problema dell'ordinamento. L'approccio incrementale. Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): SelectionSort, InsertionSort, BubbleSort.
[Slide e appunti] [T1] 3.3.3, 4.2.
16-22/10/2023 Introduzione a Heapsort. Soluzione di equazioni di ricorrenza: metodo dell'albero della ricorsione, Implementazione in C delle funzioni per il calcolo dei numeri di Fibonacci. metodo dell'iterazione, metodo della sostituzione. Principio di induzione matematica ed esempio di applicazione (formula di Gauss per la somma di interi).
[Slide e appunti]. [T1] 2.3 - 2.5.2.
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): HeapSort. Algoritmi con approccio divide et impera (descrizione, pseudocodice, analisi): MergeSort, QuickSort (senza dimostrazione complessità caso medio). Dimostrazione del lower bound per ordinamento basato su confronti.
[Slide e appunti] [T1] 4.1-4.5
23-29/10/2023 Lezione registrata:
  • Realizzazione in C del tipo Pila con rappresentazione indicizzata: Video, Codice
  • Realizzazione in C del tipo Coda con rappresentazione collegata: Video, Codice
  • Realizzazione in C del tipo Albero con rappresentazione collegata (liste dei figli): Video, Codice
Lezione registrata (Video): Il problema della ricerca. Alberi binari di ricerca (BST): ricerca, inserimento, cancellazione.

[Slide e appunti] [T1] 6.1.
30/10-05/11/2023 Festa. Alberi AVL: definizione, analisi della profondità (con dimostrazione), rotazioni. Alberi AVL: inserimento e cancellazione; costo delle operazioni.
[Slide e appunti] [T1] 6.1-6.2.
6-12/11/2023 Esercizi d'esame su implementazione di funzioni ricorsive, algoritmi di ordinamento e alberi AVL.

 Hash table: introduzione, generalità, esempi, uniformità semplice. Risoluzione delle collisioni mediante liste di collisione e indirizzamento aperto; scansione lineare e hashing doppio.
Esercizio d'esame: Progetto e analisi di funzione ricorsiva per la verifica di unicità della chiave di tutti i nodi in un albero binario.
[Slide e appunti] [T1] Cap. 7
13-19/11/2023 Hash table: analisi del costo delle operazioni nel caso peggiore e nel caso medio. Grafi: generalità e nozioni preliminari. Strutture dati per la rappresentazione di grafi (e costo delle operazioni comuni): liste di archi, liste di adiacenza, matrice di adiacenza.
[Slide e appunti] [T1] 11.1 - 11.2 (escluso)
Esercizi su notazione O-grande, equazioni di ricorrenza, algoritmi ricorsivi, ordinamento, Alberi AVL.
20-26/11/2023 Prova Intermedia. Algoritmi per la visita di grafi e analisi del costo: generica, in ampiezza, in profondità (iterativo e ricorsivo). La relazione di raggiungibilità. Componenti connesse di un grafo non orientato e loro calcolo. Visita di grafi non connessi.
[Slide e appunti] [T1] Cap.11, fino a 11.4 incluso.
27/11-3/12/2023 Componenti fortemente connesse di un grafo orientato e loro calcolo. Visita di grafi non fortemente connessi. Minimo albero ricoprente, definizione e proprietà. Regola del ciclo. Regola del taglio.
[Slide e appunti] [T1] 11.5, fino a 11.5.2 escluso). Cap. 12, fino a 12.2 (escluso Th. 12.1).
Algoritmo generico per la costruzione del minimo albero ricoprente (descrizione, dimostrazione di terminazione e correttezza). Algoritmi per il calcolo del minimo albero ricoprente (descrizione e costo, con e senza ottimizzazione): algoritmi di Kruskal, Prim, Borůvka.
[Slide e appunti] [T1] Cap. 12, da Th. 12.1 a 12.4, esclusi 12.2.1 e 12.3.1.
4-10/12/2023 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. Tecnica del rilassamento. Algoritmo di Bellman e Ford per il calcolo delle distanze (descrizione e analisi).
[Slide e appunti] [T1] Cap. 13, fino a 13.3 incluso.
 Festa.
11-17/12/2023 Ordinamento topologico: definizione e algoritmo per il calcolo (descrizione e analisi). Algoritmo per il calcolo delle distanze in grafi diretti aciclici (descrizione e analisi).
[Slide e appunti] [T1] 13.4.
 Algoritmo di Dijkstra (descrizione e analisi). Esercizi d'esame. Fine corso. [T1] 13.5, fino a 13.5.1 escluso.

Esami

Modalità d'esame

L'esame prevede per tutti (indipendentemente dall'anno di iscrizione):

Le date degli appelli sono indicate in fondo alla pagina (non appena disponibili).

Progetto

Istruzioni per la consegna del progetto (in caso di problemi con il sistema di assegnazione, contattare il docente).

Le date per la discussione del progetto sono indicate insieme agli appelli d'esame.

Prova intermedia

È prevista una prova scritta intermedia (facoltativa) che consiste in due esercizi da svolgere in un'ora. Il voto ottenuto nella prova intermedia è valido per l'intero anno accademico (fino all'appello straordinario di ottobre 2024). In caso di superamento della prova intermedia (voto maggiore o uguale a 18) si può decidere, in ogni appello, di svolgere solo gli ultimi due esercizi della prova scritta (in un'ora di tempo); in tal caso, il voto finale della prova scritta è ottenuto come media del voto ottenuto nelle due prove.

Appelli d'esame