26 | 26-01-2017
Esercitazione. Riepilogo del corso. |
25 | 24-01-2017
Risoluzione degli esercizi del compito. Esercitazione. |
24 | 19-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) |
23 | 17-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) |
22 | 12-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) |
21 | 10-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) |
20 | 22-12-2016
Esercitazione |
19 | 20-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) |
18 | 15-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. |
17 | 13-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) |
16 | 05-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) |
15 | 01-12-2016
Esercitazione. |
14 | 28-11-2016
Risoluzione degli esercizi del compito. Riepilogo di probabilità discreta: Spazi di probabilità, eventi, probabilità condizionate, indipendenza. Introduzione agli algoritmi probabilistici. |
13 | 24-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) |
12 | 21-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). |
11 | 17-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). |
10 | 14-11-2016
Esercitazione. |
9 | 10-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) |
8 | 07-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). |
7 | 03-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). |
6 | 27-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). |
5 | 24-10-2016
Esercitazione sulle tecniche algoritmiche. |
4 | 20-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) |
3 | 17-10-2016
La tecnica della Programmazione Dinamica. Esempio: un algoritmo per il problema Longest Increasing Subsequence ([1]: Cap. 6.1, 6.2). |
2 | 13-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) |
1 | 10-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) |