Mein zweiter Versuch in BuK ist in die Hose gegangen und ich hatte die 
zweifelhafte Ehre, das Opfer einer mndlichen Prfung zu sein :-)

1) zuerst hat er gefragt: was ist das Clique-Problem, das hab ich ihm genannt.
Dann wollte er Clique auf 3Sat reduziert haben, dann gings erstmal um die 
Codierung einer Formel als Graph, wofr ich in dem Moment zu dumm war:
man hat ja 3KNF:  UND (x oder y oder z)
und ich berleg die ganze Zeit wie ich die einzelnen Literale Kodieren soll 
(als Knoten? als Kanten? aber man hat ja 3 und kann die alle vertauschen, 
weil die oder-Verknpft sind...), anstatt einfach so ein ganzes 
(x,y,z)-Tripel als Knoten zu nehmen, das war einfach dumm.
Das hat er dann gelst und die einzelnen Knoten untereinander aufgeschrieben. 
Dann hat er gefragt, wie die verbunden werden.
Da stand ich dann auch auf dem Schlauch, ich habe mich erinnert dass wir das 
gemacht haben, aber wie das genau aussah, da kam ich einfach nicht mehr 
drauf.
Das hat er dann gelst und gesagt, dass man die Knoten aus einem Tripel nicht 
verbindet, sondern Kanten zwischen den Tripeln zieht: Sei x aus einem Tripel 
und !x aus einem anderen, dann zieht man zwischen denen eine Kante.

2) Dann sollte ich Rucksack auf Subsetsum reduzieren; erstmal die Probleme 
nennen, hab ich gemacht.
Er hat die Probleme dann formal aufgeschrieben und es ging weiter:
Dann fr die Funktion KP-Gewichte = KP-Profite = Zahl aus Subsetsum setzen: 
war kein Prob mehr.
Und dann wollte er wissen, wie ich die Korrektheit dieser Abbildung zeige.
Da hab ich mir nur gedacht... WTF? Korrektheit? Wie jetzt...
Was er wissen wollte: x Element SSS <=> f(x) Element KPE
Hab ich sogar genannt und als er dann sagte, dass das genau das war was er 
hren wollte, htte ich am liebsten mit dem Kopf auf den Tisch gesmasht, weil 
ich genau das (nmlich w in L1 <=> f(w) in L2) weiter oben schon 
aufgeschrieben hatte, deshalb dachte ich eigentlich das wr schon klar, das 
knne er nicht meinen wollen (erinnert mich an Datenstrukturen: der Prof 
hatte spter was gefragt, das ich oben schon so hnlich aufgeschrieben 
hatte).
Man sortiert die richtige Lsung als trivial aus und sucht dann im brig 
bleibenden Dunkeln, was er wohl meinen knnte... Htte ich nicht laut gedacht 
und das gesagt, wr das nix geworden.

Dann wollte er noch wissen warum w in SSS <=> f(w) in KPE in beide Richtungen 
geht, da hab ich mir nur gedacht: "ISSO, wie soll ich das begrnden?" Man 
sucht also nach einer Begrndung und wei schon, dass die ganz billig sein 
muss.
Er fragt dann, was so ein Wort x aus SSS denn sei. Ich bin erstmal nicht drauf 
gekommen, was er damit jetzt meint, bis er ein Beispiel aufgeschrieben hat: 
a1=11, a2=3, b=12, dann hab ich gesagt, dass das nicht in der Sprache liegt, 
weil 11+3 nicht 12 ist, dann war auch klar was er wissen wollte: Ein Wort ist 
in der Sprache, wenn es akzeptiert wird. Ist klar, war nur ber 7 Ecken 
versteckt.
Aber zurck zur eigentlichen Frage, da konnte ich dann nur sagen dass das 
irgendwie klar ist, keine Ahnung wie ich das begrnden solle, das hat er dann 
als trivial eingesehen :-)

3) Dann wollte er wissen wie wir Hamiltonkreis als NPC-zugehrig gezeigt 
haben.
Mir ist direkt das Diamantengadget eingefallen, aber das war eigentlich als 
HC -> DHC in meinem Kopf abgespeichert.
Dann stellte sich raus, das war wohl SAT auf HC und wre richtig gewesen.
Er hat mich dann noch gefragt wie die Gadgets aufgebaut sind (wie sind die 
Variablen der Formel kodiert und wie fgt man den zustzlichen Knoten ein), 
Aber das konnte ich nur ungefhr, weil mein Kopf mit 300 Seiten anderen Zeugs 
voll war.

Naja, dann war die Zeit um und ich war fucked.

Ich hab gerne "will Graph als Formel" benutzt, wenn wir "wollen Formel als 
Graph" haben wollten und peinlicherweise mehrmals bei L1 <= L2 die 
Pfeilrichtung vertauscht

Er sagte dann, das wre knapp nichts geworden (wobei ich eher das Gefhl 
hatte, dass ich noch nie so schlecht war).
Tip fr den 3. Versuch war dann, die Reduktionen zu lernen die wir hatten und 
die Unterprogrammtechnik auch nochmal (obwohl die in der Mndlichen nicht 
drankam).
Tip vom Assistent (der nur protokolliert hat) war noch, die Reduktionen der bungen 
und Vorlesung zu wiederholen, damit die sitzen und auch dann auf hnliche 
Probleme auszuweiten.

rgerlich, dass die Prfung so gelaufen ist, ich htte dem so viel Zeug wie 
aus der Pistole geschossen nennen knnen, aber vom reinen Prfungsergebnis 
gesehen, war die Leistung einfach bel.

----------------

Naja, die dritte Klausur war dann ein voller Erfolg, siehe mein Lernscript hier 
auf s-inf.
Wenn man sich dieses Script verinnerlicht und zustzlich die Fragekataloge beantworten 
kann ohne nachzudenken und die Probeklausuren gut rechnen kann, dann ist die Klausur 
sicher bestanden.
Trotzdem keine schne Erfahrung, die Entscheidung "Leben im Arsch vs nchstes Semester",
das kann durch keine 2er-Note in der Klausur ausgeglichen werden.