Syllabus
Title
5181 Theory of Computation
Instructors
ao.Univ.Prof. Dr. Josef Leydold
Type
PI
Weekly hours
2
Language of instruction
Englisch
Registration
02/06/19 to 02/21/19
Registration via LPIS
Registration via LPIS
Notes to the course
This class is only offered in summer semesters.
Subject(s) Master Programs
Dates
| Day | Date | Time | Room |
|---|---|---|---|
| Monday | 02/25/19 | 09:15 AM - 01:00 PM | TC.3.21 |
| Monday | 03/04/19 | 09:15 AM - 01:00 PM | TC.3.21 |
| Monday | 03/11/19 | 09:15 AM - 01:00 PM | TC.3.21 |
| Monday | 03/18/19 | 09:15 AM - 01:00 PM | TC.3.21 |
| Monday | 03/25/19 | 09:15 AM - 01:00 PM | TC.3.21 |
| Monday | 04/01/19 | 09:15 AM - 01:00 PM | TC.3.21 |
| Monday | 04/08/19 | 09:15 AM - 01:00 PM | TC.3.21 |
This course gives a short introduction into fundamental mathematical properties of computer hardware and software. In studying this subject we seek to determine what can be and what cannot be computed, how quickly, with how much memory, and of which type of computational model. Computational problems are strongly related to the recognition of particular languages, that is, sets of strings over same given alphabet. Thus we will study various types of automata and characterize the kind of languages that can be recognized by their spective type of machine.
- Deterministic Finite Automata
have a finite number of states but no memory. They recognize regular languages which can be described by regular expressions. - Nondeterministic Finite Automata
are similar to deterministic automata except that they allow to run all possible branches of an algorithm in parallel. Interestingly, nondeterministic automata often are not more powerful than their deterministic counterpart. - PushDown Automata
are finite automata with a stack added. They recognize languages which are generated by some context free grammar. - Turing Machines
are the most powerful machines. They have a finite number of states with an infinite tape added that can be both read and written at arbitrary positions. By the Church-Turing thesis our intuitive notion of algorithm is equivalent to Turing machine algorithms. An important difference to the above machines is, that Turing machines may loop forever. If a Turing machine never loops it is called a decider.
Surprisingly there are languages that are not Turing-recognizable, that is, there are computational problems that cannot be solved by any computer. There also are languages that are Turing-recognizable but not decidable, e.g., the halting problem.
Students who have mastered this course understand the concepts behind various types of automata and languages and their relations to each other.They are able to give formal definitions of particular machines and their corresponding languages.They can create an automaton to solve a particular computational problem. Conversely they can describe a language that is recognized by a given automaton and provide a regular expression and context free grammar, respectively, that generates a given language.They also understand why the halting problem is not decidable whyt here exist languages that are not Turing-recognizable. Finally they can estimate running times of algorithms.
Full attendance is compulsory. This means that students should attend at least 80% of all lectures, at most one lecture can be missed.
In each unit of this course new material is presented and discussed. Ideally students have read the corresponding chapter of the book in advance. Students prepare solutions to corresponding exercises and problems for homework which are presented in the next unit. Short quizzes at the end of each unit give feedback about the learning progress.
Grading is based on the following two items:
- Homework (35%).
- Quizzes (short tests) at the end of each unit (65%).
Last edited: 2019-02-22
Back