CIS Abroad has joined forces with
CEA CAPA Education Abroad
As part of the CEA CAPA Education Abroad family, you'll find even more opportunities with our expanding global network.
Barcelona SAE has joined forces with
CEA CAPA Education Abroad
As part of the CEA CAPA Education Abroad family, you'll find even more opportunities with our expanding global network.
Automata and Complexity- Period 4
Honors Program Program
Amsterdam, Netherlands
Dates: 1/31/20 - 5/30/20
Automata and Complexity- Period 4
OVERVIEW
CEA CAPA Partner Institution: Vrije Universiteit Amsterdam
Location: Amsterdam, Netherlands
Primary Subject Area: Computer Sciences
Instruction in: English
Course Code: X_401049
Transcript Source: Partner Institution
Course Details: Level 300
Recommended Semester Credits: 3
Contact Hours: 84
DESCRIPTION
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.
Contact hours listed under a course description may vary due to the combination of lecture-based and independent work required for each course therefore, CEA's recommended credits are based on the ECTS credits assigned by VU Amsterdam. 1 ECTS equals 28 contact hours assigned by VU Amsterdam.
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.
Contact hours listed under a course description may vary due to the combination of lecture-based and independent work required for each course therefore, CEA's recommended credits are based on the ECTS credits assigned by VU Amsterdam. 1 ECTS equals 28 contact hours assigned by VU Amsterdam.