Course Catalog 2006-2007

MAT-41176 THEORY OF AUTOMATA, 5 cr
Theory of Automata

Courses persons responsible
Stephane Foldes

Lecturetimes and places
Per I: Tuesday 14 - 16, TB224
Per I: Wednesday 14 - 15, S2
Per II: Tuesday 17 - 19, TB223
Per II: Wednesday 16 - 18, TB223

Implementations
  Period 1 Period 2 Period 3 Period 4 Period 5 Summer
Lecture 3 h/week 4 h/week - - - -
Exercise 2 h/week 2 h/week - - - -
Exam  
(Timetable for academic year 2006-2007)

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.       

Requirements for completing the course
Final exam plus activity points, particularly to be announced during first lecture.

Evaluation criteria for the course

  • Used assessment scale is numeric (1-5)

    • Study material
    Type Name Auhor ISBN URL Edition, availability... Exam material Language
    Book Introduction to the Theory of Computation Sipser, M.     PWS Publ. Co., Boston 1996 Yes  English 

    Prerequisites
    Code Course Credits M/R
    MAT-21160 MAT-21160 Mathematics for Algorithms 3 Mandatory

    Prequisite relations (Sign up to TUT Intranet required)

    Remarks

    The course is given biannually.

  • The course is suitable for postgraduate studies.

    • Correspondence of content
    73117 Theory of Automata

    Last modified 30.01.2006
    Modified byEmilia Ylirinne