Universität Wien

250153 VO Introduction to theoretical computer science (2024S)

5.00 ECTS (3.00 SWS), SPL 25 - Mathematik
ON-SITE
Moodle
Fr 17.05. 09:45-11:15 Seminarraum 10, Kolingasse 14-16, OG01

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

Thursday 26.09.2024

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
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: We 08.05.2024 10:46