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

250153 VO Introduction to theoretical computer science (2024S)

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

  • Wednesday 06.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 08.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 13.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 15.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 20.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 22.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 10.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 12.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 17.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 19.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 24.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 26.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 03.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 08.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 10.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 15.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 17.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 22.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 24.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 29.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 31.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 05.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 07.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 12.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 14.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Wednesday 19.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
  • Friday 21.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01

Information

Aims, contents and method of the course

This course is an introduction to recursion theory, Kolmogorov complexity, and computational complexity.

Recursion theory deals with the question of algorithmic solvability of problems, whereas computational complexity aims to classify algorithmically solvable problems based on the amount of resources (time and space) a solution requires. Kolmogorov complexity is a formalization of the concept of randomness.

The two computational models introduced in this course are recursive functions and Turing machines.

Assessment and permitted materials

There will be a written exam in the end of the semester.

Minimum requirements and assessment criteria

To pass the course you need to take the final exam and obtain a score of at least 50 percent.

Examination topics

The material covered on the exam is the same as the material covered in the lectures. You will need to be able to state the definitions and theorems, know the main ideas of their proofs, and be able to apply the course material to solve basic problems.

Reading list

tba

Association in the course directory

MLOI

Last modified: Mo 27.01.2025 12:06