Course Catalog 2007-2008

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

Courses persons responsible
Stephane Foldes

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 2007-2008)

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.

  • Course will not be lectured in the academic year 2007-2008.

    • Correspondence of content
    73117 Theory of Automata

    Last modified 12.02.2007
    Modified byJanne Kauhanen