Technische Universität Ilmenau

Spezielle Themen der Komplexitätstheorie - Modultafeln der TU Ilmenau

Die Modultafeln 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.

Informationen und Handreichungen zur Pflege von Modulbeschreibungen durch die Modulverantwortlichen finden Sie unter Modulpflege.

Hinweise zu fehlenden oder fehlerhaften Modulbeschreibungen senden Sie bitte direkt an modulkatalog@tu-ilmenau.de.

Modulinformationen zu Spezielle Themen der Komplexitätstheorie im Studiengang Master Informatik 2009
ACHTUNG: wird nicht mehr angeboten!
Modulnummer9186
Prüfungsnummer2200311
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Modulverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusSommersemester
SpracheDeutsch
Leistungspunkte2
Präsenzstudium (h)22
Selbststudium (h)38
VerpflichtungWahlmodul
Abschlussmündliche Prüfungsleistung, 20 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse

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

Lernergebnisse und erworbene Kompetenzen

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 und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

Tafel, Folien, Übungsaufgaben.

Literatur

Originalliteratur

Lehrevaluation