Klausur Komplexität von Algorithmen Feedback

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

1

Monday, September 2nd 2013, 4:50pm

Liebe Studenten,

ich würde mich freuen, wenn Sie Ihre Meinung zu der Klausur abgeben würden. Hat Ihnen der Schwierigkeitsgrad gefallen?

Für mich kann ich als kleines Resumée ziehen, dass es etwas unglücklich war, dass an zwei kleinen Stellen die Formulierung etwas ungenau war, welches ich während der Klausur noch korrigiert habe. Wir versuchen natürlich immer soetwas zu vermeiden. Außerdem hat mir der Raum nicht so sehr wie früher das Audimax gefallen (ich werde versuchen beim nächsten mal das Audimax wieder zu bekommen).

Beste Grüße,
Arne Meier

PS: Die Korrekt wird voraussichtlich 2 Wochen dauern. Ich werde dann hier im Forum und auf unserer Webseite bekannt geben, wenn es soweit ist.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

1nf1n1ty

Unregistered

2

Monday, September 2nd 2013, 6:28pm

Hallo,

also ich fand die Prüfung vollkommen okay. Vom Umfang her konnte ich sogar alle Aufgaben bearbeiten und war am Ende in der misslichen Lage mir überlegen zu müssen, welche Aufgabe ich dann doch noch durchstreiche um da bei der Bewertung keine Schwierigkeiten zu bekommen ..

Fehler können immer mal passieren und so tragisch war es jetzt nicht.

Der Schwierigkeitsgrad war auch in Ordnung; eine Kurzfrage und die Aufgabe mit HALF-SAT haben mir zwar etwas Nachdenken beschert, waren aber auch machbar.

Von einigen Anderen Teilnehmern habe ich gehört, dass sie die Verfahren/den Vorlesungsstoff/etc. zwar verstanden haben und anwenden können, aber (Zeit-)Probleme mit dem "Finden der richtigen Idee" hatten.

Go to the top of the page

banane

Praktikant

Posts: 5

Date of registration: Oct 12th 2011

3

Monday, September 2nd 2013, 6:33pm

Ich kam mit allem gut klar außer Aufgabe 4. Aufgabe 5 war ein bisschen gemein, weil man daran denken musste, den Pfad mit in die Lösung einzuschließen.
Aber nochmal zu Aufgabe 4, die lässt mich nicht mehr los:

1.) Habs jetzt nicht mehr so genau im Kopf, war HALF-SAT ausschließlich in KNF angegeben oder in beliebig aufgebauten Formeln?

2.) Wie funktioniert die Reduktion?
Hab zuerst über $SAT \preceq HALF-SAT$ nachgedacht, aber schnell verworfen, da man das Verhältnis erfüllender/beliebiger Belegungen nicht durch Hinzufügen neuer Variablen in zusätzlichen Klauseln verändern kann.
Mittlerweile bin ich auf $TAUT \preceq HALF-SAT$ über $\varphi \mapsto \varphi \wedge x_{neu}$ gekommen, aber TAUT ist ja leider aus coNP...

This post has been edited 3 times, last edit by "banane" (Sep 4th 2013, 10:59am)

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

4

Monday, September 2nd 2013, 6:33pm

Bei HALF-SAT war ich mir ziemlich unsicher, hatte mehrere Reduktionsfunktionen, die aber alle nicht so ganz funktioniert haben und am Ende hat mir dann die Zeit gefehlt für eine richtige Lösung.

Eine andere Sache war Aufgabe 3 (?) a), in den alten Klausuren kam nämlich nie der Zeithierarchiesatz dran, daher war ich davon ausgegangen, dass der auch diesmal nicht drankommt. Letztendlich kann ich ihn zwar, aber dann blieb dieser doofe Bruch mit dem Logarithmus und dann habe ich es sein lassen. Mit dem Platzhierarchiesatz wär's einfach gewesen.

Insgesamt also absolut ok, wenn man es kann, dann sollte es keine Probleme gegeben haben.

Go to the top of the page

pliedtke

Trainee

Posts: 42

Date of registration: Oct 25th 2010

5

Monday, September 2nd 2013, 8:45pm

HALF-SAT war wie bei relativ vielen anderen auch der einzige richtige Knackpunkt bei mir, ich habe eine Reduktionsfunktion die nicht zu 100% funktioniert, der "Trick" wollte mir während der Klausur aber leider nicht mehr einfallen.

Ein bisschen Schade fand ich, dass nicht einfach die drei Aufgaben mit den meisten Punkten gezählt werden. Nummer 3 hätte ich auch hinbekommen, wenn auch nicht perfekt. Damit wäre Nummer 4 gut ausgeglichen gewesen, aber weil es hieß, dass nicht garantiert werden kann welche Aufgaben gezählt werden wenn man alle macht hab ichs dann sein lassen...

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

6

Wednesday, September 4th 2013, 10:35am

Quoted from "banane"

2.) Wie funktioniert die Reduktion?

Wir zeigen eine Reduktion von SAT auf Half-SAT. Wenn $x_1,\dots,x_n$ die Variablen von der gegebenen Formel $\phi$ sind, dann ist eine Möglichkeit für die Reduktion die folgende Abbildung:
$f(\phi):= (\phi\wedge y)\vee\left(\neg y\wedge\bigvee_{i=1}^nx_i\right)$ .
Die Formel $f(\phi)$ hat $2^{n+1}$ Belegungen.
- Wenn $\phi$ unerfüllbar ist, dann ist der linke Teil immer falsch und der rechte Teil bringt lediglich

erfüllende Belegungen für

(was nicht genug für Half-SAT ist).
- Wenn $\phi$ erfüllbar ist, dann bringt der linke Teil

erfüllende Belegungen für

und der rechte Teil

erfüllende Belegungen für

macht zusammen $2^n-1+c\ge2^n$ für

.

PS: Schöne Reduktion für coNP-Härte. Die scheint zu stimmen, was dazu passt, da HalfSAT auch coNP-hart ist.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 1 times, last edit by "Arne" (Sep 4th 2013, 10:40am)

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

7

Wednesday, September 4th 2013, 10:38am

Mist, da hätte ich meine beiden Ideen nur kombinieren müssen.

Go to the top of the page

banane

Praktikant

Posts: 5

Date of registration: Oct 12th 2011

8

Wednesday, September 4th 2013, 11:11am

Quoted from "Arne"

$f(\phi):= (\phi\wedge y)\vee\left(\neg y\wedge\bigvee_{i=1}^nx_i\right)$

Tja, HALF-SAT war wohl nicht umsonst nicht in KNF...
Ich war ungeduldig und hab mir schon Hilfe erfragt: http://cstheory.stackexchange.com/questi…ess-of-half-sat
Da habe ich mir dann auf ähnliche Weise ins Gesicht gefasst...
Das Problem ist übrigens verwandt mit MAJSAT (nur mit unechtem Vergleich), das erleichtert das googlen.

This post has been edited 1 times, last edit by "banane" (Sep 4th 2013, 11:12am)

Go to the top of the page

werderkrümel

Praktikant

Posts: 19

Date of registration: Oct 19th 2010

9

Monday, September 9th 2013, 9:46am

Also gefallen hat mir der Schwierigkeitsgrad nicht

Insgesamt war es sicherlich in Ordnung, wenn auch vllt. etwas schwieriger als die letzten 2 - 3 Jahre.
Die Reduktion fand ich persönlich aber sehr schwer, v.a. in Anbetracht der Zeit und im Vergleich zu den alten Klausuren/Übungen. Wenn man die richtige Idee erstmal hat gehts natürlich

Ich bin aber gespannt ob die überhaupt jemand hatte, schließlich hatten selbst die Tutoren ziemliche Probleme damit als ich sie nach der Klausur danach gefragt habe.

Go to the top of the page

Ozz

Trainee

Posts: 102

Date of registration: Oct 19th 2010

10

Monday, September 9th 2013, 12:41pm

Ja also allgemein, war die Klausur machbar. Die Ankreuzaufgaben waren teilweise tükisch, aber mit überlegen und kombinieren waren sie auch gut lösbar. Ich fand auch das die Klausur im Vergleich etwas schwieriger als die vorherigen Klausuren war.

Allerdings hatte ich auch Probleme mit der HALF-SAT Aufgabe... Ich hab mir da die Methodik bissel von DOUBLE-SAT abgeguckt. $SAT \le DOUBLE-SAT$ war ja $f(\phi)= \phi \wedge (x \vee \neg x)$ wenn ich mich nicht täusche. Hier wurden aus min. 1 Belegund min. 2 gemacht. bzw aus mind. 2 wurden mind. 4 usw...

Wenn ich die Hälfte der Belegungen ansprechen möchte benötige ich ja theoretisch $2^{n-1}$ Variablen die ich verknüpfe? Sprich $SAT \le HALF-SAT$ wäre dann $f(\phi)= \phi \wedge \bigwedge_{k=1}^{n-1}(x_{k} \vee \neg x_{k})$ ? Oder mach ich da was falsch? Wenn $\phi$ un erfüllt ist, ist alles unerfüllt. Wenn $\phi$ erfüllt ist, kommen wir damit doch auf mind. halb soviele erfüllende Belegungen?

Arrr!!! :evil:

This post has been edited 1 times, last edit by "Ozz" (Sep 9th 2013, 2:03pm)

Go to the top of the page

nano

Alter Hase

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

11

Monday, September 9th 2013, 1:09pm

Ne, die Formel dort ist immer 0 wegen der Widersprüche in der Konjunktion. Wenn es ein großes Oder wäre, hättest du nur genau so viele Belegungen wie mit Phi alleine, da die x alle durch die Belegungen von Phi bestimmt werden.
Wenn du stattdessen neue Variablen nimmst, wird die Gesamtanzahl der Variablen mitverdoppelt.
Ist schon nicht so trivial...

Go to the top of the page

Ozz

Trainee

Posts: 102

Date of registration: Oct 19th 2010

12

Monday, September 9th 2013, 2:07pm

Hab mich da vertippt... habs korregiert. die eine Konjunktion muss natürlich eine Disjunktion sein...

Arrr!!! :evil:

Go to the top of the page

werderkrümel

Praktikant

Posts: 19

Date of registration: Oct 19th 2010

13

Monday, September 9th 2013, 2:16pm

So ähnlich dachte ich mir das auch, aber mit n neuen Variablen. Ich dachte dann hab ich die Anzahl an erfüllenden Belegungen oft genug verdoppelt

Ist ja aber wohl falsch...

Go to the top of the page

Anselm

borlark

Posts: 164

Date of registration: Oct 13th 2010

Occupation: WiMi ThI

14

Monday, September 9th 2013, 2:32pm

Wie Martin schrieb: Du verdoppelst damit nicht nur die Anzahl der erfüllenden Belegungen, sondern auch die Anzahl der nicht erfüllenden Belegungen. Das Verhältnis bleibt also gleich.

"Once you figure out what a joke everything is, being the comedian's the only thing makes sense."
~The Comedian

Go to the top of the page

Ozz

Trainee

Posts: 102

Date of registration: Oct 19th 2010

15

Monday, September 9th 2013, 3:05pm

Ah... macht Sinn... Danke
Verdammte Axt... na dann hoffen wir mal, dass es mit dem Rest reicht... eine gute Note kann ich nun leider nicht mehr erwarten V____________________________________________V

Arrr!!! :evil: