VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

252-0057-00L 7 Credits BSC , SHE D-MATH , D-INFK
You're viewing possible stale or outdated data. Please check the latest semester for more up-to-date information.

Theoretical Computer Science

Theoretische Informatik

Lecturers & Examiners: Prof. em. Dr. Juraj Hromkovic, Dr. Hans-Joachim Böckenhauer
VVZ CR 4.47

Last Updated: 2026-02-05 15:35:14

Abstract

Concepts 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?

Objective

Learning the basic concepts of computer science along their historical development

Content

This 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

Resources

Lecture Notes

The lecture is covered in detail by the textbook "Theoretical Computer Science".

Literature

Basic 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

Learning Materials (Links)

General Information

Language
German
Levels
BSC , SHE
Frequency
Yearly recurring

Examination

Type
session examination
Mode
written 180 minutes
Aids
Keine.
Es 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.

Course Components

Type Title Time & Place Hours
lecture Theoretische Informatik
Aufgrund der Corona-Beschränkungen wird diese Veranstaltung in einem hybriden Modus stattfinden, bestehend aus einem Selbststudium anhand des angegebenen Lehrbuchs und einer Zusammenfassung des Vorlesungsstoffs mit anschliessender Diskussion. Der Lesestoff für jede Woche wird auf der Webseite zur Vorlesung angegeben. Die Zusammenfassung und Diskussion wird im Hörsaal stattfinden. Damit die Abstandsregeln und Platzbeschränkungen eingehalten werden können, werden die Teilnehmenden auf vier Gruppen verteilt, die jeweils einmal pro Woche für 45 Minuten (Dienstag 8-9, Dienstag 9-10, Freitag 10-11 oder Freitag 11-12) an der Diskussion teilnehmen können. Fragen oder Anregungen für die Diskussion können vorgängig per E-Mail schriftlich formuliert werden oder auch spontan während der Diskussion vorgetragen werden. Für alle Teilnehmenden, denen es nicht möglich ist, an physischen Veranstaltungen an der ETH teilzunehmen, werden wir nach Bedarf auch eine Online-Diskussion via Zoom anbieten.
  • Tue 08:15-10:00 (HG E 5)
  • Fri 10:15-12:00 (HG E 5)
4 h weekly
exercise Theoretische Informatik
  • Tue 14:15-16:00 (CAB G 52)
  • Tue 14:15-16:00 (CAB G 59)
  • Tue 14:15-16:00 (IFW A 32.1)
  • Tue 14:15-16:00 (LEE E 101)
  • Tue 14:15-16:00 (LFW C 4)
  • Wed 16:15-18:00 (CAB G 59)
  • Wed 16:15-18:00 (CHN F 42)
  • Wed 16:15-18:00 (ETZ E 7)
  • Wed 16:15-18:00 (LFW B 1)
  • Wed 16:15-18:00 (LFW B 3)
  • Thu 16:15-18:00 (CHN E 46)
  • Thu 16:15-18:00 (CHN G 42)
2 h weekly

Offered In