Algoritmi e strutture dati 2

Docente: Francesco Pasquale

Comunicazioni

Avviso

16-01-2017 23:13

Il secondo homework è disponibile per il download. Consegna entro le ore 9:00 di Martedì 24 Gennaio 2017.


Avviso

05-12-2016 23:32

A partire dalla settimana del 12 dicembre, la lezione del lunedì è spostata al martedì. Stessa aula, stessa ora.


Avviso

20-11-2016 23:17

Il primo homework è disponibile per il download. Consegna entro le ore 9:00 di Lunedì 28 Novembre 2016.


Avviso

27-10-2016 19:10

Lunedì 31 ottobre non c'è lezione


Avviso

10-10-2016 19:02

Le lezioni iniziano alle ore 9:15


Avviso

28-09-2016 12:36

Il corso inizierà lunedì 10 ottobre


Lezioni

2626-01-2017

Esercitazione. Riepilogo del corso.

2524-01-2017

Risoluzione degli esercizi del compito. Esercitazione.

2419-01-2017

Il metodo dei Multiplicative Weights Update. Esempio: analisi dell'algoritmo Randomized Weighted Majority per il problema Regret Minimization. ([5]: Cap. 4.3.2)

2317-01-2017

Algoritmi online e competitive ratio. Algoritmi che "imparano". Esempio: il problema Regret Minimization. Un algoritmo greedy deterministico, un algoritmo greedy probabilistico e il ruolo della randomness. ([5]: Cap. 4.1, 4.2, 4.3.1)

2212-01-2017

Catene di Markov a stati finiti e tempo discreto e loro utilizzo per l'analisi di algoritmi probabilitstici. Esempio: analisi di un semplice algoritmo probabilistico per 2-SAT. ([3]: Cap. 7.1)

2110-01-2017

Il World Wide Web e la sua struttura di grafo diretto. Cenni al funzionamento di un motore di ricerca: Crawling, Indexing e il problema del Ranking. Il PageRank e sua formulazione come Random Walk. ([4]: Cap. 13 e 14.3)

2022-12-2016

Esercitazione

1920-12-2016

Stimare la deviazione di una variabile aleatoria dal suo valore atteso: Disuguaglianze di Markov, Chebyshev e Chernoff. Esempio: L'algoritmo di ordinamento RandomQuickSort, calcolo del valore atteso del numero di confronti e cenni all'analisi della deviazione dal valore atteso. ([3]: Cap. 2.5 e Esercizio 4.20)

1815-12-2016

Implementazione in Python di alcuni test di primalità: un test deterministico semplice con running time esponenziale, il test probabilistico di Fermat, il test probabilistico di Miller-Rabin. Generare numeri primi di grandi dimensioni.

1713-12-2016

Algoritmi per testare la primalità di un numero. Richiami di teoria dei numeri elementare: teorema di Fermat, radici non banali dell'unità. Il test di primalità di Miller-Rabin. ([1]: Cap. 1.3)

1605-12-2016

Richiami di probabilità discreta: Variabili aleatorie, distribuzioni geometrica e binomiale, valore atteso e linearità. Tecniche di analisi del running time di algoritmi probabilistici. ([2]: Cap. 13.3)

1501-12-2016

Esercitazione.

1428-11-2016

Risoluzione degli esercizi del compito. Riepilogo di probabilità discreta: Spazi di probabilità, eventi, probabilità condizionate, indipendenza. Introduzione agli algoritmi probabilistici.

1324-11-2016

I problemi computazionalmente difficili possono essere una risorsa. Esempio: scambiare messaggi in modo sicuro. Richiami di aritmetica modulare, i fondamenti della crittografia a chiave pubblica e il sistema di cifratura RSA. ([1]: Cap. 1.2 e 1.4)

1221-11-2016

Euristiche di ricerca locale. Esempi: Ricerca locale per Min Vertex Cover e Travelling Salesman Problem. Ricerca locale con fattore di approssimazione garantito. Esempio: Un algoritmo approssimante per Max-Cut ([1]: Cap. 9.3, si veda anche [2]: Cap. 12.4). 

1117-11-2016

Un algoritmo 2-approssimante per il problema TSP. Approssimazioni arbitrariamente buone. Esempio: un PTAS (Polynomial-Time Approximation Scheme) per il problema Knapsack ([1]: Cap. 9.2, si veda anche [2]: Cap. 11.8).

1014-11-2016

Esercitazione.

910-11-2016

Algoritmi approssimanti per problemi di ottimizzazione NP-hard. Esempi: Un algoritmo greedy 1.5-approssimante per il problema Load Balancing ([2]: Cap. 11.1); un algoritmo 2-approssimante per il problema Min Vertex Cover ([1]: Prima parte Cap. 9.2)

807-11-2016

Ricerca esaustiva intelligente. Le tecniche: Backtracking e Branch and Bound. Esempi: Un algoritmo per SAT e un algoritmo per Travelling Salesman Problem ([1]: Cap. 9.1).

703-11-2016

Il problema Circuit SAT e sua riduzione polinomiale a SAT. Il concetto di NP-completezza e il teorema di Cook-Levin con cenni di dimostrazione. ([1]: Ultima parte del Cap. 8.3; si veda anche [2]: Cap. 8.3 e 8.4). Introduzione alla ricerca esaustiva intelligente ([1]: Cap. 9.1).

627-10-2016

Problemi computazionalmente difficili. La tecnica delle riduzioni polinomiali per valutare la difficoltà di un problema relativamente a un altro problema. Esempi: Se esiste un algoritmo polinomiale per 3-SAT allora esiste anche un algoritmo polinomiale per SAT; se esiste un algoritmo polinomiale per Independent Set allora esiste anche un algorimo polinomiale per 3-SAT ([1]: Cap. 8.2 e parte di 8.3).

524-10-2016

Esercitazione sulle tecniche algoritmiche.

420-10-2016

La tecnica della Riduzione. Esempio: un algoritmo efficiente per 2-SAT tramite riduzione al problema di trovare le componenti fortemente connesse in un grafo diretto ([1]: Esercizio 3.28). Richiami su grafi diretti, componenti fortemente connesse, DAGs e topological sorting ([1]: Cap. 3.3 e 3.4)

317-10-2016

La tecnica della Programmazione Dinamica. Esempio: un algoritmo per il problema Longest Increasing Subsequence ([1]: Cap. 6.1, 6.2).

213-10-2016

La tecnica Divide et Impera. Esempio: un algoritmo per moltiplicare due interi di n bit con running time asintoticamente inferiore a n^2. Richiami sulle relazioni di ricorrenza. ([1]: Cap. 1.1, 2.1, 2.2)

110-10-2016

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)


Materiale didattico

Si veda la pagina del corso sul sito del docente

http://www.mat.uniroma2.it/~pasquale/dida/aa1617/asd2/index.html

Informazioni

Anno accademico2016-2017
Crediti6
SettoreINF/01
Anno3
Semestre1
PropedeuticitàAlgoritmi e strutture dati.

Programma

Programma provvisorio

 

Prima parte (4cfu)

 

Progettare algoritmi efficienti. Riepilogo delle tecniche più efficaci per progettare algoritmi efficienti: Greedy, Divide et Impera, Programmazione dinamica, Riduzioni polinomiali.

 

Problemi computazionalmente difficili. La teoria dell'NP-completezza da un punto di vista algoritmico. Affrontare i problemi computazionalmente difficili: ricerca esaustiva intelligente, algoritmi approssimanti, euristiche di ricerca locale.

Algoritmi che sfruttano l'esistenza di problemi computazionalmente difficili: il protocollo RSA e i fondamenti della crittografia a chiave pubblica. La matematica dietro le scene: Teoria dei numeri.

 

Algoritmi probabilistici. Il ruolo della randomness negli algoritmi. Quando scegliere a caso semplifica gli algoritmi: Test di primalità di Miller-Rabin. Quando scegliere a caso rende gli algoritmi più efficienti: Packet Routing. Quando poter scegliere a caso è indispensabile: Protocolli interattivi e zero-knowledge proofs. Le tecniche per analizzare gli algoritmi probabilistici.

Hashing, il problema dei dizionari. Hashing universale e hashing perfetto. Funzioni hash crittografiche.

 

 

Seconda parte (2cfu)

 

La rapida evoluzione tecnologica degli ultimi decenni ha portato all'ordine del giorno nuove sfide algoritmiche. Nella seconda parte del corso ne studieremo alcune e vedremo come sono state affrontate.

 

Ranking. Le semplici idee algoritmiche che hanno rivoluzionato i motori di ricerca: PageRank e HITS. La matematica dietro le scene: Algebra lineare e catene di Markov.

 

Algoritmi che imparano. Expert selection e il meta-algoritmo dei multiplicative updates.

 

Big Data. Lavorare con grandi quantità di dati. Quando polinomiale non è abbastanza efficiente: algoritmi sublineari.


Testi di riferimento

[1] S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill, 2006.

 

[2] J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.

 

 

Testi di supporto

 

[3] M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005.

 

[4] D. Easley and J. Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.

 

[5] N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani (eds.). Algorithmic Game Theory. Cambridge University Press, 2007


Ricevimento studenti

Durante il periodo di svolgimento del corso (Ottobre 2016 - Gennaio 2017):
Giovedì 14:30 - 16:30 oppure su appuntamento.

Al di fuori del periodo di svolgimento del corso:
Su appuntamento.  


Modalità di esame

L'esame consiste in una prova scritta e in un colloquio orale.

 

Durante il corso si effettueranno due prove intermedie sotto forma di homework. Gli studenti che ricevono una valutazione positiva agli homework sono esonerati dalla prova scritta.