Technische Universität Ilmenau

Spezielle Kapitel der Komplexitätstheorie und Berechenbarkeit - 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.

Modulinformationen zum Modul Spezielle Kapitel der Komplexitätstheorie und Berechenbarkeit im Studiengang Master Informatik 2013
ModulnameSpezielle Kapitel der Komplexitätstheorie und Berechenbarkeit
Modulnummer101183
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 224 (Institut für Theoretische Informatik)
Modulverantwortliche(r)PD Dr. Karl-Heinz Niggl
Leistungspunkte5
VerpflichtungWahlpflicht
Voraussetzungen
ModulabschlussEinzelleistungen
Details zum Abschluss
Lernergebnisse

Version 1:  Zertifizierung von FP, FLINSPACE und FPSPACE für imperative Programme


Fachkompetenz:


Die Studierenden kennen die in der Vorlesung vorgestellten Konstruktionen und Beweise im Gebiet der Impliziten Komplexitätstheorie.  Sie kennen die notwendigen Grundlagen aus der Komplexitätstheorie.

Methodenkompetenz:


Die Studierenden können die Konstruktionsmethoden von Beschränkungspolynomen und Zertifikaten präzise beschreiben und die jeweiligen Kriterien für eine Zertifizierung im Fall einer Schleife benennen. Sie können die wesentlichen Konstruktionen und Beweise nachvollziehen und präzise wiedergeben, insbesondere der Nachweis, dass die von einem zertifizierten Programm berechneten Funktionen in einer der fraglichen Komplexitätsklassen (FP, FLINSPACE oder FPSPACE) liegen. Umgekehrt können sie mittels der Basistheoreme zeigen, dass jede  Funktion aus einer der fraglichen  Komplexitätsklassen durch ein zertifiziertes Programm berechnet werden kann.


Version 2:  Polynomialzeit im Kontext funktionaler Programmierung


Fachkompetenz:


Die Studierenden kennen das in der Vorlesung vorgestellte, von Hilbert eingeführte und durch Gödel bekannt gewordene System T, das für das Studium höherstufiger Funktionale und die Entwicklung funktionaler Programmiersprachen grundlegend war.  Ferner kennen sie die Funktionenalgebra BC von  Bellantoni  und  Cook, in dem genau die Funktionen aus FP definiert werden können, sowie das System RA ("ramified affinable" Terms") von Bellantoni, N. und Schwichtenberg, ein Teilsystem von System T, jedoch basierend auf Rekursion auf Notation in allen endlichen Typen, in dem genau die Funktionen aus FP durch RA-Programme berechnet werden können.


Methodenkompetenz:


Die Studierenden können neben Syntax und denotationaler Semantik auch die operationale Semantik von System T (ein via "Reduktionsregeln" basierter Auswertungsmechanismus von T-Programmen) präzise beschreiben und klassische Ergebnisse wie Korrektheit der operationalen Semantik, Starke Normalisierung und Eindeutigkeit der Normalform präzise formulieren und  ihre Beweisstruktur (nach W. Tait) wiedergeben. Ferner können sie die Funktionenalgebra BC präzise beschreiben und die Konstruktion für den Nachweis, dass jede FP-Funktion in BC definierbar ist (die Umkehrung ist einfach), im Kern präzise wiedergeben.


Schließlich können die Studierenden das System RA präzise beschreiben und die Kernideen für seine Konstruktion darlegen. Ferner können sie das induktive Argument, dass jede BC-Funktion in RA definierbar ist, sauber wiedergeben und den vorgestellten Polynomialzeit-Algorithmus zur Auswertung von RA-Programmen in seiner Grundstruktur präzise beschreiben.


Version 3 (alternierend zu Version 1 bzw. Version 2) : Berechenbarkeit


Fachkompetenz:


Die Studierenden kennen die in der Vorlesung vertieften partiell rekursiven Funktionen auf Basis der µ-rekursiven Funktionen sowie die davon abgeleiteten Begriffe der entscheidbaren und rekursiv aufzählbaren Mengen, Nummerierungen für das Rechnen auf nicht-natürlichen Zahlen und Standardnummerierungen der berechenbaren Zahlenfunktionen und ihre Charakterisierung. Sie sind mit den Konzepten Reduzierbarkeit von Problemen und das Rechnen mit Indizes von berechenbaren Zahlenfunktionen vertraut, insbesondere mit dem Fixpunktsatz, dem Satz von Rice und dem Satz von Rice/Shapiro. Ferner kennen sie die Konzepte einer produktiven, kreativen und simplen Menge zur Klärung der Frage, ob es rekursiv aufzählbare, aber nicht entscheidbare  Mengen gibt, die nicht zum Halteproblem H oder dem Selbstanwendungs-problem K äquivalent und somit "leichter" sind. Sie sind mit unlösbaren Problemen wie das Postsche Korrespondenzproblem und der Unentscheidbarkeit der Prädikatenlogik 1. Stufe vertraut, sowie mit einer Variante des ersten Gödelschen Unvollständikeitssatzes, wonach jedes korrekte Beweissystem für arithmetische Formeln unvollständig ist. Sie kennen die arithmetische Hierarchie und die damit verbundenen Fragestellungen.


Methodenkompetenz:


Die Studierenden können mittels µ-Kalkül  bzw. Kalkül  PR der primitiv rekursiven Funktionen nachweisen, dass konkrete einfache Funktionen partiell bzw. primitiv rekursiv sind und grundlegende Abschlusseigenschaften der partiell bzw. primitiv rekursiven Funktionen bzw. der rekursiv aufzählbaren oder entscheidbaren bzw. primitiv rekursiven Mengen gelten.  Sie können die Konstruktion einer Aufzählungsfunktion aller k-stelligen partiell rekursiven Funktionen wiedergeben und mittels des S-m-n-Theorems zeigen, dass man zu jeder aufgezählten Funktion f mit Nummer i die Gödelnummer eines GOTO-Programms berechnen kann, das f berechnet.  Ferner können die Studierenden präzise formulieren und beweisen: Kleenes Normalformsatz und Rekursionssatz, sowie Fixpunktsatz, der Satz von Rice und Rice/Shapiro. Sie können damit die Unentscheidbarkeit von grundlegenden konkreten semantischen Fragen an Programmen zeigen. Die Studierenden können die vorgestellte Codierung der prädikatenlogischen Formeln und Herleitungen in einem vollständigen Kalkül des natürlichen Schließens wiedergeben und die Konstruktion angeben, dass jede partiell rekursive Funktion arithmetisch repräsentierbar und jede rekursiv aufzählbare Menge arithmetisch ist. Sie können die arithmetische Hierarchie definieren und die entscheidbaren und rekursiv aufzählbaren Mengen korrekt einordnen sowie von konkreten Problemen ihre Lage in der Hierarchie angeben.

Das Modul beinhaltet die folgenden Fächer:
Spezielle Kapitel der Komplexitätstheorie und Berechenbarkeit
Leistungspunkte5
VerpflichtungWahlpflicht
Fachabschlussmündliche Prüfungsleistung, 30 Minuten
TurnusSommersemester

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