Computer Science, 2016-12-14

Module: 
Computer Science
Examiner: 
Vornberger
Assessor: 
Chimani
Date: 
Wed, 2016-12-14

Modulprüfung: Info A, Info D
Fachsemester: 7
Wiederholungsprüfung? Nein.
Note: 1,0
Bereiche nach Zeit: Jeweils 10 Minuten
Vorbereitung: Info A Vorlesungsvideos in doppelter Geschwindigkeit und Skript, Info D Vorlesungsslides, abfragen lassen von Leuten, die schon bestanden haben!

Wie lauteten die Fragen?

Info A:

Was ist denn eigentlich Rekursion?
Rekursion ist, wenn sich eine Methode in der Deklaration des Methodenrumpfes selbst aufruft. Der Sinn ist, dass das gegebene Problem in kleinere Teilprobleme aufgeteilt wird - solange, bis der sogenannte Rekursionsanker erreicht ist. Dann ist das Problem so klein, dass wir die Lösung wissen.

Wie wird Rekursion denn bei den Türmen von Hanoi genutzt?
Problem an sich erklärt, dann: Die Idee ist, dass man wenn man n-1 Scheiben verlegt hat, ja schon fast fertig ist und nur noch die n-te Scheibe verlegen muss. Also: Erst n-1 Scheiben von start über ziel nach zwischen, dann n-te Scheibe nach ziel verlegen, dann die n-1 Scheiben über start nach ziel.

Und wie ist das mit der Laufzeit, welche explizite Funktion würde die Rekursionsgleichung ergeben?
Da man 2 mal n-1 Scheiben und dann noch die n-te Scheibe: f(n)=2*f(n-1)+1. Das ergbit eine explizite Funktion von 2^n -1. Im O-Kalkül wäre uns die -1 egal, also O(2^n).

Wir haben auch über Fibonaccci geredet. Wie lautet da die Rekursionsgleichung?
Da lautet die GLeichung f(n)=f(n-1)+f(n-2)+1.

Und was ist der Unterschied zwischen den Türmen und Fibonacci?
Da hatte ich keine Ahnung, was er meinte, und sollte dann die Gleichungen aufschreiben. Hab ziemlich rumgedruckst und meinte, dass Fibonacci auf jeden Fall kleiner ist. Die meinten beide, ich solle nicht so kompliziert denken. Irgendwann hat Vornberger aufgelöst, dass der Unterschied ist: Bei Türmen n-1, bei Fibonacci auch einmal auch n-2.

Wie wird Rekursion denn z.B. bei Sortieralgorithmen verwendet?
Habe MergeSort und QuickSort erwähnt und meinte, dass z.B. bei QuciSort das Problem ja immer kleiner gemacht wird durch das Aufteilen in eine elementweise kleinere und eine größere Hälfte. Hab dann die Laufzeiten genannt und gesagt, dass QuickSort ja leider O(n^2) im worstcase hat.

Und woran liegt das?
Wenn man das Pivot-Element blöd wählt, z.B. immer das kleinste oder größte Element.

Ok. Was ist denn der Chinese Postman?
Problem erklärt. Zwei Fälle, entweder Graph ist Eulergraph oder nicht. Erklärt, was man in beiden Fällen macht. Dabei kamen wir natürlich auch auf Floyd zu sprechen.

Können Sie denn ein bisschen mehr über Floyd sagen?
Habe All-pairs-shortest-path erklärt und dass man Graphen generell ja entweder als Adjazenzmatrix oder -liste implementieren kann. Bei Floyd ist der Graph halt als Matrix gegeben. Habe dann die Idee erklärt: Entweder man hat schon den kürzesten Weg von i nacj j oder man kann den Weg verkürzen, indem man über k geht. Habe das dann formell nochmal aufgeschrieben mit der Matrix-Gleichung.

Info D:

Fangen wir mal ganz generell an: Was ist denn P und NP?
Habe die Definitionen von P und NP gegeben, auch die Def. mit der Überprüfung des Zeugens. Da hat er nachgefragt, was denn ein Zeuge ist. Habe ihm ein Beispiel einer 3-Sat-Instanz aufgemalt. Da ich nur "Problem" gesagt habe, hat er gefragt, ob dass denn für alle Probleme gelte. Hab dann korrigiert: "Entscheidungsprobleme."

Und was ist NP-vollständig?
Definition gegeben. Entscheidungsproblem muss in NP sein und NP-schwer. Habe dann von mir aus direkt NP-schwer erklärt und in dem Sinne natürlich auch, was denn Reduktion ist. Da ich nicht erwähnt habe, dass die Funktion, die man finden möchte polynomielle Laufzeit haben muss, hat er da nochmal nachgefragt, bis ich es explizit gesagt habe.

Was ist denn Berechenbarkeit und Entscheidbarkeit bzw. wie hängt das zusammen?
Habe erklärt, dass ein Entscheidungsproblem entscheidbar ist, wenn die charakteristische Funkion entscheidbar ist. Vornberger: "Redefehhler!" Ich: "Stimmt. Wenn die Funktion berechnbar ist." Vornberger: "Gut."
Habe dann noch semi-entschaidbar und co-semi-entscheidbar anhand des Halteproblems erklärt.

Welche unentscheidbaren Probleme haben wir denn so kennengelernt?
Busy-Beaver, Kolmogorov-Komplexität, Wang-Parkett, PCP und Halteproblem.

Ok, dann suchen sich sich aus dem Beaver und der Kolmogorov-Komplexität mal eins aus und erklären sie es.
Habe den Beaver genommen und erklärt, was die Frage ist und dass man die Funktion S(n) gern hätte, die einem die größtmögliche Anzahl an Schritten der TM berechnet, sodass die TM hält.
Dann die Argumentation: Wenn man S(n) berechnen könnte, könnte man das Halteproblem lösen, weil man dann ja einfach für jede TM immer nur S(n) Schritte abwarten müsste. Hat die TM dann nicht gehalten, tut sie es auch künftig nicht.

OK, und warum ist die Funktion genau nicht berechenbar?
Wollte darauf hinaus, dass die Funktion enorm schnell wächst. Habe ich erst nach zwei Versuchen dann gecheckt.

Und was kann man daraus für andere Funktionen schließen?
Wusste erst gar nicht, was er meinte, aber bin dann irgendwann drauf gekommen, dass für jede Funktion, die größer als S(n) ist, die gleiche Argumentation gilt.

Was ist denn schwache bzw. starke NP-Vollständigkeit?
Vorüberlegung, dass eine Zahl, die auf n bits codiert ist, höchstens 2^n groß sein kann. Dann schwache/starke Vollständigkeit erklärt: Wenn ein Problem, beschränkt auf polynomiell beschränkte Zahlenwerte, immer noch vollständig ist, ist es stark. Wenn es, auf diese Zahlenwerte beschränkt, nicht mehr vollständig ist, ist es schwach. Als Beispiel Subsetsum genannt.

Und wie wird das dann für die kleinen Werte bei Subsetsum umgesetzt?
Durch einen pseudopolynomiellen Algorithmus. Deswegen pseudopolynomiell, weil auch wenn die Codierung n lang ist, der Wert ja trotzdem exponentiell sein kann. Also sieht der Alg. erstmal nur polynomiell aus, kann aber durchaus exponentiell lang dauern dann.
------------------------
Was musste schriftlich gelöst werden?
Grundsätzlich gar nichts. Aber als ich Hanoi und Fibonacci vergleichen sollte, meinte Vornberger, es wäre hilfreich, sich das vielleicht nochmal aufzuschreiben. Hab aber von mir aus z.B. den Floyd-Algorithmus und die Ja-Instanz eines 3-Sat Problems aufgemalt.

Wie waren Einstieg, Ablauf, Ende, Bewertung und Begründung?
Da Chimani sich etwas Zeit gelassen hat, hab ich vorher n bisschen mit Vornberger geschnackt. Als Chimani dann da war, haben wir einfach angefangen. Ablauf war total entspannt. Auch, wenn ich mal nicht direkt die Antwort wusste, haben sie mir weiter Tipps gegeben und es immer so rübergebracht, als wäre ihre Frage nur nicht explizit genug gestellt gewesen.
Sie wollten schon immer die Zusammmenhänge wissen und haben sich nicht so für die Formeln an sich interessiert. Ich konnte das Gespräch aber ziemlich easy lenken, weil ich mir schon denken konnte welche Fragen als nächstes kommen. Das fanden die beiden auch recht amüsant und hatten nichts dagegen. Für die Bewertung haben sie sich 30 Sekunden Zeit genommen und danach noch ein bisschen mit mir geredet.

Verhalten der Prüfer:
Sehr fair und ganz entspannt. Hätte gedacht, dass ich bei dem Vergleich Hanoi/Fibonacci Punkte abgezogen bekomme, aber das fanden die überhaupt nicht wild. Haben mir immer geholfen, wenn ich mal nicht weiter wusste und waren bei richtigen Antworten auch immer begeistert.