|
Course Catalog 2012-2013
MAT-41176 Theory of Automata, 5 cr |
Additional information
Periods 1-2
Suitable for postgraduate studies
Person responsible
Stephane Foldes
Lessons
Study type | P1 | P2 | P3 | P4 | Summer | Implementations | Lecture times and places |
|
|
|
|
|
|
|
|
Requirements
Final exam plus classroom activity, particulars to be announced during first lecture.
Principles and baselines related to teaching and learning
-
Content
Content | Core content | Complementary knowledge | Specialist knowledge |
1. | Strings of symbols, languages and mathematical machines. | ||
2. | Deterministic and non-deterministic computations. Turing machines, algorithms, decidability. | ||
3. | Oracles and reducibility. Complexity of computation. | ||
4. | COURSE NOT GIVEN IN 2009-2010 |
Study material
Type | Name | Author | ISBN | URL | Edition, availability, ... | Examination material | Language |
Book | Introduction to the Theory of Computation | Sipser, M. | PWS Publ. Co., Boston 1996 | English |
Prerequisite relations (Requires logging in to POP)
Correspondence of content
Course | Corresponds course | Description |
|
|
More precise information per implementation
Implementation | Description | Methods of instruction | Implementation |