Fachschaft Informatik - Benutzerbeiträge [de]

Gedächtnisprotokoll FGI210-1

2010-02-19T18:32:34Z

92.224.122.145:

== Aufgabe 1 ==

TS1 und TS2 gegeben

1. L(TS1) und L(TS2) angeben

2. Produktautomaten TS3 konstruieren mit <math>Sync=(x,x) \forall x \in A</math>

3. L(TS3) "berechnen"

4. Gilt <math>L(TS3) = L(TS1) \cap L(TS2)</math> ? Falls ja, gilt dies sogar allgemein?

5.

== Aufgabe X1 ==

Algorithmus so ungefähr gegeben:

f(n)
{
v := 0
for i=0 to n
{
v:=v+i;
}
return v/n;
}

1. Welchen Ausdruck berechnet der Algorithmus für n>0?

2. Schätze die Zeit- und Platzkomplexität im uniformen Kostenmaß ab.
3. Schätze die Zeit- und Platzkomplexität im logarithmischen Kostenmaß ab.

== Aufgabe X2 ==

Kripke-Struktur gegeben.

Per CTL-Algorithmus soll geprüft werden, ob EGa gilt.

1. Markiere alle Zustände (+ dazugehörende Kanten), in denen a gilt

2. Markiere alle SZK und kennzeichne die nicht trivialen.

3. Falls EGa gilt, gib einen entsprechenden Pfad in an (<math>\omega</math>-regulärer Ausdruck). Wie berechnet der Algorithmus diesen Pfad?

== Aufgabe X3 ==

Per Induktion sollte gezeigt werden, dass für alle erreichbaren Markierungen in allen Plätzen m(p) > 0 gilt, unter der Vorraussetzung, dass m0(p) > 0 in allen Plätzen ist, und W~(t,p) > 0 für alle t und p gilt.

== Aufgabe X4 ==

Das Workflow-Netz aus Präsenzaufgabe 5.1 war gegeben.

1. Ist das angegebene Workflow Netz N korrekt? (mit Begründung!)

2. Gilt folgende Aussage: Ein Workflow-Netz ist korrekt gdw. sein Abschluss <math>\overline{N}</math> lebendig ist.

Außerdem gabs noch Aufgaben:
Petrinetze (Startmarkierung als Vektor von Multimengen angeben, Folgemarkierungen berechnen, ...)
Vektorielle Zeitstempel (in Graphen eintragen),
BPA (Prozessgraphen zeichnen, Ableitung im Prozessgraphenkalkül, Reduktion mit den Axiomen),
Bisimilarität, Paralleloperator und Prozessgraph in ACP

Gedächtnisprotokoll FGI210-1

2010-02-19T17:03:37Z

92.224.122.145:

Aufgabe 1

TS1 und TS2 gegeben

1. L(TS1) und L(TS2) angeben

2. Produktautomaten TS3 konstruieren

3. L(TS3) "berechnen"

4. Gilt L(TS3) = L(TS1) geschnitten L(TS2)? Falls ja, gilt dies sogar allgemein?

5.

Aufgabe X

Algorithmus so ungefähr gegeben:

f(n)
{
v := 0
for i=0 to n
{
v:=v+i;
}
return v/n;
}

1. Welchen Ausdruck berechnet der Algorithmus für n>0?

2. und 3. Zeit- und Platzkomplexität uniform und logarithmisch

Aufgabe X

Kripke-Struktur gegeben.

Per CTL-Algorithmus soll geprüft werden, ob EGa gilt.

1. Markiere alle Zustände (+ dazugehörende Kanten), in denen a gilt

2. Markiere alle SZK und kennzeichne die nicht trivialen.

3. Falls EGa gilt, gib einen entsprechenden Pfad in klein-omega-Schreibweise an. Wie berechnet der Algorithmus diesen Pfad?

Aufgabe X

Per Induktion sollte gezeigt werden, dass für alle erreichbaren Markierungen in allen Plätzen m(p) > 0 gilt, unter der Vorraussetzung, dass m0(p) > 0 in allen Plätzen ist, und W~(t,p) > 0 für alle t und p gilt.

Aufgabe X

Das Workflow-Netz von einem der Aufgabenzettel war gegeben und es sollte bestimmt werden, ob dies Korrekt ist (inkl. Begründung).

Des Weiteren sollte bestimmt werden, ob folgendes gilt: Workflow-Netz ist korrekt gdw. sein Abschluss lebendig ist.

Außerdem gabs noch Aufgaben: Petrinetze, Vektorielle Zeitstempel, BPA Prozessgraphen und Bisimilarität, Paralleloperator und Prozessgraph in ACP

Gedächtnisprotokoll FGI210-1

2010-02-19T16:59:03Z

92.224.122.145:

Aufgabe 1

TS1 und TS2 gegeben

1. L(TS1) und L(TS2) angeben

2. Produktautomaten TS3 konstruieren

3. L(TS3) "berechnen"

4. Gilt L(TS3) = L(TS1) geschnitten L(TS2)? Falls ja, gilt dies sogar allgemein?

5.

Aufgabe X

Algorithmus so ungefähr gegeben:

f(n)
{
v := 0
for i=0 to n
{
v:=v+i;
}
return v;
}

1. Welchen Ausdruck berechnet der Algorithmus für n>0?

2. und 3. Zeit- und Platzkomplexität uniform und logarithmisch

Aufgabe X

Kripke-Struktur gegeben.

Per CTL-Algorithmus soll geprüft werden, ob EGa gilt.

1. Markiere alle Zustände (+ dazugehörende Kanten), in denen a gilt

2. Markiere alle SZK und kennzeichne die nicht trivialen.

3. Falls EGa gilt, gib einen entsprechenden Pfad in klein-omega-Schreibweise an. Wie berechnet der Algorithmus diesen Pfad?

Aufgabe Y

Per Induktion sollte gezeigt werden, dass für alle erreichbaren Markierungen in allen Plätzen m(p) > 0 gilt, unter der Vorraussetzung, dass m0(p) > 0 in allen Plätzen ist, und W~(t,p) > 0 für alle t und p gilt.

Außerdem gabs noch Aufgaben: Petrinetze, Vektorielle Zeitstempel, BPA Prozessgraphen und Bisimilarität, Paralleloperator und Prozessgraph im ACP Kalkül