Corso di Algoritmi Avanzati

Riferimenti

1. [KT] Algorithm Design, Kleinberg, Tardos. Editore: Pearson, 2014.
2. [CLRS] Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein. Editore: MIT Press, 2009.
3. [DPV] Algorithms, Dasgupta, Papadimitriou, Vazirani. Editore: McGrawHill, 2006.
4. [GJ] Computers and intractability, Garey e Johnson. Editore: Freeman and Company, 1979.
5. [L] Distributed Algorithms, N. Lynch. Editore: Morgan Kaufmman, 1996.
6. [B] Bitcoin and Cryptocurrency Technologies, Narayanan et al., Princeton University Press, 2016.

Programma

1. Problemi difficili (Rif.: [KT,CLRS,GJ])
   • Introduzione
   • Problemi decisionali
   • Riduzioni
     1. IndependentSet e VertexCover
     2. SetCover
     3. SetPacking
     4. SAT e 3SAT
   • Classi P e NP
   • Problemi NP-completi
     1. Soddisfacibilità di un circuito
     2. Cicli hamiltoniani
     3. Commesso viaggiatore
     4. Colorazione di grafi
   • Problemi NP-hard
   • Co-NP e PSPACE
2. Ricerca esaustiva (Rif.: [DPV])
   • Backtracking
     1. SAT
     2. Sudoku
   • Branch-and-bound
     1. TSP
3. Algoritmi di approssimazione(Rif.: [KT] capitolo Approximation Algorithms)
   • Introduzione
   • Approccio greedy
     • Load balancing
     • Selezione dei centri
   • Metodo dei pagamenti
     • Vertex Cover
   • Programmazione lineare
     • Vertex Cover con programmazione lineare
   • Programmazione dinamica
     • Il problema dello zaino
4. Algoritmi randomizzati(Rif.: [KT] capitolo Randomized Algorithms)
   • Introduzione
   • Taglio minimo globale
   • MAX 3-SAT
   • Mediana
   • Quicksort
5. Algoritmi online(Rif.: Note del corso)
   • Il problema dell'affitto degli sci
   • Problema del paging (algoritmi LRU, FIFO, LIFO, ottimalità)
   • Aggiornamento di liste (Strategia MTF, limite competitività)
   • Problema load balancing
   • Problema Bin Packing
   • Analisi probabilistica
6. Algoritmi distribuiti(Rif.: [L,B])
   • Introduzione
   • Definizione di sistema distribuito
   • Formalisimi per la descrizione e misure per l'analisi
   • Sistemi sincroni
   • Problema del consenso
   • Consenso con perdita di messaggi
   • Consenso con perdita di messaggi randomizzato
   • Consenso con guasti stop
   • Consenso con guasti bizantini
   • Consenso in sistemi asincroni
   • Registri distribuiti e blockchain
   • Criptovalute, Bitcoin

Codice

• Sudoku (forza bruta)
• Sudoku (backtracking)

Dispensa

• Capitolo 1
• Capitolo 2
• Capitolo 3
• Capitolo 4
• Capitolo 5
• Capitolo 6