Computer Science, 2016-10-19

Module: 
Computer Science
Examiner: 
Vornberger und Chimani
Date: 
Wed, 2016-10-19

So in etwa ist es abgelaufen:

Info A:
- Ungerichtete Graphen, was fällt Ihnen dazu ein?
Habe kurz Graphen allgemein definiert [Graphen sind 2 Tupel, bestehen aus Knoten, die durch Kanten verbunden sind. Kanten können gerichtet sein und/oder mit einer Kostenfunktion gewichtet sein] und dann den Minimaler Spannbaum und Chinese Postman erwähnt

- Dann erklären Sie mal den Chinese Postman.
Der Chinese Postman möchte in einem ungerichteten, gewichteten Graphen die billigste Kantenrundreise Ablaufen. Am besten geht das in einem Eulergraphen – gerade Grade – Eulertour bla bla, Floyd’s all-pais shortest path mit ungeraden Problemknoten, als Clique (Hilfsgraph): Minimum cost matching -> die Kanten werden im Originalgraphen verdoppelt, jetzt hat man Eulergraphen

- Wenn man jetzt nicht die billigste Kantenrundreise, sondern Knotenrundreise haben möchte?
Dann muss man einen Hamiltonkreis finden.

- Wie kompliziert ist das und wie setzt man das um?
auf Details zum Hamiltonkreis war ich nicht vorbereitet, habe dann erzählt, dass vielleicht ‘ne Adjazenzliste gut wäre, wenn ich mich um die Nachbarknoten kümmern möchte und dass ich davon ausgehe, dass es recht kompliziert ist, da der Chinese Postman ja auch ziemlich komplex ist, alleine weil er Floyd beinhaltet.

- Da kann Herr Chimani ja vielleicht gleich nochmal zurück kommen.. Sie haben gerade Floyd erwähnt, was macht der Algorithmus denn?
Habe all-pairs-shortest-path Algorithmus erklärt.

- Können Sie dazu was aufschreiben? Dij^k, was heißt das genau?
.. bisschen rumgelabert: erstmal ist k^-1 die matrix mit den gegebenen Kantenkosten von knoten i zu j… Minimum aus aktueller und der vorherigen berechnen…

- Okay, und wenn ich jetzt nur einen Knoten habe und von diesem die kürzesten Wege berechnen möchte, wie geht das dann?
Auch noch kurz Dijkstra erklärt.

- Wechseln wir mal das Thema. Was ist Rekursion?
Selbstaufruf der Methode in der Deklaration des eigenen Methodenrumpfes, Teilprobleme, Rekursionsanker,…

- Was für Beispiele kennen Sie da?
Fibonacci, Fakultät, Türme von Hanoi

- Ja, Türme von Hanoi. Beschreiben Sie mal das Problem und wie wir dabei Rekursion nutzen können
Habe das Problem beschrieben und grob den Programmcode aufgeschrieben

- Und wenn ich jetzt die Laufzeit bestimmen möchte, wie mach ich das?
Rekursionsgleichung aufgeschrieben, bin dann aber dummerweise nicht auf die Laufzeit gekommen.

- Dann machen Sie mal die Wertetabelle dazu.
Wertetabelle ausgerechnet, stand aber blöderweise immer noch auf dem Schlauch.

- Das muss Ihnen jetzt wie Schuppen von den Augen fallen, als Informatikerin sieht man sowas
Hm..

-Ne? Dann wechseln wir jetzt.

Info D:
- Was heißt denn NP-vollständig?
Das ein Problem in NP liegt und sich jedes andere Problem auf dieses reduzieren lässt.

- Moment, und was ist denn NP überhaupt?
Dann fang ich mal ganz vorne an: Also P und NP sind Komplexitätsklassen für Entscheidungsprobleme… Habe die Standard- und die Definition über den Zeugen genannt

- Okay, dann haben sie vorhin von reduzieren gesprochen. Was heißt das genau?
Durch eine Reduktion von einem Problem A auf ein Problem B zeigt man, dass B mindestens so schwer ist wie A, weil man B als Spezialfall von A darstellen kann. Dafür muss es eine deterministisch in polynomieller Zeit berechenbare Funktion geben, die alle Instanzen von A in Instanzen von B mit demselben Wahrheitswert umwandelt.

- Kommen wir mal zu berechenbarkeit und entscheidbarkeit, was gibt es für unentscheidbare probleme?
Wang kachelung, kolmogorov, PCP, halteproblem

- Nehmen wir mal die Kolmogorov-Komplexität heraus, was ist das?
Die Kolmogorov-Komplexität beschreibt die beste Komprimierung einer Zeichenkette, das ist die Länge des kürzest möglichen Programms das w beschreibt. Aber das ganze ist eben nicht berechenbar. Das kann man in einem Widerspruchsbeweis zeigen. Dafür nimmt man an, dass die Kolmogorov Komplexität berechenbar ist und es ein Programm B(n) gibt, dass in einer for-Schleife Wörter ihrer Länge nach durchgeht und für jedes Wort prüft ob ob die Ko-ko des Wortes größer gleich dem eingegebenen n’s ist. Sobald ein Wort gefunden wurde, wird dieses zurückgegeben. Das Programm hat eine konstante Programmgröße, benötigt beispielsweise 7 Schritte um halt eben das kürzeste Wort, das mindestens so komplex ist wie n, zu erzeugen. Wenn n jetzt aber beispielsweise 9 ist, bekommen wir ein Wort, dass laut der Ko-Ko mindestens die Komplexität 9 hat. Das Programm hat dieses ja aber in 7 Schritten erzeugt, welches ja kürzer ist als die angeblich kürzeste Beschreibung des Wortes.

- Gut, dann kommen wir nochmal zum Hamiltonkreis zurück. Der ist nämlich NP-vollständig. Wie zeigt man das?
Ja genau, die NP-Vollständigkeit vom Hamiltonkreis kann man durch eine Reduktion von 3-SAT zeigen.

- Ja, und was ist 3-SAT?
3-SAT fragt dannach, ob eine logische Formel in der konjunktiven Normalform erfüllbar ist. Bei 3-SAT besteht jede Klausel maximal aus 3 Literalen. Also durch Oder-Verbindungen verknüpte Variabeln, die wiederum durch Und-Verbindungen verknüpft sind. Hatte mich da etwas verhaspelt und ein bisschen was verdreht. Chimani hat nochmal nachgehakt, was Klauseln sind und wie ich das genau meine. Habe dann auf Vornbergers Vorschlag hin kurz ein Beispiel aufgeschrieben.

- Und wie kommt man jetzt von solchen Klauseln auf einen Graphen?
Ich hatte leider überhaupt keine Ahnung von den Reduktionsbeweisen und konnte quasi nichts dazu sagen. Habe dann ein bisschen rumgelabert, dass man dafür erst SAT auf 3-SAT reduzieren muss, dass Cook-Levin die NP-Vollständigkeit von SAT gezeigt hat und es deshalb diese Kette gibt.

- Okay, Sie haben gesagt, dass SubsetSum auch von 3SAT reduziert wurde. Wissen Sie denn da die Beweisidee? Sie müssen mir nicht den kompletten Beweis wiedergeben, nur den Ansatz wenigstens.
Da konnte ich genauso wenig zu sagen und habe eigentlich nur noch etwas rumgedruckst bis die Zeit vorbei war..

Das müsste alles gewesen sein. Vornberger war teilweise schnell mit knappen Ideen zufrieden zu stellen (z.B. Dijkstra). Chimani hingegen hat meistens sehr genau nachgehakt. Zwischendurch ist es sehr gut gelaufen, aber wegen Laufzeit von Hanoi und den Beweisen, die ich nicht konnte, hat es nur für eine 2,7 gereicht.