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.
Tatsächlicher Ablauf:
- 1. Donnerstag, 06.04.2017:
- Kapitel 0: Informationen zur Vorlesung / Organisatorisches
(Folie 0-1 bis 0-36)
Kapitel 1: Einführung
(Folie 1-1 bis 1-37, 1-49 bis 1-56)
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, 13.04.2017:
- Kapitel 1: Einführung
(Folie 1-34 bis 1-77)
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.
Vergleich mit anderen Lösungen zur Integration
von Programmiersprache und Datenbank.
Vergleich mit Prolog.
- 3. Donnerstag, 20.04.2017:
- 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, 27.04.2017:
- 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-34)
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".
Kurzeinführung zu Listen.
- 5. Donnerstag, 04.05.2017:
- Kapitel 3: "Pure Prolog"
(Folie 3-32 bis 3-61)
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.
Definitionen Logisches Programm,
Regelkopf, Regelrumpf,
Regel über ein Prädikat,
Fakt.
Definitionen Herbrand-Interpretation,
Herbrand-Universum,
Herbrand-Basis.
- 6. Donnerstag, 11.05.2017:
- Kapitel 3: "Pure Prolog"
(Folie 3-71 bis 3-76, 3-94 bis 3-115)
Wiederholung zu Substitutionen.
Unifikation, Unifikator, allgemeinster Unifikator.
"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"),
formale Definition eines SLD-Resolutions-Schrittes.
- 7. Donnerstag, 18.05.2017:
- Kapitel 3: "Pure Prolog"
(Folie 3-114 bis 3-148)
Wiederholung zum SLD-Resolutions-Schritt.
Selektionsfunktion,
Diskussion der Prolog-Selektionsfunktion ("First Literal"),
faire Selektionsfunktionen,
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.
Vierport-Modell des Prolog-Debuggers,
praktische Verwendung des Debuggers.
- 8. Donnerstag, 01.06.2017:
- Kapitel 3: "Pure Prolog"
(Folie 3-61 bis 3-93)
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.
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).
- 9. Donnerstag, 08.06.2017:
- Kapitel 4: Eingebaute Prädikate
(Folie 4-1 bis 4-40)
Bindungsmuster,
Beziehung von Prädikaten mit Bindungsmustern
zu klassischen Prozeduren,
formale Behandlung von eingebauten Prädikaten.
Eingebaute Prädikate von Prolog:
Term-Vergleich (=, ==, \=, \==, @> @< ...),
Term-Klassifikation
(var, nonvar, atom, atomic, integer, number, ...),
Zugriff auf Komponenten von Termen und Term-Synthese
(=.., functor, arg, name, ...),
arithmetische Prädikate (is, =:=, =\=, <, =< >=, >),
String-Funktionen,
Prädikate zur Ausführung von Anfragen
(call, findall, bagof, setof),
dynamische Datenbank
(dynamic, assert, retract, retractall, listing),
Ein-/Ausgaben (kurzer Überblick).
- ...
Planung
(unverbindlich, wird noch aktualisiert):
- 10. Donnerstag, 15.06.2017:
- 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, 22.06.2017:
- Kapitel 7: Magische Mengen
(Folie 7-1 bis 7-105)
...
- 12. Donnerstag, 29.06.2017:
- Kapitel 8: Nichtmonotone Negation
(Folie 8-1 bis 8-48)
...
- 13. Donnerstag, 06.07.2017:
- Kapitel 9: Answer Set Programmierung
(?)
...
- 14. Donnerstag, 13.07.2017:
- 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),
10. April 2017
URL:
http://www.informatik.uni-halle.de/~brass/lp17/ablauf.html
[XHTML 1.0 Checked]
[CSS Checked]
[Links Geprüft]
[Impressum]