250074 VO Introduction to theoretical computer science (2018W)
Labels
Registration/Deregistration
Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).
Details
Language: English
Examination dates
Friday
18.01.2019
Wednesday
30.01.2019
Wednesday
13.02.2019
Monday
25.02.2019
Thursday
28.02.2019
Friday
01.03.2019
Thursday
07.03.2019
Lecturers
Classes (iCal) - next class is marked with N
The first course will be on Friday, Oct. 12.
Friday
12.10.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
19.10.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
09.11.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
16.11.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
23.11.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
30.11.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
07.12.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
14.12.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
11.01.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
18.01.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Friday
25.01.
16:00 - 18:15
(ehem.Seminarraum d. Inst. f. Formale Logik, Währinger Straße 25, 2. Stock, Raum 101)
Information
Aims, contents and method of the course
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.
Assessment and permitted materials
Oral examination.
Minimum requirements and assessment criteria
Examination topics
Content of the lectures.
Reading list
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.
Association in the course directory
MLOI
Last modified: Fr 18.11.2022 00:23