Beweiskomplexität - Interaktive Studienpläne der TU Ilmenau
Die Interaktiven Studienpläne sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.
Die rechtsverbindlichen Studienpläne entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).
Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im elektronischen Vorlesungsverzeichnis.
Bitte beachten Sie, dass auf dieser Seite keine Aktualisierungen mehr vorgenommen werden. Alle Module und Studienpläne ab der PO-Version 2021 (Bachelor- und Master-Studiengänge) sind ab sofort im Campus-Portal erreichbar.
| Modulinformationen zu Beweiskomplexität im Studiengang Master Informatik 2021 | |
|---|---|
| Modulnummer | 201114 |
| Prüfungsnummer | 2200862 |
| Fakultät | Fakultät für Informatik und Automatisierung |
| Fachgebietsnummer | 2242 (Algorithmik) |
| Modulverantwortliche(r) | Prof. Dr. Christoph Berkholz |
| Turnus | Wintersemester |
| Sprache | Deutsch |
| Leistungspunkte | 5 |
| Präsenzstudium (h) | 34 |
| Selbststudium (h) | 116 |
| Verpflichtung | Wahlmodul |
| Abschluss | mündliche Prüfungsleistung, 30 Minuten |
| Details zum Abschluss | |
| Link zum Moodle-Kurs | https://moodle.tu-ilmenau.de/course/view.php?id=1700 |
| Lehrende | Prof. Berkholz |
| Anmeldemodalitäten für alternative PL oder SL | |
| max. Teilnehmerzahl | |
| Vorkenntnisse | Aussagenlogik, Komplexitätstheorie und lineare Algebra aus den Bachelor-Grundvorlesungen |
| Lernergebnisse und erworbene Kompetenzen | Die Studierenden kennen grundlegende Resultate und Methoden der Beweiskomplexität und können Beweissysteme hinsichtlich ihrer Effizienz vergleichen. Sie wissen, wie Grenzen von Algorithmen mit Hilfe der Beweiskomplexität bewiesen werden können und sind in der Lage, die Vor- und Nachteile verschiedener algorithmischer Strategien zu beurteilen. |
| Inhalt | In der Beweiskomplexität wird die Frage, was sich effizient beweisen lässt, für konkrete Beweissysteme untersucht. Diese Systeme weisen häufig einen engen Zusammenhang zu Algorithmen für NP-schwere Probleme auf. Bekanntestes Beispiel ist der Resolutionskalkül, welcher die Grundlage für nahezu alle modernen SAT-Solver bildet. Die Lehrveranstaltung gibt eine Einführung in die Konzepte und Methoden der Beweiskomplexität und ihrer Anwendung in der Analyse von Algorithmen für NP-schwere Probleme. Neben dem Resolutionskalkül werden auch algebraische und semi-algebraische Beweisysteme und die entsprechenden Algorithmen vorgestellt. Beispielsweise: - Polynomial Calculus und Buchberger's Gröbnerbasis-Algorithmus - Cutting Planes und das Schnittebenenverfahren - Sum-of-Squares und semidefinite Optimierung |
| Medienformen und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form | Tafelvortrag, Beamerpräsentation, Skript, Übungsblätter |
| Literatur | Samuel R. Buss and Jakob Nordström: Proof Complexity and SAT Solving. In: Handbook of Satisfiability (2nd ed., 2021), Chapter 7. https://doi.org/10.3233/FAIA200990
Jan Krajícek: Proof Complexity. Cambridge University Press (2019). |
| Lehrevaluation | |