Students can
- recognize, formally describe and analyze finite automata (K2, K4, K5)
- rigorously prove fundamental limitations of finite automata (keyword: pumping lemma) (K4, K3, K6)
- recognize, formally describe and analyze Turing machines (K2, K4, K5)
- are able to prove fundamental limitations of Turing machines with mathematical rigor (keyword: Halting theorem) (K4, K3, K6)
- recognize and formally describe the most important complexity classes -- P, NP, PSPACE, PSIZE, P/poly EXP -- and classify existing computing challenges into these (K2, K4, K5)
- explain the connection between NP and SAT (keywords: Cook-Levin theorem) intuitively and rigorously (K4, K5)
- independently perform Karp reductions of a given NP-complete problem to SAT (K3, K4, K6)
- Knowledge and understanding of the polynomial hierarchy and how to use a collapse of it for rigorous implications (K2, K3, K4, K5)
- Recognize, formally describe and analyze logical circuits (K2, K4, K5)
- Translate complexity statements from the Turing machine model into the circuit model and vice versa (K2, K3, K4)
|
- logical/mathematical thinking
- understanding, appreciating and performing proofs
- fundamental limits of computability
- landscape of complexity theory
- and how to use it for arguments
- switch between software model (Turing machine) and hardware model (logical circuits)
|
