Cursuri CAIT 2008
 
  • Cursul 1: Probleme de decizie. Masini Turing. Universalitate. Nedecidabilitatea problemei opririi.

 Referinte: 

Arora-Barak capitolul 1. 

Goldreich   (book draft), capitolul 1.  

 M.I.T. Course "Great Ideas in Theoretical Computer Science",  course 4 

  • Cursul 2: P, NP. NP-completitudinea problemei SAT

Referinte: 

Arora-Barak capitolul 2.   

Goldreich   (book draft), capitolul 2.

 

  • Cursul 3: Demonstratii de NP-completitudine: k-SAT, IP.

Referinte: 

Arora-Barak capitolul 2.   

Goldreich   (book draft), capitolul 2.

 

  • Cursul 4:  Programare Liniara

Referinte:   notele de curs ale lui Thomas S. Ferguson (UCLA).

  • Cursul 5: Algoritmi de aproximare pentru Set Cover, Weighted Set Cover. Metoda primal-dual pentru algoritmi de aproximare. 

Referinte: 

Note de curs "Approximation algorithms" , Lenore Cowen (John Hopkins). Cursul 3. Cursul 6. 

Note de curs "Approximation algorithms for network problems", Joseph Cheryian si R. Ravi. Capitolul "Set Cover". 

M. Goemans si D.  Williamson, The Primal-Dual Method for Approximation Algorithms, in Approximation Algorithms, D. Hochbaum, Ed., 1997.



Referinte suplimentare: 

Note de curs "Probabilistic Method I" Sariel Hal-Peled (UIUC) 

Note de curs "Moments and Deviations" Sariel Hal-Peled (UIUC)

Note de curs "Tail Inequalities" Sariel Hal-Peled (UIUC)

Articol "Randomized Rounding", Raghavan si Thompson