Arbeitsaufwand:
180 h
|
Nummer INF3421 |
Titel Komplexitätstheorie |
Art der Vorlesung Wahlpflicht |
|---|---|---|
| ECTS | 6 | |
|
Arbeitsaufwand - Kontaktzeit - Selbststudium |
Arbeitsaufwand:
180 h Kontaktzeit:
60 h / 4 SWS Selbststudium:
120 h |
|
| Veranstaltungsdauer | 1 Semester | |
| Häufigkeit des Angebots | Im Wintersemester | |
| Unterrichtssprache | Deutsch | |
| Prüfungsform | Klausur (mündliche Prüfung bei geringer Teilnehmeranzahl) |
|
| Lehrform(en) | Vorlesung | |
| Inhalt | Themen sind u.a. Komplexitätsmaße und ihre grundlegenden Beziehungen, Hierarchiesätze, Reduktion und Vollständigkeit, Alternierung und Schaltkreise, die polynomielle Hierarchie und Komplexität von Fragen der Approximierbarkeit. |
|
| Qualifikationsziele | Die Studierenden haben eine Übersicht über das Gefüge der wichtigsten Komplexitätsklassen und daher einen Bezugsrahmen zur komplexitätsmäßigen Einordnung kombinatorischer Fragestellungen. Sie haben ein Problembewusstsein entwickelt bzgl.\ der anscheinenden notorischen Schwierigkeit der kombinatorischen Fragestellungen sowie der formalen Ungewissheit dieser Sachlage. |
|
| Vergabe von Leistungspunkten/Benotung |
Lehrform
Status
SWS
LP
Prüfungsform
Prüfungsdauer
Benotung
Berechnung
Modulnote (%) |
|
| Teilnahmevoraussetzungen | Es gibt keine besonderen Voraussetzungen. | |
| Dozent/in | Lange | |
| Literatur / Sonstiges | Hopcroft u. Ullman, Introduction to automata theory, languages and computation, 1979 Rogers, The theory of recursive functions and effective computability, 1989 Arora and Barak. Computational complexity: a modern approach, 2009. |
|
| Zuletzt angeboten | nicht bekannt | |
| Geplant für | derzeit nicht geplant | |
| Zugeordnete Studienbereiche | BIOINFM2510, INFM2510, INFM3410, MDZINFM2510, MEINFM3210 | |