Universität Wien FIND

Bedingt durch die COVID-19-Pandemie können kurzfristige Änderungen bei Lehrveranstaltungen und Prüfungen (z.B. Absage von Vor-Ort-Lehre und Umstellung auf Online-Prüfungen) erforderlich sein. Melden Sie sich für Lehrveranstaltungen/Prüfungen über u:space an, informieren Sie sich über den aktuellen Stand auf u:find und auf der Lernplattform moodle.

Weitere Informationen zum Lehrbetrieb vor Ort finden Sie unter https://studieren.univie.ac.at/info.

Achtung! Das Lehrangebot ist noch nicht vollständig und wird bis Semesterbeginn laufend ergänzt.

250074 VO Introduction to theoretical computer science (2019W)

5.00 ECTS (3.00 SWS), SPL 25 - Mathematik

An/Abmeldung

Details

Sprache: Englisch

Prüfungstermine

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

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

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

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.

Art der Leistungskontrolle und erlaubte Hilfsmittel

Oral examination.

Mindestanforderungen und Beurteilungsmaßstab

Prüfungsstoff

Content of the lectures.

Literatur

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.

Zuordnung im Vorlesungsverzeichnis

MLOI

Letzte Änderung: Mi 18.11.2020 15:08