KomplexitätstheorieModulbeschreibung #40379 / Version 7
- 9 LP
- Mündliche Prüfung
- Benotet
- Winter- und Sommersemester
- Englisch
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
Zur aktuellen Version (v9)
| Modul / Version | #40379 / #7 |
|---|---|
| Gültigkeit | SoSe 2022 – WiSe 2022/23 |
| Verfügbare Sprache(n) | Englisch |
| Leistungspunkte | 9 |
| Modulverantwortliche*r | Nichterlein, André |
| 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
On successful completion, students will be able to:
- estimate the computational costs for solving fundamental problems
- classify discrete computational problems according to their computational complexity using reductions and standard complexity classes
- understand structural properties of complexity classes
- make qualitative and quantitative statements about computational complexity questions
- estimate the computational costs for solving fundamental problems
- classify discrete computational problems according to their computational complexity using reductions and standard complexity classes
- understand structural properties of complexity classes
- make qualitative and quantitative statements about computational complexity questions
Lehrinhalte
Introduction into structural complexity theory, with particular emphasis on complexity resources time and space.
Particular topics are:
- complexity classes
- reductions between problems
- theory of the NP-completeness and the P vs. NP question
- hierarchy theorems and polynomial time hierarchy
- interactive proof systems
Particular topics are:
- complexity classes
- reductions between problems
- theory of the NP-completeness and the P vs. NP question
- 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 | 5 h | 75 h |
| 135 h | |||
Computational Complexity (Übung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 5 h | 75 h |
| 105 h | |||
Lehrveranstaltungsunabhängiger Aufwand
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Prüfungsvorbereitung | 1 | 30 h | 30 h |
| 30 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 tutorials in which distributed work sheets are solved together.
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 |
| Dauer/Umfang | 30 min |
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: Winter- und Sommersemester.
Maximale teilnehmende Personen
Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.
Anmeldeformalitäten
Please register at QISPOS or directly at the examination office.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
verfügbar – Slides will be made available during the lecture period: www.isis.tu-berlin.de
Empfohlene Literatur
- Christos H. Papadimitriou: Computational Complexity, Addison Wesley, 1994.
- Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009
Zugeordnete Studiengänge
Dieses Modul findet in keinem Studiengang Verwendung.
Sonstiges
This course is not offered regularly, you will find detailed information on our website: http://www.akt.tu-berlin.de/menue/teaching/