Universität Wien

250074 VO Introduction to theoretical computer science (2018W)

5.00 ECTS (3.00 SWS), SPL 25 - Mathematik

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

The first course will be on Friday, Oct. 12.

  • Freitag 12.10. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 19.10. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 09.11. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 16.11. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 23.11. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 30.11. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 07.12. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 14.12. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 11.01. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 18.01. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
  • Freitag 25.01. 16:00 - 18:15 (ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

This is an introductory lecture in theoretical computer science, which does not require preliminary knowledge in mathematical logic. The course is divided into two main themes: recursion theory and complexity of computation. In recursion theory we will study the notion of recursiveness, recursive enumerability, oracles, Turing jump and the Turing operator. In complexity theory, we will consider various complexity classes, time and space hierarchy theorems, as well as certain hard (in complexity theoretic sense) problems.

Art der Leistungskontrolle und erlaubte Hilfsmittel

Oral examination.

Mindestanforderungen und Beurteilungsmaßstab

Prüfungsstoff

Content of the lectures.

Literatur

1) A. Arora, B. Barak, "Computational complexity. A Modern Approach". Cambridge University Press, Cambridge, 2009.
2) H. Enderton, "Computability theory. An introduction to recursion theory". Elsevier/academic Press, Amsterdam, 2011
3) C. H. Papadimitriou, "Computational complexity". Addision-Wesley Publishing Company, 1994.

Zuordnung im Vorlesungsverzeichnis

MLOI

Letzte Änderung: Fr 18.11.2022 00:23