Gedächtnisprotokoll FGI209-2

Zum zweiten Versuch der FGI2-Klausur wurde in PhilA geschrieben, Aufsichten hatten Herr Valk und Herr Köhler. Insgesamt waren 181Punkte zu erreichen, der Schwierigkeitsgrad war ähnlich hoch wie zur ersten Klausur.

Aufgabe 1

1. Gegen waren zwei Transitionssysteme mit Sync = *leereMenge*. Geben sie das synchrone TS an.
2. Geben sie L(TS_1) und L(TS_2) an, bestimmen sie auch L(TS_3) = L(TS_1) \cap L(TS_2)

1. Formen sie TS_3 so um, dass es den Schnitt akzeptiert.
2. Geben sie die Synchronisationsmenge an.

Aufgabe 2

Gegeben war ein (Workflow-)Netz <math>\mathcal N_1</math>, wo die letzte Stelle mit einer Transition mit der ersten verbunden war, sowie <math>\mathcal N</math>, wo diese Transition weggelassen wurde.

1. Zeichnen sie den Erreichbarkeitsgraphen zu <math>\mathcal N_1</math>
2. ...
3. Geben sie drei Eigenschaften an, die ein Workflownetz ausmachen. Wahlweise formal oder informal.
4. Wann ist ein Workflownetz korrekt?
5. Ist diese Workflownetz korrekt?
6. Ein paar Multiple-Choice Fragen (so oder so ähnlich)
   1. Ist <math>\mathcal N_1</math> k-beschränkt für <math>k=1</math>?
   2. Ist <math>\mathcal N_1</math> k-beschränkt für <math>k=2</math>?
   3. Ist <math>\mathcal N_1</math> reversibel?
   4. Ist <math>\mathcal N_1</math> lebendig?

Aufgabe 3

Gegeben ist dieses Netz

und eine Schaltsequenz <math>m_1 \rightarrow^{t_1} m_2 \rightarrow^{t_2} m_3 \rightarrow^{t_3} m_4 \rightarrow^{t_2} m_5 \rightarrow^{t_3} m_6 \rightarrow^{t_4} m_7</math> mit der Anfangsmarkierung a = 8, b = 2.

1. Gebe die folgenden Markierungen an:
   1. <math>m_1(p_1) = \dots</math>
   2. <math>m_2(p_2) = \dots</math>
   3. <math>m_3(p_3) = \dots</math>
   4. <math>m_4(p_2) = \dots</math>
   5. <math>m_5(p_3) = \dots</math>
   6. <math>m_6(p_2) = \dots</math>
   7. <math>m_7(p_4) = \dots</math>
2. Welche allgemeine Beziehung besteht auf <math>p_4</math> zwischen a, b, r, y, q?
3. Ist das Netz k-beschrenkt für k=1? Begründe.

Aufgabe 5

Gegeben war ein Lückentext-Baum, etwa so:

         _ _ _ _ _ _ _ _
        /              \   
     _ _ _ _          _ _ _ _
    /      \         /       \
   _ _     _ _      _ _     _ _

der die Zwischenergebnisse eines bekannten Sortieralgorithmus aus der Vorlesung einzutragen waren. Es war eine Zeichenfolge, etwa 5 8 6 4 9 2 7 1, gegeben.

Außerdem gab es noch ein Paar Fragen

1. Wann ist ein Algorithmus optimal?
2. Ist dieser [Sortieralgorithmus] optimal?
3. Wie ist die Zeitkomplexität dieses Algorithmus?
4. Wie ist die Operatorenkomplexität des Algorithmus?

Aufgabe 6

Zwei BPA-Terme waren gegeben.

1. Zeichnen sie die Prozessgraphen.
2. Kennzeichnen sie die bisimilaren Knoten.
3. Bestimmen sie die Normalformen mit den Regeln R1-R5.
4. Sind die Terme bisimilar?

Aufgabe 7

Hier kam eine Aufgabe zum rekursiven Ableiten dran.

1. Zeichnen sie den Prozessgraphen <X|E> mit {X=Ya+c, Y=Xc}.
2. Leiten sie <X|E> mit für die Aktion a ab.
3. Wann ist eine Spezifikation geschlossen?
4. Ist diese Spezifikation geschützt?

Aufgabe 8

20 Punkte zu LTL und CTL

1. Gegeben war eine Kripkestruktur. Geben sie alle PLätze an wo die Formel gilt.
2. Wo liegen die Syntaktischen Unterschiede zwischen CTL und LTL?
3. Geben sie je eine Formel an die für CTL oder LTL nicht korrekt ist.
4. Geben sie Vor- und Nachteile von LTL- und CTL-Formeln an.
5. ...

Aufgabe 9

Man musste die logischen, nicht die vektoriellen, Zeitstempel eintragen.

Aufgabe 10

1. Wie unterscheiden sich der Ausfallalgorithmus von dem des byzantinischen Konsenses?
2. Was ist Nachrichtenkomplexität?
3. Geben Sie die Nachrichtenkomplexität des Ausfallalgorithmuses an.
4. Warum ist der erste Algorithmus aus der Vorlesung exponentiell?
5. Warum ist der zweite Algorithmus aus der Vorlesung polinomiell?