Komplexpraktikum/Masterpraktikum/Project Group im WS 2014/2015

Technische Universität Dresden Institut für Theoretische Informatik Lehrstuhl für Automatentheorie

Die Einführungsveranstaltung

findet am 22. Oktober um 14:50 im Raum 3027 statt. Falls Ihnen eine Teilnahme nicht möglich ist, nehmen Sie bitte Kontakt mit Anni-Yasmin Turhan auf.

Position im Studienplan

- Diplomstudiengang Informatik (Diplom- und Bakkalaureatsabschluß), ab 5. Semester; Wahlpflichtveranstaltung (-/-/4)
- Masterstudiengang Informatik; Wahlpflichtveranstaltung (-/-/8)
- Studienfach Computational Logic; Komplexpraktikum (12 credits)

Voraussetzungen

Kenntnisse der Aussagenlogik sind notwendig.
Kenntnisse aus folgenden Vorlesungen sind hilfreich:
- Formale Systeme
- Theoretische Informatik und Logik
- Description Logics

Organisation

In einer Einführungsveranstaltung (siehe oben) werden verschiedene Themen vorgestellt. Die interessierten Studenten können dann ein Thema zur Bearbeitung auswählen. Studenten, die an einer Teilnahme am Praktikum interessiert sind, jedoch an der Einführungsveranstaltung nicht teilnehmen können, sollten Anni-Yasmin Turhan kontaktieren. Jedem Studenten wird abhängig vom gewählten Thema ein Tutor zugewiesen. Während des Semesters werden regelmäßige Treffen des Studenten und seines Tutors abgehalten. Am Ende des Semesters präsentiert der Student die Ergebnisse des Praktikums in einem Vortrag.

Sprache

Die Abschlusspräsentation kann in deutsch oder englisch gehalten werden.

Pflichten der Teilnehmer

Die Teilnehmer sollten die relevante Literatur lesen und diese mit ihrem Tutor diskutieren, um mit dem gewählten Thema vertraut zu werden. Die nötige Implementierungsarbeit (falls vorhanden) sollte in einer strukturierten Weise ausgeführt werden, und muss ordentlich dokumentiert werden. Falls ein Thema von zwei oder mehr Studenten bearbeitet wird, dann ist das Aneignen von Fähigkeiten zur Gruppenarbeit ein weiteres Ziel des Praktikums. Die Ergebnisse des Projekts müssen in einem Praktikumsbericht (~15 Seiten) beschrieben und in einem Vortrag (~30 Minuten) am Semesterende präsentiert werden.
Weiterhin sind die Teilnehmer verpflichtet, genügend Zeit für die Durchführung des Praktikums zu reservieren. Die unbedingte Frist zur Beendigung des Praktikums ist der Beginn des folgenden Semesters, d.h. die Bearbeitungszeit für das Praktikums beträgt ein Semester inklusive der vorlesungsfreien Zeit. Wenn das Praktikum nicht rechtzeitig abgeschlossen werden kann, dann können keine Credits vergeben werden. Es obliegt dem teilnehmenden Studenten, das Praktikum rechtzeitig zu beginnen und Termine mit dem Tutor für regelmäßige Besprechungen während des Semesters zu vereinbaren.

Themen

Bei der Themenauswahl berücksichtigen Sie bitte Ihr Vorwissen. Falls Sie bespielsweise ein Thema im Fachgebiet Beschreibungslogik wählen möchten, dann sollten Sie erfolgreich an der Vorlesung "Description Logics" teilgenommen haben.

(1) Endliche Herbrand-Modelle für Hornklauseln

Man kann die Existenz eines endlichen Herbrand-Modells für bestimmte Mengen von prädikatenlogischen Anti-Hornklauseln in exponentieller Zeit entscheiden. Dieses Entscheidungsproblem ist außerdem ExpTime-hart. Das Ziel dieses Praktikums ist es, die Komplexität des analogen Problems für Mengen von Hornklauseln zu bestimmen. Dazu soll ein Algorithmus entwickelt und/oder untere Schranken mittels eines Härtebeweises gefunden werden.

Es werden grundlegende Kenntnisse über Prädikatenlogik sowie Komplexitätstheorie vorausgesetzt.

Tutor: Stefan Borgwardt

(2) Endliche Herbrand-Modelle für Anti-Hornklauseln

Das Ziel dieses Praktikums ist es, einen Algorithmus zu implementieren, der die Existenz endlicher Herbrand-Modelle für bestimmte Mengen von prädikatenlogischen Anti-Hornklauseln entscheidet. Das Programm soll an vielfältigen Eingabeproblemen getestet werden. Die Programmiersprache kann frei gewählt werden.

Es werden grundlegende Kenntnisse über Prädikatenlogik sowie gute Programmierfähigkeiten vorausgesetzt.

Tutor: Stefan Borgwardt

(3) The Cost of Rough Reasoning

In this project, the student is expected to design, implement and execute different tests for evaluating the practical cost of adding support to new constructors into a reasoner. As a guiding example, the cost of adding support of rough logical constructors is to be analysed. A deep statistical analysis and understanding of the obtained data is expected.

A basic knowledge of statistical tools and methods is desired, but not mandatory.

Tutor: Rafael Peñaloza

(4) Most Specific Generalizations w.r.t. General TBoxes in ELgfp

Dieses Thema zielt auf die Implementierung und Evaluierung von Methoden zur Berechnung des kleinsten gemeinsamen Oberbegriff (least common subsumer) und speziellster Begriff (most specific concept) in der leicht-gewichtigen Beschreibungslogik ELgfp, d.h. EL interpretiert mit größter Fixpunkt Semantik. Im Unterschied zu Standard-EL mit deskriptiver Semantik existieren diese speziellsten Verallgemeinerungen stets in ELgfp und können in polynomieller Zeit berechnet werden. Weiterhin sollte der Student einen Vergleich mit speziellsten Generalisierungen bezüglich deskriptiver Semantik und mit Rollentiefe-beschränkten speziellsten Generalisierungen bezüglich deskriptiver Semantik machen.

Grundlegende Kenntnisse von Beschreibungslogiken und gute Programmierfähigkeiten werden erwartet. Für eine einfachere Verwendung und Integration mit existierenden Programmen (z.B. Elk, Protégé usw.) sollte das Programm auf der OWL API aufbauen.

Literatur
[1] Franz Baader: Least Common Subsumers and Most Specific Concepts in a Description Logic with Existential Restrictions and Terminological Cycles
[2] OWL API

Tutor: Francesco Kriegel

(5) Formale Begriffsanalyse & Aussagenlogik: Von Pseudo-Inhalten zu Implikations-Basen

Ziel dieses Themas ist die Formulierung einer minimalen Theorie von Implikationen, die in einer gegebenen Menge von aussagenlogischen Modellen gelten, und aus der alle anderen Implikationen folgen, die in der gegebenen Modellmenge gelten. Hierfür ist ein Isomorphismus zwischen aussagenlogischen Modellmengen und formalen Kontexten nötig, um bestehende Ergebnisse aus der formalen Begriffsanalyse zu verwenden. Weiterhin sollte der Student einen Algorithmus zur Berechnung der Implikations-Basis angeben. Die Resultate können auf aussagenlogische Basen erweitert werden.

Grundlegende Kenntnisse in Aussagenlogik und Mengenlehre werden erwartet. Weitere Kenntnisse in Logik oder Ordnungstheorie können hilfreich sein.

Literatur
[1] Bernhard Ganter und Rudolf Wille: Formale Begriffsanalyse - Mathematische Grundlagen, Springer Verlag, Heidelberg 1996
[2] Bernhard Ganter: Attribute Exploration with Background Knowledge

Tutor: Francesco Kriegel

Weitere Themen werden noch hinzugefügt.