Algoritmi e Strutture Dati 2
CdL Informatica - Univ. Roma Tor Vergata
AA 2022/2023
Homework
Orario lezioni
Mercoledì: 09:00 - 11:00 e Giovedì: 14:00 - 16:00 in Aula 5 Edificio PP2
-
5 ottobre 2022: Introduzione al corso, descrizione del programma di
massima. La tecnica Greedy. Esempio: Un algoritmo greedy per decidere
la soddisfacibilità delle formule di Horn ([1]: Cap. 5.3. Per un ripasso
sulla tecnica greedy si veda il Capitolo 4 in [4] o anche il Capitolo 13 in
[7]).
Esercizi.
-
6 ottobre 2022: La tecnica Divide et Impera. Esempio: l'algoritmo di Karatsuba per moltiplicare due interi. Cenni
all'algoritmo di Strassen per la moltiplicazione di matrici.
Richiami sulle relazioni di ricorrenza e sul Teorema Master. ([1]: Cap. 1.1, 2.1, 2.2, 2.5. Per
un ripasso sulla tecnica Divide et Impera si veda il Capitolo 5 in [4] o anche
i Capitoli 3 e 4 in [8]).
Esercizi.
-
12 ottobre 2022: La tecnica della Programmazione Dinamica. Esempi:
Un algoritmo per Chain matrix multiplication e un algoritmo per
Independent set su alberi. ([1]: Cap. 6.5, 6.7. Per
un ripasso sulla tecnica della Programmazione Dinamica si veda il Capitolo 6 in
[4] o anche i Capitoli 16 e 17 in [7]).
Esercizi.
-
13 ottobre 2022: La tecnica della Riduzione. Esempi: Un algoritmo
lineare per 2-SAT ottenuto tramite riduzione al problema di scomporre
un grafo diretto in componenti fortemente connesse e DAG delle componenti.
Richiami su grafi diretti, DAGs e topological sorting.
Introduzione al problema
Max Flow ([1]: Esercizio 3.28 - per approfondire si veda
anche [9] - e inizio Cap. 7.2).
Esercizi.
-
19 ottobre 2022: Esercitazione.
-
20 ottobre 2022: Reti di flusso e "grafo residuo". L'algoritmo di Ford e Fulkerson per il problema
Max-Flow: correttezza, terminazione e running time. ([1]: Cap.
7.2. Si veda anche [4]: Cap. 7.1 e 7.2).
Esercizi.
-
26 ottobre 2022:
Flusso massimo e taglio minimo: ottimalità dell'algoritmo di Ford e
Fulkerson. Cenni alla variante con capacity scaling per rendere
l'algoritmo polinomiale. ([4]: Cap. 7.2 e 7.3).
Esercizi.
-
27 ottobre 2022: Problemi computazionalmente difficili e come affrontarli:
1. Ricerca esaustiva intelligente. Le tecniche:
Backtracking e
Branch-and-bound.
Esempi: Un algoritmo per SAT e un algoritmo per TSP
([1]: Cap. 9.1).
Esercizi.
(Se vi dovesse venire in mente un'idea promettente per risolvere istanze di
SAT, considerate la possibilità di partecipare alla prossima
edizione di questo evento)
-
2 novembre 2022: Affrontare i problemi computazionalmente difficili: 2.
Algoritmi Approssimanti. Esempio: un algoritmo
2-approssimante per il problema k-clustering. Approssimazioni
arbitrariamente buone. Esempio: un FPTAS (Fully Polynomial-Time Approximation Scheme)
per il problema Knapsack ([1]: Cap. 9.2, [4]: Cap. 11.8).
Esercizi.
-
3 novembre 2022: Esercitazione.
-
9 novembre 2022:
Euristiche di ricerca locale.
Ricerca locale con fattore di approssimazione garantito. Esempio: Un algoritmo
approssimante per Max-Cut.
Cenni a
Simulated annealing.
([1]: Cap. 9.3, e [4]: Cap. 12.4).
Esercizi.
-
10 novembre 2022:
I problemi computazionalmente difficili come risorsa: I fondamenti della
crittografia a chiave pubblica, il protocollo di Diffie-Hellman per la generazione di una chiave condivisa e
il sistema di cifratura RSA. Firme
digitali. Cenni a One-time pad e cifrari a
blocchi.
([1]: Cap. 1.2 e 1.4).
Esercizi.
-
16 novembre 2022:
Introduzione agli algoritmi probabilistici.
Esempio: un algoritmo probabilistico per verificare il prodotto di matrici.
Spazi di probabilità, eventi disgiunti, eventi indipendenti, probabilità condizionate
([2]: Cap. 1.2, 1.3. Per un ripasso di probabilità dicreta si vedano, per esempio,
i primi due capitoli in [2]).
Esercizi.
-
17 novembre 2022: Variabili aleatorie e valore atteso: le distribuzioni
geometrica e binomiale. Valore atteso di una variabile aleatoria e
linearità. Esempi: Analisi di un semplice algoritmo 2-apx in
valore atteso per Max-Cut. Analisi del numero atteso di confronti
dell'algoritmo Random Quick Sort. ([2]: Cap. 2.4, 2.5).
Esercizi.
-
23 novembre 2022: Esercitazione.
-
24 novembre 2022: Test di primalità probabilistici polinomiali.
Il test di Fermat. Richiami di teoria elementare dei numeri:
numeri di Carmichael, radici non-banali dell'unità,
cenni al Teorema dei numeri primi. Il test di Miller-Rabin. ([1]: Cap. 1.3. Per approfondire si
veda [5]: Cap. 13.8).
Codice: primes.py.
Esercizi.
-
30 novembre 2022: Stime del discostamento di una variabile aleatoria dal
suo valore atteso. La disuguaglianza di Markov. La varianza di
una variabile aleatoria e la
disuguaglianza di Chebyshev. Somme di variabili aleatorie
indipendenti e le disuguaglianze di Chernoff ([2]: Cap. 3.1, 3.2, 3.3, 4.1,
4.2).
Esercizi.
-
1 dicembre 2022:
Il Metodo Probabilistico: il conteggio di base e il metodo del
valore atteso. Esempi. ([2]: Cap. 6.1, 6.2, 6.4).
Esercizi.
-
7 dicembre 2022:
Introduzione alle Catene di Markov. Analisi di
un algoritmo probabilistico per 2-SAT. ([2]: Cap. 7.1).
Esercizi.
-
14 dicembre 2022: Esercitazione.
-
15 dicembre 2022:
Analisi di un algoritmo probabilistico per 3-SAT con running time
O((4/3)npoly(n)). ([2]: Cap. 7.1).
Esercizi.
-
21 dicembre 2022:
Metodi Monte Carlo per la stima di parametri. Campionamento
casuale (sampling) e conteggio.
Esempio: Un FPRAS (Fully Polynomial-time Randomized Approximation
Scheme) per il problema del conteggio delle assegnazioni che soddisfano una
formula in DNF. ([2]: Cap. 11.1, 11.2).
Esercizi.
-
22 dicembre 2022:
Introduzione alle Cryptocurrencies: le funzioni hash crittografiche e le loro proprietà. Collision resistance e il paradosso
dei compleanni. Cenni alla costruzione di Merkle-Damgård. ([3]: Cap. 1 e [2]: Cap 5.1).
Esercizi.
-
11 gennaio 2023:
Indirizzi bitcoin e transazioni. Cenni al linguaggio di scripting e alla
struttura dei blocchi. La blockchain testnet: Esempi. ([3]: Cap. 2 e 3.
Si veda anche [10]).
Esercizi.
-
12 gennaio 2023: Esercitazione.
[1] Algorithms
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani.
McGraw Hill, 2006
[2] Probability and Computing (2nd edition)
Michael Mitzenmacher, Eli Upfal
Cambridge University Press, 2017
[3]: Bitcoin and Cryptocurrency Technologies
Arvind Narayanan, Joseph Bonneau, Edward W. Felten, Andrew Miller, and Steven Goldfeder
Princeton University Press, 2016
(Una versione preliminare di questo libro e altro materiale collegato è liberamente scaricabili qui:
http://bitcoinbook.cs.princeton.edu/)
Testi di supporto
[4] Algorithm Design
Jon Kleinberg, Eva Tardos
Addison Wesley, 2005
[5] Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
The MIT press, 2001
[6] Algorithms Illuminated. Part 4: Algorithms for NP-Hard Problems
Tim Rougharden
Soundlikeyourself Publishing, 2020
Altri riferimenti
[7] Algorithms Illuminated. Part 3: Greedy Algorithms and Dynamic Programming
Tim Rougharden
Soundlikeyourself Publishing, 2019
[8] Algorithms Illuminated. Part 1: The Basics
Tim Rougharden
Soundlikeyourself Publishing, 2017
[9] Bengt Aspvall, Michael F. Plass and Robert Endre Tarjan.
A linear-time algorithm for
testing the truth of certain quantified Boolean formulas.
Information Processing Letters, 8(3):121--123, 1979.
[10]: Mastering Bitcoin. Programming the Open Blockchain
(2nd edition)
Andrea M. Antonopoulos
O'Reilly, 2017
(I capitoli di questo libro sono liberamente scaricabili qui:
https://github.com/bitcoinbook/bitcoinbook)
Modalità d'esame
L'esame consiste in una prova scritta e in un colloquio orale.
Durante il corso gli studenti potranno svolgere due test intermedi sotto forma
di homework. Chi ottiene una valutazione positiva a entrambi gli
homework è esonerato dalla prova scritta.
Ricevimento studenti
Durante il periodo delle lezioni (Ottobre 2022 - Gennaio 2023):
Giovedì 16:00 - 18:00 oppure su appuntamento.
Al di fuori del periodo delle lezioni:
Su appuntamento.
Francesco Pasquale
Dipartimento di Matematica - Università di Roma "Tor Vergata"
Via della ricerca scientifica, 1 - 00133 Roma - Italy
Edificio: Sogene - Primo Piano - Dente 1 - Stanza 1212
Tel.: +39 06 7259 4670
pasquale@mat.uniroma2.it
(OpenPGP: 0xBF979C2A)