Opinto-opas 2005-2006

MAT-41176 AUTOMAATTITEORIA, 5 cr
THEORY OF AUTOMATA

Person responsible
Stephan Foldes

Lecturers
Stephan Foldes, professor

Implementation rounds
Implementation 1
  Period 1 Period 2 Period 3 Period 4 Period 5 Summer Language of instruction
Lecture 3 h/week+ 2 h/week - - - - In English only
Exercise 2 h/week+ 2 h/week - - - - In English only
Exam   In English only
(Academic Calender 2005-2006)

Contents
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
Examination.

Assessment criteria

  • Used assessment scale is numeric (1-5)

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

    Prerequisites
    Number Name Credits M/R
    MAT-21160 Mathematics for Algorithms 3 Mandatory

    Other comments
    The course is given biannually.

  • The course is suitable for postgraduate studies.
  • Course will not be lectured in the academic year 2005-2006.

    • Correspondence of content
    73117 Theory of Automata

    Last modified 10.03.2005
    Modified byArto Aho