Algoritmi e strutture dati

Docente: Luciano Guala'

Comunicazioni

POSTICIPO LEZIONE DI GIOVEDI 16

13-03-2023 09:48

Buongiorno, la lezione/esercitazione di Giovedi 16 Marzo di ASD (Mod 2), avrà inizio alle ore 15.30. Salvo imprevisti tecnici, la lezione si svolgerà in aula 3 PP2. Eventuali cambiamenti di aula saranno comunicati entro mercoledi 15.


lezione di oggi

09-03-2023 12:54

La lezione di oggi 09/03/2023 di ASD si terrà eccezionalmente in aula G2B


LINK CANALE TEAM DEL CORSO ASD

08-03-2023 12:14

si ricorda che e' necessario collegarsi e aggiornarsi sul canale teams del corso mediante le proprie credenziali di ateneo. Per richiedere la partecipazione al canale team del corso, bisogna connettersi a teams, e poi va richiesto l'inserimento al seguente canale:

 

https://teams.microsoft.com/l/team/19%3ace5ad504104c49adbf62270ec0f9ff96%40thread.tacv2/conversations?groupId=893851d1-5d30-42e5-9bde-3a2d5ede8a59&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

 

 


ASD MOD 2: problemi con videoproiezione

08-03-2023 11:45

In attesa che venga riparato il videoproiettore, si invitano gli studenti  di portare

portatile o tablet in classe nelle prossime lezioni per poter seguire le slides del professore.

 

 


ASD MOD II: SLIDES

08-03-2023 11:43

Le slides del modulo 2 sono ora disponibili su questa pagina del corso.


Lezioni

2416-01-2023

Correzione Problem Set 1.

2312-01-2023

Esercitazione 6. Esercizi di progettazione di algoritmi su grafi.

2209-01-2023

Esercitazione 5. Esercizi di progettazione di algoritmi su grafi.

2122-12-2022

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. 

2019-12-2022

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.

1915-12-2022

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.

1812-12-2022

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

1705-12-2022

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

1601-12-2022

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].

1528-11-2022

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.

1424-11-2022

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

1321-11-2022

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.

1217-11-2022

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.

1114-11-2022

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].

1010-11-2022

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

907-11-2022

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

803-11-2022

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

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.

620-10-2022

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

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.

413-10-2022

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

Modello di calcolo RAM. Costi uniformi e logaritmici. Complessità caso peggiore e 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.

206-10-2022

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

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

Slides del Modulo II

Informazioni

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

Programma

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

 

Tutte le informazioni ed il materiale  relativi al II modulo (Prof. Clementi) sono disponibili

sul canale team di ASD.

 

Le lezioni inizieranno mercoledi 8 marzo alle ore 9 in aula PP3.

 

Per informazioni di carattere didattico **non amministrativo** su ASD si prega di contattare i docenti via email.

 

LEZIONI SVOLTE:

 

ASD MOD 2 

Prof. Andrea CLEMENTI 

LIBRETTO DELLE LEZIONI DELL’ANNO ACCADEMICO 2022-23 

 

  1. 08-03-2023:  Introduzione al secondo modulo, rivisitazione dei concetti rigorosi di problemi computazionali, istanze, lunghezza di un’istanza. Approccio modulare dell’Algoritmica: tecniche generali per il progetto di algoritmi per problemi di ottimizzazione; tecniche generali di analisi degli algoritmi. Un primo esempio dell’Approccio: il problema Single-Source Shortest-Paths (SSSP); il Principio di Sub-Ottimalità dei Cammini Minimi; L’Algoritmo Greedy di Dijkstra (Prima Parte). 
  2. 09-03-2023: Descrizione completa dell’ Algoritmo di Dijkstra (DALG). Analisi della complessità con diverse strutture dati e dimostrazione dell’ottimalità. Riduzione non polinomiale al problema della visita in ampiezza su un grafo non pesato. Esempi. Introduzione al problema del Minimum Spanning Tree (MST). Definizione formale e sua rilevanza applicativa. Tre algoritmi basati su approcci GREEDY: descrizione informale ed esempi. 
  3. 15-03-2023: Dimostrazione di ottimalità dei tre approcci GREEDY: proprieta’ del taglio e del ciclo (con dimostrazione). Descrizione dell’algoritmo di visita di Prim e dell’Algoritmo di Kruskal. Dimostrazione di ottimalità dei due algoritmi. Esempi di esecuzione. Il problema dell’implementazione efficiente dell’algoritmo di Kruskal: strutture dati per operazioni di SET UNION&FIND. 
  4. 16-03-2023: Esercitazione su Shortest Paths et MST: verifica di appartenenza di un arco ad un MST ed altri esercizi. 
  5. 22-03-2023: IL problema del k-clustering. Definizione del Problema k-clustering, applicazioni. Algoritmo Greddy basato sul calcolo del MST. Dimostrazione di ottimalità dell’approccio MST. La struttura SET-UNION-FIND: definizione del problema, applicazioni. Soluzione mediante foreste.  
  6. 23-03-2023: La struttura QUICK-SET-UNION-FIND: definizione, implementazione mediante alberi ed indici. Bilanciamento. Analisi ammortizzata del costo di sequenze arbitrarie UNIONE, FIND, MAKE_SET. Problema INTERVAL SCHEDULING (IS): Introduzione ai problemi di Scheduling, definizione  formale del problema. Schema di approccio Greedy per IS. Analisi di vari criteri Greedy: controesempi. Il criterio Greedy Finish Time (FT). Analisi dell’algoritmo FT (Parte I). 
  7. 29-03-23: Analisi dell’algoritmo FT (Parte II): dimostrazione dell’Ottimalità di FT. Il problema INTERVAL PARTITIONING (IP). Introduzione e definizione formale. Esempi e rappresentazione grafica di soluzioni ammissibili. Ia funzione Depth(I): definizione e calcolo efficiente. Lower bound Depth(I) per l’ottimo. Un algoritmo greedy  G per IP. Implementazione di G ed analisi del tempo. Dimostrazione della correttezza di G (restituisce sempre una soluzione ammissibile). Dimostrazione dell’ottimalità di G mediante confronto con Depth(I). 
  8. 30-3-23: Il problema  MINIMIZING LATENESS (ML): motivazioni e definizione formale. Analisi e contro-esempi di approccio greedy. L’algoritmo greedy Deadline_First (DF). Analisi e dimostrazione della ottimalità di DF: struttura delle soluzioni ottime. Analisi delle inversioni. Analisi del tempo di DF. Considerazioni generali sulla tecnica greedy. L’esercizio 1 a p. 183 del libro. 
  9. 5-4-23: Svolgimento  dell’esercizio 1 a p. 183 del libro. Introduzione alla compressione dati. Il problema del Minimizing Average_Bit_Length (Min_ABL). Codici: definizioni ed esempi. Codifica e Decodifica efficiente. I Codici Prefissi: proprietà, efficienza, esempi. Equivalenza tra Codici Prefissi ed Alberi Binari. 

Testi di riferimento

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

 

Per il secondo modulo:

 

Tardos, Upfal:  Algorithm Design - Pearson, Addison-Wesley;  le Slides disponibili su Teams.


Ricevimento studenti

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

 

MOD_2: per appuntamento con il docente via email


Modalità di esame

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

 

ASD MOD_2: scritto ed orale