Inhaltsübersicht
1. Einführung
- Grundbegriffe: Fakten, Anfragen, logische Variable,
Substitution, existenzielle Anfragen, universelle Fakten, konjunktive
Anfragen, Regeln, operationale und deklarative Sicht auf Regeln,
logisches Programm.
- Abstrakter Interpreter für logische Programme als
indeterministisches Programm (ohne Unifikation).
Literatur: [1, Kapitel 1]
2. Rekursive Programme
- Datentypen als unäre Prädikate
- Listen und Operationen auf Listen, Vergleich von Prolog- und
imperativem Programm (am Beispiel Teilliste)
- Akkumulatoren als Programmiertechnik
Literatur: [1, Kapitel 3.2 & 3.3]
3. Unifikation
- Unifikator, Quasiordnung auf Substitutionen, allgemeinster
Unifikator
- Unifikationsproblem, Unifikationsproblem in gelöster Form,
Unifikationsalgorithmus
- Satz über den Unifikationsalgorithmus: Termination, Korrektheit,
Vollständigkeit
- Abstrakter Interpreter für logische Programme als
indeterministisches Programm (mit Unifikation)
Literatur: [2, Kapitel 4.5 & 4.6]
4. Semantik logischer Programme
- Prädikatenlogik: Syntax, Semantik, Interpretation, Wahrheit
- Allgemeingültigkeit, Erfüllbarkeit (Konsistenz), Modell,
Folgerbarkeit, semantische Äquivalenz
- Herbrand-Universum, Herbrand-Interpretation, Herbrand-Expansion,
kleinstes Herbrand-Modell
- Definites Programm, SLD-Ableitung, SLD-Widerlegung, Erfolgsmenge
- Korrektheit der SLD-Resolution (Satz von Clark)
- Fixpunkte, Monotonie, Stetigkeit, Fixpunktsätze von
Knaster-Tarski und Kleene (ohne Beweis)
- Fixpunktcharakterisierung des kleinsten Herbrand-Modells eines
definiten Programms.
- Korrektheit der SLD-Resolution (Satz von Apt & van Emden,
Satz von Clark)
Literatur: [3, Kapitel 5 & 8.3], [4, §§ 5-8]
5. Ausserlogische Erweiterungen von Prolog
- Cut-Operator, SLD-Baum, grüne und rote Cuts
- Negation als Fehlschlagen, im Endlichen erfolglosesr SLD-Baum,
Implementierung von Negation mit Hilfe von Cut
- Weitere Anwendungen des Cut: Weglassen von Bedingungen,
Endrekursion
Literatur: [1, Kapitel 11]
6. Progammiertechniken
- Differenz-Listen, Herleitung von Akkumulatoren
- Implementierung von Tabellen (im Sinn von partiellen Abbildungen)
- Parser für definite Klauselgrammatiken
Literatur: [1, Kapitel 15 & 19]
7. Constraint-Programmierung (Programmierung mit Randbedingungen)
- Generate-and-Test als Paradigma zur Lösung kombinatorischer
Probleme
- Erweiterung der operationalen Semantik von logischen Programmen
auf constraint-logische Programme
- Constraint-Systeme und deren Eigenschaften, Löser für
Constraint-Systeme
- Lokale Propagation, arc-Konsistenz, Algorithmus zur Berechnung
lokal konsistenter Domains AC-3.
- Anwendungen
Literatur: [1, Kapitel 14.1], [5, Kapitel 5 & 8], [6], [7]
Literatur
- Leon Sterling, Ehud Shapiro:
The Art of Prolog, 2. Auflage, MIT Press, 1994.
- Franz Baader, Tobias Nipkow: Term
Rewriting and All That, Cambridge University Press, 1998.
- Lawrence C. Paulson: Logic
and Proof, Lecture Notes, University of Cambridge Computer
Laboratory, 2005.
- J. W. Lloyd: Foundations of
Logic Programming, 2. erweiterte Auflage, Springer, 1987.
- Thom Frühwirth, Slim
Abdennadher: Constraint-Programmierung. Springer, 1997.
- Joxan Jaffar, Michael J. Maher:
Constraint Logic Programming: A Survey. The Journal of Logic
Programming 19, 20: 503-581, 1994.
- Pascal van Hentenryck et al.: A
Generic Arc-Consistency Algorithm and its Specializations.
Artificial Intelligence 57(2-3)291-321, 1992.
|
