Gedächtnisprotokoll FGI210-1: Unterschied zwischen den Versionen
(Die Seite wurde neu angelegt: 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)? ...) |
Keine Bearbeitungszusammenfassung |
||
| Zeile 47: | Zeile 47: | ||
3. Falls EGa gilt, gib einen entsprechenden Pfad in klein-omega-Schreibweise an. Wie berechnet der Algorithmus diesen Pfad? | 3. Falls EGa gilt, gib einen entsprechenden Pfad in klein-omega-Schreibweise an. Wie berechnet der Algorithmus diesen Pfad? | ||
Außerdem gabs noch Aufgaben: Petrinetze, Vektorielle Zeitstempel, BPA Prozessgraphen und Bisimilarität, Paralleloperator und Prozessgraph | |||
Version vom 19. Februar 2010, 17:19 Uhr
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?
Außerdem gabs noch Aufgaben: Petrinetze, Vektorielle Zeitstempel, BPA Prozessgraphen und Bisimilarität, Paralleloperator und Prozessgraph