Navigation auf uzh.ch

The goal of the course is to familiarize the student with formal methods of computing and their value for computer science and related disciplines, and to provide basic training in applying formal methods to many different kinds of problems. Students should learn the fundamental limits of computation and extend their knowledge on formal languages as well as on formal programming models. Principles of interference, deduction, induction and contradiction should regularly be applied to demonstrate the formal correctness of models and limits.

- Introduction to Computing
- Course Organisation
- Regular Expressions
- Finite Automata
- Equivalence of Models
- Automata Minimisation
- Pumping Lemma, Closure Properties, Algorithms for Regular Languages
- Context-free Grammars
- Chomsky Normal Forms
- Pushdown Automata
- Pumping lemma, closure properties, deterministic pushdown automata
- Syntax Analysis: CYK algorithm, LL1 LR2
- Turing machines
- Undecidability, Reductions
- Further undecidability results (PCP), Rice's theorem
- Universal Turing machine, Semidecidability
- P vs NP
- Cook's theorem
- Further NP-complete problems
- Beyond NP

There are six classes, every other week starting week 3, and an exam revision at the end of the semester.

- Regular expressions
- Finite Automata
- Pumping lemma for regular languages, Context Free Grammars
- Pushdown automata, pumping lemma, syntax analysis
- Turing machines, undecidability
- NP-completeness