KI Artificial Intelligence Group - Dept. of Computer Science - TU Berlin
[ KI Home | Members | Publications | Research | Courses | Events | Support ]

Künstliche Intelligenz und Software-Engineering

(LV 1332 L 705)

Seminar im WS 00/01


Veranstalter Organisation Themen Einführungsvorträge Literatur Blockveranstaltung Mailingliste

Eine gemeinsame Veranstaltung von KI und UEBB


Organisation

Themen

Im Seminar werden Konzepte und Methoden der induktiven Synthese funktionaler und logischer Programme und Programmtransformation diskutiert. Wir wollen dabei sowohl die Grundlagen aufarbeiten, sowie (je nach Interesse der TeilnehmerInnen) auch den aktuellen Forschungsstand und Anwendungen betrachten. Dabei interessieren uns insbesondere auch die Überschneidungen zwischen diesen Gebieten der sogenannten "Automatischen Programmierung".

Deduktive Programmsynthese/Transformationelle Programmentwicklung

Im Zentrum der deduktiven Programmsynthese steht die Entwicklung von Programmen aus Spezifikationen mit Hilfe logischer Deduktionsmittel. Die Spezifikationen können dabei in verschiedenen Formen vorliegen: als algebraische Spezifikationen, als Pre- und Postconditions, usw. Die transformationelle Programmentwicklung ist eine verwandte Methode, welche auf der bedeutungserhaltenden Transformationen von Spezifikationen und/oder Programmen in mehreren Schritten basiert, und nicht nur für die Synthese aus Spezifikation, sondern auch für die (teilweise vollautomatische) Optimierung von Programmen verwendet wird (z.B. Vereinfachung von Rekursionsklassen: Überführung von lineare Rekursion in Tailrekursion (Schleifen)).

Im Seminar sollen der Transformationsansatz CIP, das Programmsynthese-System KIDS [KIDS Homepage], und "reverse transformation" (Umwandlung von Tailrekursion in lineare Rekursion) behandelt werden.

Induktive Programmsynthese

Während Systeme, die auf deduktiven Ansätzen basieren, vor allem die Erstellung korrekter bzw. effizienter Programme unterstützen, hat der Bereich induktive Programmsynthese das Ziel, Programme aus unvollständiger Information zu induzieren (manchmal als auto-magic programming bezeichnet). Üblicherweise gibt der Programmierer I/O Beispiele vor. Gesucht ist dann das rekursive Programm, das alle Beispiele korrekt transformiert und eine minimale Generalisierung dieser Transformationen ist (d.h. es werden keine überflüssigen Berechnungsschritte erzeugt). Alternativ kann induktive Programmsynthese auch von Berechnungsspuren ausgehen (programming by demonstration). Bei Induktion kann natürlich nie Korrektheit garantiert werden (wenn man aus der Beobachtung von n Schwänen schließt, daß alle Schwäne weiß sind, kann man sich eben täuschen, da man ja immer nur Beispiele, nie die Grundgesamtheit der Schwäne zu Gesicht bekommt). Anders als bei den deduktiven und transformationalen Ansätzen ist die Anwendung daher eher im Bereich von Tutorsystemen zur Unterstützung von Programmieranfängern oder der Entlastung von Programmieren von einfachen Routineaufgaben zu suchen. Induktive Programmsynthese ist ein spannendes Thema für die Grundlagenforschung: Menschen - zumindest einige - sind in der Lage aus einigen Beispielen die rekursive Berechnungsvorschrift zu induzieren; gibt es Algorithmen, die diese Intelligenzleistung erbringen können?

Im Seminar sollen grundlegende Ansätze und aktuelle, anwendungsbezogene Arbeiten zur induktiven funktionalen und logischen Programmierung dargestellt werden:


Einführungsvorträge


Literatur

Thema: Induktive Synthese funktionaler Programme

Thema: Induktive Logische Programmierung

Thema: Programm Transformation


Blockveranstaltung

Freitag, den 26.1.01, ab 10 Uhr in FR 5045

Mailingliste

[mailto Seminar-Veranstalter und Teilnehmer]

[mailto Teilnehmer -- Thema "Induktive Synthese Funkt. Prog."]

[mailto Teilnehmer -- Thema "ILP"/"Transformation"]


(schmid, 03.11.2000)