TU Wien:Deklaratives Problemlösen VO (Egly)/Prüfung 2012-01-24

insgesamt 100pkt

SAT (33pkt)

• Warum kann man mit vollständigen und korrekten Modellen das Erfüllbarkeitsprinzip für viele Aufgaben in der Informatik anwenden?
  • geben sie 3 Beispiele (Bsps aus dem Test zählen nicht) (6pkt)
  • erkläre SAT, Max-SAT, Parital-Max-SAT und zu 2 jeweils ein Beispiel. (6pkt)
• k-coloring Problem haendisch (21pkt)
  • allgemein das Problem auf ein Max-SAT reduzieren und die Constraints erklären
  • transformation in ein AnswerSet-Problem,
  • haendisch in einen CNF bringen,
  • Ergebnis ableiten und begründen wie das geht; am (gegebenen) Graph zeigen welche Schritte man macht.

Models (33pkt)

• stable supported models, redukt
  • Allgemeine AnswerSetMethodology erklären.
  • erklaeren sie das redukt P^i von einem logischen Programm P, I ist ein Model von P
    • ?geben sie das/ein stable Model von P an?
  • was ist ein supported model
  • was ist der Zusammenhang zwischen stable und supported model
• praktisches:
  • herbrand universum, (4pkt)
  • PuQ damit (a v -b :-, -b v c :-, a v c :-} -> {a,c}, (4pkt)
    • Loesung? Q={a, c}
  • Grundatome a b c d, regeln damit genau 3 answersets, in allen D (6pkt)
    • Lösung? { a v b v c. d. }

ASP (34pkt)

• DLV: (die beispiele warun händischen zu beweise/umformen/anzuschreiben)
  • was versteht man unter symbolic set, (3pkt)
  • erstellen sie die AnswerSet Programm in DLV-syntax für folgende Probleme
    • vertex cover, (8pkt)
    • erweitern sie das vorgehende um weak constraints. -> gewichtet vertex cover (mit penalties), (8pkt)
    • graph coloring problem (15pkt)