Diese Webseite wird nicht mehr aktualisiert.

Mit 1.10.2022 ist die Fakultät für Physik in der TUM School of Natural Sciences mit der Webseite https://www.nat.tum.de/ aufgegangen. Unter Umstellung der bisherigen Webauftritte finden Sie weitere Informationen.

de | en

Komplexitätstheorie (IN2007)
Complexity Theory (IN2007)

Lehrveranstaltung 0000002557 im SS 2019

Basisdaten

LV-Art Vorlesung mit integrierten Übungen
Umfang 6 SWS
betreuende Organisation Informatik 7 - Lehrstuhl für Theoretische Informatik (Prof. Esparza)
Dozent(inn)en Jan Kretinsky
Termine Di, 10:00–12:00, MI 03.09.014
Di, 12:00–14:00, MI 03.09.014
Mi, 08:00–10:00, MI 03.09.014
Fr, 12:00–14:00, MI 03.09.014
Fr, 14:00–16:00, MI 03.09.014
Mo, 14:00–16:00, MI 03.09.014

Zuordnung zu Modulen

weitere Informationen

Lehrveranstaltungen sind neben Prüfungen Bausteine von Modulen. Beachten Sie daher, dass Sie Informationen zu den Lehrinhalten und insbesondere zu Prüfungs- und Studienleistungen in der Regel nur auf Modulebene erhalten können (siehe Abschnitt "Zuordnung zu Modulen" oben).

ergänzende Hinweise Turing-Maschinen. Zeit-und Platzkomplexität. Schaltkreise als Berechnungsmodell. L, NL, P, NP, PSPACE, EXP, NEXP, PH. Vollständigkeit und fundamentale strukturelle Zusammenhänge zwischen Komplexitätsklassen. Mögliche Vertiefungen und Anwendungen (nicht vollständig): Strukturelle Komplexitätstheorie. Untere Schranken. Deskriptive Komplexitätstheorie. Funktionale Probleme, Optimierungsprobleme und deren Approximation (PCP- Theorem), komplexitätstheoretische Grundlagen der Kryptographie.
Links LV-Unterlagen
TUMonline-Eintrag

Gleiche Lehrveranstaltungen (z. B. in anderen Semestern)

SemesterTitelDozent(en)Termine
WS 2023/4 Complexity Theory (IN2007) Ghoshdastidar, D. Guttenberg, R. Di, 10:00–12:00, MI 03.09.014
Mi, 14:00–16:00, MI 03.09.014
Do, 10:00–12:00, MI 03.09.014
SS 2021 Complexity Theory (IN2007) Ayikudi Ramachandrakumar, B. Ghoshdastidar, D. Mo, 10:00–12:00, virtuell
Di, 14:00–16:00, virtuell
Do, 16:00–18:00, virtuell
SS 2016 Complexity Theory (IN2007) Mo, 10:00–12:00, MI 03.09.014
Di, 14:00–16:00, MI 02.13.010
Mi, 08:00–10:00, MI 02.13.010
SS 2015 Complexity Theory (IN2007) Mo, 14:00–16:00, MI 00.08.038
Di, 12:00–14:00, MI 03.11.018
Do, 14:00–16:00, MI 00.08.038
SS 2014 Complexity Theory (IN2007) Mo, 08:00–10:00, MI 00.13.009A
Do, 10:00–12:00, MI HS3
Do, 12:00–14:00, MI 03.11.018
SS 2013 Complexity Theory (IN2007)
Nach oben