A. I. Cuza University of Iaşi

Computability, Decidability and Complexity

Course nameComputability, Decidability and Complexity CodeCS3105O2
Class Undergraduate, 2009 - 2012 Package 3
Level Undergraduate Year 3 Semester 1 Status Optional
Hours per weekTotal hours per semesterTotal hours of individual workCreditsEvaluation typeTeaching language
CSLPr
5
Taught byAcademic and scientific title, name
Required courses
ObjectivesAcest curs introduce studentilor unul din cele mai importante domenii ale informaticii, calculabilitate (ce probleme pot fi rezolvate algoritmic) si complexitate (cat de eficient este un algoritm).
General thematicsCursul acopera urmatoarele capitole: probleme si algoritmi, modele de baza ale calculabilitatii, probleme nedecidabile, decidabilitate, modele nestandard ale calculabilitatii, complexitate spatiu si timp, clase de complexitate, reduceri si probleme complete. Fiecare capitol este exemplificat prin probleme algoritmice fundamentale in informatica.
Seminary / Laboratory thematicsSeminariile sunt grupate in functie de capitolul studiat la curs si, ca urmare, tematica acestora este concordanta cursului. Tematica fiecarui seminar este afisata on-line a priori.
Teaching methodsCurs predat la tabla, combinat cu prezentare schematica on-line.
BibliographyJ.L. Balcazar, J. Diaz, J. Gabarro. Structural Complexity, Vol I-II, Springer-Verlag, 1995.

M.D. Davis, R. Sigal and E.J. Weyuker: Computability, Complexity and Languages, 2nd Ed., Academic Press (Morgan Kaufmann), 1994.

J.E. Hopcroft, R. Motwani and J.D. Ullman: Introduction to Automata Theory, Languages and Computation, 2nd Ed., Addison-Wesley, 2001.

N.D. Jones. Computability and Complexity, MIT Press, 1997.

Ch.H. Papadimitriou. Computational Complexity, Addison-Wesley, 1994.

Journal papers.

Evaluationconditions
criterias
modes6 teme (practice – implementare) pe parcursul semestrului, examen scris final
formula60% teme + 40% examenul final

© 2006-2010 FII | about | intranet