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-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback