Ü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
© Copyright 2024 ExpyDoc
