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 23 settembre - 20 dicembre 2024. Le lezioni si terranno mercoledì 14.00-18.00 e venerdì 9.00-13.00 in aula 2, presso la sede di Latina in via A. Doria 3.

Svolgimento delle lezioni

Google Classroom

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

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ì
23-29/09/2024 Introduzione al corso. Introduzione agli algoritmi e loro costo. Numeri di Fibonacci.
[Slide e appunti]. [T1] 1.1-1.5. 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.
[Slide e appunti]. [T1] 2.1 - 2.3. Video
30/09-06/10/2024 Metodi di analisi (caso peggiore, caso migliore, caso medio). Soluzione di equazioni di ricorrenza: metodo 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 sequenziale iterativo.
[Slide e appunti]. [T1] 2.4 - 2.5 (fino a 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. Algoritmo di ricerca binario 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] 2.5.3, 3-3.1. Video
7-13/10/2024 Lezione cancellata. 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). Introduzione al tipo di dato Albero.
[Slide e appunti]. [T1] 3.2, 3.3, fino a 3.3.1 incluso. Video
14-20/10/2024 Rappresentazioni indicizzate di alberi: vettore dei padri; vettore posizionale. Rappresentazioni collegate di alberi: lista di figli. Visite di alberi: algoritmo di visita generica. Implementazione in C delle strutture dati per la modellazione del tipo Albero con rappresentazione collegata (Codice).
[Slide e appunti]. [T1] 3.3.1 - 3.3.3. Video 		Lezione registrata:
  • Realizzazione in C del tipo Pila con rappresentazione indicizzata: Video, Codice
  • Realizzazione in C del tipo Coda con rappresentazione collegata: Video, Codice
21-27/10/2024 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).
[Slide e appunti]. [T1] 3.3.3. Video
28/10-03/11/2024 Il problema dell'ordinamento. L'approccio incrementale. Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): SelectionSort, InsertionSort, BubbleSort, HeapSort (cenni). 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, fino a 4.5 (incluso), escluso 4.3. Video 		Festa.
4-10/11/2024 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 		Seminario su Intelligenza Artificiale
(ore 10.00, Sala Conferenze presso facoltà di Economia).
11-17/11/2024 Alberi AVL: rotazioni, inserimento e cancellazione; costo delle operazioni. Esercizi su alberi AVL.
[Slide e appunti] [T1] 6.1-6.2. Video 		Esercizi d'esame su implementazione di funzioni ricorsive, algoritmi di ordinamento, equazioni di ricorrenza, alberi AVL.
[Appunti]. Video
18-24/11/2024 Prova Intermedia. Correzione esercizi della prova intermedia. Video Esercizi di programmazione in C: implementazione dell'algoritmo QuickSort in loco; implementazione del tipo di dato astratto albero. Video
25/11-1/12/2024 Lezione online. Hash tables: introduzione, generalità, esempi, uniformità semplice. Risoluzione delle collisioni mediante liste di collisione. Costo delle operazioni nel caso peggiore e nel caso medio. Introduzione alla risoluzione delle collisioni mediante indirizzamento aperto.
[Slide e appunti] [T1] Cap. 7, fino a 7.3.1 incluso. Video 		Hash table: risoluzione delle collisioni mediante indirizzamento aperto; scansione lineare e hashing doppio. Costo della scasione nel caso medio per i metodi di scansione lineare e hashing doppio. Grafi: generalità e nozioni preliminari.
[Slide e appunti] [T1] 7.3.2; 11, 11.1. Video
2-8/12/2024 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 (incluso) Video 		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. Componenti fortemente connesse di un grafo orientato e loro calcolo. Visita di grafi non fortemente connessi. Implementazione del tipo di dato astratto Albero in rappresentazione con liste di adiacenza.
[Slide e appunti] [T1] 11.3 - 11.4 (incluso). Video
9-15/12/2024 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.
[Slide e appunti] [T1] 13 - 13.2 (incluso). Video 		Algoritmo di Bellman e Ford per il calcolo delle distanze (descrizione 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 (descrizione e analisi).
[Slide e appunti] [T1] 13.3 - 13.5.1 (escluso)
Video
16-22/12/2024 Strutture dati per la rappresentazione di grafi con archi pesati. Esercizi d'esame. Fine corso. [Slide e 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 (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 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