Technische Universität Ilmenau

Spezielle Kapitel der Komplexitätstheorie und Berechenbarkeit - Modultafeln of TU Ilmenau

The module lists provide information on the degree programmes offered by the TU Ilmenau.

Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).

You can find all details on planned lectures and classes in the electronic university catalogue.

Information and guidance on the maintenance of module descriptions by the module officers are provided at Module maintenance.

Please send information on missing or incorrect module descriptions directly to modulkatalog@tu-ilmenau.de.

module properties Spezielle Kapitel der Komplexitätstheorie und Berechenbarkeit in degree program Master Informatik 2013
module nameSpezielle Kapitel der Komplexitätstheorie und Berechenbarkeit
module number101183
departmentDepartment of Computer Science and Automation
ID of group 224 (Institut für Theoretische Informatik)
module leaderPD Dr. Karl-Heinz Niggl
credit points5
obligationelective module
requirements
certificate of the module Individual achievements or exams
details of the certificate
signup details for alternative examinations
learning outcome

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.

The module contains the following subjects:
Special Chapters of Complexity Theory and Computability
credit points5
obligationelective module
certificate of the moduleoral examination performance, 30 minutes
term Sommersemester