[BuK] Lösungen der Präsenzübungen

[abgemeldeter Benutzer]

Hi,
ist jemand so nett und stellt 'mal die Lösungen der Präsenzübungen hier ein?

Gruß
Philip

[serious]

Hätte ich prinzipiell auch Interesse dran.
Besonders Lösungen von den Reduktionen und Unterprogrammtechniken der 1. Präsensübung.

Sitzen hier und kriegen 2e nicht gelöst, das nervt

HELP !!

[$veno]

Kann zwar nicht die kompletten Lösungen online stellen, da ich keinen Scanner habe, aber kann mal kurz die Reduktion der 2e) der 1. PÜ skizzieren:

Reduktion des speziellen Halteproblems auf L_self:

Die Funtkion f(x) prüft zunächst, ob die Eingabe x syntaktisch korrekt ist, also x = <M> für eine TM M.
Wenn nein wird verworfen, wenn ja, dann konstruiert f(x) aus <M> die Gödelnummer einer TM M' mit folgender Eigenschaft:
M' übernimmt auf allen Eingaben das Verhalten von M außer auf der Eingabe <M'>. Auf der Eingabe <M'> ignoriert die TM M' die Eingabe und simuliert das Verhalten von M auf der Eingabe epsilon.

Hoffe das hat geholfen.


Gruß Sven

[mirko]

Sitzen hier und kriegen 2e nicht gelöst, das nervt

einscannen kann ich das nicht, aber zumindest die idee kann ich dir mal skizzieren:

Man konstruiere eine TM M_H, die H entscheidet. Diese besteht aus den Komponenten S, G und M_S. S ist der Syntax-Check. G ist eine Gödelnummer-Transformation, die die Eingabe <M>w in eine GNr <M*_w> transformiert. M_S ist das Orakel. Das Akzeptanzverhalten wird übernommen.

M*_w verhält sich wie folgt:

1. Wenn Eingabe ist <M*_w>, dann lösche eigene Eingabe; sonst verhalte dich beliebig
2. Schreibe w auf's Band
3. Simuliere M auf w

Ich glaube in Schritt 1 kann man auch einfach sagen "Lösche Eingabe", aber das o.g. wurde zumindest als korrekt korrigiert.

wenn du die implikationskette auch noch benötigst, sag bescheid. sonst schreib ich die nicht auf

edit: da war jemand schneller - naja, jetzt hast du 2 alternativen

[serious]

Danke Jungs, hat beides geholfen
Ich denke die Implikationskette ist dann klar.


M*_w hält ja nur auf seiner eigenen Gödelnr wenn die Simulation von M auf epsilon funktioniert. Richtig?

[Anand]

M*_w verhält sich wie folgt:

1. Wenn Eingabe ist <M*_w>, dann lösche eigene Eingabe; sonst verhalte dich beliebig

Versteh nicht ganz, warum man die eigene Eingabe zunächst löscht...??
Wäre nett, wenn du die Idee sagen könntest, was da hinter steckt

[serious]

Das ist schlecht formuliert

Schritt 2 und 3 werden nur ausgeführt, wenn die Eingabe die gödelnr war.
oder?

[Anand]

danke

[mirko]

Danke Jungs, hat beides geholfen
Ich denke die Implikationskette ist dann klar.


M*_w hält ja nur auf seiner eigenen Gödelnr wenn die Simulation von M auf epsilon funktioniert. Richtig?

ich würde eher sagen "M*_w hält ja nur auf seiner eigenen Gödelnr wenn die Simulation von M auf w funktioniert." das ergibt sich daraus, dass M*_w ja im letzten schritt M auf w simuliert. wenn das nicht terminiert, terminiert natürlich auch M*_w nicht.

Das ist schlecht formuliert

Schritt 2 und 3 werden nur ausgeführt, wenn die Eingabe die gödelnr war.
oder?

wenn die eingabe nicht die eigene gnr war, darf sich die M*_w beliebig verhalten. ob sie dann die schritte 2 und 3 ausführt oder nicht, bleibt ihr überlassen

[tobias]

Soweit es hier um die Musterlösung der 1. Präsenzübung geht (Berechenbarkeit), die kann HIER runtergeladen werden. (Buk-Ordner -> Praesenz-muloe.pdf)

[Sheol]

Hat denn jemand die Musterlösung von der zweiten Präsenzübung?

[CrazyPumuckl]

Hab mal ne Frage zur Präsenzübung 2, Aufgabe 3a.

Habe da folgendes überlegt: Man reduziere Clique auf Iso.

Die Clique in G sei die Menge C={0,...,k-1} (wobei 0,...,k-1 Knotenindizes sind). Für die Eingabe von Iso habe ich mir dann folgendes überlegt: G1 = G aus Clique, G2= G', wobei G' wie folgt konstruiert wird:

Jeder Knoten, der nicht in C vorkommt, wird 1:1 übernommen, d.h. v_i aus V nicht aus C => v_i in V_2 von G'.
Für alle Knoten, die in C enthalten sind, wende folgende Permutation an:
, wobei k = Anzahl der Elemente aus C, und i ein Element aus C sei. Dann werden die Knoten aus C sozusagen um einen Index permutiert, wobei der größte Index dann auf 0 gesetzt wird.
Jetzt übergibt man also G als G1 und G' als G2 an Iso. V2 besteht also aus den nicht-permutierten Knoten, die eh nicht in C waren, vereinigt mit den permutierten Knoten. Da ja alle Knoten aus C untereinander verkantet sind, so sind es auch die permutierten Knoten. Demnach müsste ja gelten, dass G1 und G2 aus Iso sind. Die Permutation alpha ist offensichtlich in polynomieller Zeit berechenbar, also müsste damit gezeigt sein. Kann man das so machen / so argumentieren?

[maddinac]

CrazyPumuckl hat geschrieben:

wobei G' wie folgt konstruiert wird:

Jeder Knoten, der nicht in C vorkommt, wird 1:1 übernommen

Du kannst doch bei der Konstr. nicht vorraussetzen, dass die Clique bekannt ist.

Ich hab mir den Rest nicht nicht durchgelesen, aber einfacher gehts auf jeden fall mit HC.

[CrazyPumuckl]

Nun, aber man kann doch die Knoten o.B.d.A von 0 bis |V|-1 durchnummerieren, und das k ist doch gegeben!? Ich zähle also die ersten k Knoten zu meiner Clique.

[MartinL]

Naja das Problem bei deiner Lösung ist wirklich, dass du deine Funktion, die Clique weder kennt, noch in Polynomieller Zeit berechnen kann.

Wichtig für die Aufgabe ist, dass es hier um Teilgraph isomorphismus geht. D.h. man kann einen Teilgraphen reingeben und gucken ob dieser in einem anderen Graph quasi enthalten ist.

Dann ist die Reduktion von Clique nicht so aufwendig.

Gefragt, hat G eine k CLIQUE?

Dann erzeugst du einen vollständigen Graphen G' mit k Knoten und fragst ob G' in G enthalten ist. Wenn das der Fall ist, dann gibt es in G' auch eine Clique.

Für Graphenisomorphie müsst man sich was anderes ausdenken