Gedächtnisprotokoll FGI209-1 - Versionsgeschichte

1steenfa: Bot: Kosmetische Änderungen

2012-06-08T16:06:05Z

Bot: Kosmetische Änderungen

213.39.156.223: /* Aufgabe 1 */

2010-02-18T14:48:23Z

Aufgabe 1

← Nächstältere Version		Version vom 18. Februar 2010, 14:48 Uhr
Zeile 20:		Zeile 20:
	# Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert.		# Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert.
	# Geben sie die Omega-Sprache <math>L^\omega(TS)</math> an		# 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		# Gegeben das Transitionssystem <math>TS_2 \rightarrow s_0' \overset{c}{\leftrightarrow} (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 ==

Olli: aufgehübscht

2009-04-06T16:26:36Z

aufgehübscht

← Nächstältere Version		Version vom 6. April 2009, 16:26 Uhr
Zeile 7:		Zeile 7:

	== Aufgabe 1 ==		== Aufgabe 1 ==
	1. Transitionssystem TS		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:		# Formale Definition angeben:
	**S=		## S=
	**A=		## A=
	**tr=		## tr=
	**<math>S^0</math>=		## <math>S^0</math>=
	**<math>S^F</math>=		## <math>S^F</math>=
	* Wie ist die akzeptierte Sprache des Systems?		# Wie ist die akzeptierte Sprache des Systems?
	* Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert.		# Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert.
	* Geben sie die Omega-Sprache <math>L^\omega(TS)</math> an		# 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		# 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 61:		Zeile 61:
	Gegeben war ein CPN.		Gegeben war ein CPN.

	a) zeichne den Erreichbarkeitsgraphen		# zeichne den Erreichbarkeitsgraphen
			# Ist die Makierung (1'1 , <math> \emptyset </math>, 1'false) erreichbar?
	~~...~~		# Gilt <math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?

	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 83:		Zeile 78:
	== Aufgabe 8 ==		== Aufgabe 8 ==

	Hier gab es viele Punkte zur Prozessalgebra.		''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 104:		Zeile 99:
	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)		# Was für Dinge werden im BPA-Kalkül bewiesen? Bzw. um was dreht es sich im BPA-Kalkül. (Ja/Nein Fragen)
			# <math>t_1 + t_2</math>
	a) <math>t_1 + t_2</math>		## <math> t_1 \rightarrow t_2 </math>
			## <math> t_1 \underline{\leftrightarrow} t_2 </math>
	b)<math> t_1 \rightarrow t_2 </math>		## <math> t_1 = t_2 </math>
			# Ist <math> t_1 \underline{\leftrightarrow} t_2 </math> entscheidbar?
	c) <math> t_1 \underline{\leftrightarrow} t_2 </math>		# Ist <math> \neg (t_1 \underline{\leftrightarrow} t_2) </math> entscheidbar?
			# Was bedeutet es, wenn das BPA-Kalkül korrekt ist?
	d) <math> t_1 = t_2 </math>		# Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

	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 126:		Zeile 113:
	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~~.		# Male das Zustandsdiagram zu dem Harelgraphen.
			# Um was erweitern Harel-Graphen endliche Automaten?
	~~Weiterhin sollte man erklären, um~~ was Harel-Graphen endliche Automaten ~~erweitern.~~

	== Aufgabe 11 ==		== Aufgabe 11 ==
Zeile 134:		Zeile 120:
	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.		# Beweisen sie, dass zu einer gegebenen CTL-Formel <math> \phi </math> der Model-Checking Algorithmus die Laufzeit O( <math>\|\phi\|*(\|S\|+\|R\|)</math>) hat.
			# Man musste die Formel EGa auf einer Kripkestruktur anwenden, und zeigen, wo sie gilt.
	2. Man musste die Formel EGa auf einer Kripkestruktur anwenden, und zeigen, wo sie gilt.

	== Aufgabe 12 ==		== Aufgabe 12 ==
Zeile 142:		Zeile 127:
	DTM und RAM		DTM und RAM

	6 ~~Multiply~~ Choice Fragen		6 Multiple 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 ==

			Vektorzeitstempel in eine vorhandene Struktur eintragen

	[[Kategorie:Gedaechtnisprotokoll\|FGI2]]		[[Kategorie:Gedaechtnisprotokoll\|FGI2]]

	~~Vektorzeitstempel in eine vorhandene Struktur eintragen~~

JimiHendrix: Aufgabe 6 korriegiert

2009-03-27T10:30:44Z

Aufgabe 6 korriegiert

← Nächstältere Version		Version vom 27. März 2009, 10:30 Uhr
Zeile 65:		Zeile 65:
	...		...

	b) Ist die Makierung (1'1 , ~~false ,~~ <math> \emptyset </math>) erreichbar?		b) Ist die Makierung (1'1 , <math> \emptyset </math>, 1'false) erreichbar?

	c) Gilt		c) Gilt
	<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?		<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?

Olli: aufgehübscht

2009-03-26T17:34:38Z

aufgehübscht

← Nächstältere Version		Version vom 26. März 2009, 17:34 Uhr
Zeile 50:		Zeile 50:
	== Aufgabe 5 ==		== Aufgabe 5 ==

	(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.)''

	a)		# 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 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!
	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 ==		== Aufgabe 6 ==

Olli: dfdasdf

2009-03-26T17:29:32Z

dfdasdf

← Nächstältere Version		Version vom 26. März 2009, 17:29 Uhr
Zeile 44:		Zeile 44:
	# Wenn das Netz beschränkt ist, ist dann <math>RG(\mathcal N)</math> endlich?		# Wenn das Netz beschränkt ist, ist dann <math>RG(\mathcal N)</math> endlich?
	# Wenn das Netz unbeschränkt ist, ist dann <math>RG(\mathcal N)</math> unendlich?		# Wenn das Netz unbeschränkt ist, ist dann <math>RG(\mathcal N)</math> unendlich?
	# Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,~~...~~,omega) in G(N)?		# Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten <math>(\omega,\omega,\dots,\omega)</math> in <math>G(\mathcal N)</math>?
	# Wenn ein Platz <math>p_i</math> unbeschränkt ist, gilt dann <math>(x_0,x_1, \dots,\omega,...,x_n)</math>. (<math>\omega</math> ist an der Stelle <math>i</math>) für jeden Knoten im Überdeckungsgraphen <math>G(\mathcal N)</math>?		# Wenn ein Platz <math>p_i</math> unbeschränkt ist, gilt dann <math>(x_0,x_1, \dots,\omega,...,x_n)</math>. (<math>\omega</math> ist an der Stelle <math>i</math>) für jeden Knoten im Überdeckungsgraphen <math>G(\mathcal N)</math>?
	# ''Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann sollte die Menge der unbeschränkten Plätze angegeben werden.''		# ''Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann sollte die Menge der unbeschränkten Plätze angegeben werden.''

Olli: Aufgehübscht

2009-03-26T17:26:35Z

Aufgehübscht

← Nächstältere Version		Version vom 26. März 2009, 17:26 Uhr
Zeile 39:		Zeile 39:
	== Aufgabe 4 ==		== Aufgabe 4 ==

	Hier gab es allgemeine Fragen zu einem Erreichbarkeitsgraphen RG(N) und einem Überdeckungsgraphen G(N) eines Netzes.		Hier gab es allgemeine Fragen zu einem Erreichbarkeitsgraphen <math>RG( \mathcal N)</math> und einem Überdeckungsgraphen <math>G(\mathcal N)</math> eines Netzes.
	Auch hier Ja/Nein Kreuze und begründen.		Auch hier Ja/Nein Kreuze und begründen.

	a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?		# Wenn das Netz beschränkt ist, ist dann <math>RG(\mathcal N)</math> endlich?
			# Wenn das Netz unbeschränkt ist, ist dann <math>RG(\mathcal N)</math> unendlich?
	b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?		# Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?
			# Wenn ein Platz <math>p_i</math> unbeschränkt ist, gilt dann <math>(x_0,x_1, \dots,\omega,...,x_n)</math>. (<math>\omega</math> ist an der Stelle <math>i</math>) für jeden Knoten im Überdeckungsgraphen <math>G(\mathcal N)</math>?
	c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?		# ''Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann sollte die Menge der unbeschränkten Plätze angegeben werden.''

	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 5 ==		== Aufgabe 5 ==

Olli: Aufgehübscht

2009-03-25T14:49:36Z

Aufgehübscht

← Nächstältere Version		Version vom 25. März 2009, 14:49 Uhr
Zeile 32:		Zeile 32:
	== Aufgabe 3 ==		== Aufgabe 3 ==

	a)		# 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.
			# 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.''
	b)		# Ändert es etwas, wenn das Netz unbeschränkt ist?
	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 4 ==

Olli: aufgehübscht

2009-03-25T14:43:32Z

aufgehübscht

← Nächstältere Version		Version vom 25. März 2009, 14:43 Uhr
Zeile 25:		Zeile 25:


	1. Geben sie die Definition einer Makierungsinvarianz an.		# Geben sie die Definition einer Makierungsinvarianz an.
			# Geben sie die Definition einer Lebendigkeitsinvarianz an.
	2. Geben sie die Definition einer Lebendigkeitsinvarianz an.		# Geben sie die allgemeine Form eines Makierungsprädikates an.
			# Vervollständigen sie <math>m \rightarrow^t \Leftrightarrow \dots</math> wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.
	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 ==		== Aufgabe 3 ==

Olli: /* Aufgabe 1 */

2009-03-25T14:31:17Z

Aufgabe 1

← Nächstältere Version		Version vom 25. März 2009, 14:31 Uhr
Zeile 20:		Zeile 20:
	* Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert.		* Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert.
	* Geben sie die Omega-Sprache <math>L^\omega(TS)</math> an		* 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		* 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 ==

← Nächstältere Version		Version vom 8. Juni 2012, 16:06 Uhr
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>''Wenn ein Netz beschränkt ist, und der Erreichbarkeitsgraph zwei oder mehr strenge Zusammenhangskomponenten besitzt, dann ist das Netz nicht reversibel.''		# 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 62:		Zeile 62:

	# zeichne den Erreichbarkeitsgraphen		# zeichne den Erreichbarkeitsgraphen
	# Ist die Makierung (1'1 , <math> \emptyset </math>, 1'false) erreichbar?		# Ist die Makierung (1'1 , <math> \emptyset </math>, 1'false) erreichbar?
	# Gilt <math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?		# Gilt <math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?