+- FB18.de - Das Informatikforum ( /mybb )
+-- Forum: Bachelorstudieng ( /forumdisplay.php?fid=112 )
+--- Forum: PM Formale Informatik ( /forumdisplay.php?fid=99 )
+--- Thema: FGI Blatt 4 \o/ ( /showthread.php?tid=10955 )
FGI Blatt 4 \o/ - Anonymer User - 11.11.2009 18:16
Aufgabe 4.7 2.)
Im Hinweis steht, dass man Algorithmus 3.1 verwenden darf.
Gut, aber was zur **** ist Algorithmus 3.1?
Ist vllcht Algorithmus 4.7.1 gemeint?
RE: FGI Blatt 4 \o/ - Anonymer User - 11.11.2009 18:42
Algorithmus 3.1 ist aus dem Skript und auf Seite 86 zu finden.
RE: FGI Blatt 4 \o/ - Anonymer User - 11.11.2009 18:48
Oh - dankeschön. Kleiner Verweis darauf wäre in der Aufgabe nett gewesen.
RE: FGI Blatt 4 \o/ - Anonymer User - 11.11.2009 19:34
Eine Frage zu 4.3
Es sei ein P/T-Netz und eine beliebige Schaltfolge w element T* gegeben.
Ich soll zeigen, dass immer eine Markierung m existiert, die w aktiviert.
Aber ist das denn überhaupt so? Wieso muss denn immer eine Markierung m existieren? Ein P/T-Netz kann doch eine Verklemmung haben und plötzlich sind nicht genug Marken da, um eine Transition schalten zu lassen.
Oder ist eine auf dem P/T-Netz gültige Schaltfolge gemeint? In diesem Fall verstehe ich den Sinn der Aufgabe nicht.
RE: FGI Blatt 4 \o/ - doodles - 11.11.2009 19:43
Eine Markierung m gibt es immer. Ob diese von m0 erreichbar ist, ist eine andere Frage.
Eine Markierung, die die Schaltfolge w aktiviert kann man zum Beispiel ganz einfach finden, in dem man die Vorbereiche aller Transitionen der Schaltfolge zusammenaddiert. Solange es keine Kapazitäten gibt ist damit die Schaltfolge aktiviert.
Das diese Markierung aber immer diese Schaltfolge aktiviert müsstest du dann formal beweisen... anschaulich sollte das ja recht einleuchtend sein.
RE: FGI Blatt 4 \o/ - Anonymer User - 11.11.2009 19:47
Vielen dank! Jetzt versteh ich erst die Frage.
Super.
RE: FGI Blatt 4 \o/ - Anonymer User - 11.11.2009 19:59
Zitat:
Eine Markierung, die die Schaltfolge w aktiviert kann man zum Beispiel ganz einfach finden, in dem man die Vorbereiche aller Transitionen der Schaltfolge zusammenaddiert.
Ist das denn richtig?
() = Stelle ; [] = Transition
()--5-->[]--1-->()--6-->[]--2-->()
11 Marken wären hier nicht ausreichend. Oder verstehe ich etwas falsch?
RE: FGI Blatt 4 \o/ - UncleOwen - 11.11.2009 20:05
Anonymer User schrieb:
Zitat:
Eine Markierung, die die Schaltfolge w aktiviert kann man zum Beispiel ganz einfach finden, in dem man die Vorbereiche aller Transitionen der Schaltfolge zusammenaddiert.
Ist das denn richtig?
() = Stelle ; [] = Transition
()--5-->[]--1-->()--6-->[]--2-->()
11 Marken wären hier nicht ausreichend. Oder verstehe ich etwas falsch?
Doch, 11 Marken sind ausreichend. 5 auf der ersten, 6 auf der zweiten Stelle.
RE: FGI Blatt 4 \o/ - Anonymer User - 11.11.2009 20:07
Oh, die dürfen also auch verteilt sein wie sie wollen. Hmm...
RE: FGI Blatt 4 \o/ - Anonymer User - 11.11.2009 20:11
Die Schaltfolge dazu wäre also
(5,6,0) --t1-->(0,7,0)--t2-->(0,2,2) ?
t2->t1 ginge ja schonwieder nicht. o_o
RE: FGI Blatt 4 \o/ - doodles - 11.11.2009 20:15
du sollst das ja für beliebige schaltfolgen zeigen.
aber für die Schaltfolge t1t2 wäre die Markierung (5,6,0) die gesuchte Markierung m. Für t2t1 geht die geleiche markierung m (Warum sollte t2t1 da nicht gehen @Anonymer User). Für t1t1t2 aber zum beispiel geht das m nicht. Dafür müsste dann wieder eine andere Markierung wählen. Nun sollt ihr aber beweisen, dass man für jede beliebige Schaltfolge immer eine Markierung wählen kann.
RE: FGI Blatt 4 \o/ - Anonymer User - 11.11.2009 20:20
Autsch. Die Definition für Markierung in meinem Kopf war total für'n Arsch. Die Markierung m kann ja als Vektor aufgefasst werden und zeigt sozusagen die gesamte Verteilung der Marken im gesamten P/T-Netz! (Nicht etwa die Anzahl an Marken im "Startzustand").
Danke!
RE: FGI Blatt 4 \o/ - Anonymer User - 14.11.2009 11:52
Auch Frage!
Übungsaufgabe 4.9
Man soll die Sprache L1 = FS(N1) teilmenge ....
Wofür steht das FS? Habe mein Skript verlegt und kann es im Internet(Wiki) nicht finden :.( .
RE: FGI Blatt 4 \o/ - Anonymer User - 14.11.2009 12:01
...und
wie kann es eine Sprache geben die vom TS akzeptiert wird, wenn es keinen einzigen Endzustand gibt? Was ist denn dann das Kriterium für die Akzeptanz? Sf = Leere Multimenge nicht dasselbe wie kein Endzustand?
RE: FGI Blatt 4 \o/ - Anonymer User - 14.11.2009 12:23
In der Aufgabe ist gemeint, den Erreichbarkeitsgraphen des P/T-Netzes zu zeichnen, und dann diesen Erreichbarkeitsgraphen als Transistionssystem TS aufzufassen. Die Sprache dieses Transitionssystemes soll dann gezeigt werden.
FS(N) duerfte falsch sein, es muesste FS(TS) heissen, wobei TS der Erreichbarkeitsgraph als Transitionsystem aufzufassen ist.
RE: FGI Blatt 4 \o/ - RaG - 14.11.2009 13:03
FS(N) für ein P/T-Netz N ist auch definiert: Es ist die Menge aller Schaltfolgen, die im Netz möglich sind.
RE: FGI Blatt 4 \o/ - theorinix - 14.11.2009 13:04
Anonymer User schrieb:
...und
wie kann es eine Sprache geben die vom TS akzeptiert wird, wenn es keinen einzigen Endzustand gibt? Was ist denn dann das Kriterium für die Akzeptanz? Sf = Leere Multimenge nicht dasselbe wie kein Endzustand?
wie kann es eine Sprache geben die vom TS akzeptiert wird, wenn es keinen einzigen Endzustand gibt? Was ist denn dann das Kriterium für die Akzeptanz? Sf = Leere Multimenge nicht dasselbe wie kein Endzustand?
Die leere Multimenge bedeutet, dass keine Marken mehr da sind. Das ist also eine spezielle Markierung eines (gefärbten) Petrinetzes (o.ä.). Markierungen (also Multimengen) sind keine Zustände sondern eventuell zu erreichende Markierungen, sog. Endmarkierungen. Nur in seltenen Fällen, ist die leere Multimenge eine Markierung, in der noch Transitionen aktiviert sind! Dann nämlich, wenn diese keine einzige Eingangskante besitzen!
RE: FGI Blatt 4 \o/ - Anonymer User - 14.11.2009 13:54
RaG schrieb:
FS(N) für ein P/T-Netz N ist auch definiert: Es ist die Menge aller Schaltfolgen, die im Netz möglich sind.
Ja, nur macht FS(N) hier keinen Sinn. Weil FS(N) waeren ja alle moeglichen Schaltfolgen.
Wir suchen aber nicht alle moeglichen Schaltfolgen.
Deshalb muesste es FS(TS) sein!
RE: FGI Blatt 4 \o/ - Anonymer User - 14.11.2009 17:16
Übungsaufgabe 4.5
Sei N = (P, T, F,W,m0) ein P/T Netz, für das ∀t ∈ T :
Summe p∈P W(p, t) = Summe p∈P W(t, p) gilt
Ich verstehe das nicht richtig. Sagt es aus, dass die Summe aller "Vor"-Kantengewichtungen gleich der Summe aller "Nach"-Kantengewichtungen ist? Oder gilt es für jede aber jeweils eine Transition? Also dass die (Summe der) Kantengewichte die in eine(!) Transition reingehen gleich der Kantegewichte ist, die aus einer Transition herausgehen?
RE: FGI Blatt 4 \o/ - Anonymer User - 14.11.2009 17:32
Anonymer User schrieb:
Übungsaufgabe 4.5
Sei N = (P, T, F,W,m0) ein P/T Netz, für das ∀t ∈ T :
Summe p∈P W(p, t) = Summe p∈P W(t, p) gilt
Ich verstehe das nicht richtig. Sagt es aus, dass die Summe aller "Vor"-Kantengewichtungen gleich der Summe aller "Nach"-Kantengewichtungen ist? Oder gilt es für jede aber jeweils eine Transition? Also dass die (Summe der) Kantengewichte die in eine(!) Transition reingehen gleich der Kantegewichte ist, die aus einer Transition herausgehen?
Sei N = (P, T, F,W,m0) ein P/T Netz, für das ∀t ∈ T :
Summe p∈P W(p, t) = Summe p∈P W(t, p) gilt
Ich verstehe das nicht richtig. Sagt es aus, dass die Summe aller "Vor"-Kantengewichtungen gleich der Summe aller "Nach"-Kantengewichtungen ist? Oder gilt es für jede aber jeweils eine Transition? Also dass die (Summe der) Kantengewichte die in eine(!) Transition reingehen gleich der Kantegewichte ist, die aus einer Transition herausgehen?
Lies: Fuer jede Transition gilt: ....
D.h. fuer jede einzelne Transition gilt das!
RE: FGI Blatt 4 \o/ - Anonymer User - 14.11.2009 18:18
Danke!
Ich lese es immer "Für alle t Element...", da wird nicht ganz ersichtlich, dass es für jede seperat gilt.
RE: FGI Blatt 4 \o/ - Anonymer User - 16.11.2009 20:27
Welches Netz ist gemeint bei 4.9?
¨Obiges Netz N¨ - ich finde nur ein N1.
Und fuer dieses macht die letzte Frage erstaunlich wenig sinn -_-
Überhaupt sind die Aufgaben ziemlich bescheuert gestellt!
RE: FGI Blatt 4 \o/ - Anonymer User - 17.11.2009 19:16
AUFG 4.9.1:
Geben Sie für das obige Netz N die Sprache L1 = FS(N1) ....
meint das Netz N1 aus Aufg 4.8.