| 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
|
Printer-friendly version