Universität Wien
Warning! The directory is not yet complete and will be amended until the beginning of the term.

250074 VO Introduction to theoretical computer science (2018W)

5.00 ECTS (3.00 SWS), SPL 25 - Mathematik

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).
Register/Deregister for this course

Details

Language: English

Examination dates

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.

Association in the course directory

MLOI

Last modified: Fr 18.11.2022 00:23