Prüfung
BTU-Vorlesungsverzeichnis ↗- Sonntag—01:00 bis 02:30mündliche Prüfung, Terminvereinbarung mit Teilnehmern, Ort: HG, Raum 2.19
← Zurück zur Übersicht
11449Fakultät 1 – MINT – Mathematik, Informatik, Physik, Elektro- und Informationstechnik
Strukturelle Komplexitätstheorie
Titel auf Englisch: Structural Complexity Theory
Lernergebnisse
- das Kennenlernen sinnvoller Ressourcen zur Beurteilung der Komplexität eines Problems,
- das Verständnis für die grundlegende Struktur von Komplexitätsaussagen, …
Inhalte
- Wie misst man sinnvoll den Aufwand, der nötig ist, ein Problem algorithmisch zu lösen?
- Welche Ressourcen spielen dabei eine Rolle?
- Wie lassen sich Probleme hinsichtlich dieser Ressourcen sinnvoll vergleichen und klassifizieren?
- Was sind inhärente Hindernisse, die der Existenz beliebig guter Lösungen gewisser Probleme entgegen stehen?
- Turingmaschine, Zeit- und Platzverbrauch einer Rechnung
- Komplexitätsklassen bzgl. Zeit- oder Platzbedarf
- Hierarchiesätze
- die Klassen P und NP als Formalisierung effizient lösbarer und effizient verifizierbarer Probleme
- NP-Vollständigkeit, Reduktion
- Satz von Cook: NP-Vollständigkeit von SAT
- weitere Bsp. NP-vollständiger Probleme
- Randomisierte Algorithmen und die Klassen ZPP, RP und BPP
- Komplexitätsklassen innerhalb von P: Paralleles Rechnen und NC
- Komplexitätsklassen jenseits von NP: die Polynomhierarchie, PSPACE und NSPACE, Zählklassen
- Ausblicke auf andere Zugänge zu Komplexität
Voraussetzungen
Verpflichtende Voraussetzungen
Keine
Empfohlene Voraussetzungen
Prüfungsmodalitäten
Mündliche Prüfung, 30-45 Minuten
Termine im WiSe 26/27
Die einzigen Termine im WiSe 26/27 sind Prüfungstermine – gelehrt wird das Modul in diesem Semester nicht.
Angeboten in
- Angewandte MathematikM.Sc.
Wahlpflichtkomplex: Anwendungen
- Angewandte MathematikM.Sc.
Wahlpflichtkomplex: Informatik
- InformatikM.Sc.
Wahlpflichtkomplex: Grundlagen der Informatik
| Studiengang | Abschluss | Wahlpflichtkomplex |
|---|---|---|
| Angewandte Mathematik | M.Sc. | Anwendungen |
| Angewandte Mathematik | M.Sc. | Informatik |
| Informatik | M.Sc. | Grundlagen der Informatik |
Literatur und Materialien
- M. R. Garey, D. S. Johnson: Computers and Intractability, Freeman 1979
- C. H. Papadimitriou: Computational Complexity, Addison & Wesley 1994
- I. Wegener: Komplexitätstheorie, Springer 2003
- J. L. Balcazar, J. Diaz, J. Gabarro: Structural Complexity I + II, Springer 1995
- S. Arora, B. Barak: Computational Complexity, Cambridge University Press 2009
Bewertungen von Studierenden
Was Studierende über dieses Modul sagen. Die BTU hat damit nichts zu tun — hier schreiben nur Studierende, und jede Bewertung ist die Meinung einer einzelnen Person.