|
|
|
|
|
[Termine] [Zusammenfassung] [Skript] [Übungen]
| Wann? | Wo? | Wer? | |
| Vorlesungen: | Mo 12.15 - 13.45 | GB IV, HS 112 | Detlef Sieling |
| Do 12.15 - 13.45 | GB IV, HS 112 | Detlef Sieling | |
| Übungen: | Mi 8.30 - 10.00 | Zwischenbau C Rechts | Beate Bollig |
| Übungen: | Mi 8.30 - 10.00 | Zwischenbau C Links | Stefan Droste |
| Übungen: | Do 8.30 - 10.00 | GB V, R 420 | Beate Bollig |
| Übungen: | Do 14.15 - 15.45 | GB IV, R 013 | Stefan Droste |
Die Komplexitätstheorie bietet jedoch Methoden, um Probleme bezüglich ihrer Schwierigkeit zu klassifizieren. Im Mittelpunkt steht dabei die bereits in der Vorlesung Grundbegriffe der Theoretischen Informatik angesprochene NP-Vollständigkeitstheorie. Mit ihr lassen sich inzwischen Tausende von Problemen (darunter das Traveling Salesman Problem, Stundenplanprobleme, Datenbankprobleme, Schedulingprobleme, VLSI-Designprobleme) im folgendem Sinn als gleich schwer klassifizieren. Entweder gibt es für alle diese Probleme polynomielle Algorithmen oder für keines. Die zweite Möglichkeit gilt heute als die weitaus wahrscheinlichere und wird als NP ungleich P-Hypothese bezeichnet.
Nach einer kurzen Wiederholung der NP-Vollständigkeitstheorie wird diese Theorie auf weitere Probleme angewendet und erweitert. Mit der Komplexitätsanalyse eines Problems wird entschieden, welche Teilprobleme eines schwierigen Problems effizient lösbar sind. Dazu gehört auch die Untersuchung, welche schwierigen Probleme dann einfach werden, wenn alle in der Eingabe vorkommenden Zahlen klein sind. Die Beziehungen zwischen Entscheidungsproblemen und Optimierungsproblemen, allgemeiner Suchproblemen, werden untersucht. Einen Schwerpunkt bildet die Komplexitätstheorie für Approximationsprobleme, dies sind Optimierungsprobleme, bei denen wir mit fast optimalen Lösungen zufrieden sind. Erst die relativ neue PCP-Theorie erlaubt es, für viele Approximationsprobleme zu entscheiden, ob sie schwierig sind. Die strukturelle Komplexitätstheorie wird nur kurz gestreift. Danach wird die Komplexität von der Ressource Rechenzeit auf die Ressource Speicherplatz erweitert.
Große Teile der Komplexitätstheorie sind softwareorientiert. Am Ende der Vorlesung werden Einblicke in die hardwareorientierte Komplexitätstheorie präsentiert.
Allgemein ist es ein Hauptziel, den Bezug der theoretischen Ergebnisse zu praktischen Fragestellungen herzustellen.
In der Skriptenverkaufsstelle ist eine korrigierte Version des KT-Skripts von Ingo Wegener WS 2000/01 erhältlich, nach dem sich die Vorlesung im Wesentlichen richtet.
Weiterhin ist es möglich, dieses Skript unter dem Namen kt-ws01 mit Hilfe des lprdoc-Befehls auf dem nd50-Drucker auszudrucken (siehe auch die entsprechende WWW-Seite der IRB unter "Vorlesungsmitschriften").
Eine Liste mit den uns bekannten Fehlers des Skripts ist hier als Postscript- bzw. PDF-Datei verfügbar.
Eine Erweiterung des Skripts zu Kapitel 8 ist hier als gezipte Postscript- bzw. PDF-Datei verfügbar.
Eine Ergänzung des Skripts zu Kapitel 13 ist hier als gezipte Postscript- bzw. PDF-Datei verfügbar.
Eine Ergänzung des Skripts zu Kapitel 14 ist hier als gezipte Postscript- bzw. PDF-Datei verfügbar.
Eine Übersicht der in der in der Vorlesung behandelten Themengebiete findet man hier als gezipte Postscript- bzw. PDF-Datei
Für eine Übersicht der wichtigsten Resultate der Stochastik empfehlen wir neben einführenden Büchern zur Wahrscheinlichkeitsrechnung bzw. -theorie insbesondere das Buch Randomized Algorithms von Rajeev Motwani und Prabhakar Raghavan (Cambridge University Press, 1995).
Ansprechpartnerin bzw. -partner bezüglich der Übungen sind Beate Bollig und Stefan Droste.
 |
Startseite | Lehre | Team | Service |
 |
 |
 |
|
 |
|
||||