KomplexitätstheorieModulbeschreibung #40379 / Version 1
- 9 LP
- Mündliche Prüfung
- Benotet
- Sommersemester
- Englisch
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
Zur aktuellen Version (v9)
| Modul / Version | #40379 / #1 |
|---|---|
| Gültigkeit | SS 2014 – SS 2014 |
| Verfügbare Sprache(n) | Englisch |
| Leistungspunkte | 9 |
| Modulverantwortliche*r | Niedermeier, Rolf |
| Benotung | Benotet |
| Prüfungsform | Mündliche Prüfung |
| Lehrsprache(n) | Englisch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Softwaretechnik und Theoretische Informatik |
| Fachgebiet | 34351100 FG Algorithmik und Komplexitätstheorie (AKT) |
Kontakt
| Sekretariat | EN 23 |
|---|---|
| Ansprechpartner*in | Thielcke, Christlinde |
| E-Mail-Adresse | lehre@akt.tu-berlin.de |
| Webseite | https://www.tu.berlin/akt/studium-lehre/lehrveranstaltungen |
Lernergebnisse
Participants of this module can classify discrete computational problems according to their computational complexity using standard complexity classes. They understand structural properties of complexity classes and can make qualitative and quantitative statements about computational complexity questions.
The course is principally designed to impart:
technical skills 50x , method skills 50 x ,system skills 0x …,social skills 0x
The course is principally designed to impart:
technical skills 50x , method skills 50 x ,system skills 0x …,social skills 0x
Lehrinhalte
Introduction into structural complexity theory, with particular emphasis on complexity resources time and space.
Particular topics are:
* complexity classes
* theory of the NP-completeness
* hierarchy theorems and polynomial time hierarchy
* interactive proof systems
Particular topics are:
* complexity classes
* theory of the NP-completeness
* hierarchy theorems and polynomial time hierarchy
* interactive proof systems
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
Arbeitsaufwand und Leistungspunkte
Computational Complexity (Vorlesung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 4 h | 60 h |
| Vor-/Nachbereitung | 15 | 6 h | 90 h |
| 150 h | |||
Computational Complexity (Übung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 6 h | 90 h |
| 120 h | |||
Der Aufwand des Moduls summiert sich zu 270 Stunden. Damit umfasst das Modul 9 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
There is a lecture 4 hours per week presenting the whole course material. The lectures are accompanied by 2-hour tutorials, where an active participation and homework on the work sheets distributed every week is required.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
a) obligatory: Basic course on automata and complexity
b) desirable: Basic knowledge on algorithms
b) desirable: Basic knowledge on algorithms
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Mündliche Prüfung |
| Sprache | Englisch |
Prüfungsbeschreibung (Abschluss des Moduls)
Final oral exam determining the grade (MP).
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Sommersemester.
Maximale teilnehmende Personen
Die maximale Teilnehmerzahl beträgt 0.
Anmeldeformalitäten
Please register at QISPOS or directly at the examination office.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
nicht verfügbar
Empfohlene Literatur
- Christos H. Papadimitriou: Computational Complexity, Addison Wesley, 1994.
- Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Ca mbrid ge University Press, 2009
Zugeordnete Studiengänge
Dieses Modul findet in keinem Studiengang Verwendung.
Computer Science Master with focus “Reliable Systems”
Computer Science diploma
Technical Computer Science Master with focus “Software Engineering”
Technical Computer Science diploma
Computer Science diploma
Technical Computer Science Master with focus “Software Engineering”
Technical Computer Science diploma
Sonstiges
Keine Angabe