Hallo, ich habe da mal eine Frage zu dem F4 Skript, zu Aufgabe 4.2 (5 Philosphen). Wie kann man da die Invarianten berechnen? Beziehungsweise bei Aufgabe 4.1 ergab sich dasselbe Problem. da dort die Marken in s1 ja nach jedem Durchlauf mehr werden, wenn man nur das Teilnetz N' betrachtet.

Hallo, ich habe da mal eine Frage zu dem F4 Skript, zu Aufgabe 4.2 (5 Philosphen). Wie kann man da die Invarianten berechnen?

Wirkungsmatrix aufstellen, und das Gleichungssystem
[img]http://mokrates.de/cgi-bin/texstring?%5CDelta_N%20%5Ccdot%20w%20%3D%200[/img] (für T-Invarianten) bzw.
[img]http://mokrates.de/cgi-bin/texstring?%7B%5CDelta_N%7D%5Et%20%5Ccdot%20w%20%3D%200[/img] (für S-Invarianten)
lösen.

Beziehungsweise bei Aufgabe 4.1 ergab sich dasselbe Problem. da dort die Marken in s1 ja nach jedem Durchlauf mehr werden, wenn man nur das Teilnetz N' betrachtet.

Dann gibts halt keine Invarianten…

Wirkungsmatrix aufstellen, und das Gleichungssystem
[img]http://mokrates.de/cgi-bin/texstring?%5CDelta_N%20%5Ccdot%20w%20%3D%200[/img] (für T-Invarianten) bzw.
[img]http://mokrates.de/cgi-bin/texstring?%7B%5CDelta_N%7D%5Et%20%5Ccdot%20w%20%3D%200[/img] (für S-Invarianten)
lösen.

Nur so: Hast Du das mal fuer das PhilosophenProblem versucht?
Ich finde das nicht so simpel [img]http://www.fb18.de/gfx/26.gif[/img]

Naja, auch wenn's 10x15-Matrizen sind… die sind doch recht regelmässig aufgebaut, und somit gerade noch handhabbar. Auch wenns natürlich _viel_ Schreibkram ist.
(Wobei man die Invarianten natürlich auch durch "scharf hinsehen" "berechnen" kann…)

Naja, die Wirkungsmatrix hatte ich schon, nur wie man dann mit den Formeln umgeht, da breche ich mir meine Gehirnwindungen bei. Wahrscheinlich fehlt da nur ein kleines Bruchstückchen zum Verständnis, aber…

{EDIT: Die unten stehende Aussage, das ersteres Problem in P, letzteres in NP (und NICHT AUCH in P) ist, ist nicht richtig. Siehe weitere Nachrichten in diesem Thread}

Im Prinzip ist das aber doch einfach ein Lineares Gleichungssystem (vgl. M3 - Lineare Algebra), das zu lösen ist.

Wobei die Bestimmung der S-Invariante leichter sein dürfte, da der Vektor Komponenten in Z (= ganze Zahlen sind gemeint) hat, bei T-Invarianten sind sie in N (= natürliche Zahlen sind gemeint). Das erstere Problem ist in P, das letztere leider in NP (vgl. F3-Skript, Kapitel 8).

Könnt' ja eine Prüfungsfrage werden [img]http://www.fb18.de/gfx/25.gif[/img]

Cheers,
Frank

bei T-Invarianten sind sie in N (= natürliche Zahlen sind gemeint).

Danke. Da wär ich drauf reingefallen…

Wobei die Bestimmung der S-Invariante leichter sein dürfte, da der Vektor Komponenten in Z (= ganze Zahlen sind gemeint) hat, bei T-Invarianten sind sie in N (= natürliche Zahlen sind gemeint). Das erstere Problem ist in P, das letztere leider in NP (vgl. F3-Skript, Kapitel 8).

Könnt' ja eine Prüfungsfrage werden

Nun ja, falsch ist KEINE der obigen Aussagen, aber auch linear zu lösende Probleme sind in NP!
Beide Problem der Frage nach der Existenz von Invarianten (P und T) sind polynomiell lösbar,
und offensichtlich gilt ja auch [img]http://mokrates.de/cgi-bin/texstring?%5Cmathcal%7BP%7D%5Csubseteq%5Cmathcal%7BNP%7D[/img]. Ich hoffe im F3-Skript steht nichts von NP-Vollständigkeit, denn das ist falsch!
(vergl. F4-Vorlesung, so schon dabeigewesen…)

servus

Im F3 Skript steht auf Seite 153, dass zu einer Matrix A \in Z^(m x n) die Frage ob zu einem Vektor b \in Z^m ein x \in Z^n
existiert mit Ax = b in P liegt. Die Frage aber ob es ein x \in N^n gibt in NP.

Ich gestehe, dass ich das so interpretiert habe, dass letzteres automatisch bedeuten soll, dass dies nicht in P ist. Dazu (und das haette ich auch nicht einfach so annehmen duerfen) habe ich dies einfach auf die LGS beim Bestimmen von S- und T-Invarianten uebertragen, obwohl man hier vielleicht noch weitere Eigenschaften des Netzes ausnutzen kann und zudem stets weiss, dass b=0 ist.

Ist das Problem (obiges Ax = b mit x Vektor in N) allgemein in P oder nur bei dem speziellen Fall der T-Invarianten (mit u.a. obigem weiteren Wissen) ?

Ist nur die Frage ob ein solches x exisitert in P oder auch dessen Bestimmung?

Mit der Bitte um Vergebung [img]http://www.fb18.de/gfx/22.gif[/img]

Frank