Was kam alles dran?
ich hab zwar mitgeschrieben, hab aber alles wieder vergessen.

12 Aufgaben.
Strikordnung, Relationenprodukt etc. Der Prolog von Teil 1 halt

Petrinetz Erreichbarkeitsgraphen, Überdeckungsgraph, Unterschied P/T zu gefärbte Netze, s und t Invarianten ausrechnen, einmal direkt aus dem Netz eine s Invariante angeben. Son Zeugs halt. Achso, in einem gefärbten Netz Guards und Variablen an die Kanten schreiben, sodass da was gilt. Überdeckungsgraphen malen, Schaltfolge im Graphen finden, die im Netz nicht geht.

Prozeßalgebra: Graphen malen, ableiten, Bisimilarität am Graphen zeigen und danach bisimilare Terme hinschreiben. Rekursiven Graphen aufmalen, Im Graphen eine Schaltefolge mit 5 Aktionen und Tau Transition finden, ab||cd <- dazu den Graphen malen.

Laufzeiten parallels mergesort.

Laufzeit bizantinischer Konsens. Halt so die Essens der Sätze kennen und die Laufzeiten, Nachrichtenkomplexität, Nachrichtengröße (exp. und poly Algorithmus) kennen, wieviele Runden.


Mehr fällt mir nicht ein. Gibt aber ein ganz gutes Bild der Klausur, denke ich.

RSA: Formeln, Vorteil von Asymmetrischen Verfahren

Probabilistische Algorithmen: Vor- und Nachteile, 2 Beispiele geben

Ah, guter Überblick, das ruft ein paar Erinnerungen wach.

Strikordnung, Relationenprodukt etc. Der Prolog von Teil 1 halt

Aufgabe 1:
R = {(a,b), (a,c), (b,c), (c,d)}

Ist R eine Striktordnung? Ja / Nein + Begründung
{ Nein, Transitivität verletzt, Beispielsweise sind (a,c) und (c,d) in R, aber nicht (a,d) }

Bestimmen Sie R^2 und S=R\R^2.
{ R^2 = {(a,c)}, R\R^2 = {(a,b), (b,c), (c,d)} }

Bestimmen Sie S^+.
{ S^+ = {(a,b), (a,c), (a,d), (b,c), (b,c), (c,d) }

Ist S^+ eine lineare (=totale) Striktordnung? Ja / Nein
{ Ja. }

Zeigen Sie: Wenn [img]http://mokrates.de/cgi-bin/texstring?R%20%5Csubseteq%20(A%20%5Ctimes%20A)[/img] eine lineare Striktordnung ist, dann ist [img]http://mokrates.de/cgi-bin/texstring?%5Coverline%7BR%7D%20%3D%20(A%20%5Ctimes%20A)%20%5Cbackslash%20R[/img] eine partielle Ordnung.
1. Reflexivität:
2. Antisymmetrie:
3. Transitivität:

Petrinetz Erreichbarkeitsgraphen

Hmm, ich bekomme das Netz nicht mehr so richtig zusammen. Es hatte 5 Transitionen a bis e und 4 oder 5 Plätze. Zuerst war der Erreichbarkeitsgraph zu zeichnen.
Dann Multiple Choice: Beschränkt? {Ja} Reversibel? {Nein} Lebendig? {Ja} Noch irgendwas.
Geben Sie eine Markierungsinvarianzgleichung an, ohne dazu S-Invarianten zu berechnen. { Einfache Lösung wäre etwas wie: [img]http://mokrates.de/cgi-bin/texstring?m(p_4)%20%5Cleq%20100[/img], die aussagekräftigste Lösung war [img]http://mokrates.de/cgi-bin/texstring?2%20%5Ccdot%20m(p_1)%20%2B%20m(p_2)%20%2B%20m(p_3)%20%2B%20m(p_4)%20%3D%202[/img] (Vielleicht auch noch p5, wenn es den Platz gab.) }

Überdeckungsgraph

Recht einfaches Netz. Ein Zyklus mit zwei Plätzen und zwei Transitionen, dessen eine Transition zusätzlich auf Platz p3 Marken generiert, sowie ein zweiter solcher Zyklus, der die Marken von p3 wieder konsumiert.
1. Welche Plätze sind beschränkt, welche nicht?
2. Überdeckungsgraph konstruieren
3. Geben Sie eine Schaltfolge an, die im Überdeckungsgraphen möglich ist, jedoch nicht im Netz selbst. { abcdc }

s und t Invarianten ausrechnen

Das war wieder ein neues Netz mit 3 Transitionen und 3 Plätzen. Ein Platz war unbeschränkt, das Netz war aber reversibel (irgendwie konnten auf den Platz Marken geschmissen werden, die wurden aber von einer anderen Transition ins Nichts befördert). Keine bzw. leere Anfangsmarkierung, da die Markierung für die Aufgabe keine Rolle spielte.
{ T-Invarianten: k*(2 2 1). S-Invarianten: k*(1 1 0). }

Achso, in einem gefärbten Netz Guards und Variablen an die Kanten schreiben

Ein Platz mit Büchern ("petri", "dijkstra" und noch eins) und ein Platz mit Personen-Berechtigung-Tupeln (sinngemäß: [hans, 'a'], [petra, 'a'], [susanne, 'n']). Eine Transition, die diese Plätze im Vorbereich und einen weiteren im Nachbereich hat. Nun sollte man die Transition und Kanten so beschriften, dass nur Person-Buch-Tupel in den dritten Bereich wechseln können, bei denen die Person eine Ausleihberechtigung ('a') hat.

Unterschied P/T zu gefärbte Netze

Was muss gelten, um ein gefärbtes Netz in ein äquivalentes P/T-Netz umwandeln zu können? Beschreiben Sie außerdem, was Äquivalenz in diesem Zusammenhang bedeutet (informell).
{ Farbmengen müssen endlich sein. Äquivalenz: Bijektion zwischen den Markierungen und Schaltfolgen, so dass die übereinstimmen (und das ganze ein bisschen besser erklären und informeller - ganz formell steht's auf dem einen Aufgabenblatt). }

Prozeßalgebra: Graphen malen, ableiten, Bisimilarität am Graphen zeigen und danach bisimilare Terme hinschreiben.

Hmm… t1 = a + a + a*(b + cd)*a, t2 = a + a*(ba + cda) (zumindest so in etwa war es, die beiden Terme waren bisimilar, der erste enthielt aber eine überfüssige Auswahl und war dafür nicht so ausmultipliziert wie der andere).
1. Zeichnen sie die Prozessgraphen.
2. Welche der Teilterme sind bisimilar?
3. Sind t1 und t2 bisimilar? { Ja }
4. Wenden Sie den Reduktionsalgorithmus auf t1 und t2 an, um sie in Normalform zu bringen. Geben Sie an, welche Regeln Sie jeweils benutzt haben.
{ t1 wird beim Umwandeln zu t2, t2 ist bereits in Normalform. Regeln am Besten einmal mit eigener Nummerierung aufschreiben, also man muss die 5 Axiome nur kennen (von denen nur 3 benutzt werden) und nicht die Nummerierung aus dem Skript. }

Rekursiven Graphen aufmalen

Die Rekursion war geschützt, sogar linear geschützt. Also recht einfach; keine Aktionen, die sich am Ende des Terms ansammeln.

/Posting zu lang, Fortsetzung folgt.

Im Graphen eine Schaltefolge mit 5 Aktionen und Tau Transition finden

Dazu war angegeben, welche Aktionen durch tau ersetzt werden, man sollte den Graphen noch einmal zeichnen (der war aber auch sehr klein - oder sollte man ihn von vornherein schon mit tau zeichnen? Ich weiß das nicht mehr) und dann ließ sich auch schnell was finden. Die Aufgabe war: b und c sind durch tau ersetzt, finden Sie eine Schaltfolge mit genau 5 Aktionen aus der Menge {a,b,c,d}, die terminiert (d.h. sie konnte so viele taus enthalten, wie man wollte - möglich waren entweder 3 oder 4 taus).

ab||cd <- dazu den Graphen malen

Allerdings durften b und c kommunizieren und sonst niemand, das machte den Graphen einfacher.

Alles klar, nun erstmal GDB lernen.

oder sollte man ihn von vornherein schon mit tau zeichnen?

Wenn ich mich recht erinnere: nein, der tau operator war erst bei der schaltfolge.

Die Netze sahen afaik so aus:
[img]http://home.arcor.de/angeber/shared/fgi_ptnetz.gif[/img]
1. Erreichbarkeitsgraph aufgabe (Verklemmungsfrei: ja)
2. überdeckungsgraph
3. invarianten

S-Invariantengleichung zu 1 ohne matrix: 2*p1+p2+p3+p4+p5 = 2
S und T invarianten zu 3 habe ich wie f0k.

Die Netze sahen afaik so aus: […]

Ah, gut erinnert, Netz 2 und 3 kann ich so bestätigen. Netz 1 ist im Moment so nicht ganz gültig, weil vor p6 gar keine Transition steht. Die Transition, die Du ganz oben mit der großen Schleife gemalt hast, hat die Marke erstmal links hingelegt, das stimmt (aber ohne einen Platz p6 dazwischen, meine ich - den gab es IMHO nicht). Hmm, und die Transitionen von p1 abgehend hab ich auch in etwa so in Erinnerung, zumindest vom Verhalten her. Auch an die kreuzenden Kanten kann ich mich erinnern.

S-Invariantengleichung zu 1 ohne matrix: 2*p1+p2+p3+p4+p5 = 2

Ja genau. Also ohne Platz p6. Ersetz einfach p6 durch eine Transition und lass die Transition oben weg, dann müsste es stimmen!

(PS: Wer bist Du eigentlich? Du hast kein Foto [img]http://www.fb18.de/gfx/3.gif[/img])

Netz 1 ist im Moment so nicht ganz gültig, weil vor p6 gar keine Transition steht.

Ups, hatte ich vermurkst.

(PS: Wer bist Du eigentlich? Du hast kein Foto [img]http://www.fb18.de/gfx/3.gif[/img])

Lasse F. (In SE3, GDB und AD waren wir in der selben übungsgruppe).

Die Netze sind jetzt, so wie sie da stehen, richtig. Daran kann ich mich auch gut erinnern.

Zu der Prozeßalgebra Aufgabe: Die Tau Transition sollte er in der Schaltfolge berücksichtigt werden.
Die rekursion lautete:

X=aY + bZ
Y=cZ
Z=dY + d

Graphen aufmalen und dann eine Schaltefolge zu Tau{b,c}{a,b,c,d} finden, die genau 5 mal schaltet und dann terminiert.

Dummerweise habe ich Tau für Gamma gelesen und meine Schaltefolge lautete damit a,c,d,c,d oder ähnlich ;-( Oder b,c,d,c,d …. Mist. Die Zeichen sind aber auch zum verwechseln ähnlich.

Graphen aufmalen und dann eine Schaltefolge zu Tau{b,c}{a,b,c,d} finden, die genau 5 mal schaltet und dann terminiert.

Nein, sie sollte nicht genau fünf mal schalten, sondern es sollten fünf Aktionen aus der Menge {a,b,c,d} vorkommen, es waren also außer den fünf benannten Aktionen beliebig viele anonyme Tau-Aktionen erlaubt.

Mir ist noch eine Aufgabe eingefallen:

Harel-Graph gegeben (ziemlich einfach; ein elementarer Zustand und ein zweiter orthogonal in zwei Teile mit je zwei Unterzuständen geteilt).
Frage: Welche der folgenden Schaltfolgen sind möglich? { Ja, Ja, Nein }
{ Allerdings finde ich die Fragestellung im Nachhinein komisch… ein Harel-Graph gibt doch nur an, wie ein System auf bestimmte Ereignisse reagiert. Demnach wäre jede Folge von Ereignissen möglich, das System reagiert nur nicht immer darauf. Hoffe, das war keine Fangfrage in der Klausur. }

Noch ein Harel-Graph gegeben, diesmal mit History-Funktion.
Frage: In welchem Zustand befindet sich das System nach der Folge … ?
{ Das letzte Ereignis führte in die History-Funktion. Es war eine History-Funktion ohne *, also nur für die eine Ebene. Allerdings hatte der Zustand sowieso nur einen einzigen Unterzustand, damit wurde immer in den Default-Unterzustand dieses Unterzustandes gesprungen. }

Hmm. Weiter GDB lernen. Aber wir schreiben ja erst Montag [img]http://www.fb18.de/gfx/2.gif[/img]

weiß gar nicht, obs hier schon irgendwo gesagt wurde, aber auf eine E-Mail bzgl der Klausurergebnisse hat Herr Valk wie folgt geantwortet:

Ich denke Montag Abend steht das für uns fest. Ich gebe das im PrüA ab und habe mit STiNE nichts zu tun. Mit besten Grüßen Ihr Rüdiger Valk

Interessant ist, dass er meint, er müsse sich um Stine nicht kümmern. Dabei liegt das doch ganz klar in seiner Verwantwortung, dass die Ergebnisse dort reinkommen? Das PA hat damit doch gar nichts zu tun?

Interessant ist, dass er meint, er müsse sich um Stine nicht kümmern. Dabei liegt das doch ganz klar in seiner Verwantwortung, dass die Ergebnisse dort reinkommen? Das PA hat damit doch gar nichts zu tun?

Das PA war auch bisher für die Veröffentlichung von Klausurergebnissen zuständig (die Liste im Glaskasten), soweit ich weiß.
Warum sollte sich das geändert haben?

Hmm, kann dir keine Begründung dafür liefern, außer das wir ähnliches heute nach der GDB Klausur angesprochen hatten und wir als Antwort eben jenes bekommen haben (ich glaube sogar von Professor Ritter? - aber nagelt mich darauf nicht fest)

Wir waren gestern zufällig im Informatikum und haben nachgefragt, wann die Ergebnisse nun draußen sind. Man hat uns gesagt, dass die Punktzahl in jeder Klausur feststeht aber nicht die Note. Außerdem müsse Herr Valk die Note doch in Stine eintragen (obwohl er mir direkt nach der Klausur zusicherte, dass er das nicht macht ). Herr Valk ist diese Woche aber nicht da. Also kommen die Ergebnisse voraussichtlich nächste Woche ins Stine.

sobald jmd weiss, ob die ergebnisse aushängen/STiNE gerne mal hier ansagen.

Die FGI Ergebnisse sind jetzt in Stine. Den Durchschnitt poste ich mal hier nicht, weil er unterschiedlich ist, je nachdem, ob ich ihn bei "Meine Leistungen" oder "Prüfungsergebnisse" ansehe.

seltsam, AD steht nun auch drin. aber nur unter "meine leistungen", nicht unter "prüfungsergebnisse".

Auf jeden Fall hat FGI ein ganz katrastophales Ergebnis!!

Ja, Stine unterscheidet da anscheinend zwischen den Bachelorleuten (deren Ergebniss (7 haben bestanden) bekommen wir vielleicht unter "Prüfungsergebnisse" zu Gesicht) und den Diplomern, die die Klausur geschrieben haben (waren das überhaupt welche???) - diese Ergebnisse könnten die 11 bestandenen Klausuren unter "Meine Leistungen" sein?!
Auf jeden Fall sind 32 Klausuren dabei, die als nicht bestanden gewertet wurden. Keine Ahnung, ob da irgendwann auch mal zwischen Nicht-Werten, nicht-mitgeschrieben und zu wenig Punkte unterschieden wird.

So katastrophal finde ich das Ergebnis nicht. War doch abzusehen. Schau doch mal, wieviele rausgegangen sind und haben nicht werten lassen. Das waren doch mehr als die Hälfte. Dann war der Raum doch auf einmal fast leer. Daher fehlt mir da wirklich irgendwie mal die Unterscheidung zwischen nicht werten etc.


PS: AD steht bei mir auch nur unter "Meine Leistungen", dort aber mit derselben Note wir im Aushang!

Ja, Stine unterscheidet da anscheinend zwischen den Bachelorleuten (deren Ergebnis (7 haben bestanden)

Das ist zu bezweifeln. Prof. Valk schrieb in einer Rundmail:

die erste Klausur hat gezeigt, dass auch Studierende ohne Vorliebe
für Theorie diese gut bestehen können.
(Der Notenspiegel in Stine, wie er mir angezeigt wird, enthält viele
Ergebnisse mit "bestanden" nicht, zählt dafür aber auch die nicht
erschienen Stud. mit 5,0).

Es scheinen also einige Leute, die bestanden haben nicht dabei zu sein.

Im Graphen eine Schaltefolge mit 5 Aktionen und Tau Transition finden

Dazu war angegeben, welche Aktionen durch tau ersetzt werden, man sollte den Graphen noch einmal zeichnen (der war aber auch sehr klein - oder sollte man ihn von vornherein schon mit tau zeichnen? Ich weiß das nicht mehr) und dann ließ sich auch schnell was finden. Die Aufgabe war: b und c sind durch tau ersetzt, finden Sie eine Schaltfolge mit genau 5 Aktionen aus der Menge {a,b,c,d}, die terminiert (d.h. sie konnte so viele taus enthalten, wie man wollte - möglich waren entweder 3 oder 4 taus).

ab||cd <- dazu den Graphen malen

Allerdings durften b und c kommunizieren und sonst niemand, das machte den Graphen einfacher.

Alles klar, nun erstmal GDB lernen.

Kann vielleicht jemand diese Schaltfolge mal angeben..? Stehe mit dem Tau-Operator noch auf Kriegsfuß… Wäre echt nett.. Danke

Die Aufgabe war: b und c sind durch tau ersetzt, finden Sie eine Schaltfolge mit genau 5 Aktionen aus der Menge {a,b,c,d}, die terminiert (d.h. sie konnte so viele taus enthalten, wie man wollte - möglich waren entweder 3 oder 4 taus).

Kann vielleicht jemand diese Schaltfolge mal angeben..? Stehe mit dem Tau-Operator noch auf Kriegsfuß… Wäre echt nett.. Danke

X=aY + bZ
Y=cZ
Z=dY + d

Beginn war bei <X|E> und b, c sind durch tau ersetzt, also ist eine mögliche Schaltfolge:[latex]a \tau d \tau d \tau d \tau d[/latex] (Beginn bei <X|E> und dann hin- und her zwischen <Y|E> und <Z|E>.) Wenn Du den Prozessgraphen aufzeichnest, lässt sich das leichter nachverfolgen.