Gedächtnisprotokoll FGI209-1: Unterschied zwischen den Versionen
Zeile 108: | Zeile 108: | ||
== Aufgabe 8 == | == Aufgabe 8 == | ||
Hier gab es viele Punkte zur Prozessalgebra. | |||
1. Menge der BPA-Terme definieren. | |||
2. Zwei Terme aus BPA gegeben, und Prozessgraphen zeichnen. | |||
3. Alle bisimilaren Knoten identifizieren. | |||
4. Reduktionskalkül anwenden. | |||
5. Sind sie bisimilar(Ja/Nein) Frage. | |||
6. | |||
7. Sind Prozessgraphen in BPA immer endlich? | |||
== Aufgabe 9 == | == Aufgabe 9 == |
Version vom 19. Februar 2009, 13:58 Uhr
Die Klausur war wesentlich schwieriger als die im letztem Jahr (sofern man das an dem Gprot erkennen konnte) Man musste vorallem viele Definitionen können, und es kam vieles dran was so direkt nicht in den Übungsaufgaben besprochen wurde.
Auffallend war wieder die Personenkontrolle am Eingang.
Insgesamt gab es 192 Punkte zu erreichen
Aufgabe 1
1. Transitionssystem TS
->(s_0) -> b (s_1) ->b (s_2) -> b ...
wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist. Formale Definition angeben:
S=
A=
tr=
S^0=
S^F=
2. Wie ist die akzeptierte Sprache des Systems?
3. Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert.
4. Geben sie die Omega-Sprache L^omega(TS) an
5. Gegeben das Transitionssystem TS_2 ->(s_0') <->c (s_1') wobei s_1' Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem TS_1 X TS_2 mit Sync={(b,c) } und gamma(b,c)=d an
Aufgabe 2
1. Geben sie die Definition einer Makierungsinvarianz an.
2. Geben sie die Definition einer Lebendigkeitsinvarianz an.
3. Geben sie die allgemeine Form eines Makierungsprädikates an.
4. Vervollständigen sie m->t (t ist in m aktiviert) <=>
wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.
Aufgabe 3
a) Geben sie die formale Definition von Beschränktheit eines Netzes an.
b) Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.
c) Beweisen oder widerlegen sie die Behauptung:
Wenn ein Netz beschränkt ist, und der Erreichbarkeitsgraph zwei oder mehr strenge Zusammenhangskomponenten besitzt, dann ist das Netz nicht reversibel.
d) Ändert es etwas, wenn das Netz unbeschränkt ist?
Aufgabe 4
Aufgabe 5
(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)
a) Ist es entscheidbar ob ein P/T Netz beschränkt ist?
b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?
c)
Ist die Erreichbarkeit für CPN entscheidbar?
d) Gegeben ist ein P/T Netz mit |P| Plätzen und |T| Transitionen. Wir wissen, dass es k- beschränkt ist. Geben sie eine obere Abschätzung für die Anzahl der Knoten an, die der Erreichbarkeitsgraph hat!
Aufgabe 6
Gegeben war ein CPN.
a) zeichne den Erreichbarkeitsgraphen
...
c) Gilt
<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?
Aufgabe 7
Hier gab es allgemeine Fragen zu einem Erreichbarkeitsgraphen RG(N) und einem Überdeckungsgraphen G(N) eines Netzes. Auch hier Ja/Nein Kreuze und begründen.
a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?
b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?
c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?
d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?
e) Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann soltle die Menge der unbeschränkten Plätze angegeben werden.
Aufgabe 8
Hier gab es viele Punkte zur Prozessalgebra.
1. Menge der BPA-Terme definieren.
2. Zwei Terme aus BPA gegeben, und Prozessgraphen zeichnen.
3. Alle bisimilaren Knoten identifizieren.
4. Reduktionskalkül anwenden.
5. Sind sie bisimilar(Ja/Nein) Frage.
6.
7. Sind Prozessgraphen in BPA immer endlich?
Aufgabe 9
Aufgabe 10
Aufgabe 11
Aufgabe 12
DTM und RAM
6 Multiply Choice Fragen Komplexitaetsklassen von irgendwas (uniformes Mass und logarithmischens foo fuer Stellen und Plaetze)
Aufgabe 13
Vektorzeitstempel in eine vorhandene Struktur eintragen