Gedächtnisprotokoll FGI209-2

Aus Fachschaft_Informatik
Zur Navigation springen Zur Suche springen

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)

A1.jpg

  • 3) Formen sie TS_3 so um, dass es den Schnitt akzeptiert.
  • 4) Geben sie die Synchronisationsmenge an.

Aufgabe 2

Aufgabe 3

Gegeben ist dieses Netz FGI2-Modulo-Netz.png

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

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


Aufgabe 4

Aufgabe 5

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 geschlossen?

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?