# 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 01.03.2011 - 05:05