Technische Universität Ilmenau

Spezielle Themen der Komplexitätstheorie - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis. Angaben zum Raum und Zeitpunkt der einzelnen Lehrveranstaltungen entnehmen Sie bitte dem aktuellen Vorlesungsverzeichnis.

Fachinformationen zu Spezielle Themen der Komplexitätstheorie im Studiengang Master Informatik 2009
ACHTUNG: wird nicht mehr angeboten!
Fachnummer9186
Prüfungsnummer2200311
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Fachverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusSommersemester
SpracheDeutsch
Leistungspunkte2
Präsenzstudium (h)22
Selbststudium (h)38
VerpflichtungWahlpflicht
Abschlussmündliche Prüfungsleistung, 20 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Vorkenntnisse

Berechenbarkeit und Komplexitätstheorie. Nützlich: Komplexitätstheorie

Lernergebnisse

Tiefes Verständnis für eine effektive Analysetechnik für imperative Programme

Inhalt

SKKT: Zertifizierung von FP/FLINSPACE/FPSPACE für imperative Programme

Die Vorlesung bespricht eine effiziente Methode zur Zertifizierung von

• polynomiellem Zeitbedarf (FP) und
• linearem bzw. polynomiellem Platzbedarf (FLINSPACE bzw. FPSPACE)
für imperative Programme, die aus beliebigen Basisanweisungen mittels Anweisungsfolgen, bedingten Anweisungen und FOR-Schleifen aufgebaut sind. Solche Programme arbeiten auf Variablen X_1, . . . , X_n, wovon jede einen beliebigen Datentyp (Stack, Register, Baum, Graph, usw.) repräsentiert und implizit mit einer Größe |X_i| ausgestattet ist. Fungiert X_i z.B. als Register, so könnte |X_i| die binäre Länge der in X_i gespeicherten Zahl sein. Kern der Methode ist ein effizienter Matrizen-Kalkül für die Zertifizierung der polynomiellen Größenbeschränktheit von imperativen Programmen mit polynomiell größenbeschränkten Basisanweisungen. Das Zertifikat für ein Programm in n Variablen ist eine (n+1)×(n+1)-Matrix über der „Vergissmenge“  {0, 1, unendlich}. Die Methode ist konstruktiv in dem Sinne, dass neben dem Zertifikat auch stets ein Beschränkungspolynom berechnet wird. Die folgenden Charakterisierungstheoreme werden erarbeitet und bewiesen:
• FP = Zertifizierte Stringprogramme (Stack-Programme mit beliebigen polynomialzeitberechenbaren Basisanweisungen)
• FLINSPACE  = Zertifizierte verallgemeinerte Loop-Programme (Loop-Programme mit beliebigen in linearem Platzbedarf berechenbaren Basisanweisungen)
• FPSPACE  = Zertifizierte Power-Stringprogramme (Stringprog. erweitert um Schleifen, deren Rumpf exponentiell oft in der Größe der Kontrollvariablen iteriert wird, mit beliebigen in polynomiellem Platzbedarf berechenbaren Basisanweisungen)

Das Verfahren steht als Java-Applet zur Verfügung. An Schulbeispielen wie binäres Addieren, binäres Multiplizieren oder Insertion-Sort werden wir daher die Theorie laufen lassen, also Zertifikate berechnen und Beschränkungspolynome extrahieren.

Medienformen

Tafel, Folien, Übungsaufgaben.

Literatur

Originalliteratur

Lehrevaluation

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.