Wir beschäftigen uns gerade mit Aufgabe 4.8 (S.81) im F4 Skript und haben genau einen S-Invariantenvektor für das Netz N aufgestellt, nämlich (0,0,0,n,n)', was soviel heissen soll, wie weder in s4 noch in s5 liegt jemals eine Marke.
Aber eigentlich liegt doch auch in s3 nie eine Marke, da weder t3 noch t5 schalten können.
Hätte das nicht auch als ein S-Invariantenvektor rauskommen müssen?
Und da sind wir nochmal auf was Spannendes gestoßen, im Zuge von Aufgabe 6.1.(a). Ganz allgemein gefragt: Wenn die Prozessorkomplexität eines parallelen Algorithmus vom Typ O(n) ist und die Zeitkomplexität ebenfalls vom Typ O(log(n)), kann dann die Operationenkomplexität, die als Produkt der beiden anderen definiert ist, vom Typ O(n) sein? Müßte sie nicht vielmehr nach F3-Skript Seite 18 Satz (6)
"O(f(n))O(g(n)) = O(f(n)g(n))" also O(n * log(n)) betragen?
bei dem berechnen der S-Invarianten aus der matrix wird
ja offensichtlich die startmarkierung nicht miteinbezogen,
egal wieviele marken anfangs auf jeder stelle liegen,
die S-Invariante gilt garantiert,
wenn auf S3 anfangs 4 marken liegen würden,
wäre die anzahl der marken nicht konstant,
bei der startmarkierung in der aufgabe ist es aber zufällig so,
wären in der startmarkierung auf allen stellen keine marken,
dann wäre in diesem fall die anzahl der marken auf
allen stellen konstant null,
das kann man eben mit der matrix nicht ausrechnen!,
für die andere frage fehlt mir der skriptteil,
aber muss das wirklich das produkt der beiden sein?
können nicht die n prozessoren in endlich vielen schritten am
algorithmus beteiligt sein, und danach rechnen nur soviele
prozessoren weiter so dass es mit der operationenkomplexität hinkommt?
Das kam uns auch schon in den Sinn. Aber können denn die Invarianten *völlig* unabhängig von der Startmarkierung sein?
Ich meine, wir könnten doch auch eine ganz absurde Startmarkierung wählen, von der zwar aus kaum bzw. nichts Sinnvolles passieren kann, die aber die Invarianten verletzt, z.B. indem wir auf s5 zwei Marken tun und sonst nirgendwohin. Dann ist die Invariante "n * m(s4) + n * m(s5) = 0" hin.
Die Invarianten hängen vom NETZ ab. Und zur Definition
des Netzes gehören doch: P,T,F,…(je nach Netzart) UND
m_0!!!
zu Prozessorkompl. stand doch im Skript, dass man wirklich
das Produkt ausrechnet. Ich erinnere mich, dass Herr Jantzen
extra gesagt hat, dass die Prozessoren, die nichts (mehr) tun,
mitgezählt werden müssen. (Weil es halt nicht entscheidbar (?)
ist, ob ein Prozessor was zum Ergebnis beiträgt)
Aber können denn die Invarianten *völlig* unabhängig von der Startmarkierung sein?
Ich meine, wir könnten doch auch eine ganz absurde Startmarkierung wählen, von der zwar aus kaum bzw. nichts Sinnvolles passieren kann, die aber die Invarianten verletzt, z.B. indem wir auf s5 zwei Marken tun und sonst nirgendwohin.
Dann ist die Invariante "n * m(s4) + n * m(s5) = 0" hin.
ja aber die matrix errechnet ja auch nicht diese S-Invariante ;)
sondern:
n*m(s4) +n*m(s5) = n*m0(s4)+n*m0(s5) = n*2
für das beispiel mit 2 marken am anfang, und die gilt
was die matrix ausrechnet kann man nicht verletzten,
die S-Invarianten DER MATRIX sind unabhängig von der startmarkierung
(also hab jetzt 10 min nachgedacht und noch kein gegenbeispiel gefunden..)
und das ist doch verständlich, man sieht doch an diesem beispiel,
dass egal wieviele marken auf s4 und s5 liegen,
deren summe konstant bleibt,
mit besonderer transitionsanordnung geht das
und klar, zum gesamten netz gehören eventl. noch weitere S-Invarianten,
z.b. abhängig von der startmarkierung,
diese wird man wohl auch so erkennen,
ob es noch ganz andere gibt?..
ob es noch ganz andere gibt?..
Man kann alle Invarianten berechnen. Sie sind die
Lösung des Gleichungssystems (dN'*i bzw. i'*dN).
Das Problem, das auszurechnen, ist zwar NP-vollst.
(siehe F3), aber es ist lösbar.
Das ist ja gerade das *tolle* an den Netzen
im Gegensatz zu Programmen in Hochsprache…
Natürlich findet man auch Invarianten durch
Hingucken, wenn man sich anstrengt, aber es ist
glaube ich immer noch einfacher, eben das Gleichungs-
system zu lösen
ja aber die matrix errechnet ja auch nicht diese S-Invariante ;)
sondern:
n*m(s4) +n*m(s5) = n*m0(s4)+n*m0(s5) = n*2
für das beispiel mit 2 marken am anfang, und die gilt
Danke, das war mein Fehler.
