FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Unterbereich Grundstudium / Formale Informatik

Übungsaufgabe 6.1

Übungsaufgabe 6.1 2004-05-12 20:39
Toam
Im Skript steht zum Thema Färbealgorithmus, wenn man man einen Knoten {(p)^a, (q)^a} | in Worten: ("p hoch a, q hoch a") |
gefunden hat der Schwarz ist, wird {p,q} auch schwarz gefärbt und alle Kanten die im Knoten {p,q} enden werden entfernt. Welche Kanten werden da genau entfernt?
p und q sind doch zwei Zustände, werden jetzt die Kanten zwischen den beiden Zuständen entfernt, oder welche[img]http://www.fb18.de/gfx/5.gif[/img]

Re: Übungsaufgabe 6.1 2004-05-12 21:53
BigBFD
Die Dreiecksmatrix, die du dir wahrscheinlich erzeugt hast ist gleichzeitig ein Graph von Zustandstupeln. Wir betrachten in diesem Graph {p,q) als einen Knoten.
Zu diesem können ja laut Konstruktion ("Schritt 2:" … "wenn nein:…") Kanten führen.

Diese werden wieder entfernt wenn du herausfindest, dass die Knoten im DFA p und q nicht äquivalent sind.

Re: Übungsaufgabe 6.1 2004-05-12 22:31
Toam
Danke, jetzt ist klar. Ich dachte es wären die Kanten im ursprünglichen Automat gemeint.
Jetzt aber noch ne zweite Frage, wenn ich mit Färben fertig bin und noch Kanten habe, spielen die eine Rolle oder guck ich nur nach den Farben der Knoten?

Re: Übungsaufgabe 6.1 2004-05-12 23:34
BigBFD
Die Kanten dienen "nur" zur Verkürzung des Algorithmus, was bei 6.1 nicht so gut zur Geltung kommt.
Wenn du alle Knoten gefärbt hast, dann sind die weißen die endgültig äquivalenten.

Re: Übungsaufgabe 6.1 2004-05-15 20:59
Anonymer User
Hi.
ich versteh das mit dem
Im Skript steht zum Thema Färbealgorithmus, wenn man man einen Knoten {(p)^a, (q)^a} | in Worten: ("p hoch a, q hoch a") |
gefunden hat der Schwarz ist, wird {p,q} auch schwarz gefärbt und alle Kanten die im Knoten {p,q} enden werden entfernt. Welche Kanten werden da genau entfernt?
nicht so ganz.
versuche grad das Beispiel aus den Folien nachzuvollziehen…
(Folie 614).
Kann mir vielleicht einer sagen, wiso einige gestrichelt markiert werden..(also gefärbt werden) und andre ned??

Re: Übungsaufgabe 6.1 2004-05-15 21:59
Joker
Kann mir vielleicht einer sagen, wiso einige gestrichelt markiert werden..(also gefärbt werden) und andre ned??

Wann und warum ein Knoten gefärbt wird steht doch im Algorithmus?

Re: Übungsaufgabe 6.1 2004-05-15 23:11
Anonymer User
dann siehts doch wohl so aus, als hätte ich das nicht verstanden!
sonst würd ich wohl kaum fragen

Re: Übungsaufgabe 6.1 2004-05-15 23:26
Joker
Solange du keine konkrete Frage stellst, wird man dir wohl kaum weiterhelfen können.

Re: Übungsaufgabe 6.1 2004-05-15 23:34
Anonymer User
hab doch ne frage gestellt.
Wie kommt man auf die "schwarzmakierungen" auf Folie 614..?

Re: Übungsaufgabe 6.1 2004-05-15 23:44
a nonymous user
hab doch ne frage gestellt.
Wie kommt man auf die "schwarzmakierungen" auf Folie 614..?


Steht doch im Algorithmus, wenn du zwei Zustände hast, einer ist Endzustand, der andere nicht das zugehörige Paar schwarz färben, dann die nicht schwarz gefärbten nehmen, schauen zu welchem Paar man von denen aus kommt, wenn man dadurch auf ein schwarzes Paar trifft auch das Ausgangspaar schwarz färben usw.

5 Minuten vor dem Algorithmus meditieren, dann nochmal Beispiel anschauen und dann solltest du es nachvollziehen können [img]http://www.fb18.de/gfx/25.gif[/img]

Edit: Absatz

Re: Übungsaufgabe 6.1 2004-05-16 17:00
Viciarg
a) Falls für ein a (element) (Sigma) die Menge {(p)a, (q)a} schwarz gefärbt ist, so färbe {p, q} sowie alle von dort aus erreichbaren Mengen schwarz.

Gehe ich dabei von dem im vorigen Punkt weiß gefärbten Zustand aus?

Re: Übungsaufgabe 6.1 2004-05-16 17:30
korelstar
a) Falls für ein a (element) (Sigma) die Menge {(p)a, (q)a} schwarz gefärbt ist, so färbe {p, q} sowie alle von dort aus erreichbaren Mengen schwarz.

Gehe ich dabei von dem im vorigen Punkt weiß gefärbten Zustand aus?

Ja. Du sollst ja {p, q} zuvor weiß gefärbt haben. Wobei in den Folien wohl ein "eine" fehlt (bei "Wähle _eine_ beliebige Zuständsmenge…"). Alle folgenden {p,q} beziehen sich natürlich auf dieses eine, was du gewählt und weiß gemacht hast. Sonst würde der Algorithmus keinen Sinn ergeben.