VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Theory of Computing
Theoretische Informatik
Last Updated: 2026-02-05 14:55:13
Abstract
Concepts to cope with: a) what can be accomplished in a fully auto- mated 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
Vermittlung der grundlegenden Konzepte der Informatik in ihrer geschichtlichen Entwicklung
Content
1. Formale Sprachen und Darstellung der algorithmischen Aufgaben. 2. Automatentheorie 3. Turingmachinen als ein formales Modell von Algorithmen 4. Berechenbarkeit 5. Komplexitätstheorie 6. Algorithmik für schwere Probleme 7. Randomisierung und zufallsgesteuerte Systeme 8. Kommunikation
Resources
Lecture Notes
Die Vorlesung ist detailiert durch das Lehrbuch "Theoretische Informatik" bedeckt
Literature
Basislieratur: 1. J. Hromkovic: Theoretische Informatik. Teubner 2004 Weiterführende Litteratur: 2. M. Sipser: Introduction to the Theory of Computation, PWS Publ. Comp.1997 3. J.E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson 2002. 4. I. Wegener: Theoretische Informatik. Teubner Weitere Übungen und Beispiele: 5. A. Asteroth, Ch. Baier: Theoretische Informatik
General Information
- Language
- German
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- written 180 minutes
- Aids
- 2 A4-Seiten handschriftliche Notizen
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Theoretische Informatik |
|
4 h weekly |
| exercise | Theoretische Informatik |
|
2 h weekly |