Automata and Complexity

Vrije Universiteit Amsterdam

Course Description

  • Course Name

    Automata and Complexity

  • Host University

    Vrije Universiteit Amsterdam

  • Location

    Amsterdam, The Netherlands

  • Area of Study

    Computer Science

  • Language Level

    Taught In English

  • Course Level Recommendations

    Upper

    ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.

    Hours & Credits

  • ECTS Credits

    6
  • Recommended U.S. Semester Credits
    3
  • Recommended U.S. Quarter Units
    4
  • Overview

    COURSE OBJECTIVE
    The student is acquainted with important notions and algorithms regarding formal languages, automata, grammars, compilers, computability and complexity.

    This course addresses foundational questions in computer science, such as: "What is a (programming) language?", "How can languages be recognised by computers (automata)", "Which problems can be solved using a class of automata?", "How much time and memory does solving a problem require?".

    The course is divided into three parts: automata & languages, computability theory and quantum computing.

    COURSE CONTENT
    The first part, on automata and languages, deals with the concepts of formal language, grammar, and automaton. Two types of languages are covered: regular and context-free languages. Regular languages are used, e.g., in search queries, in the form of regular expressions. Context-free languages are suitable to describe programming languages. The automata-theoretic counterparts here are finite automata and the more powerful pushdown automata. Pumping lemmas are discussed to determine whether a language is regular or context-free. With each type of language a class of grammars is associated: left-linear and context-free grammars. Parsing algorithms are presented for context-free languages, to determine whether a string is in the language.

    In the second part of the course, on computability theory, the central question is "Which computations can be performed on a computer?". To reason about this question, Turing machines are introduced, as well the Church-Turing thesis, along with examples of undecidable problems: the halting problem and the Post correspondence problem. It is shown how undecidability of new problems can be shown by reduction from a known undecidable problem. Important complexity classes from the complexity hierarchy are discussed, notably P, NP, and NP-complete, together with the corresponding reduction arguments.

    The final part treats basic concepts in quantum computing: qubits, entanglement and quantum-operations. It is shown how quantum computing can improve computing, first using a parity game, and later by introducing Simon’s algorithm. The latter solves a problem in polynomial time, where in the traditional setting the best known solution has an exponential time complexity. We conclude with the quantum and probabilistic complexity classes BQP and BPP.

    TEACHING METHODS
    Lectures and seminars

    TYPE OF ASSESSMENT
    Written exam (plus weekly homework exercises, which can earn up to 0.5 bonus point)

Course Disclaimer

Courses and course hours of instruction are subject to change.

Some courses may require additional fees.