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 (2019W)

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

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

  • Thursday 03.10. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 10.10. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 17.10. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 24.10. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 31.10. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 07.11. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 14.11. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 21.11. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 28.11. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 05.12. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 12.12. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 09.01. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 16.01. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 23.01. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48
  • Thursday 30.01. 09:00 - 12:00 Seminarraum , UZA Augasse 2-6, 5.Stock Kern D SR5.48

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: We 18.11.2020 15:08