Logikorientierte-Programmierung-Prüfung (Egyl)


Vorbereitung von mir (Simon, Dez. 2011 hat geklappt), keine Garantie auf Richtigkeit oder Vollständigkeit

Danke an die Leuten von:
http://www.informatik-forum.at/showthread.php?82112-Bisherige-Testfragen&daysprune=-1
http://www.informatik-forum.at/showthread.php?88448-After-Pr%FCfungs-Thread&daysprune=-1

Edit: Habe die Prüfung am 2. Nebentermin gemacht, die Prüfungen waren bei allen drei Terminen bis jetzt eigentlich immer gleich aufgebaut. Bei mir kamen folgende Fragen: 1) 2) 3) 4) 5) 6) 7) 8) 13). Ich hoffe es hat gereicht, dass Beispiel 8) war allerdings mit den Regeln von GOL+. Zusätzlich war noch eine Frage zu GOL+.

Vorbereitung:

- Skriptum lesen
- Die Übungsbeispiele nochmal anschauen
- Die Beispiele hier durchgehen

Logikorientierte-Programmierung-Prüfung (Egyl)
Vorbereitung:
1.) Welches Wissen wird in Prolog dargestellt? Wie wird es dargestellt? Wie sieht eine Abfrage aus? Wie wird negatives Wissen repräsentiert?
2.) Wenn ein Programm disjunktiv ist... kann es dann 2 Answersets X1,X2 geben mit X1 ist echte Teilmenge von X2?
3.) Definition von reduct P^M (ground auf Basic)?
3a.) Wie wird reduct P^M mit Aggregaten generalisiert?
4.) Wann ist I ein AnswerSet von P?
5.) Multiple-Choice-Fragen zur Reduktion
6) Weak-Constraint Beispiel (!)
7.) Hinzufügen von Constraints (!)
8.) Absorptionsgesetzt mit gol beweisen
9.) Dann war noch ein AnswerSet Beispiel: 3 kurze Punkte wie im letzten HÜ Beispiel. Answer Set schreiben!
10.) Wieso haben Axiome (in unserem Sequenzialkalkül) die Form |= a, -a für “atomar a”?
11.) Was sind 2-sequents?
12.) Was ist eine disjunktive/normale/propositionale Regel?
13.) Allgemeine Idee der ASP Methodologie?
14.) Was ist die Negationsnormalform (NNF), DNF und KNF?
15.) Was ist eine Horn-Formel?
16.) Was sind Constraints?
17.) Was ist ein Ground Basic Program?



1.) Welches Wissen wird in Prolog dargestellt? Wie wird es dargestellt? Wie sieht eine Abfrage aus? Wie wird negatives Wissen repräsentiert?


- Wissen wird in Prolog in Form von Eigenschaften und Relationen als Fakten dargestellt. Dabei wird nur positives Wissen dargestellt: es gilt die closed-world-assumption. Nicht-negatives Wissen kann nur mit “negation as failure” in Form von nichtmonotonem schließen realisiert werden.

Definite Klauseln(Fakten und Regeln) bilden gemeinsam das Programm, dass Wissen wird dadurch direkt gespeichert.

- Eine Anfrage sieht so aus: “:- subgoal1(parameter), subgoal2(parameter), usw .” Wobei die Subgoals konjunktiv verknüpft werden.

2.) Wenn ein Programm disjunktiv ist... kann es dann 2 Answersets X1,X2 geben mit X1 ist echte Teilmenge von X2?


Nein, da die Disjunktion in DLV subset-minimal ist (ASP2 Folie S.30).
3.) Definition von reduct P^M (ground auf Basic)?


Es gibt ein ground Program P und M, ein Set von Literalen. P von M wird so gemacht:

- Man eliminiert jede Regel in P die ein Literal not a im Body hat, mit a Element M.
- Man entfernt alle “default negated” Literals(not) im Body von dem restlichen Regeln.

-> P^M ist basic

Bsp:

man :- ,
single :- man, not husband,
husband :- man, not single.

Jetzt gibt es zwei answer set: M1 = {man, single} M2 = {man, husband}

Hier wird husband eliminiert, da es von single her not husband ist und dann von single das not entfernt:

man :-,
single :- man.

{man, single}
3a.) Wie wird reduct P^M mit Aggregaten generalisiert?


- entferne Regeln von P:
- mit not a im Body, so dass a true bezüglich M ist, oder
- mit a im Body, so dass a ein Aggregations-Atom falsch bezüglich M ist
- Entferne Literale not a und Aggregations-Atome von allen anderen Regeln.

4.) Wann ist I ein AnswerSet von P?


Ein konsistentes Set I, bestehend aus Literalen, ist ein Answer-set eines ground Programmes P, dann wenn (iff) es ein Answer set von P^I ist.
5.) Multiple-Choice-Fragen zur Reduktion


- Wenn eine Regel bei der Berechnung des Redukts P^M nicht gelöscht wird, werden dann alle Aggregatatome entfernt? Antwort: Ja, letzte Regel
- Wenn eine Regel bei der Berechnung des Redukts P^M nicht gelöscht wird, werden alle Aggregatatome entfernt, die bezüglich M wahr sind? Antwort: Nein, alle werden entfernt
- Muss eine Regel gelöscht werden, wenn sie Aggregatatome enthält, die bezüglich M falsch sind? Antwort: Ja, wenn es im body ist

Bin mir aber nicht sicher!
6) Weak-Constraint Beispiel (!)


Das Constraint-Beispiel:
Unter Annahme der gleichen Datenbasis wie beim zweiten Übungsbeispiel sollte man folgende Aufgaben lösen.

(i) Angenommen, für jedes PC-Mitglied ist in der Datenbasis auch die Zeit, zu der er seine Präferenzen eingereicht hat, angegeben (in Form von Fakten bid_at(M, T) wobei T die Zeit ist). Dann sollte man ein Prädikat order(M, N) definieren, das jedem Mitglied seine Position in der Reihenfolge zuweist, d. h. wenn Mitglied m als Dritter eingereicht hat, gilt order(m, 3).
(ii) Ein Prädikat, das die Summe der Ordnungszahlen aller PC-Mitglieder berechnet, denen ein bestimmtes Paper zugewiesen wurde.
(iii) Ein Weak Constraint, der jedes Paper "bestraft", bei dem die Summe dieser Ordnungszahlen größer ist als irgendein Schwellenwert.









7.) Hinzufügen von Constraints (!)

(ich hoffe, ich erinnere mich richtig...)

Gegeben war das Programm

-c v -d.
a v b :- not c.

Man sollte eine Menge von Constraints angeben, so dass dieses Programm nur die Answer Sets {a, -c} und {b, -c} hat.

Antwort: {:- -d.}
8.) Absorptionsgesetzt mit gol beweisen


Dann kam noch ein Teil aus dem ersten HÜ Beispiel. Das Absorptionsgesetzt sollte mit gol bewiesen werden und die Frage ist wie man das machen kann. Mann musste eine Regel anwenden..

Antwort von Juggl3r:

Zum Beispiel Absorptionsgesetz.
a äquivalent zu a v (a & b)
(oder es waren v und & vertauscht, weiß ich nicht mehr, ist aber nicht wichtig).

Wie beim "Beweiser" bei Bspl 1.
Nun müssen wir zeigen a |- a v (a & b) und a v (a & b) |- a
=> Mit Regel R7 aus der Angabe von Bspl 1 bekommen wir:
|- NNF(-a), a v (a & b)
|- a, NNF(-(a v (a & b))

=> Wenn man beides ableiten kann, dann ist die Äquivalenz gültig. Und das ableiten ist trivial.
Weil:
|- NNF(-a), a v (a & b)
=>
|- -a, a v (a & b)
Nun die oder regel anwenden
|- -a, a
Axiom


|- a, NNF(-(a v (a & b))
=>
|- a, -a & (-a v -b))
Und Regel, splitet sich auf 2 Teile:
1ter Teil:
|- a, -a
Axiom

2ter Teil:
|- a, -a v -b
Oder Regel
|- a, -a
Axiom

9.) Dann war noch ein AnswerSet Beispiel: 3 kurze Punkte wie im letzten HÜ Beispiel. Answer Set schreiben!


Ich habe einfach aus dem Skriptum ein paar genommen:

BSP:

P = {
a :-,
-b :- a,
c :- -b, not d.}

AS = {a, -b, c}

BSP: Ableiten! P = {
p :-,
-q :-,
r :- p,q,
-r :-,
s :- r,
s :- q,s,
-s :- p,-q,-r.
}
Ableitung:
T0Q({}) = {}
T1Q({}) = {p, -q}
T2Q({}) = {p, -q, -r}
T3Q({}) = {p, -q, -r, -s}
T4Q({}) = T3Q({})

-> AS = {p, -q, -r, -s}

BSP: P = {a v b v c:-} AS = {a}, {b}, {c} (Disjunktion minimal)
BSP: P = {a v b :-, a v c :- } AS = {a}, {b,c} (Disjunktion ist in ASP ist sogar subset minimal)
BSP: P = {
-c v -d.
a v b :- not c.
:- -d.
}
AS = {-c, a}, {-c, b}

10.) Wieso haben Axiome (in unserem Sequenzialkalkül) die Form |= a, -a für “atomar a”?


Wir lösen die Formeln solange auf, bis wir bei GOL-Axiomen sind(a atomar) und wir somit garantieren können, dass a v -a eine Tautologie ist.
11.) Was sind 2-sequents?



Die Sequents sind sets von Formeln. Jedes Sequentent in einem 2-Sequent hat max. 2 Formeln. In GOL benutzen wir nur 2-Sequents.

12.) Was ist eine disjunktive/normale/propositionale Regel?


Fakt: Nur head
Basic: Body & Head: Body hat keine not
Non-disjunktiv: Kopf hat genau ein Literal
Normale: Regeln, die Non-Disjunktiv (Kopf = 1 Literal) und keine starke Negation enthalten
Horn: Normal und Basic
Ground: Alle Literale haben keine Variablen
13.) Allgemeine Idee der ASP Methodologie?


1) Man kodiert ein die Instanz eines Suchproblems in ein Logikprogramm, so dass die Lösung des Suchproblems für die Instanz bei den Modellen von P repräsentiert wird.
2) Dann generiert man eines dieser Modelle
3) Und rekonstruiert daraus die Lösung für die Instanz I aus dem Modell.

Oder man generiert alle Modelle für alle Lösungen
14.) Was ist die Negationsnormalform (NNF), DNF und KNF?


Eine logische Formel ist in Negationsnormalform (NNF), falls die Negationsoperator in ihr nur direkt über atomaren Aussagen vorkommen. Die Disjunktive Normalform besagt, dass die Formel eine Disjunktion von Konjunktionstermen ist. Bei der Konjunktiven Normalform gegenteilig.

15.) Was ist eine Horn-Formel?


Eine Horn-Formel besteht nur aus einer Konjunktion von Horn-Klauseln. Horn-Klauseln sind Disjunktionen, bei der höchstens ein(ein oder 0) atomarer Ausdruck nicht-negiert ist.

Bsp. Horn-Formel: (a v -b v -c) & (b) & (a v -c) & (c v -a)

16.) Was sind Constraints?


Das sind Zwangsbedingungen, die erfüllt sein müssen, damit dieAnswer set eines Programms nicht “gekillt” wird. Sie haben die Form:

p :- bedingungsliteral1, …, bedingungsliteralN, not p

p kann nur dann true sein wenn alle Bedingungen wahr sind, d.h. es muss auch not p wahr sein muss. -> wenn die Bedingungsliterale wahr sind widersprechen sich p und not p und die Answer sets werden gekillt.

Einfacher geschrieben: :- bedingungsliteral1, …, bedingungsliteralN

17.) Was ist ein Ground Basic Program?


Wenn X ein set von ground Literalen(ohne Variablen) ist, dann ist X ein answer set eines ground basic Programms P genau wenn es ein minimales set von Literalen ist, dass konsistent und geschlossen bezüglich P ist.

- konsistent: es gibt kein Atom p, so dass {p, -p} Teilmenge von X
- geschlossen: Immer wenn der body einer Regel in X vorhanden ist, dann darf der Kopf mit X konjugiert nicht die leere Menge ergeben, d.h. mindestens ein Literal vom Kopf muss in X sein.