Hi,
ich hab da einige Fragen aus den protokollen die ihr hier gepostet habt. einige konnte ich nicht beantworten, ich hoffe ihr könnt mir weiterhelfen:

1.)Warum ist die Komplexität immer das Minimum?
2.)Welche Komplexität hat Simple-Merge-Sort?
3.)Was ist die Komplexität einer DTM, einer NTM?
4.)Wo werden parallele Algorithmen eingesetzt?
5.)Wie berechnet man die T-Invariante?
6.)Wann akzeptiert eine TM ein Wort?
7.)Was heißt es, wenn ein Problem polynomiell reduzierbar auf ein anderes ist?
8.)Was macht W-Dach ?
9.)Wann ist eine Transition aktiviert?
10.)Kann man jedes gefärbte Petrinetz als S/T-Netz modellieren?
11.)Was ist eine S-Invariante? Wie berechnet man sie? Wenn ich dir ein Netz (grafisch) und einen Vektor gebe, von dem ich behaupte, dass er eine S-Invariante ist.. wie kannst du das nachprüfen?
12.)Gibt es noch andere Formalismen zum modellieren von Nebenläufigkeit?

Danke im voraus

zu 6.

Skript 2.5 L(A):= {w aus Sigma*| Es gibt ein u und ein v aus Gamma* und ein q aus der Menge der Endzustände, so daß gilt: Es gibt eine Erfolgsrechnung, so daß die DTM A aus dem Anfangszustand q0 mit dem LSK über dem ersten Zeichen der Bandinschrift w in eine Konfiguration mit dem Wort uv gelangt bei der der LSK über dem ersten Zeichen von v steht und die DTM im Zustand q ist}

Da u und v aus Gamma* sein dürfen, verkürzt sich das Ganze darauf, zu sagen: Wenn die DTM mit der Konfiguration q0w startet, muß sie irgendwann in einen Endzustand übergehen.

Ob dabei das gesamte Wort gelesen wurde oder 1 Million Arbeitsschritte mit und ohne Bandinschriftsveränderungen durchlaufen werden mussten, ist irrelevant.

Hmm. Dann such ich mir mal die leichteste Frage raus:

9.)Wann ist eine Transition aktiviert?

Dann wenn alle ihre Eingangsstellen in ausreichender Form belegt sind (also je nach Netzart ist auch eine entsprechende Anzahl und/oder Farbe wichtig).

zu 7.

Skript 8.11

Problem A heißt polynomial reduzierbar auf Problem B, wenn es eine DTM gibt, die (bei L(A) ist Teilmenge von Sigma* und L(B) ist Teilmenge von Gamma*) in polynomialer Zeit eine Funktion f als Abbildung von Sigma* nach Gamma* berechnet, so daß w genau dann Element von L(A) ist, wenn f(w) Element von L(B) ist.

Sprich: Du kannst diese o.b. DTM benutzen, schreibst w auf das Band und erhälst nach polynomialer Zeit das Wort f(w).

Ergänzung:

Wenn Du dann f(w) auf das Band der DTM B schreibst und das Problem B in polynomialer Zeit lösbar ist, weißt Du wiederum nach polynomialer Zeit, ob f(w) Element von L(B) ist.

Da die Hintereinanderausführung zweier in Polynomzeit beschränkter Schritte wiederum in Polynomzeit beschränkt ist, ist somit Problem A auch in polynomialer Zeit lösbar.

2.)Welche Komplexität hat Simple-Merge-Sort?

O(n log n)

Hab da ein Problem mit der Simulation DTM in NTM und umgekehrt. Im Skript habe ich nichts dazu gefunden. Danke

Steht alles aus Seite 38ff, beim Theorem, dass DTM = NTM