252-0057-00L  Theoretical Computer Science

SemesterAutumn Semester 2017
LecturersJ. Hromkovic
Periodicityyearly recurring course
Language of instructionGerman
CommentRemark: Students, who already took the course 252-0065-00 Theoretische Informatik (8 KP) are not allowed to register for 252-0057-00 Theoretische Informatik (7 KP).


252-0057-00 VTheoretische Informatik4 hrs
Tue08-10HG G 5 »
Fri08-10HG G 5 »
10.11.08-10HG E 1.2 »
08-10HG E 3 »
08-10HG E 7 »
15.12.08-10HG E 1.2 »
08-10HG E 3 »
08-10HG E 7 »
J. Hromkovic
252-0057-00 UTheoretische Informatik2 hrs
Tue13-15CAB G 59 »
13-15HG E 21 »
13-15ML J 37.1 »
13-15NO C 44 »
Wed15-17ETZ E 7 »
15-17ETZ E 9 »
15-17ETZ G 91 »
15-17HG D 3.3 »
15-17HG G 26.3 »
Thu16-18HG E 33.1 »
16-18HG E 33.5 »
16-18HG F 26.3 »
J. Hromkovic

Catalogue data

AbstractConcepts to cope with: a) what can be accomplished in a fully automated fashion (algorithmically solvable) b) How to measure the inherent difficulty of tasks (problems) c) What is randomness and how can it be useful? d) What is nondeterminism and what role does it play in CS? e) How to represent infinite objects by finite automata and grammars?
ObjectiveLearning the basic concepts of computer science along their historical development
ContentThis lecture gives an introduction to theoretical computer science, presenting the basic concepts and methods of computer science in its historical context. We present computer science as an interdisciplinary science which, on the one hand, investigates the border between the possible and the impossible and the quantitative laws of information processing, and, on the other hand, designs, analyzes, verifies, and implements computer systems.

The main topics of the lecture are:

- alphabets, words, languages, measuring the information content of words, representation of algorithmic tasks
- finite automata, regular and context-free grammars
- Turing machines and computability
- complexity theory and NP-completeness
- design of algorithms for hard problems
Lecture notesThe lecture is covered in detail by the textbook "Theoretical Computer Science".
LiteratureBasic literature:

1. J. Hromkovic: Theoretische Informatik. 5th edition, Springer Vieweg 2014.

2. J. Hromkovic: Theoretical Computer Science. Springer 2004.

Further reading:

3. M. Sipser: Introduction to the Theory of Computation, PWS Publ. Comp.1997
4. J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley 2006.
5. I. Wegener: Theoretische Informatik. Teubner.

More exercises and examples in:

6. A. Asteroth, Ch. Baier: Theoretische Informatik
Prerequisites / NoticeDuring the semester, two non-obligatory test exams will be offered.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits7 credits
ExaminersJ. Hromkovic
Typesession examination
Language of examinationGerman
RepetitionThe performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examinationwritten 180 minutes
Additional information on mode of examinationEs finden zwei freiwillige Zwischenklausuren statt. Um zu den Zwischenklausuren zugelassen zu werden, werden jeweils 50 Prozent der Punkte aus den Übungen benötigt bis zu dem jeweiligen Klausurtermin. Aus den beiden Zwischenklausuren wird eine Durchschnittsnote ermittelt (ggf. Rundung auf nächstbessere Viertelnote). Am Ende des Semesters wählt jeder Teilnehmer eine von zwei Möglichkeiten aus: Entweder Übernahme der Note aus den Zwischenklausuren oder Teilnahme an der Sessionsprüfung.
Written aidsKeine.
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

Main linkInformation
LiteratureJuraj Hromkovic: Theoretische Informatik, 5. Auflage, Springer Vieweg 2014.
Only public learning materials are listed.


No information on groups available.


There are no additional restrictions for the registration.

Offered in

Computational Biology and Bioinformatics MasterMethods of Computer ScienceWInformation
Computer Science BachelorBasic CoursesOInformation
Computer Science Teaching DiplomaPart 1OInformation
Mathematics BachelorCore Courses: Applied Mathematics and Further Appl.-Oriented FieldsWInformation