TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Prüfung 2010-04-23

Jeder Hauptpunkt ist 20 Punkte wert, einzelne Wertungen der Unterpunkte wurden nicht angegeben. MC Fragen: Richtige zählen positiv, falsche negativ!

Diskussionsthread im Informatikforum dazu: https://web.archive.org/web/*/www.informatik-forum.at/showthread.php?80027-After-Test-23.04.2010-Ausarbeitung&p=645680#post645680

Logische Wissensrepräsentation

• a.) Es sei eine Wissensbasis gegeben mit (phi) = Vx ( p(x) /\ ( p(x) -> q(a) ) ) und eine Anfrage mit (whatever) = q(a).
  • 1. Erstellen sie ein Entailmentproblem aus diesen Informationen.
  • 2. Wandeln sie dieses Entailmentproblem in ein Erfüllbarkeitsproblem einer Formel F um. Achten sie auf exakte Darstellung und beschreiben sie, welche Theoreme sie dafür benutzt haben.
  • 3. Wandeln sie das Erfüllbarkeitsproblem in ein NNF-Problem um.
  • 4. Versuchen sie, das Problem in TC1 zu lösen. Interpretieren sie diese Ergebnisse bezüglich des Entailmentproblems.
• b.) Zeigen sie semantisch, das das Entailment gilt. Machen sie das, indem sie zeigen, dass jedes Model von (phi) auch ein Model von (whatever) ist.

CSP

• a.) Es war ein Hypergraph zu zeichnen, ähnlich der in der vorigen Prüfung bzw. der in den Folien.
• b.) MC-Fragen:
  • MRV wählt jene Variable aus, die die meisten möglichen Variablenbelegungen hat.
  • Die Degree-Heuristik wählt jene Variable aus, die in den meisten Constraints noch unbelegter Variablen vorkommt.
  • In einem CSP mit n Variablen und d Werten je Variable, gibt es maximal O(d^n) Belegungen.
• c.) Wann ist die Kante X -> Y konsitent?

Nichtmonotones Schließen

• a.) Es sei eine Theorie gegeben:
  • a,b,c seien die Konstanten, x die einzige Variable und p und q die einzigen Prädikate.
  • T = {p(a), Vx (q(x) -> p(x)), q(b), -q(c)}
  • Schreiben sie die dazu passende CWA auf (analog zur vorigen Prüfung).
  • MC-Fragen: Was passt zur obigen CWA
    • T ist vollständig.
    • CWA(T) ist konsistent.
    • CWA(T) ist deduktiv abgeschlossen.
• b.) Definieren sie das Redukt einer Menge von ... bla.
• c.) Extensions:
  • W = { p }
  • D = { p : -q / q }
  • T1 = {W,D}
  • T2 = {W u {q}, D}
  • Berechnen sie die Extensions zu den beiden Default-Theorien.

RBS und Suche

• a.) Wann ist eine Heuristik zulässig (admissible) und wann konsistent (consistent)?
• b.) Zeigen sie, dass eine zulässige Heuristik immer auch konsistent ist. (vgl. Übungsbeispiel)
• c.) Geben sie ein Beispiel, wo eine DFS mehr als doppelt so viele Knoten als eine BFS erweitert/aufmacht/bla.
• d.) Was ist und wozu dient Konfliktresolution in RBS? Nennen sie 4 Möglichkeiten, wie Konflikte behandelt werden können.