MARTIN-LUTHER-UNIVERSITÄT HALLE-WITTENBERG LOGISCHE PROGRAMMIERUNG UND DEDUKTIVE DB
Institut für Informatik Sommersemester 2016
Prof. Dr. Stefan Brass [StudIP: Vorlesung]

 

 

Logische Programmierung und deduktive Datenbanken

Ablauf (Planung der zeitlichen Aufteilung)

Hier wird eine ungefähre Übersicht gegeben, wann welcher Stoff behandelt werden soll. Im Laufe des Semesters ist beabsichtigt, die Liste zu aktualisieren, und den tatsächlich behandelten Stoff einzutragen. Selbstverständlich sind alle Angaben unverbindlich.

1. Donnerstag, 07.04.2016:
Kapitel 0: Informationen zur Vorlesung / Organisatorisches (Folie 0-1 bis 0-33)
Kapitel 1: Einführung (Folie 1-1 bis 1-42)
Einführung in das Gebiet. Prädikate. Fakten. Datenbanken als Faktenmenge. Regeln. Definition abgeleiteter Prädikate. Beispiel: Verwandtschaftsbeziehungen. Mehrere Regeln über ein Prädikat zur Formulierung von Disjunktionen. Anfragen. Aufruf eines Prädikats mit verschiedenen Bindungsmustern (Ein-/Ausgabeargumente). Rekursion.
2. Donnerstag, 14.04.2016:
Kapitel 1: Einführung (Folie 1-42 bis 1-88)
Rekursion (Standard-Beispiel: "ancestor"/Vorfahr - transitive Hülle). Bearbeitung von Rekursion bottom-up (Anwendung der Regeln in Pfeilrichtung wie in deduktiven Datenbanken) oder top-down (zielorientiert wie in Prolog). Rekursion in SQL-99. Vergleich von Datalog und Prolog. Benutzung eines Prolog-Systems. Anonyme Variablen. Laden eines Prolog-Programms aus einer Datei. Definitionsmodus und Anfragemodus. Unterbrechen einer Endlos-Rekursion mit Control-C. Debugger, "a" (abort) zum Verlassen des Debuggers. "halt." zum Beenden von Prolog. "help". Motivation für deduktive Datenbanken.
3. Donnerstag, 21.04.2016:
Kapitel 2: Grundlagen der Prädikatenlogik (Wiederholung) (Folie 2-1 bis 2-68)
Signaturen, sortierte und unsortierte Logik. Interpretationen. Variablendeklaration (nur für sortierte Logik nötig). Terme, Formeln. Variablenbelegung. Auswertung von Termen. Wahrheitswert von Formeln, Modell. Bereichsunabhängigkeit und Bereichsbeschränkung (zur effektiven Auswertbarkeit von Formeln bei gegebener Interpretation). Konsistenz, Äquivalenz, logische Folgerung. Einige bekannte Äquivalenzen der Prädikatenlogik. Pränex-Normalform. Konjunktive Normalform, disjunktive Normalform. Literal, Klausel. Substitution. Grundliteral, Grundinstanz einer Klausel, Grundsubstitution für eine Klausel. Skolemnisierung zur Umwandlung beliebiger Formeln in Allaussagen/Klauseln. Bedeutung der Klauselform: Erfüllbarkeitsgleichheit.
4. Donnerstag, 28.04.2016:
Kapitel 2: Grundlagen der Prädikatenlogik (Wiederholung) (Folie 2-68 bis 2-73)
Wiederholung zu Klauseln, Herbrand-Modelle, Bedeutung von Herbrand-Modellen für Allaussagen, Automatisches Beweisen durch Widerspruch mit Umwandlung in Klauseln.
Kapitel 3: Pure Prolog (Folie 3-1 bis 3-31)
Anfrage-Beantwortung als Aufgabe des automatischen Beweisens. Lexikalische SYntax von Prolog. Verschiedene Möglichkeiten zur Repräsentation von Zeichenketten. Interne Datenstrukturen zur Termrepräsentation. Abstrakte Syntax von Prolog. Standardsyntax und Operatorsyntax. Besprechung vordefinierter Operatoren. Prädikat "display".
5. Donnerstag, 12.05.2016:
Kapitel 3: "Pure Prolog" (Folie 3-32 bis 3-51)
Wiederholung zur Operator-Syntax und Standard-Syntax, Listen-Syntax, Beispiele append, member, Diskussion der Rekursion über Listen, Beispiel: Rätsel vom Fährmann, Wolf, Ziege und Kohlkopf. Unterschiede deduktiver Datenbanken und Prolog. Terminierung.
6. Donnerstag, 19.05.2016:
Kapitel 3: "Pure Prolog" (Folie 3-52 bis 3-82)
Definitionen Logisches Programm, Regelkopf, Regelrumpf, Regel über ein Prädikat, Fakt. Definitionen Herbrand-Interpretation, Herbrand-Universum, Herbrand-Basis. Minimales Herbrandmodell. Beispiele für Nicht-minimale Modelle. Gründe, warum man die logischen Formeln nicht so schreibt, dass man nur intendierte Modelle hat. Umwandlung von <- in <-> mittels Clark's CDB. Grenzen der CDB. Positives Wissen explizit, negatives implizit. Existenz und Eindeutigkeit des minimalen Modells (mit Beweis). Beziehung des minimalen Modells zur logischen Folgerung.
7. Donnerstag, 26.05.2016:
Kapitel 3: "Pure Prolog" (Folie 3-83 bis 3-102)
Wiederholung zum T_P-Operator, Einführung in die Verbandtheorie um einen "Grenzwert" für unendliche Iterationen des T_P-Operators zu bekommen, Verband der Herbrand-Interpretationen, Satz: "Eine monotone Abbildung T auf einem vollständigen Verband hat immer einen kleinsten Fixpunkt, und zwar glb({I|T(I)<=I})." Bei unserer Anwendung ist das gerade das minimale Modell. Definition der Iteration einer Abbildung. Satz: Bei stetigen Abbildungen reicht eine omega-fache Iteration um den kleinsten Fixpunkt zu erreichen. "Supported" Modelle (kausale Modelle).
8. Donnerstag, 02.06.2016:
Kapitel 3: "Pure Prolog" (Folie 3-104 bis 3-131)
Wiederholung zur Unifikation, "Occur Check" (Problem und Lösungsalternativen), Allgemeine Resolventenmethode ("Resolution") zum automatischen Beweisen, Lineare Resolution, SLD-Resolution, Sichtweisen: Beweis durch Widerspruch bis zur leeren Klausel (false) oder Vereinfachung der Anfrage bis zur leeren Konjunktion (true), Beispiel für SLD-Herleitung ("SLD Derivation"), Selektionsfunktion, Diskussion der Prolog-Selektionsfunktion ("First Literal"), faire Selektionsfunktionen, formale Definition eines SLD-Resolutions-Schrittes, formale Definition einer SLD-Herleitung/Ableitung, Klassifikation von SLD-Herleitungen (erfolgreich, gescheitert, unendlich, unvollständig), formale Definition der berechneten Antwortsubstitution, Korrektheit und Vollständigkeit der SLD-Resolution für definite Hornklauseln, Probleme bei der Übertragung dieser Aussagen auf Prolog, SLD-Bäume.
9. Donnerstag, 09.06.2016:
Kapitel 3: "Pure Prolog" (Folie 3-99 bis 3-148)
Wiederholung zu SLD-Bäumen, Vierport-Modell des Prolog-Debuggers, praktische Verwendung des Debuggers.
Kapitel 4: Eingebaute Prädikate (Folie 4-1 bis 4-22)
Bindungsmuster, Beziehung von Prädikaten mit Bindungsmustern zu klassischen Prozeduren, formale Behandlung von eingebauten Prädikaten.
10. Donnerstag, 16.06.2016:
Kapitel 4: Eingebaute Prädikate (Folie 4-59 bis 4-82)
...
Kapitel 5: Praktische Prolog-Programmierung (Folie 5-1 bis 5-30)
...
Kapitel 5: Praktische Prolog-Programmierung (Folie 5-21 bis 5-70)
...
Kapitel 6: Bottom-Up Auswertung (Folie 6-1 bis 6-79)
...
11. Donnerstag, 23.06.2016:
Kapitel 7: Magische Mengen (Folie 7-1 bis 7-105)
...
12. Donnerstag, 30.06.2016:
Kapitel 8: Nichtmonotone Negation (Folie 8-1 bis 8-48)
...
13. Donnerstag, 07.07.2016:
Kapitel 9: Answer Set Programmierung (?)
...
14. Donnerstag, 14.07.2016:
Kapitel 10: Constraint Logic Programming (?)
...
Kapitel 11: Integritätsüberwachung, Propagierung von Änderungen (?)
...
Kapitel 12: Implementierung von Prolog (?)
...

 


Stefan Brass (brass@informatik.uni-halle.de), 22. März 2016

Original URL: http://www.informatik.uni-halle.de/~brass/lp16/ablauf.html   [XHTML 1.0 Checked]   [CSS Checked]   [Links Geprüft]   [Impressum]