Navigation auf uzh.ch

Suche

Department of Informatics Data Systems and Theory

Foundations of Computing II

This is a second year (3rd semester) course covering topics from discrete math and formal methods building the foundation of computing. The material of this course is pervasive in the areas of algorithms, data structures and programming but appears virtually in all areas of computer science as well. The course will cover topics such as, but not limited to, proof methods, formal languages, deterministic and nondeterministic finite automata, grammars and pushdown automata, Turing machines, computability, decidability and complexity, P and NP, NP-completeness.

Learning Outcomes

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.

Course Topics

  1. Introduction to Computing
  2. Course Organisation
  3. Regular Expressions
  4. Finite Automata
  5. Equivalence of Models
  6. Automata Minimisation
  7. Pumping Lemma, Closure Properties, Algorithms for Regular Languages
  8. Context-free Grammars
  9. Chomsky Normal Forms
  10. Pushdown Automata
  11. Pumping lemma, closure properties, deterministic pushdown automata
  12. Syntax Analysis: CYK algorithm, LL1 LR2
  13. Turing machines
  14. Undecidability, Reductions
  15. Further undecidability results (PCP), Rice's theorem
  16. Universal Turing machine, Semidecidability
  17. P vs NP
  18. Cook's theorem
  19. Further NP-complete problems
  20. Beyond NP

Classes

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

  1. Regular expressions
  2. Finite Automata
  3. Pumping lemma for regular languages, Context Free Grammars
  4. Pushdown automata, pumping lemma, syntax analysis
  5. Turing machines, undecidability
  6. NP-completeness