Cursuri CAIT 2007
 
  • Cursul 1: Probleme de decizie. Masini Turing. Universalitate. Nedecidabilitatea problemei opririi. Automate celulare.  universalitatea "Game of Life" si a regulii 110. 

 Referinte: Arora-Barak capitolul 1. 

                 Pagina jflap (simulator pentru automate si masini Turing) 

                 Simulator pentru Game of Life

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

Referinte: Arora-Barak capitolul 2.  

 

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

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

  • Cursul 4:  Operatia de pivotare in programarea liniara. Algoritmi de aproximare pentru problema Set Cover. 

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

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

  • 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. 

  • Cursul 6: Algoritmul primal-dual pentru padurea Steiner  

Referinte:  

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

  •      Cursul 7: Metode probabiliste. Algoritmi de aproximare pentru MAX 3-SAT si MAX-SAT. 

Referinte: 

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