Algoritmi e strutture dati

Docenti: Andrea Clementi, Luciano Guala'

Comunicazioni

Settimana 11-15 ottobre: ancora aula magna!

10-10-2021 21:24

Cari, le lezioni di lunedì 11 e giovedì 14 ottobre si svolgeranno in aula magna (Gismondi). Faranno fede anche le prenotazioni relative all'aula 3PP2. Ci vediamo in classe. 


Si parte!

01-10-2021 13:23

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 divertenti, oltre che utili. 

Sarà per me particolarmente piacevole vedervi di persona, quest'anno, e spero che parteciperete per quanto più possibile alle lezioni in presenza. Ad ogni modo, le lezioni saranno erogate in modalità mista, per consentire anche a chi non riesce a venire in aula di seguire in remoto. Non sempre le aule sono attrezzate adeguatamente e la modalità mista è da un punto di vista tecnico più complicata. Faremo del nostro meglio.

 

La prima lezione si svolgerà lunedì 4 ottobre alle ore 11, in aula magna (aula Gismondi). Ricordatevi di prenotare un posto tramite il sistema delphi. 

La modalità remota sarà erogata attraverso una classe virtuale su Teams. Peraltro vi invito a richiedere la partecipazione alla seguente classe:

GUALA'-8067331-ALGORITMI_E_STRUTTURE_DATI

Chi riscontrasse problemi tecnici può scrivermi all'indirizzo 

guala@mat.uniroma2.it

 

Mi sembra sia tutto. Ci vediamo lunedì!

LG 


Lezioni

1702-12-2021

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

1629-11-2021

Esercitazione. 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) (Es. 8). 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] (Es. 9).  

1525-11-2021

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.

1422-11-2021

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

1318-11-2021

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 (Es 5). Altro esercizio: progettare un algoritmo che,  preso un albero e in intero h, restituisce il numero di nodi dell'albero di profondità almeno h (Es 6). 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 (Es. 7).

1215-11-2021

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.

1111-11-2021

Esercitazione. 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 (Es. 3). 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] (Es. 4).

1008-11-2021

Esercitazione. Esercizio: dimostrare o confutare una relazione asintotica (Es. 1). 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) (Es. 2). 

904-11-2021

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

828-10-2021

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.

725-10-2021

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.

621-10-2021

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.

518-10-2021

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.

414-10-2021

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.

311-10-2021

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

207-10-2021

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.

104-10-2021

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 accademico2021-2022
Crediti12
SettoreINF/01
Anno2
Semestre1-2
PropedeuticitàAnalisi Matematica. Matematica discreta. Programmazione dei calcolatori con laboratorio.

Programma

http://www.mat.uniroma2.it/~guala/ASDL_2021.htm


Testi di riferimento

http://www.mat.uniroma2.it/~guala/ASDL_2021.htm


Ricevimento studenti

http://www.mat.uniroma2.it/~guala/ASDL_2021.htm


Modalità di esame

http://www.mat.uniroma2.it/~guala/ASDL_2021.htm