Transcript
Übersicht H. Kleine Büning Universität Paderborn Konfiguration und Diagnose WS 15/16 10. Februar 2016
Vorlesung
H. Kleine Büning
1/15
Abduktion 1
Wie ist das Abduktionsproblem definiert?
2
Welcher Zusammenhang besteht zu Diagnoseproblemen?
3
Welche Komplexität besitzt das Abduktionsproblem ?
4
abdV (DHORN, DHORN)?
5
abd(DHORN, DHORN)?
6
Beispiele
Übung
H. Kleine Büning
2/15
Abduktion-Konfiguration 1
Zusammenhang Abduktion und Konfiguration
2
formale Beschreibung der Konfigurationsprobleme conf (A, B)
3
Komplexität conf (2Term, Term)
4
andere Klassen
Übung
H. Kleine Büning
3/15
Abduktion-Konfiguration 1
Erweiterungen von conf: globales Wissen, Äquivalenz
2
Idee
3
Formalismus
4
Beispielklassen, Beispiele
Übung
H. Kleine Büning
4/15
Skelettkonfiguration 1
Erklären Sie bitte die Idee.
2
Beispiel PKW:
3
Kann man das Problem mit Hilfe von logischen Formel und/ oder Regelsystemen repräsentieren?
4
Wie schwierig ist es festzustellen, ob es eine Lösung gibt?
5
Wie schwierig ist es festzustellen, ob es eine Lösung mit maximal k Komponenten gibt?
Übung
H. Kleine Büning
5/15
Demster-Shafer Erklären Sie bitte die Idee: Beispiel Insgesamt gebe es die Diagnosen {A1 , A2 , A3 }. Es werden nun hintereinander die folgenden Beobachtungen gemacht: 1
Das Symptom S1 spricht mit 0,2 für {A1 , A3 }.
2
Das Symptom S2 spricht mit 0,5 für {A2 , A3 }.
3
Das Symptom S3 spricht mit 0,7 gegen die Diagnosen A1 und A3 .
Bestimmen sie die einzelnen Basismaße und berechnen Sie ein Basismaß, welches die drei Beobachtungen berücksichtigt. Welche Diagnose würden Sie auswählen? Wie komplex ist der Ansatz (Zeit- und Platzbedarf)?
Übung
H. Kleine Büning
6/15
Ressourcenbasierte Konfiguration 1
Erklären Sie bitte die Idee.
2
Gegeben Komponenten: C1 : Geboten werden ein Anschluß B und zwei Ausgänge A, gefordert werden 230 Volt. C2 : Geboten wird ein Anschluß 230 Volt, gefordert wird ein Eingang A. C3 : Geboten wird ein Anschluß A, gefordert werden 230 Volt. Die Komponenten Ci kosten i Euro. Der Kunde möchte ein System mit 2 Anschlüssen B und drei Ausgängen A zum maximalen Preis von 15 Euro. Gibt es eine Lösung?
3
Übung
Komplexität des Konfigurationsproblems?
H. Kleine Büning
7/15
ATMS 1
Erklären Sie bitte die Idee.
2
Beispiel: Gegeben sind: Abhängigkeiten: (a, b → c), (c → t), (t → f ), (b, g → h), (h → f ) Prämissen (Assumptions) {a, b, g, h} Aufgabe: Berechnen Sie für ein ATMS die Label der Knoten. Aktualisieren Sie bitte Schritt für Schritt die Label: 1 2 3
Übung
aktualisierte Assumptions {a, b, h} aktualisiertes Wissen: entferne (c → t) aktualisieres Wissen: füge (c → h) hinzu
H. Kleine Büning
8/15
Modellbasierte Konfiguration (Hitting Sets, Reiter) 1
Idee
2
System mit Komponenten K = {x1 , . . . , xn } 1. Ki ⊆ K ist Konfliktmenge gdw. die Korrektheit von Komponenten aus Ki steht im Widerspruch zu den Beobachtungen. 2. D is Diagnose gdw. D ist eine minimale Hitting Set für alle Konfliktmengen K1 , . . . , Kr
1
Berechnung von minimalen Hitting Sets.
2
Was ist eine Diagnose?
3
Warum ist eine minimale Hitting Set eine Diagnose?
Übung
H. Kleine Büning
9/15
Default Logik 1
Erklären Sie bitte die Idee.
2
Was ist ein normaler Default?
3
Was ist eine Extension?
4
Wann folgt eine Formel β aus einer Default Theorie (D, W )?
5
Beispiel: 1 2 3
Übung
:Mb D = { :Ma a , b }, W = {(a → c), (c → ¬b), (¬b ∨ ¬a)} Gibt es eine konsistente (erfüllbare Extension)? Frage: Folgt ¬b aus (D, W )?
H. Kleine Büning
10/15
Set-Covering 1
Idee
2
Gegeben: S = {s1 , . . . , s5 } und F = {f1 , . . . , f4 } ursache(s1 ) = {f1 , f2 , f3 , f4 }, ursache(s2 ) = {f2 } ursache(s3 ) = {f2 , f3 }, ursache(s4 ) = {f1 , f2 } ursache(s5 ) = {f3 } S + = {s1 , s3 }
Bestimmen Sie bitte die minimalen Erklärungen für S + .
Übung
H. Kleine Büning
11/15
Lernen von Spezifikationen 1
Übung
Welche Ideen stecken hinter dem Lernen einer Spezifikation für eine fehlende Komponente in einer partiellen Konfiguration?
H. Kleine Büning
12/15
Lernen von Spezifikationen 1
Wie sind Membership- und eine Equivalence-Queries definiert?
2
Gegeben sei eine Black-Box mit einem aussagenlogischen Term T über den Variablen x1 , . . . , x4 . Beschreiben Sie den Lenalgorithmus für Terme an Hand des Beispiels.
3
Wie groß ist die Laufzeit des Verfahrens?
Übung
H. Kleine Büning
13/15
Constraint Systeme 1
Idee: Woraus besteht ein Constraintsystem?
2
Wie ist die lokale und globale Konsistenz definiert? Geben Sie dazu ein Beispiel ein.
3
Läßt sich das Erfüllbarkeitsproblem der Aussagenlogik als Constraintsystem darstellen? Was bedeuten in diesem Fall lokale- und globale Konsistenz?
4
Wie sind Knoten- und Kantenkonsistenz definiert?
Übung
H. Kleine Büning
14/15
Fallbasierte Diagnose 1
Erklären Sie bitte die Struktur eines fallbasierten Systems.
2
Welche Vor- und Nachteile besitzen fallbasierte Diagnose- und Konfigurationssysteme?
3
Welchen Anforderungen sollte ein Ähnlichkeitsmaß genügen?
Übung
H. Kleine Büning
15/15
