Algoritmi Avanzati (AA)

Prof. Roberto De Prisco Dip. di Informatica, Università di Salerno - a.a. 2020-2021

Programma

Programma di massima; verrà aggiornato durante il corso.
  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
      1. Load balancing
      2. Selezione dei centri
    • Metodo dei pagamenti
      1. Vertex Cover
    • Programmazione lineare
      1. Vertex Cover con programmazione lineare
    • Programmazione dinamica
      1. Il problema dello zaino
  4. Algoritmi randomizzati(Rif.: [KT] capitolo Randomized Algorithms)
    • Introduzione
    • Taglio minimo globale
    • MAX 3-SAT
    • Mediana
    • Quicksort
  5. Algoritmi distribuiti(Rif.: [L])
    • 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
  6. 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
Corso di Algoritmi Avanzati - Prof. Roberto De Prisco - Dip. di Informatica, Università di Salerno - a.a. 2020-2021