Bearbeiten von „Gedächtnisprotokoll FGI209-1“
Zur Navigation springen
Zur Suche springen
Warnung: Du bist nicht angemeldet. Deine IP-Adresse wird bei Bearbeitungen öffentlich sichtbar. Melde dich an oder erstelle ein Benutzerkonto, damit Bearbeitungen deinem Benutzernamen zugeordnet werden.
Die Bearbeitung kann rückgängig gemacht werden. Bitte prüfe den Vergleich unten, um sicherzustellen, dass du dies tun möchtest, und veröffentliche dann unten deine Änderungen, um die Bearbeitung rückgängig zu machen.
Aktuelle Version | Dein Text | ||
Zeile 7: | Zeile 7: | ||
== Aufgabe 1 == | == Aufgabe 1 == | ||
Transitionssystem TS | 1. Transitionssystem TS | ||
<math>\rightarrow \overset{\overset{a}{\curvearrowleft}}{(s_0)} \rightarrow^b \overset{\overset{a}{\curvearrowleft}}{(s_1)} \rightarrow^b \overset{\overset{a}{\curvearrowleft}}{(s_2)} \rightarrow^b ...</math> | <math>\rightarrow \overset{\overset{a}{\curvearrowleft}}{(s_0)} \rightarrow^b \overset{\overset{a}{\curvearrowleft}}{(s_1)} \rightarrow^b \overset{\overset{a}{\curvearrowleft}}{(s_2)} \rightarrow^b ...</math> | ||
*Formale Definition angeben: | |||
**S= | |||
**A= | |||
**tr= | |||
**<math>S^0</math>= | |||
**<math>S^F</math>= | |||
* Wie ist die akzeptierte Sprache des Systems? | |||
* Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert. | |||
* Geben sie die Omega-Sprache <math>L^\omega(TS)</math> an | |||
* Gegeben das Transitionssystem <math>TS_2 \rightarrow s_0' \leftrightarrow^c (s_1')</math> wobei <math>s_1'</math> Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem <math>TS_1 \times TS_2</math> mit <math>Sync=\{(b,c)\}</math> und <math>\gamma(b,c)=d</math> an | |||
== Aufgabe 2 == | == Aufgabe 2 == | ||
Zeile 34: | Zeile 34: | ||
# Geben sie die formale Definition von Beschränktheit eines Netzes an. | # Geben sie die formale Definition von Beschränktheit eines Netzes an. | ||
# Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an. | # Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an. | ||
# Beweisen oder widerlegen sie die Behauptung: <br | # Beweisen oder widerlegen sie die Behauptung: <br>''Wenn ein Netz beschränkt ist, und der Erreichbarkeitsgraph zwei oder mehr strenge Zusammenhangskomponenten besitzt, dann ist das Netz nicht reversibel.'' | ||
# Ändert es etwas, wenn das Netz unbeschränkt ist? | # Ändert es etwas, wenn das Netz unbeschränkt ist? | ||
Zeile 52: | Zeile 52: | ||
''(ich glaube man musste bei den Fragen Ja/Nein ankreuzen und begründen.)'' | ''(ich glaube man musste bei den Fragen Ja/Nein ankreuzen und begründen.)'' | ||
# Ist es entscheidbar ob ein P/T Netz beschränkt ist? | # Ist es entscheidbar ob ein P/T Netz beschränkt ist? | ||
# Ist es entscheidbar ob ein P/T Netz k-beschränkt ist? | # Ist es entscheidbar ob ein P/T Netz k-beschränkt ist? | ||
# Ist die Erreichbarkeit für CPN entscheidbar? | # Ist die Erreichbarkeit für CPN entscheidbar? | ||
# Gegeben ist ein P/T Netz mit <math>|P|</math> Plätzen und <math>|T|</math> Transitionen. Wir wissen, dass es <math>k</math>-beschränkt ist. Geben sie eine obere Abschätzung für die Anzahl der Knoten an, die der Erreichbarkeitsgraph hat! | # Gegeben ist ein P/T Netz mit <math>|P|</math> Plätzen und <math>|T|</math> Transitionen. Wir wissen, dass es <math>k</math>-beschränkt ist. Geben sie eine obere Abschätzung für die Anzahl der Knoten an, die der Erreichbarkeitsgraph hat! | ||
== Aufgabe 6 == | == Aufgabe 6 == | ||
Zeile 61: | Zeile 61: | ||
Gegeben war ein CPN. | Gegeben war ein CPN. | ||
a) zeichne den Erreichbarkeitsgraphen | |||
... | |||
b) Ist die Makierung (1'1 , <math> \emptyset </math>, 1'false) erreichbar? | |||
c) Gilt | |||
<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ? | |||
== Aufgabe 7 == | == Aufgabe 7 == | ||
Zeile 78: | Zeile 83: | ||
== Aufgabe 8 == | == Aufgabe 8 == | ||
Hier gab es viele Punkte zur Prozessalgebra. | |||
<math>t1 = d((ac + b)e) + d((b + c)a) + ba</math> | <math>t1 = d((ac + b)e) + d((b + c)a) + ba</math> | ||
Zeile 99: | Zeile 104: | ||
Noch eine Aufgabe zur Prozessalgebra. | Noch eine Aufgabe zur Prozessalgebra. | ||
1. Was für Dinge werden im BPA-Kalkül bewiesen? Bzw. um was dreht es sich im BPA-Kalkül. (Ja/Nein Fragen) | |||
a) <math>t_1 + t_2</math> | |||
b)<math> t_1 \rightarrow t_2 </math> | |||
c) <math> t_1 \underline{\leftrightarrow} t_2 </math> | |||
d) <math> t_1 = t_2 </math> | |||
2. Ist <math> t_1 \underline{\leftrightarrow} t_2 </math> entscheidbar? | |||
3. Ist <math> \neg (t_1 \underline{\leftrightarrow} t_2) </math> entscheidbar? | |||
4. Was bedeutet es, wenn das BPA-Kalkül korrekt ist? | |||
5. Was bedeutet es, wenn das BPA-Kalkül vollständig ist? | |||
== Aufgabe 10 == | == Aufgabe 10 == | ||
Zeile 113: | Zeile 126: | ||
Folgender Harelgraph war gegeben: [[Bild:FGI2-WS08-Klausur-1-Statechart.png]] | Folgender Harelgraph war gegeben: [[Bild:FGI2-WS08-Klausur-1-Statechart.png]] | ||
Man sollte das Zustandsdiagramm dazu malen. | |||
Weiterhin sollte man erklären, um was Harel-Graphen endliche Automaten erweitern. | |||
== Aufgabe 11 == | == Aufgabe 11 == | ||
Zeile 120: | Zeile 134: | ||
Aufgabe zum CTL-Modelchecking. | Aufgabe zum CTL-Modelchecking. | ||
1. Beweisen sie, dass zu einer gegebenen CTL-Formel <math> \phi </math> der Model-Checking Algorithmus die Laufzeit O( <math>|\phi|*(|S|+|R|)</math>) hat. | |||
2. Man musste die Formel EGa auf einer Kripkestruktur anwenden, und zeigen, wo sie gilt. | |||
== Aufgabe 12 == | == Aufgabe 12 == | ||
Zeile 127: | Zeile 142: | ||
DTM und RAM | DTM und RAM | ||
6 | 6 Multiply Choice Fragen | ||
Komplexitaetsklassen von ''irgendwas'' (uniformes Mass und logarithmischens foo fuer Stellen und Plaetze) | Komplexitaetsklassen von ''irgendwas'' (uniformes Mass und logarithmischens foo fuer Stellen und Plaetze) | ||
== Aufgabe 13 == | == Aufgabe 13 == | ||
[[Kategorie:Gedaechtnisprotokoll|FGI2]] | |||
Vektorzeitstempel in eine vorhandene Struktur eintragen | Vektorzeitstempel in eine vorhandene Struktur eintragen | ||