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

Aus VoWi
Zur Navigation springen Zur Suche springen

insgesamt 100pkt

SAT (33pkt)[Bearbeiten | Quelltext bearbeiten]

  • 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)[Bearbeiten | Quelltext bearbeiten]

  • 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)[Bearbeiten | Quelltext bearbeiten]

  • 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)