fb18.de
/ Bachelorstudieng
/ PM Formale Informatik
FGI2 Klausur-Fragen-Thread 2010
Ja, so einer fehlt noch.
Die erste Frage: Unterschied LTL CTL - im Skript steht, dass die LTL Formel
A(FGp) nicht in CTL dargestellt werden kann.
Aber es wird hier doch ein Allquantor verwendet, der (nur) in der CTL enthalen ist? Die Formel steht doch quasi in CTL da. Also…wtf?
Guck dir Syntax und Semantik von CTL und LTL noch mal genau an.
Bei LTL haben alle Formeln implizit einen Pfad-All-Quantor vorne stehen.
FG p ist also das gleiche wie A FG p. (Letzteres schreibt man manchmal,
wenn man von CTL* ausgeht.)
Bei CTL treten die Pfadquantoren A und E und die Temporalquantoren (X, F, G, U)
immer zusammen auf, soll heissen: Wenn du einen Pfadquantor (A oder E) hast,
dann kommt direkt danach zunächst einer der vier Temporalquantoren. Andersherum
kommt direkt vor jedem Temporalquantor immer einer der beiden Pfadquantoren.
A FG p ist also keine CTL Formel (A F A G p waere eine oder A F E G p), *aber*
es geht hier sogar darum, dass dies nicht nur keine CTL Formel ist, sondern dass
du auch keine äquivalente CTL Formel finden kannst!
Frank :)
Vielen Dank, Frank. Damit sind einige Fragen weggefallen bzw schon beantwortet.
Im Gprot von 08 und 09 gibt es Aufgaben zu "Harel Graphen". Im Skript und in Wikipedia kann ich dazu nichts finden - kann mir da einer Helfen?
Hey…
Harel-Graphen sind kurz gesagt, ein (weiterer) Formalismus (oder vielleicht eher eine Notation,
da sie nicht so formal untermauert ist wie z.B. Petri Netze oder Prozessalgebra) zur Modellierung
komplexer Systeme (mit Nebenläufigkeit). Wie Petri Netze sind sie eine graphische Notation.
Harel-Graphen waren früher Stoff von FGI2, sind es in diesem Jahr aber nicht und also auch nicht
prüfungsrelevant.
Wenn du dennoch etwas dazu wissen möchtest, dann findest du dazu etwas im FGI2-Skript vom
Vorjahr:
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0809/FGI2/(Dort in Teil 1 des Skriptes.)
Ein anderer Name dafür sind übrigens Statecharts oder auch Zustandsübergangsdiagramm. Unter
den Bezeichnungen findest du dann auch was bei Wikipedia:
http://de.wikipedia.org/wiki/StatechartDort steht z.B. auch, dass sie mittlerweile ein Teil der UML sind.
Ausserdem findest du dort den Link zu dem original Paper von Harel (ganz unten).
Aber wie gesagt, dass nur wenn es dich interessiert. Ist eine nette Notation mit der man insb. auch
Leuten, die jetzt nicht so mathematisch/formal affin sind, etwas über ein Programm verdeutlichen
kann (z.B. bei Projekten bei denen man mit Menschen, die in unterschiedlichen Disziplinen ausgebildet
sind, arbeitet). Dafür war das glaube ich auch ursprünglich von Harel entwickelt worden.
Für die FGI2-Prüfung brauchst du das (diesmal) aber nicht.
Frank :)
Wird in dieser Klausur jetzt vielleicht auch vermieden werden, dass man stumpf irgendwelche formalen Definitionen hinpinseln muss?
Hallo, ich habe auch mal eine Frage und zwar zur Rekursion in der Prozessalgebra. Im Skript auf Seite 131 Beispiel 4.25 b) steht, dass alle Prozesse, die mit a terminieren (wie z.B.) a+cd eine Lösung für die Spezifikation X = a + X ist. Soweit logisch, dann ist ja auch a+ef eine Lösung, aber unter der Definition 4.24 steht, dass Lösungen bisimilar sein müssen, was a+ef und a+cd ja nicht sind. Was verstehe ich da falsch?
Hallo, ich hab auch eine Frage. Wie kann denn auf Seite 11 im Skript die Funktion pr1 mit
pr1(Sync) := {s | E r € S2 : (s, r) € Sync} (E stellt den Existenzquantor und € ein "Element von" Zeichen dar)
definiert sein, wenn laut Definition 1.9 die Menge Sync eine Teilmenge von A1 x A2 ist. Demnach kann doch in Sync garnichts enthalten sein, was Element von S2 ist, weil Sync nur Transitionen und keine Zustände enthält. Überseh ich gerade etwas oder wieso blick ich hier nicht durch?
Hallo, ich hab auch eine Frage. Wie kann denn auf Seite 11 im Skript die Funktion pr1 mit
pr1(Sync) := {s | E r € S2 : (s, r) € Sync} (E stellt den Existenzquantor und € ein "Element von" Zeichen dar)
definiert sein, wenn laut Definition 1.9 die Menge Sync eine Teilmenge von A1 x A2 ist. Demnach kann doch in Sync garnichts enthalten sein, was Element von S2 ist, weil Sync nur Transitionen und keine Zustände enthält. Überseh ich gerade etwas oder wieso blick ich hier nicht durch?
Jo du hast recht, muss [latex] A_2 [/latex] und nicht [latex] S_2[/latex] sein!
Gleich dem Prof mailen damit er das zu seiner Errata Liste hinzufuegen kann :)
ps: Achtung mit den Begriffen. Sync enthaelt Tupel von Aktionen, und nicht von Transitionen =) Eine Transition ist bei Transitionssystemen ein Dreiertupel (q,a,q') mit q,q' als Zustaenden und a als Aktion. Bei Petri-Netzen sind Transitionen nochmal was anderes….
Danke, das mit den Transitionen und Aktionen war mir gerade garnicht so bewusst. Und dann hab ichs also doch richtig verstanden :D.
hat er eigentlich irgendwas über die klausur gesagt? bei der ersten vorlesung hieß es, dass die übungen explizit auf die prüfung vorbereiten sollen. womit kann man rechnen? oder werden wieder stumpf definitionen abgefragt wie letztes jahr?
2. Aufgabenblatt, Übungsaufgabe 2.3.3
Kann es ein endliches TS geben, das L(TS) akzeptiert. Musterlösung sagt nein, da L(TS) nicht regulär ist.
Ich weiss ich muss falsch liegen, aber kann mir jemand sagen, wieso folgendes TS diese Sprache nicht akzepieren soll?
[img]
http://img205.imageshack.us/img205/5771/huch.png[/img]
Ich vermute mal das b rechts soll ein c sein und das c unten ein b oder?
weil sonst macht das gar keinen sinn
wenn du es so wie vermutet meinst, dann akzeptiert das TS zwar alle wörter, die in der gesuchten sprache liegen, allerdings darüber hinaus noch deutlich mehr wörter, zB aacb, aaacb
–> es gibt kein TS, welches genau die Sprache akzeptiert
Richtig, b und c vertauscht.
Verstehe, also darf das TS nur die Sprache und nichts darüber akzeptieren. Danke.
Fehler in Musterlösung(?)
Blatt 3 Präsenzaufgabe 3.1.2
TS1(X)TS2 mit Sync = {(x,x) | x e A}
Soll gebaut werden. Das ProduktTS stimmt nicht, oder? Vom Zustand (A,1) kann ich ein a laufen oder ich kann ein c laufen. Der c Pfad fehlt doch?
Außerdem Nebenfrage:
Kann mir einer erklären, was Sync überhaupt macht oder bringt? Ich komme einfach nicht dahinger, was mir hier z.B. Sync = {(x,x) | x e A} sagen oder bringen soll. Dasselbe mit der zugehörigen Gamma Funktion.
Wahrscheinlich ist die Lösung garnicht falsch und das Sync sagt mir irgendwie, dass ich den c Weg garnicht gehen darf?
Ich glaube mein eigener Satz hat es mir gerade erklärt.
Sync = {(x,x)| x e A}
->sagt mir, dass ich nur gleichnamige Aktionen (A = Aktion? Element aus Sigma würde ich beim Automaten sagen) ersetzen darf?
Und mein Automat mit c Pfad wäre Sync = leere Menge?
Wenn ja, was macht die Gamme Funktion?
Hallo, ich habe auch mal eine Frage und zwar zur Rekursion in der Prozessalgebra. Im Skript auf Seite 131 Beispiel 4.25 b) steht, dass alle Prozesse, die mit a terminieren (wie z.B.) a+cd eine Lösung für die Spezifikation X = a + X ist. Soweit logisch, dann ist ja auch a+ef eine Lösung, aber unter der Definition 4.24 steht, dass Lösungen bisimilar sein müssen, was a+ef und a+cd ja nicht sind. Was verstehe ich da falsch?
Die geforderte Bisimilarität bezieht sich auf die Spezifikationsgleichung (Äquivalenz entspricht Bisimulation). Es sollen also nicht a+ef und a+cd bisimilar sein, sondern folgendes:
Sei die Lösung von X = a+ef: Es muss a+ef = a + a+ef gelten.
Sei die Lösung von X = a+cd: Es muss a+cd = a + a+cd gelten.
Die Gleichung mit der eingesetzten Lösung muss also eine korrekte Äquivalenz ergeben. Also muss im ersten Beispiel eine Bisimulation zwischen a+ef und a + a+ef bestehen und im zweiten Beispiel eine zwischen a+cd und a + a+cd.
Müssen wir die Transisitonsregeln (Skript S. 118) eigentlich auswendig können oder stehen die nochmal in der Klausur drin?
heute wurde im rep gesagt das es noch nie einen anhang bei den FGI2 klausuren gab…
also muss man wohl ne menge auswendig lernen :X
Was ist eigentlich das Beschränktheitsproblem bei zählerautomaten bzw TM's und warum ist es unentscheidbar?
Mal eine Frage zu verteilten Algorithmen und dessen Schichtenmodell
Im Skript Seite 236 drittes Diagramm steht, dass es ssf (single-source FIFO) sei aber das es ist meiner Meinung nach nicht.
Die Definition sagt ja:
pi sendet m1 vor m2 an pj => m2 wird von pj nicht vor m1 empfangen
Auf dieses Beispiel bezogen ist es ja so, dass vom p1 a an p1 und p2 gesendet wird ud b von p2 an p1 und p2.
p2 empfängt das a auch vor dem b.
Aber p1 empfängt doch erst das b und dann das a, obwohl doch a vor b losgeschickt wurde, damit ist es doch nicht mehr ssf oder verstehe ich das gerade falsch?
ssf ist richtig, denn pi sendet ja nur eine Nachricht an pj und umgekehrt, die irgendwann empfangen werden. zur ordnung der nachrichten von verschiedenen prozessoren sagt ssf nichts aus.
wenn pi noch ne zweite nachricht an pj senden würde, dann dürfte diese nicht vor der ersten empfangen werden.
hoffe es hilft!
Ah ok vielen dank!
War mri nämlich echt nicht sicher, ob das nur auf eine Prozessor bezogen war oder auf alles.
Aber dann weiß ich jetzt Bescheid, viel dank! ;)
Und zu den Transisitonsregeln (Skript S. 118), die sind doch nun wirklich nicht schwer!
Das einzige, was du dir daran merken musst, ist das du aus nichts sagen kannst, dass v mittels v terminiert.^^
warum wird im algorithmus 5.6 "auszeichen mit E(f1 U f2)" allen label(s) die f2 enthalten die ganze formel E(f1 U f2) zugefügt? nur weil f2 in dem zustand gilt, heißt das doch nicht, dass es einen erreichbaren pfad gibt in dem f2 gilt und vorher immer f1 oder?
Wichtig ist nur, dass F2 gilt.
weiß jetzt nicht welches beispiel du konkret meinst, aber normalerweiße wird erst überall f2 markiert und dann rekursiv alle pfade wo f1 gilt, die zu einer stelle führen, wo f2 gilt
Danke für eure antwort! Ist mit allerdings immer noch nicht so ganz klar. Wie rekursiv nach weiteren Zuständen gesucht wird ist klar, aber warum zu Beginn E(f1 U f2) in label(s) aufgenommen wird nur weil dort f2 gilt kapier ich noch nicht. E(f1 U f2) wird doch nicht von einem Zustand erfüllt in dem f2 gilt und was vorher ist, ist egal?!
E(f1 U f2) wird doch nicht von einem Zustand erfüllt in dem f2 gilt und was vorher ist, ist egal?!
Doch, genau so ist es.
Wunderbar, dann ist es jetzt klar. Danke!
öhm ich hab mal ne Frage zum "Harel-Graph(Automat)", kann es sein das dieser in der 2.Klausur dran kommt? Bin der Meinung sowas im Repetitorium gehört zu haben ^^… Das ding ist, wo finde ich was dazu?! Google hilft net so wirklich und im Skript find ich nix, wäre nett wenn mir jmd ne Quelle geben könnte =)
harel graph war doch das beispiel mit dem ofen am ende auf blatt 11?
http://en.wikipedia.org/wiki/State_diagram
harel graph war doch das beispiel mit dem ofen am ende auf blatt 11? http://en.wikipedia.org/wiki/State_diagram
ist das net ne Krippkestruktur?!
