582206 Models of Computation (ohtk 25.8.2011)

  • Principal theme
Prerequisite knowledge Approaches the learning objectives Reaches the learning objectives Deepens the learning objectives
Fundamentals of theoretical computer science
  • fundamentals of set theory and logic (Introduction to discrete mathematics)
  • basic proof techniques (Introduction to discrete mathematics)
  • explains the functionality of simple algorithms with the help of invariants (Data structures)


  • describes an algorithmic problem using precise natural language and simple mathematical formalism; reads and interprets such descriptions
  • creates simple chains of reasoning based on the concepts defined in the course


  • explains in own words basic textbook-level theoretical computer science text including the details of constructions and proofs
  • solves simple problems with valid and logically structured proofs based on the concepts presented in the course
  • by reading an article on theoretical computer science understands its basic problems and results
  • creates precise, non+trivial arguments about how an algorithm works
Automata and grammars
  • fundamentals of set theory and logic (Introduction to discrete mathematics)
  • basic definitions of graphs (Introduction to discrete mathematics)
  • uses queues, lists and tree structures as parts of normal programming (Data structures)
  • implements the traversing of graphs, path finding, and spanning trees for solving various graph problems (Data structures)
  • creates automata and grammars for simple formal languages from a verbal or mathematical description; describes the language of an automaton or a grammar
  • uses known algorithms to convert an automaton to a grammar and vice versa
  • proves a language non-regular using known methods
  • applies the closure properties and other basic properties of language classes and shows the constructions underlying these properties
  • applies finite automata, grammars and tools based on them to solve programming tasks
  • uses state automata to model e.g. distributed computing
Decidability and computational complexity as above
  • explains the Churchin-Turingin thesis and its central justifications and implications
  • recognises some central undecidable problems and explains the implications of their undecidability for practical programming
  • proves basic results about decidability
  • recognises basic examples of polynomial and exponential time complexity and NP completeness; explains the meaning of these issues on a very general level
  • studies the decidability of formal reasoning (Mathematical logic)
  • recognises several NP complete problems
  • solves NP complete problems with heuristic and approximation algorithms
28.08.2011 - 18:18 Jyrki Kivinen
01.03.2011 - 05:05 Jyrki Kivinen