28 Settembre 2020
NP Completezza (CLRS, Cap. 34)
- Presentazione ragionata del corso. Programma preliminare.
- Classi di problemi: problemi indecidibili, intrinsecamente esponenziali, intrattabili, polinomiali.
- Problemi astratti e problemi decisionali. Riduzione da problemi di ottimizzazione a problemi decisionali. Esempio: SHORTEST UNWEIGHTED PATH.
29 Settembre 2020
- Il problema dell'encoding: problemi astratti e problemi concreti.
Encoding ragionevoli.
- Linguaggi formali. Problemi concreti e linguaggi associati.
- Decisione di un linguaggio in tempo polinomiale: la classe P: definizione.
- Verificabilità in tempo polinomiale: introduzione.
- Algoritmo di verifica per HAMILTON.
- Verificabilità in tempo polinomiale: definizione.
- La classe NP.
1 Ottobre 2020
- Teorema: P è un sottoinsieme di NP.
- Riducibilità: HAMILTON e TSP
- Riducibilità in tempo polinomiale.
- Caratteristiche delle funzioni di riduzione.
- Teorema: Se L1 < L2 e L2 è in P, allora L1 è in P.
- Le classi NPH e NPC.
- Corollario: se L e' sia in NPC che in P, allora P=NP.
- Il problema BC-SAT. Definizione.
- Il teorema di Cook: 1) Algoritmo di verifica polinomiale per BC-SAT.
2) Riduzione di ogni linguaggio in NP a BC-SAT (idea della riduzione).
5 Ottobre 2020
- Il problema BC-SAT. Definizione.
- Il teorema di Cook: 1) Algoritmo di verifica polinomiale per BC-SAT.
2) Riduzione di ogni linguaggio in NP a BC-SAT (idea della riduzione).
- Il problema FORMULA-SAT. Definizione. Riduzione non polinomiale da BC-SAT.
- Riduzione polinomiale da BC-SAT a FORMULA-SAT.
6 Ottobre 2020
- Riduzione polinomiale da BC-SAT a FORMULA-SAT (cont.).
- Il problema 3CNF-SAT. Riduzione da BC-SAT.
- Il problema CLIQUE. Definizione e riduzione da 3CNF-SAT.
8 Ottobre 2020
- I problemi VERTEX-COVER e INDEPENDENT-SET e riduzioni da CLIQUE.
- Il problema SUBSET SUM. Definizione e riduzione da 3CNF-SAT.
12 Ottobre 2020
- Il problema SUBSET SUM. Definizione e riduzione da 3CNF-SAT (cont.).
Esercitazioni su NP completezza
- Oggni linguaggio in NP ammette decisione (esponenziale)
- HALTING problem è in NPH
- Se L1 < L2 e L2 è in NP, allora L1 è in P.
- BC-TESTING è in NPC
- KNAPSACK è in NPC
13 Ottobre 2020
Esercitazioni su NP completezza
- Proprietà dei linguaggi complementari e la classe Co-NP
- DOMINATING SET problem è in NPC
- LONG-PATH problem è in NPC
- Costruzione di una soluzione a partire da un oracolo per il problema decisionale: applicazione a SUBSET-SUM
15 Ottobre 2020
Algoritmi di Approssimazione (CLRS, Cap. 35)
- Definizione di algoritmo di approssimazione.
- Schemi di approssimazione polinomiali e pienamente polinomiali (PTAS e FPTAS)
- Algoritmo di 2-approssimazione per VERTEX COVER: definizione e analisi.
19 Ottobre 2020
- Inefficiacia dell'algoritmo per il calcolo di una clique.
- Spiegazione informale: le riduzioni in tempo polinomiale non preservano l'approssimazione.
- Approcci Greedy per VC che non conducono ad approssimazione controllata.
- MINIMUM WEIGHTED VERTEX COVER: approccio basato sul fair pricing
- MINIMUM WEIGHTED VERTEX COVER: approccio basato sull'arrotondamento della soluzione al rilassamento lineare dell'ILP.
19 Ottobre 2020
- Inefficiacia dell'algoritmo per il calcolo di una clique.
- Spiegazione informale: le riduzioni in tempo polinomiale non preservano l'approssimazione.
- Approcci Greedy per VC che non conducono ad approssimazione controllata.
- MINIMUM WEIGHTED VERTEX COVER (MWVC): approccio basato sul fair pricing
- MWVC: approccio basato sull'arrotondamento della soluzione al rilassamento lineare dell'ILP.
20 Ottobre 2020
- Relazione primale-duale tra i due approcci a MWVC
- TSP: NP-completezza del problema decisionale
- Inapprossimabilità del TSP generale
- TRIANGLE TSP (TSP con funzione metrica): NP-completezza del problema decisionale
- Algoritmo di 2-approssimazione basato sul Minimum Spanning Tree: descrizione
22 Ottobre 2020
- Algoritmo di 2-approssimazione basato sul Minimum Spanning Tree: analisi
- Algoritmo di Christofides per la 3/2-approssimazione di TRIANGLE-TSP
26 Ottobre 2020
- Algoritmo di Christofides:analisi
- Cenni ai risultati di approssimabilità e inapprossimabilità per TRIANGLE-TSP
- Cenni all'approssimabilità di EUCLIDEAN-TSP
- Definizione del problema SET-COVER: NP-completezza e algoritmo greedy.
- Analisi di (ln n)-approssimazione per SET-COVER.
27 Ottobre 2020
- Analisi più fine per SET-COVER basata su pesatura.
- FPTAS per SUBSET-SUM: l'algoritmo enumerativo.
29 Ottobre 2020
- FPTAS per SUBSET-SUM: l'algoritmo
approssimato.
- FPTAS per SUBSET-SUM: determinazione
del fattore di approssimazione e del tempo di esecuzione
- Definizione di algoritmo randomizzato e approssimazione randomizzata
2 Novembre 2020
- MAX-SAT. Definizione, NP-completezza e algoritmo
randomizzato di 8/7 approssimazione.
Esercitazioni su Algoritmi di Approssimazione
- RESOURCE SELECTION: 2-approssimazione basata sul rilassamento lineare
- MAX-CUT: 2-approssimazione deterministica
- MAX-CUT: 2-approssimazione randomizzata
3 Novembre 2020
Esercitazioni su Algoritmi di Approssimazione
- Impossibilità di un FPTAS per TRIANGLE TSP
- SUBSET-SUM: algoritmo greedy di 2-approssimazione
- INDEPENDENT SET: Algoritmo greedy di con rho pari al massimo grado
- MAX-CUT: 2-approssimazione randomizzata
- LOAD-BALANCING, 2-approssimazione e cenni alla 3/2-approssimazione
5 Novembre 2020
Algoritmi di Teoria dei Numeri (CLRS, Cap. 31)
- Divisibilità: definizioni e proprietà.
- Il massimo comun divisore (gcd): definizioni e proprietà.
- Identità di Bezout.
- L'algoritmo di Euclide: correttezza.
- L'algoritmo di Euclide: complessità.
- L'algoritmo di Euclide Esteso: : correttezza e complessità.
9 Novembre 2020
- Aritmetica modulare: la struttura quoziente Zn: definizione e proprietà di gruppo rispetto alla somma.
- Il sottoinsieme Z*n: definizione
- Z*n è un gruppo moltiplicativo. Calcolo dell'inverso con EXTENDED-EUCLID.
- La funzione di Eulero. Il teorema di Eulero e il piccolo teorema di Fermat.
10 Novembre 2020
- Il Teorema cinese dei resti: enunciato, applicazioni, prova e corollari
- Definizione di criptosistema e criptosistema a chiave pubblica.
- Protocolli di comunicazione e autenticazione.
12 Novembre 2020
- Dettagli di RSA: calcolo della chiave pubblica e della chiave
segreta: algoritmo ricorsivo e iterativo di esponenziazione modulare veloce.
- Prova di correttezza: la funzione di codifica e decofica sono una
l'inversa dell'altra.
- RSA: considerazioni di complessità computazionale.
16 Novembre 2020
- Attacchi a RSA.
- Decomposizione di n=pq se p e q sono molto vicini
tra loro.
- Attacchi per scelte di chiavi pubbliche con lo stesso esponente.
- Attacchi per scelte di chiavi pubbliche con lo stesso modulo.
- Attacchi basati sull'autenticazione
- Introduzione alla primalità
17 Novembre 2020
- Introduzione alla primalità
- Pseudoprimi in base a e test semplice
per numeri casuali. I numeri di Carmichael.
- Estrazione casuale di primi: il teorema di Pomerance e
analisi probabilistica dell'algoritmo basato sul test di pseudoprimalità in base 2.
- Esponenziazione modulare e radici quadrate non banali dell'unità
- Il test randomizzato di Miller-Rabin. Certificato di nonprimalità basato sul teorema di
Fermat e sull'esistenza di una radice quadrata non banale
dell'unità. Complessità.
19 Novembre 2020
- Miller-Rabin: analisi della correttezza per numeri non di Carmichael.
Esercitazioni su Algoritmi di Teoria dei Numeri
- Algoritmo di divisione intera
23 Novembre 2020
Esercitazioni su Algoritmi di Teoria dei Numeri
- Unicità dell'inverso moltiplicativo
- Calcolo efficiente del minimo comune multiplo
- Combinazioni lineari intere a due incognite
- Coefficienti di Bezout e soluzioni di combinazioni lineari intere
Tecniche algoritmiche randomizzate e applicazioni
-
- Introduzione agli algoritmi randomizzati:
algoritmi Monte Carlo e Las Vegas.
24 Novembre 2020
- Analisi in media e in alta probabilità
- Le diseguaglianze di Markov e implicazioni rispetto all'analisi al caso medio.
- I tre bound di Chernoff sulla distribuzione di probabilità di somme di Bernoulliane.
26 Novembre 2020
- Introduzione a Quicksort randomizzato: intuizione sull'efficienza computazionale
- Applicazione dei bound di Chernoff (1): Analisi in alta
probabilità di Quicksort
30 Novembre 2020
- Analisi al caso medio di Quicksort tramite la seconda diseguaglianza di Markov
- Applicazione dei bound di Chernoff (2): Amplificazione della probabilità di correttezza
- Applicazione dei bound di Chernoff (3): Il metodo Monte Carlo
1 Dicembre 2020
- Definizione del problema del taglio minimo su multigrafi
- Definizione di contrazione di un multigrafo rispetto a un arco e proprieà rispetto ai tagli.
- L'algoritmo di Min-Cut di Karger: codice analisi di complessità
3 Dicembre 2020
- L'algoritmo di Min-Cut di Karger: analisi
- L'algoritmo di Min-Cut di Karger-Stein: descrizione
della strategia divide-and-conquer e complessità dell'approccio ricorsivo.
10 Dicembre 2020
- L'algoritmo di Min-Cut di Karger-Stein: analisi di correttezza
della strategia divide-and-conquer e amnplificazione della probabilità.
-
- Il problema del coupon collecting: analisi al caso medio e in alta probabilità.
14 Dicembre 2020
- Problemi di occupancy (balls into boxes): presentazione di casi di studio e analisi
Esercitazioni su Randomizzazione
- Generazione di bit senza bias da bit con bias
15 Dicembre 2020
Esercitazioni su Randomizzazione
- Algoritmo di selezione di order-statistic: analisi al caso medio
- Bound sulla coda della distribuzione di somme di variabili geometriche
- Bound sulla coda della distribuzione di somme di variabili "win/lose"
17 Dicembre 2020
Esercitazioni su Randomizzazione
- Approssimazione randomizzata: Independent Set (algoritmo Monte Carlo)
- Approssimazione randomizzata: Independent Set (algoritmo Las Vegas)
- Approssimazione randomizzata: MAX-3CNF-SAT (algoritmo Las Vegas)
- Approssimazione randomizzata: VERTEX-COVER (algoritmo Las Vegas)
11 Gennaio 2021
Presentazioni delle tesine di esonero: Approssimazione
- Dalla Valle Simone, Guerra Elia: PTAS for the Multiple Knapsack Problem
- Dolci Luca, Maguolo Francesco: Closeness Centrality approximation: Theory and Practice
- Balzan Pietro, Teso Ruggero: Hierarchical and Incremental Clustering
- Perali Luca, Thiella Michele: Randomized Rounding and Semidefinte Programming
12 Gennaio 2021
Presentazioni delle tesine di esonero: Tecniche Randomizzate
- Codogno Alice, Michelotto Federico: Balanced Allocations and Cuckoo Hashing
- Carlassare Leonardo: Limited Independence and Universal Hashing
- Benedetti Matteo, Ghedin Filippo: The Monte Carlo Method
- Masiero Federico: The Probabilistic Method
14 Gennaio 2021
Presentazioni delle tesine di esonero: Applicazioni della randomizzazione
- Bastianello Riccardo, Valzan Nicola: Streaming Triangle Counting
- Green Tommaso, Gulmini Nicola: Odds theorem, and the Secretary and Hiring Problem
- Bettin Manuel, Dainese Matteo: Random Graph Models for Bluetooth Networks
- Bonan Federico: Power-Law Distributions
|
