Capitole Avansate de Informatica Teoretica
NOTE | |
File Size: | 32 kb |
File Type: |
Profesor/TA: Gabriel Istrate. email: prenumenume at acm dot org
Orar: Luni 16:20-17:50, sala A104. Notare 50% examen, 50% seminar.
Note de curs:
Arora-Barak capitolul 1.
Goldreich (book draft), capitolul 1.
M.I.T. Course "Great Ideas in Theoretical Computer Science", course 4
Arora-Barak capitolul 2.
Goldreich (preliminary version), capitolul 2.
Arora-Barak capitolul 2.
Goldreich (book draft), capitolul 2.
Note de curs.
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.
Note de curs.
Note de curs "Approximation algorithms" , Lenore Cowen (John Hopkins). Cursul 3. Cursul 6.
Orar: Luni 16:20-17:50, sala A104. Notare 50% examen, 50% seminar.
Note de curs:
- Cursul 1: Probleme de decizie. Masini Turing. Universalitate. Nedecidabilitatea problemei opririi.
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.
Arora-Barak capitolul 2.
Goldreich (preliminary version), capitolul 2.
- Cursul 3: Demonstratii de NP-completitudine: k-SAT, IP.
Arora-Barak capitolul 2.
Goldreich (book draft), capitolul 2.
- Cursul 4: Programare Liniara
- Cursul 5: Algoritmi de aproximare pentru Set Cover, Weighted Set Cover. Metoda primal-dual pentru algoritmi de aproximare.
Note de curs.
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: Algoritmi de aproximare pentru Problema Padurii Steiner.
Note de curs.
Note de curs "Approximation algorithms" , Lenore Cowen (John Hopkins). Cursul 3. Cursul 6.