A. I. Cuza University of IaşiComputability, Decidability and Complexity
| Course name | Computability, Decidability and Complexity | Code | CS3105O2 |
| Class | Computer Science, 2006 - 2009 | Package | 3 | ||||
| Level | Undergraduate | Year | 3 | Semester | 1 | Status | Optional |
| Hours per week | Total hours per semester | Total hours of individual work | Credits | Evaluation type | Teaching language | |||
| C | S | L | Pr | |||||
| 5 | ||||||||
| Taught by | Academic and scientific title, name |
|
Professor, PhD,
Ferucio Laurenţiu Ţiplea
|
| Required courses |
| Objectives | Acest 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 thematics | Cursul 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 thematics | Seminariile 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 methods | Curs predat la tabla, combinat cu prezentare schematica on-line. |
| Bibliography | J.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. |
| Evaluation | conditions | |
| criterias | ||
| modes | 6 teme (practice – implementare) pe parcursul semestrului, examen scris final | |
| formula | 60% teme + 40% examenul final |