Universität Wien

250068 VO Introduction to Theoretical Computer Science (2026S)

6.00 ECTS (4.00 SWS), SPL 25 - Mathematik
Moodle
Di 09.06. 13:15-14:45 Seminarraum 10, Kolingasse 14-16, OG01

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").
Für diese LV an-/abmelden

Details

Sprache: Englisch

Prüfungstermine

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

  • Dienstag 03.03. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 05.03. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 10.03. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 17.03. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 19.03. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 24.03. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 26.03. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 14.04. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 16.04. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 21.04. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 23.04. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 28.04. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 30.04. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 05.05. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 07.05. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 12.05. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 19.05. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 21.05. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 26.05. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 28.05. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 02.06. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 11.06. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 16.06. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 18.06. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Dienstag 23.06. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01
  • Donnerstag 25.06. 13:15 - 14:45 Seminarraum 10, Kolingasse 14-16, OG01

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

This class will be a mathematical introduction to the theory of recursive functions---those that can be computed mechanically. Abstracting from a particular choice for a model of computation, it investigates which functions on natural numbers, and sets of natural numbers, can be defined effectively, and how complex these objects can be. Besides its role for providing a theoretical basis for computer science, the topic has connections to other fields of mathematics, such as to decidability questions (e.g., word problems in algebra), number theory (e.g., diophantine equations), and to the foundations of probability theory (algorithmic randomness).

We will cover the basic theory of recursive functions, and time permitting, also restricted models of computation (finite automata), and topics from computational complexity, including Kolmogorov complexity.

Art der Leistungskontrolle und erlaubte Hilfsmittel

You will need to be able to state definitions and theorems, know the main ideas of their proofs, and solve basic problems.

Mindestanforderungen und Beurteilungsmaßstab

To pass the class, you need to score at least 50 percent on the final exam.

Prüfungsstoff

The material covered in class is the material covered on the exam.

Literatur

I will follow my own notes, but a few useful additional references are

L. van den Dries, Recursion theory notes (see Moodle).
C. Smoryński, Logical Number Theory, I, Springer-Verlag, 1991.
N. Cutland, Computability, Cambridge University Press, 1980.
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
J. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 3rd. ed., Addison-Wesley, 2007.
M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013.

Zuordnung im Vorlesungsverzeichnis

MLOI; ML2; MEL

Letzte Änderung: Fr 27.02.2026 18:07