Universität Wien

250153 VO Introduction to theoretical computer science (2025S)

5.00 ECTS (3.00 SWS), SPL 25 - Mathematik
Moodle

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

  • Montag 03.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 05.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 10.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 17.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 19.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 24.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 26.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 31.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 02.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 07.04. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 09.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 28.04. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 30.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 05.05. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 07.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 12.05. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 14.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 19.05. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 21.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 26.05. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 28.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 02.06. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 04.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 11.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Montag 16.06. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
  • Mittwoch 18.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

We will cover some basic recursion theory, and topics from Kolmogorov complexity and from computational 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

L. van den Dries "Recursion theory notes" (see Moodle)
M. Müller "Computational complexity theory" https://www.fim.uni-passau.de/fileadmin/dokumente/fakultaeten/fim/lehrstuhl/muller/TCS.pdf
S. Arora, B. Barak "Computational complexity: a modern approach"
C. Papadimitriou "Computational complexity"

Zuordnung im Vorlesungsverzeichnis

MLOI

Letzte Änderung: Di 17.06.2025 16:26