Complexitate Structurala
QUICK INFO: CU 2h / SE 1h / LAB 0h / EXAMEN SCRIS / 7.5 CREDITE
PROGRAMA ANALITICA
- NP-completitudine
- Ierarhii ale multimii functiilor primitiv recursive (unare si de n >= 2 argumente)
- Teoria complexitatii abstracte Blum
- Teoria complexitatii descriptive Kolmogorov-Martin-Lof
METODA DE EVALUARE
- 50%: Prezentarea unui referat, pe o temă aleasă sau propusă de student, în timpul orelor de seminar - 20 min + 5 min pentru întrebări
- 50%: examen scris
- 25% (bonus): rezolvarea unor probleme/demonstrații lăsate ca temă în cursuri
DATE IMPORTANTE
- 5 decembrie - 16 ianuarie: prezentare referate, în ordinea alfabetică după master și apoi după student. Vezi programarea atașată.
LINKURI
Există un grup pe Yahoo unde doamna profesoară pune cursurile și anunțuri legate de curs: compstr11. Dacă ești înscris la opțional, dar nu ești membru, încearcă să vorbești cu moderatorul, Cristi Neagu (cristineagu2801).
BIBLIOGRAFIE
- Cristian Sorin CALUDE: Theories of Computational Complexity, Elsevier Science Publ., Amsterdam, 1988.
- C.S. CALUDE, Information and randomness. An algorithmic perspective, Springer Verlag, Berlin 1994.
- Martin D. DAVIES, Elaine WEYUKER: Computability, Complexity, and Languages, Academic Press, Orlando, Fl., 1983.
- Christos H. PAPADIMITRIOU: Computational Complexity, Addison-Wesley Publ. Co., Reading Mass., 1994.
- Gheorghe PAUN, Grzegorz ROZENBERG, Aarto SALOMAA (Eds.): Current Trends in Theoretical Computer Science, World Scientific Publ. Co., 2001.
- Michael SIPSER: Introduction to the Theory of Computation, PWS Publ. Co. International Thomson Publ. Inc., Boston, Ma., 1997.
- O. WATANABE (Ed.): Kolmogorov Complexity and Computational Complexity, Springer-Verlag, Berlin Heidelberg, 1992.
- Marius ZIMAND: Computational Complexity: A Quantitative Perspective, Elsevier B.V., Amsterdam, 2004.