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 fondamentiali 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 - 23 dicembre 2022

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

Svolgimento delle lezioni

Le lezioni si terranno in presenza presso la sede di Ingegneria di Latina, in via A. Doria, 3.

Tutte le informazioni riguardanti le procedure di accesso alle sedi Sapienza sono disponibili qui. Si segnala, in particolare, l'obbligo di indossare la mascherina all'interno dei locali.

Per garantire il tracciamento delle presenze, è obbligatoria la prenotazione Prodigit.

Google Classroom

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

Ricevimento studenti

Informazioni disponibili qui.

Programma preliminare


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ì
26/09-02/10/2022 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.
[Slide e appunti]. [T1] 1.5 - 1.7, 1.10, 2.1 - 2.2
03-09/10/2022 Limitazione inferiore e superiore al costo di un algoritmo. Metodi di analisi (caso peggiore, caso migliore, caso medio). Soluzione di equazioni di ricorrenza: metodo dell'albero della ricorsione, 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.
Soluzione di equazioni di ricorrenza: teorema Master (senza dimostrazione). Esempi di applicazione del teorema Master. Introduzione ai tipi di dato astratto. Il tipo di dato astratto Dizionario.
[Slide e appunti]. [T1] 2.5.3. Cap. 3 (Introduzione)
10-16/10/2022 I tipi di dato astratto Pila e Coda. Tecniche di rappresentazione dei dati. Implementazione con rappresentazione indicizzata e collegata di Dizionario, Pila e Coda. [Slide e appunti] [T1] 3.1.1, 3.1.2, 3.2
Introduzione al 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.
[Slide e appunti] [T1] 3.3, fino a 3.3.3.
17-23/10/2022 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). Realizzazione in C del tipo Albero con lista dei figli in rappresentazione collegata.
[Slide e appunti] [T1] 3.3.3
Il problema dell'ordinamento. L'approccio incrementale. Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): SelectionSort, InsertionSort, BubbleSort, introduzione a Heapsort.
[Slide e appunti] [T1] 4.2
24-30/10/2022 Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): HeapSort.
[Slide e appunti] [T1] 4.3
Algoritmi con approccio divide et impera (descrizione, pseudocodice, analisi): MergeSort, QuickSort. Dimostrazione del lower bound per ordinamento basato su confronti.
[Slide e appunti] [T1] 4.4, 4.5, 4.1
31-06/11/2022 Il problema della ricerca. Alberi binari di ricerca (BST): ricerca, inserimento, cancellazione.
Introduzione agli alberi AVL: definizione.
[Slide e appunti] [T1] 6.1.
Alberi AVL: analisi della profondità (con dimostrazione), rotazioni.
[Slide e appunti] [T1] 6.2.1, 6.2.2
8-14/11/2021 Alberi AVL: inserimento e cancellazione; costo delle operazioni. Tabelle ad accesso diretto. Introduzione alle hash table: generalità, esempi.
[Slide e appunti] [T1] 6.2.3, 7.1, 7.2
Esercizi sugli alberi AVL.
Esercizi d'esame su notazione O-grande, equazioni di ricorrenza, algoritmi ricorsivi, ordinamento, costo di MergeSort.
15-21/11/2021 Prova Intermedia. Hash table: uniformità semplice, collisioni; risoluzione delle collisioni mediante liste di collisione e indirizzamento aperto; scansione lineare e hashing doppio; costo nel caso peggiore e nel caso medio.
[Slide e appunti] [T1] 7.3.1, 7.3.2
21-27/11/2022 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. Algoritmo di visita generica (con costo).
[Slide e appunti] [T1] 11.1 - 11.3.1 (escluso)
Lezione cancellata.
29/11-5/12/2021 Algoritmi di visita di un grafo (con costo): in ampiezza, in profondità (iterativo e ricorsivo). La relazione di raggiungibilità
[Slide e appunti] [T1] 11.3.1 - 11.3.3.
Componenti connesse e fortemente connesse di un grafo; calcolo. Visita di grafi non connessi. Minimo albero ricoprente, definizione e proprietà.
[Slide e appunti] [T1] 11.4, 11.5 (fino a 11.5.2 escluso), 12.1.


Esami

Modalità d'esame

L'esame prevede (anche per gli iscritti fino all'A.A. 2019-2020 incluso):

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

Progetto

Le istruzioni per la consegna del progetto saranno rese disponibili al termine del corso

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