250074 VO Introduction to theoretical computer science (2018W)
Labels
An/Abmeldung
Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").
Details
Sprache: Englisch
Prüfungstermine
Freitag
18.01.2019
Mittwoch
30.01.2019
Mittwoch
13.02.2019
Montag
25.02.2019
Donnerstag
28.02.2019
Freitag
01.03.2019
Donnerstag
07.03.2019
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.
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