Tags:
create new tag
view all tags

COMPLESSITÀ       a.a. 2009/10

Programma di massima del Corso

Nozioni di base

Algoritmi, efficienza, problemi di ottimizzazione, problemi di decisione, la classe P, la classe NP, la questione P=?NP, riduzioni polinomiali e problemi NP-completi, il teorema di Cook-Levin, NP-completezza dei problemi 3SAT, Copertura con nodi, Insieme indipendente, 3-colorazione, il problema del taglio, e il problema dello zaino, algoritmo pseudopolinomiali.
 

La complessità dei problemi di ottimizzazione

Le classi NPO e PO, algoritmi d'approssimazione e rapporto d'approssimazione. Esempi: la massima soddisfacibilità, la copertura minima con nodi, la copertura minima d'un insieme, il massimo insieme indipendente, il problema del commesso viaggiatore con diseguaglianza triangolare, il problema del massimo taglio, il problema dello zaino. Le classi APX, PTAS e FPTAS. Limiti dell?approssimabilità e la tecnica del gap. Se P ⊂ NP allora PO ⊂ FPTAS ⊂ PTAS ⊂ APX ⊂ NPO. Riduzioni che preservano l'approssimabilità. Il teorema PCP e la sua applicazione per provare risultati di non approssimabilità, esempi: MAX-3SAT e Cricca.
 

Algoritmi e classi probabilistiche

Esempi: il problema del taglio minimo, 2SAT, verifica del prodotto di matrici, verifica dell'identità di polinomi. il problema del perfect matching, il test di primalità. Approssimazione randomizzata: il problema del massimo taglio, il problema della massima soddisfattibilità. Le classi PP, BPP, RP, e ZPP, loro relazione con le classi P, NP e PSPACE. Amplificazione della probabilità di successo.
 

La gerarchia polinomiale

Le classi Σk, Πk, e PH e loro caratterizzazioni. Alcune proprietà: BPP contenuta in Σ2. Se NP = co-NP allora PH = NP. Se Σkk allora PH finita. Se PH infinita allora PH ⊂ PSPACE.
 
 
 

Testi Consigliati

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, (Jackson libri)
  2. Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, Protasi, Complexity and Approximation, Springer
  3. O. Goldreich, Introduction to Complexity Theory, 1999, disponibile online: http://www.wisdom.weizmann.ac.il/~oded/cc99.html
  4. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
  5. Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1995.
  6. D. P. Bovet e P. Crescenzi Teoria della Complessità Computazionale, (Franco Angeli) 1991.
  7. J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, (Addison Wesley) 2001.
  8. S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, disponibile online: http://www.cs.princeton.edu/theory/complexity/


Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2012-10-12 - AngeloMonti






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback