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 15:06:50
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
Die Veranstaltung ist eine Einführung in die Theoretische Informatik, die die grundlegenden Konzepte und Methoden der Informatik in ihrem geschichtlichen Zusammenhang vorstellt. Wir präsentieren Informatik als eine interdisziplinäre Wissenschaft, die auf einer Seite die Grenzen zwischen Moeglichem und Unmoeglichem und die quantitativen Gesetze der Informationsverarbeitung erforscht und auf der anderen Seite Systeme entwirft, analysiert, verifiziert und implementiert. Die Hauptthemen der Vorlesung sind: - Alphabete, Wörter, Sprachen, Messung der Informationsgehalte von Wörtern, Darstellung von algorithmischen Aufgaben - endliche Automaten, reguläre und kontextfreie Grammatiken - Turing Maschinen und Berechenbarkeit - Komplexitätstheorie und NP-Vollständigkeit - Algorithmenentwurf für schwere Probleme
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
- Levels
- BSC
- 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
Donnerstag 12 - 13 Uhr ist eine Zusatzstunde für Fragen und Problemlösungen
|
|
4 h weekly |
| exercise | Theoretische Informatik |
|
2 h weekly |