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 di 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 22 settembre - 19 dicembre 2025. Le lezioni si terranno lunedì 10.00-14.00 e giovedì 15.00-18.00 in aula 4, presso la sede di Latina in via A. Doria 3.

Google Classroom

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

Ricevimento studenti

Informazioni disponibili qui.

Programma d'esame

Materiale Didattico

Libro di Testo

[T1] C. Demetrescu, I. Finocchi, G. F. Italiano: Algoritmi e strutture dati, McGraw-Hill, Terza Edizione. 2025.

Slides

Pubblicate durante il corso.

Riferimenti bibligrafici:

News

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.

Diario delle Lezioni

Settimana Lunedì Giovedì
22-28/09/2025 Lezione cancellata. Lezione cancellata.
29/09-05/10/2025 Introduzione al corso. Introduzione agli algoritmi e loro costo. Numeri di Fibonacci.
[Slide e appunti]. [T1] Cap 1. Video 		Modello a costi uniformi. Notazione asintotica O-grande, Omega-grande, Theta-grande. Esempi. Teorema sull'andamento asintotico di un polinomio. 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] 2.1 - 2.4. Video
6-12/10/2025 Soluzione di equazioni di ricorrenza: metodi dell'albero della ricorsione, dell'iterazione, della sostituzione. Principio di induzione matematica ed esempio di applicazione (formula di Gauss per la somma di interi). Esempi di applicazione dei tre metodi. Algoritmo di ricerca binaria ricorsivo.
[Slide e appunti]. [T1] 2.4 - 2.5.3 (escluso). Video 		Cenni all'approccio divide et impera. Soluzione di equazioni di ricorrenza: teorema Master (senza dimostrazione). Esempi di applicazione del teorema Master. Algoritmi di ricerca binaria iterativo e ricorsivo. Introduzione ai tipi di dato astratti. Il tipo di dato astratto Dizionario. Tecniche di rappresentazione dei dati: indicizzata e collegata. Implementazione con rappresentazione indicizzata e collegata di Dizionario.
[Slide e appunti]. [T1] 3 - 3.1 (incluso). Video
13-19/10/2025 I tipi di dato astratti Pila e Coda. Implementazione con rappresentazione indicizzata e collegata di Pila e Coda. Realizzazione in C del Dizionario con rappresentazione mediante SCL (Codice).
[Slide e appunti]. [T1] 3.2. Video della lezione
 		Il tipo di dato astratto Albero. Rappresentazioni indicizzate di alberi: vettore dei padri; vettore posizionale. Rappresentazioni collegate di alberi: puntatori ai figli, lista dei figli, primo figlio-fratello successivo.
[Slide e appunti]. [T1] 3, fino a 3.3.3 (escluso). Video
20-26/10/2025 Visite di alberi (descrizione, pseudocodice, analisi): generica, in profondità iterativa e ricorsiva, in ampiezza.
[Slide e appunti]. [T1] 3.3.3. Video 		Il problema dell'ordinamento. L'approccio incrementale. Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): SelectionSort, InsertionSort, BubbleSort. Conteggio del numero dei nodi di un albero (soluzione ricorsiva). Implementazione in C delle strutture dati per la modellazione del tipo Albero con rappresentazione collegata (Codice).
[Slide e appunti]. [T1] 4.2. Video
27/10-02/11/2025 Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): HeapSort.
[Slide e appunti] [T1] 4.3. Video 		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.4, 4.5, 4.1. Video
3-9/11/2025 Il problema della ricerca. Alberi binari di ricerca (BST): ricerca, inserimento, cancellazione. Alberi AVL: definizione, analisi della profondità (con dimostrazione).
[Slide e appunti] [T1] Cap. 6, fino a 6.2.2 (escluso) Video 		Alberi AVL: rotazioni, inserimento e cancellazione; costo delle operazioni. Esercizi su alberi AVL.
[Slide e appunti] [T1] 6.1-6.2. Video
10-16/11/2025 Esercizi d'esame su implementazione di funzioni ricorsive e alberi AVL.
[Appunti]. Video 		Esercizi d'esame su implementazione di funzioni ricorsive, alberi AVL, equazioni di ricorrenza e algoritmi di ricerca.
[Appunti]. Video non disponibile per malfunzionamento della rete.
17-23/11/2025 Prova Intermedia. Correzione esercizi della prova intermedia. Hash tables: introduzione, generalità, esempi, uniformità semplice. Risoluzione delle collisioni mediante liste di collisione.
[Slide e appunti] [T1] Cap. 7, fino a 7.3.1 incluso. Video della lezione
Video aggiuntivi su esercizi di programmazione in C:
24-30/11/2025 Hash tables: risoluzione delle collisioni mediante indirizzamento aperto; scansione lineare e hashing doppio. Costo della scansione nel caso medio per i metodi di scansione lineare e hashing doppio. Esercizi sulle hash tables.
[Slide e appunti] [T1] 7.3.2 Video 		Grafi: generalità e nozioni preliminari. Strutture dati per la rappresentazione di grafi (e costo delle operazioni comuni): liste di adiacenza, matrice di adiacenza. Algoritmo per la visita generica.
[Slide e appunti] [T1] Cap. 11, fino a 11.3.1 escluso. Video
1-7/12/2025 Algoritmi per la visita di grafi e analisi del costo: 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. Componenti fortemente connesse di un grafo orientato e loro calcolo. Visita di grafi non fortemente connessi.
[Slide e appunti] [T1] Da 11.3.1 a 11.5.1 incluso. Video 		Minimo albero ricoprente, definizione e proprietà. Regola del ciclo. Regola del taglio. Algoritmo generico per la costruzione del minimo albero ricoprente (descrizione). Algoritmi per il calcolo del minimo albero ricoprente (descrizione e costo): algoritmi di Kruskal, Prim, Borůvka.
[Slide e appunti] [T1] Cap. 12, esclusi 12.2.1 e 12.3.1.
Video
8-14/12/2025 Festa. (Lezione Online). 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-Ford per il calcolo delle distanze (descrizione e analisi). Esempio di applicazione dell'algoritmo.
[Slide e appunti] [T1] 13 - 13.3 (incluso).
15-21/12/2025 Ordinamento topologico: definizione e algoritmo per il calcolo (descrizione e analisi). Algoritmo di Bellman-Ford per il calcolo delle distanze in grafi diretti aciclici (descrizione e analisi). Algoritmo di Dijkstra (descrizione e analisi).
[Slide e appunti] [T1] 13.3 - 13.5.1 (escluso)
Video 		Esercizi d'esame. Fine corso.
[Appunti] Video

Esami

Modalità d'esame

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

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

Progetto

Istruzioni per la consegna del progetto.

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

Comunicati appena disponibili.