Algoritmi e strutture dati

Docente: Luciano Guala'

Comunicazioni

Il Problem set 2 Ŕ online!

05-01-2024 13:08

Cari, 

 

vi segnalo che abbiamo appena messo online il secondo Problem Set. La data di consegna è domenica 21 gennaio. Trovate tutte le istruzioni sulla pagina del corso, qui:

https://www.mat.uniroma2.it/~guala/ASDL_2023.htm

Buon lavoro!

L.


lezione di giovedý 30 novembre annullata!

28-11-2023 18:34

Cari, come vi ho comunicato a lezione la lezione di giovedì 30 novembre non si terrà. Ci vediamo martedì 5 dicembre. 


Il Problem set 1 Ŕ online!

19-11-2023 21:08
Cari, vi segnalo che abbiamo appena messo online il primo Problem Set. La data di consegna è lunedì 4 dicembre. Trovate tutte le istruzioni sulla pagina del corso, qui:
Buon lavoro!
L.

Si parte!

29-09-2023 12:06

Cari studenti, benvenuti al corso di Algoritmi e Strutture Dati! Sarà un corso impegnativo. Abbiamo molte cose da fare insieme e spero che troverete alcune di queste belle, oltre che utili.  

 

Troverete informazioni, materiale, comunicazioni e quant'altro alla pagina del corso:

https://www.mat.uniroma2.it/~guala/ASDL_2023.htm

 

Alcune registrazioni video delle lezioni tenute online durante il (brutto) periodo del Covid sono ancora disponibili su Teams al seguente canale. Chi è interessato può fare richiesta di partecipazione:

GUALA'-8067331-ALGORITMI_E_STRUTTURE_DATI

 

La prima lezione si svolgerà martedì 3 ottobre alle ore 14, in aula 3, edificio PP2. Ci vediamo lì.

L.


Lezioni

2411-01-2024

Correzione Problem Set 1.

2309-01-2024

Esercitazione 6. Esercizi di progettazione di algoritmi su grafi.

2219-12-2023

Esercitazione 5. Esercizi di progettazione di algoritmi su grafi.

2114-12-2023

Cammini minimi in grafi pesati. Il problema del calcolo dei cammini minimi a singola sorgente. Un algoritmo veloce quando il grafo ha pesi non negativi: l'algoritmo di Dijkstra.

2012-12-2023

Usi meno scontati della visita DFS. Catalogare per tipo gli archi del grafo. Individuare un ciclo in grafi diretti. Grafi diretti aciclici (DAG) e ordinamento topologico. Usare la visita DFS per trovare un ordinamento topologico di un DAG. Componenti fortemente connesse: un algoritmo lineare per calcolarle.

1907-12-2023

Strutture dati per rappresentare un grafo. Matrice di adiacenza e Liste di adiacenza. Visite di un grafo. Visita in ampiezza (BFS): cammini minimi da una sorgente. Visita in profondità (DFS): uscire da un labirinto.

1805-12-2023

I Grafi (diretti, non diretti, pesati). Nozioni preliminari. Cammini, distanze, diametro. Alberi. Grafi Euleriani. I grafi come linguaggio potente per descrivere scenari e problemi. Esempi di scenari/problematiche descrivibili come grafi/problemi su grafi (reti stradali/di trasporto, reti sociali, reti "delle dipendenze").

1728-11-2023

Il problema della Coda con priorità. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci e complessità ammortizzata.

1623-11-2023

Esercitazione 4. Progettare un algoritmo che, dato un vettore ordinato A[1:n] di n bit, trova il numero k di zero presenti in A. Algoritmo con complessità O(log n). Un miglior algoritmo con tempo O(log k). Progettare un algoritmo con complessità lineare che, dato un vettore A[1:n] di n bit, trova l’indice k tale che il numero di zeri in A[1:k] è uguale al numero di uni in A[k+1:n].

1521-11-2023

Il problema del Dizionario: secondo episodio. Alberi AVL: definizione ed esempi. Dimostrazione della delimitazione superiore dell’altezza di un albero AVL (che usa la nozione di albero di Fibonacci). Operazioni sugli alberi AVL: search, insert, delete.

1416-11-2023

Il problema del Dizionario. Alberi binari di ricerca. Definizione. Visita in ordine simmetrico di un BST. Ricerca, inserimento, cancellazione (ricerca del massimo, del minimo, del predecessore e del successore di un nodo).

1314-11-2023

Esercitazione 3. Esercitazione sulle visite di alberi. Progettazione di un algoritmo che, preso un albero con valori e colori (rosso e nero), trova il valore del cammino rosso di tipo nodo-radice di valore massimo. Altro esercizio: progettare un algoritmo che,  preso un albero e in intero h, restituisce il numero di nodi dell'albero di profondità almeno h. Altro esercizio: preso un albero binario con valori, calcola il numero di nodi per cui la somma dei valori degli antenati è uguale alla somma dei valori dei discendenti.

1209-11-2023

Strutture dati elementari: rappresentazioni indicizzate e rappresentazioni collegate. Implementazione di un dizionario con array ordinato/non ordinato e lista ordinata/non ordinata. Rappresentazioni di alberi. Algoritmi di visita di un albero: profondità versione iterativa, profondità versione ricorsiva (preordine, postordine, ordine simmetrico), ampiezza. Algoritmo per calcolare l’altezza di un albero.

1107-11-2023

Esercitazione 2. Primo esercizio: dato un array di n numeri unimodale, progettare un algoritmo con complessità o(n) che trova il massimo e uno con complessità o(n log n) che lo ordina. Secondo esercizio: dato un vettore A di n numeri, progettare un algoritmo che in tempo O(n) trova due indici i e j con i<j che massimizzano A[j]-A[i].

1002-11-2023

Esercitazione 1. Esercizio: dimostrare o confutare una relazione asintotica. Esercizio di progettazione di un algoritmo che, dato un vettore ordinato A di n interi distinti e un valore x, trova (se esistono) due elementi di A che sommano a x. Soluzione banale con complessità quadratica, soluzione di complessità O(n log n) e soluzione con tempo O(n).

931-10-2023

Ancora algoritmi di ordinamento non basati su confronti. Una variante dell'IntegerSort per ordinare n record con chiavi intere: BucketSort. Un algoritmo veloce per ordinare interi "grandi": il RadixSort. Discussione del seguente esercizio: dato un array di n interi compresi fra 1 e k, costruire in tempo O(n+k) un oracolo (struttura dati) che sia in grado di rispondere in tempo costante a domande del tipo "quanti interi nell'array sono compresi fra a e b?"(Esercizio e soluzioni a fine delle slide sull'IntegerSort).

826-10-2023

Delimitazioni superiori e inferiori di algoritmi e problemi. Un lower bound alla complessità temporale necessaria per ordinare n elementi (per una classe di algoritmi ragionevoli, quelli basati su confronti). Un algoritmo veloce per ordinare interi “piccoli”: IntegerSort.

724-10-2023

Progettare algoritmi efficienti attraverso la progettazione di strutture dati efficienti. Un esempio: l'HeapSort - che ordina in loco n elementi in tempo O(n log n) nel caso peggiore.

619-10-2023

Il Problema dell’ordinamento. Un algoritmo semplice ma inefficiente: il Selection Sort. Un algoritmo migliore: il MergeSort. Un altro algoritmo che usa la tecnica divide et impera: il QuickSort: analisi del caso peggiore, migliore, e intuizioni sul caso medio. Discussione versione randomizzata del QuickSort e differenza fra complessità nel caso medio e tempo atteso di un algoritmo randomizzato.

517-10-2023

Ancora sulle equazioni di ricorrenza. Metodo della sostituzione. Teorema Fondamentale delle Ricorrenze (Master). Semplici esempi. Quando non si può applicare. Metodo del cambiamento di variabile.

412-10-2023

Analisi della complessità nel caso medio: un esempio. Il problema della ricerca di un elemento in un insieme: ricerca sequenziale e ricerca binaria. Equazioni di ricorrenza. Metodo dell’iterazione. Metodo che usa l’albero della ricorsione.  

310-10-2023

Modello di calcolo RAM. Costi uniformi e logaritmici. Complessità caso peggiore e caso medio. Notazioni asintotiche: O-grande, Omega-grande, Theta. O-piccolo, Omega-piccolo. Definizioni e semplici esempi. Proprietà. Usare la notazione asintotica nelle analisi della complessità computazionale degli algoritmi.

205-10-2023

Il problema del calcolo dell’n-esimo numero di Fibonacci. Un algoritmo numerico e un algoritmo ricorsivo. Analisi della complessità temporale dell’algoritmo ricorsivo. Un algoritmo iterativo di complessità temporale O(n) e di complessità spaziale O(n) (Fibonacci3). Portare la memoria a O(1): Fibonacci4. Introduzione informale alla notazione asintotica. Algoritmo con complessità O(log n) per il calcolo dell’n-simo numero di Fibonacci. Discussione della complessità spaziale degli algoritmi ricorsivi Fibonacci2 e Fibonacci6.

103-10-2023

Introduzione al corso. Motivazioni e concetti fondamentali. Un primo esempio: il problema di trovare una moneta falsa (più pesante) fra n monete usando una bilancia a due piatti.


Materiale didattico

Informazioni

Anno accademico2023-2024
Crediti12
SettoreINF/01
Anno2
Semestre1-2
PropedeuticitàAnalisi Matematica. Matematica discreta. Programmazione dei calcolatori con laboratorio.

Programma

https://www.mat.uniroma2.it/~guala/ASDL_2023.htm


Testi di riferimento

https://www.mat.uniroma2.it/~guala/ASDL_2023.htm


Ricevimento studenti

https://www.mat.uniroma2.it/~guala/ASDL_2023.htm


Modalità di esame

https://www.mat.uniroma2.it/~guala/ASDL_2023.htm