Hausaufgabe 1.4 - minimale Belegung

dripper
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 25. Mär 2009 14:01

Hausaufgabe 1.4 - minimale Belegung

Beitrag von dripper »

Hallo,
Wo steht eigentlich der Algorithmus für die Bestimmung der minimale Belegenung eines Hornklausels und was bedeutet eine minimale Belegung?
Ich kann leider das in den Folien nicht finde.

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: Hausaufgabe 1.4 - minimale Belegung

Beitrag von olg »

Fgdi2-Folien, Seite 42ff. ist der Algorithmus angegeben

Unter http://de.wikipedia.org/wiki/Markierungsalgorithmus gibt es den Algorithmus in einer etwas praktischeren Form angegeben.
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

dripper
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 25. Mär 2009 14:01

Re: Hausaufgabe 1.4 - minimale Belegung

Beitrag von dripper »

Danke für den Link, aber leider kann ich noch nicht den Algorithmus verstehen.
Kannst du mir vielleicht eines Beispiel geben wie man nach diesem Algorithmus rechnet?

Der_olle_Schwoebel
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 3. Okt 2008 18:22
Wohnort: Erbach (Odenwald)
Kontaktdaten:

Re: Hausaufgabe 1.4 - minimale Belegung

Beitrag von Der_olle_Schwoebel »

Das hier ist ein praktisches Beispiel und ziemlich gut erklärt meiner Meinung nach:
http://www.onli-blogging.de/index.php?/ ... thmus.html
Life's a climb. But the view is great...
Bild

kutschke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 16. Apr 2009 10:39

Re: Hausaufgabe 1.4 - minimale Belegung

Beitrag von kutschke »

Hi!
Der Algorithmus steht auch im Skript, und zwar kommt der im Beweis des Satzes vor, wo es darum geht, dass es diesen Algorithmus gibt. Der Prof hat ihn nicht auf den Power-Point-Folien gehabt, hat es aber "per Hand" auf Overhead-Folien gemacht. Naja, wie auch immer, im Skript gibts den jedenfalls.

Benutzeravatar
Puppetmaster
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 8. Okt 2008 10:02
Kontaktdaten:

Re: Hausaufgabe 1.4 - minimale Belegung

Beitrag von Puppetmaster »

Kann mir mal wer erklären, was die letzten beiden Zeilen bei der Lösung zu bedeuten haben?

s4lph0r
Neuling
Neuling
Beiträge: 5
Registriert: 24. Mai 2009 11:37

Re: Hausaufgabe 1.4 - minimale Belegung

Beitrag von s4lph0r »

So wie ich mir das aus der Vorlesung übernommen habe, müsste der Algorithmus zur Findung der minimalen Belegung in etwa so Ablaufen:

Ich nutze als Beispiel das, was auch unter dem Link von Der_olle_Schwoebel bearbeitet wird.

Dort ist folgende Menge von Hornklauseln gegeben: {a,¬c}, {c}, {¬a, b, ¬c}, {¬b, ¬c, a, ¬d}

Zunächst ist es meistens so, dass man in dieser Menge eine einstellige Klausel mit einer nicht-negierten Variable hat, das ist in diesem Fall {c}.

Somit weist man zunächst c den Wert 1 zu.
In Folge dessen streicht man nun das ¬c aus allen Klauseln, in denen es Vorkommt. Die Klauseln in denen c unnegiert vorkommt, werden komplett gestrichen, da sie nun automatisch wahr werden. ( Weil die Variablen quasi alle durch ein "oder" verbunden sind. )

Somit erhält man die Klauselmenge {a}, {¬a, b}, {¬b, a, ¬d}

Hier wird schnell ersichtlich, dass das ganze nun nochmal auf a angewandt wird.
Also wird a auch auf 1 gesetzt.

Somit bleibt nur noch die Klauselmenge {b} übrig.

Setzt man b jetzt auch noch auf 1 bleibt keine Klausel mehr übrig, folglich ist es egal, welchen Wert d bekommt.
Also bekommt d einfach den Wert 0.

Und so haben wir auch schon die selbe Belegung wie unter dem Link vorgestellt: a=b=c=1 und d=0.

Insgesamt hat die Klauselmenge 2 erfüllende Belegungen, da sie auch für d=1 erfüllt ist.


Ich hoffe mal das meine Beschreibung für den Algorithmus verständlich und vor allem auch korrekt ist.
Ein Punkt, für den ich noch keinen Richtigen Rat wüsste ist, wie man vorzgehen hat, wenn zu Beginn keine einstellige Klausel mit einem nicht-negierten Wert vorhanden ist.

Für Tipps und Kritik bin ich natürlich dankbar!

Benutzeravatar
Puppetmaster
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 8. Okt 2008 10:02
Kontaktdaten:

Re: Hausaufgabe 1.4 - minimale Belegung

Beitrag von Puppetmaster »

Dann ist es unerfüllbar.

Meine Frage nach den letzten beiden Zeilen wurde damit aber leider nicht beantwortet.

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: Hausaufgabe 1.4 - minimale Belegung

Beitrag von mister_tt »

Mit dem Algorithmus willst du ja eine minimale erfüllende Belegung für deine Hornklausel-Menge finden. Und die letzten beiden Zeilen besagen, dass diese Belegung wie folgt aussieht:
q = r = s = t = 1
p = u = v = 0

Dort wird es halt nur offiziell mit einer Belegungsfunktion J ausgedrückt...

Antworten

Zurück zu „Archiv“