Fachrat Informatik - Forum

Durch die Verdreifachung der Knoten bildest du die Richtung der gerichteten Kanten im ungerichteten Graphen ab.
Wenn du schaust wie die Kanten im ungerichteten Graphen aussehen: (v_in,v_mid) und (v_mid, v_out) sind für alle v' in V' schonmal dabei. Für jede (u,v) Kante im gerichteten Graphen wird nun eine (u_out, v_in) Kante im ungerichteten Graphen eingefügt (glaube du hast in deiner Formel nen Tippfehler eingebaut, u<->v vertauscht). Dadurch verlierst du die Information über die ursprüngliche Richtung der Kanten nicht und kannst entsprechend prüfen, ob ein äquivalenter hampath im ungerichteten Graphen existiert.

Quoted from "Sebastian"

(glaube du hast in deiner Formel nen Tippfehler eingebaut, u<->v vertauscht).

Nee, das paßt schon so, wie Skuld es aufgeschreiben hat (danke dafür ... )

Ich hab's mal an einem einfachen Beispiel nachvollzogen:

gerichtet mit Hampath:
[1] ---> [2] ---> [3] ---> [4]

ungerichtet mit Hampath:
gerichtete Kante (1,2) --> es gibt eine ungerichtete Kante (2.out,1in) usw. (aus (u,v) wird (v.out,u.in))
[1.out] ---- [1.mid] ---- [1.in] ---- [2.out] ---- [2.mid] ---- [2.in] ---- [3.out] ---- [3.mid] ---- [3.in] ---- [4.out] ---- [4.mid] ---- [4.in]
(da der Graph jetzt ungerichtet ist, ist es ja egal, daß es "am Ende" mit "in" losgeht)


gerichtet ohne Hampath:
[1] ---> [2] ---> [3] <--- [4]

ungerichtet ohne Hampath:
[1.out] ---- [1.mid] ---- [1.in] ---- [2.out] ---- [2.mid] ---- [2.in] ---- [3.out] ---- [3.mid] ---- [3.in]
und Verzweigung an 3.out:
... ---- [3.out] ---- [4.in] ---- [4.mid] ---- [4.out]


Nur wie schon gesagt, gilt auch hier wieder für mich: darauf wäre ich NIEMALS!!! gekommen ...

Quoted from "Panoramix"

Nur wie schon gesagt, gilt auch hier wieder für mich: darauf wäre ich NIEMALS!!! gekommen ...

Man kann halt üben so viel man will, wenn man Pech hat, fällt einem in der Klausur trotzdem nichts ein. Müssen wohl einfach das beste hoffen und wieder auf gnädige Kurzfragen zählen.

Sollte ich erneut nicht bestehen werde ich wohl mal fragen, ob nicht eine mündliche Prüfung (möglichst dieses Semester) noch möglich ist, da sonst das Anfangen meiner Bachelorarbeit in Gefahr ist..

Quoted from "cartman"

blöd ist auch, dass das System gewechselt wurde, bei den Klausuren zuvor haben alle Aufgaben gezählt, haben da zuviele bestanden oder warum wurde das geändert ?

Glaub nicht, da das mit der Auswahlklausur ja auch dadurch etnschärft wurde, dass Kurzfragen mit drin sind, die viele Punkte geben. Außerdem gab es (zumindest letztes Mal) mehr Punkte insg. und somit auch mehr Teilpunkte (schätze ich).

Glaub wenn du das ausreichend begründest, brauchst du dann keinen Algorithmus angeben.

Quoted from "cartman"

muss man hier überhaupt zeigen, d.h. mit einer Angabe eines Algorithmus', dass 2D-BIN-PACKING Element von NP ist, oder kann man einfach behaupten, das es so ist, aufgrund dessen, das 2D-BIN-PACKING eine "Unter"-Variante eines Problems(BIN-PACKING) ist, von dem man weiß, dass es Element von NP ist ?

Bei solchen Aussagen sollte man vorsichtiger sein. Zuerst frage ich mich gerade wieso es eine "Unter"-Variante sein soll, da es doch allgemeiner ist? Ist dann nicht eher BIN-PACKING eine "Unter"-Variante von 2D-BIN-PACKING?
Wenn ein Problem allgemeiner wird als ein schon bekanntes, heißt das noch lange nicht, dass es genau so schwer ist oder gar schwerer. Beispiele für soetwas findet man auch recht schnell, wenn man Vereinigungen von Problemen betrachtet: wenn man die "triviale" Sprache betrachtet, welche alle Instanzen enthält (also im Endeffekt nur einmal syntaktisch geprüft werden muss ob nur Zeichen aus dem Eingabealphabet vorkommen) und dann damit ein beliebiges NP-Problem vereinigt, kommt daraus wieder die triviale Sprache, die ja sehr einfach ist.

Bei 2D-BIN-PACKING ist es hingegen nicht wirklich schwer, da man eine gegebene 2D-Verteilung in Boxen schnell auf Korrektheit überprüfen kann (Mitgliedschaft in NP). Man muss lediglich testen, dass die jeweiligen Volumina auch passen (einfaches addieren und mit maximal erlaubtem Volumen vergleichen). Die NP-Härte kriegt man auch geschenkt, wenn man von BIN-PACKING reduziert und die eine Koordinate einfach mit 0 belegt. Habe hier jetzt gerade nicht mehr die genaue Definition von 2D-BIN-PACKING im Kopf, daher fällt das so unpräzise aus.

Dann mal viel Glück an alle für die Klausur. Und danke Arne, für die ausführliche Hilfe.

Soso, wie fandet ihrs? Mal ein paar Fragen zu dem, was bei mir hängen geblieben ist:

1. Kurzfragen
Sei für alle n N. Dann gilt => falsch
Wenn , folgt P = NP => falsch
Für alle gilt: => richtig, da ja der Satz von Cook aussagt, dass alle A aus NP auf SAT reduzierbar sind, also auch alle aus NL
=> richtig, da
Für alle gilt: => richtig, gleiche Begründung wie bei Frage 3
Wenn folgt P = NP => richtig, da SAT NP-vollständig
Wenn P = NP, dann ist => richtig
Wenn , folgt P = NP => falsch

2. Hierarchie
Zu zeigen war: (also von k=1 bis unendlich soll das heißen )
(Ich sehe gerade er stellt die doppelten Exponenten nicht richtig dar, das soll heißen: NTIME(2^n^k) und SPACE(2^n^log(n)))

Mein Vorgehen:


Also bleibt zu zeigen, dass (2^n^2 und 2^n^log(n))

Hier findet nun der Platzhierarchiesatz Anwendung. Zu zeigen ist, dass 2^n^log(n) echt schneller wächst als 2^n^2. Da beide die gleiche Basis "2" haben, kann diese bei der Wachstumsuntersuchung vernachlässigt werden, es ist also zu zeigen, dass


Dies sieht man entweder so, da im Nenner eine Exponentialfunktion steht und diese schneller wachsen als Polynome, oder man wendet L'Hospital zwei mal an und erhält

Damit ist , und der Platzhierarchiesatz gilt.

3. Zeigen, dass EVEN-SAT (aussagenlogische Formel, die eine gerade Anzahl an Belegungen hat) NP-hart ist

Das ist im Prinzip die gleiche Reduktionsformel wie für DOUBLE-SAT, oder?
Reduktion von SAT aus: f(phi) = phi UND (x ODER nicht-x)
Ist eine Reduktionsfunktion, da: ist aussagenlogische Formel, die nicht x enthält ist aussagenlogische Formel, die mind. 1 erfüllende Belegung besitzt phi UND (x ODER nicht-x) besitzt doppelt so viele erfüllende Belegungen wie besitzt eine gerade Anzahl erfüllender Belegungen (da Verdopplung immer zu einer geraden Zahl führt)

4. Der SUPERGRAPH
Da war ich mir nicht so sicher. Ich habe einen Algorithmus geschrieben, der wie folgt aussah:
Eingabe: Die Graphen G und H
1. Erstelle Adjazenzmatrizen (g)i,j und (h)i,j
2. Für jede Zeile in (g)i,j:
- if (g)i,j == (h)i,j, dann markiere diese Zeile
3. Für jede Zeile in (h)i,j:
- if (h)i,j unmarkiert, verwerfe
4. akzeptiere

Stimmt das so ungefähr?

Den Kurzfragen kann ich zu 100% zustimmen so - vielleicht mag uns das Arne ja bestätigen - oder gibts wieder ne Musterlösung?
Wenn ich die 16 Punkte der Kurzfragen sicher hab, dann kann ich jedenfalls wesentlich ruhiger schlafen, 10 weitere Punkte werden schon noch irgendwo abfallen...

Even-Sat hab ich ebenfalls genau so wie in der Übung gemacht, wobei mich diese Def. über der Aufgabe etwas verwirrt hat - kommt aber aufs selbe raus denk ich.

Bei der Hierachie hab ich aus U NTIME(2^n^k) ein NTIME(2^n^O(1)) gemacht, da k konstant ist und es da so ne gewisse Umformung von P=U TIME(n^k)=TIME(n^O(1)) gibt... Das wiederum ist ne Untermenge von SPACE(2^n^O(1)) und danach ist das ja trivial mit dem Hierachiesatz...

Tjo und den Supergraph hab ich wohl verkackt, hab mir da nen Zertifikat ausgesucht was H entsprach - aber das beweist ja nur NP und nicht P ... Naja, vielleicht gibts nen paar Teilpunkte. Hat mich hinterher geärgert weil eigentlich ist meine Lösung schon richtig, hätte statt H mit dem Zertifikat auszuwerten einfach H mit G auswerten müssen, hätte auch funktioniert mit dem Algo, den ich aufgeschrieben hab

Quoted from "Xular"

Even-Sat hab ich ebenfalls genau so wie in der Übung gemacht, wobei mich diese Def. über der Aufgabe etwas verwirrt hat - kommt aber aufs selbe raus denk ich.

Was hat dich an der Definition verwirrt? Stand da nicht einfach EVEN-SAT = {phi | phi hat eine gerade Anzahl an erfüllenden Belegungen} ?

Quoted from "Xular"

Tjo und den Supergraph hab ich wohl verkackt, hab mir da nen Zertifikat ausgesucht was H entsprach - aber das beweist ja nur NP und nicht P ... Naja, vielleicht gibts nen paar Teilpunkte. Hat mich hinterher geärgert weil eigentlich ist meine Lösung schon richtig, hätte statt H mit dem Zertifikat auszuwerten einfach H mit G auswerten müssen, hätte auch funktioniert mit dem Algo, den ich aufgeschrieben hab

Was für einen Algorithmus hast du denn benutzt? Den Fehler hab ich auch erst gemacht und war dann ganz entsetzt als ich gesehen habe, dass da "Zeigen Sie dass... ENTSCHEIDET" und nicht verifiziert Hab meinen ursprünglichen Algorithmus aber auch dann so ummodelliert, dass es passen sollte.

Nein, über der EVEN-SAT Aufgabe stand was von wegen "Wir definieren Belegungen als ..." whatever

Bei Supergraph hab ich einfach schrittweise das abgeprüft, was in der Aufgabe stand. Da stand ja z.B. explizit, was es bedeutet, wenn zwei Graphen isomorph sind. Also hab ich das einfach so hingeschrieben - war ja in der Übung oft auch so, dass man es nur etwas umformulieren musste... z.B. bei LPATH.