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

250153 VO Introduction to theoretical computer science (2025S)

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).

Details

Language: English

Examination dates

Lecturers

Jana Marikova

Classes (iCal) - next class is marked with N

Monday 03.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 05.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 10.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Monday 17.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 19.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 24.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 26.03. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 31.03. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 02.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 07.04. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 09.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 28.04. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 30.04. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 05.05. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 07.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 12.05. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 14.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 19.05. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 21.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 26.05. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 28.05. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 02.06. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 04.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 11.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01
Monday 16.06. 11:30 - 13:00 Seminarraum 10, Kolingasse 14-16, OG01
Wednesday 18.06. 09:45 - 11:15 Seminarraum 10, Kolingasse 14-16, OG01

Information

Aims, contents and method of the course

We will cover some basic recursion theory, and topics from Kolmogorov complexity and from computational complexity.

Assessment and permitted materials

You will need to be able to state definitions and theorems, know the main ideas of their proofs, and solve basic problems.

Minimum requirements and assessment criteria

To pass the class, you need to score at least 50 percent on the final exam.

Examination topics

The material covered in class is the material covered on the exam.

Reading list

L. van den Dries "Recursion theory notes" (see Moodle)
M. Müller "Computational complexity theory" https://www.fim.uni-passau.de/fileadmin/dokumente/fakultaeten/fim/lehrstuhl/muller/TCS.pdf
S. Arora, B. Barak "Computational complexity: a modern approach"
C. Papadimitriou "Computational complexity"

Association in the course directory

MLOI

Last modified: Mo 07.07.2025 09:46