Universitatea A. I. Cuza IaşiCalculabilitate, Decidabilitate şi Complexitate
| Numele cursului | Calculabilitate, Decidabilitate şi Complexitate | Cod | CS3105O2 |
| Generaţia | Informatică zi, 2007 - 2010 | Pachet | 3 | ||||
| Nivel de studii | Licenţă | An | 3 | Semestru | 1 | Statut | Opţional |
| Nr. de ore pe săptămână | Nr. total de ore pe semestru | Nr. de ore de lucru individual | Credite | Mod de evaluare | Limba de predare | |||
| C | S | L | Pr | |||||
| 5 | ||||||||
| Titularul disciplinei | Titlu academic şi ştiinţific |
|
Profesor, Dr.,
Ferucio Laurenţiu Ţiplea
|
| Discipline absolvite anterior |
| Obiective | 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). |
| Tematica generală | 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. |
| Tematica seminariilor / laboratoarelor | 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. |
| Metode de predare | Curs predat la tabla, combinat cu prezentare schematica on-line. |
| Bibliografie | 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. |
| Evaluare | condiţii | |
| criterii | ||
| forme | 6 teme (practice – implementare) pe parcursul semestrului, examen scris final | |
| formula notei finale | 60% teme + 40% examenul final |