Computer Science, 2017-02-15

Module: 
Computer Science
Examiner: 
Vornberger & Chimani
Date: 
Wed, 2017-02-15

FORMALIA

Modulprüfung: Info A, Info D
Fachsemester: 6.
Prüfer/2.Prüfer: Vornberger, Chimani

VORBEREITUNG

Was hast du zur Prüfungsvorbereitung benutzt?
Info A: Vorlesungsvideos, Skript, alte Zusammenfassungen, Info D: Skript und Internet (v.a. für die NPC-Beweise), abfragen lassen
Was wir hilfreich, was war weniger hilfreich?
Videos waren vor allem hilfreich, um noch mal zu sehen, was Vornberger betonend wichtig für jeweilige Implementationen findet, und wie die Graphenalgorithmen von Hand funktionieren. Bei Info D waren gerade Verbildlichungen und Beispiele sehr sinnvoll, um die NPC-Reduktionen richtig zu verstehen.

PRÜFUNG

Prüfungsdatum: 15.2.17
Wiederholungsprüfung? Nein
Note: 1.0
Bereiche nach Zeit: jeweils 10 Minuten, gefühlt Info D minimal länger

Fragensammlung: wie lauteten die Fragen im einzelnen?

Info A:

Was ist Rekursion?
Rekursion ist, wenn sich die Methode selbst aufruft. Dadurch wird der aktuelle Parameter so verändert, dass die Problemgroße schrumpft (z.B. von n auf n-1). Das wird so lange gemacht, bis das Problem so klein ist, dass es sofort gelöst werden kann (d.h. der Rekursionanker greift).

Was sind die Türme von Hanoi und wie wird da Rekursion verwendet? Gib die Rekursionsgleichung an und die explizite Gleichung an.
Hab das Problem der Türme von Hanoi prinzipiell erklärt (und schnell freiwillig aufgezeichnet, weil ichs so besser erklären konnte). Rekursion kommt daher, dass man zuerst n-1 Scheiben von start über ziel auf hilf ablegt, und so einfach die n-te Scheibe auf ziel legen kann. Diesen verlege-Aufruf kann man dann auf die n-1 Scheiben auf hilf genauso anwenden, bis eben alle n Scheiben auf ziel legen. Anzahl der Verlege-Operationen bei n Scheiben ist: f(n) = 0 wenn n=0, sonst 2*f(n-1)+1. Explizit Funktion also 2^n – 1.

Was ist denn die Rekursionsgleichung von Quicksort?
Hab kurz QuickSort erklärt (Sortieralgorithmus, sortiert abhängig von einem Pivotelement das Array rekursiv in eine kleinere & eine größere Hälfte). f(n) = f(n-k)+f(k)+n, d.h. das Pivotelement zerteilt das Array in eins, das k lang ist und eins, das n-k lang ist. Das n kommt davon, dass man sich ja immer die Grenzen der Teilarrays merken muss.
Wie wäre die Rekursionsgleichung denn, wenn man immer ein gutes Pivot hätte?
Dann würde das Array immer halbiert werden, also f(n)=2*f(n/2)+n
Was ist die Laufzeit von QuickSort?
Best/average: O(log(n)*n), worst O(n^2)
Gibt es Sortieralgorithmen, die da besser sind?
MergeSort (log(n)*n), aber man braucht noch O(n) extra Platz. HeapSort O(log(n)*n).
Was kann denn so ein Heap so?
Hab einen Heap definiert (bin Baum + vollständig + Schlüssel von Knoten x <= Schlüssel von Söhnen), dann aufgezählt: get_min, insert(Comparable x), delete(Comparable x), empty()
Wann kommt so ein Heap denn vor?
Hab dann erklärt, wie ein Heap im Minimal Spanning Tree benutzt wird & im gleichen Zug auch die Implementation vom MST erklärt: Wald von Knoten, Heap mit Kanten, nimm immer die günstigste aus dem Heap und schau, ob du sie in den Wald einfügen kannst – d.h. ob kein Kreis erzeugt wird.
Wie entdeckt man denn solche Kreise?
Hab den Wald von isolierten Knoten aufgemalt, die Repräsentation durch Chefs erklärt. Wenn Knoten x & y durch Kante (x,y) verbunden wird, übernimmt einer der Knoten die Repräsentation von beiden. Wenn x & y den gleichen Repräsentanten haben → Kreis im Spannbaum, verwerfe die Kante und nimm die nächste aus dem Heap.
Wie kann man die Chef-Suche verkürzen?
Durch Path-halving (kurz erklärt).
Und wie viel kostet dieses Path-halving so im O-Kalkül?
Inverse Ackermann-Funktion beschreibt die Kosten von Path-Halving (fast konstant, weil inverse Ackermann sehr langsam wächst)
Bei Dijkstra wird ja auch ein Heap benutzt. Was macht der Algorithmus denn?
Hab Single Source Shortest Path kurz angerissen (Knotenkosten vom Startknoten aus anfangs bei unendlich, dann immer wieder geupdatet bis an jedem Knoten günstigste Kosten stehen).
Es wird ja eine PriorityQueue aus dem Java Collection Framework verwendet. Was muss bei der Implementation also passieren?
Stand erst kurz auf dem Schlauch, bin dann aber darauf gekommen, dass die zu vergleichenden Knoten/Kanten vom Typ Comparable sein müssen, damit sie überhaupt von der PriorityQueue verglichen werden können

Info D

Was ist P, was ist NP?
Hab da einfach die Definitionen gesagt.
Was ist denn so der Unterschied zwischen einer deteterministischen und nicht-deterministischen TM im Vergleich zu PCs? Und was kann ein Computer so?
War mir nicht ganz sicher, worauf er hinaus wollte, hab dann aber erst mal erklärt, dass PCs eher deterministisch arbeiten und alles, was nicht-deterministisch in polynomieller Zeit von einer TM berechnet werden kann, bei PCs zu exponentiellen Laufzeiten führt. Außerdem wären PCs prinzipiell so mächtig sind wie TM, wenn sie denn einen unendlichen Speicher hätten.
Aber können Computer nicht mehr als TMs?
Nach kurzer Verwirrung bei der Trickfrage meinte ich dann: Nein.
Was gibt es noch für Komplexitätsklassen?
Bei NP: Schwach/stark NP-Vollständigkeit, dann noch Co-NP.
Moment, über NP-Vollständigkeit haben wir noch gar nicht geredet. Was ist das?
Entscheidungsproblem X NPC, wenn aus NP und X NP-schwer ist, also Reduktion von allen Problemen aus NP zu X deterministisch und in polynomieller Zeit machbar.
Was heißt denn „reduzieren“?
Hab die Definition davon gesagt.
Und was ist ein Zeuge genau?
Auch davon die Definition wiedergegeben.
Und was bedeutet jetzt schwach/stark NPC?
Hab zuerst erklärt, dass man eine Zahl a auf log(a) bits schreiben kann. Bei einem Wort, das n lang ist, kann der Wert der Zahl also sogar 2^n sein.
Basierend darauf dann die Definition gegeben.
So, und was ist Co-NP noch mal genau?
Alle Entscheidungsprobleme, bei denen det. und in polynomieller Zeit ein Zeuge für eine Nein-Instanz validiert werden kann. (Hatte auch die Def. übers Komplement von NP gegeben, da meinte Chimani, die sei nicht aussagekräftig genug, weil natürlich alle Probleme, die schwieriger als NP sind, auch im Komplement von von NP liegen.)
So, Themenwechsel. Was ist denn Berechenbarkeit und was ist Entscheidbarkeit?
Berechenbarkeit: „gibt eine endliche algorithmische Beschreibung … usw“, hab es sowohl für partielle als auch totale erklärt. Bezieht sich auf Funktionen. Entscheidbarkeit bei Problemen/Sprachen. L entscheidbar, wenn charakteristische Funktion berechenbar ist.
Warum gibt es überhaupt Algorithmen, die nur partielle Funktionen berechnen? Warum erlauben wir Algorithmen mit Endlosschleifen? Macht das nicht alles komplizierter?
Ich war total verwirrt und wusste nicht, worauf er hinaus wollte. Hab kurz überlegt („Hmm … warum erlauben Algorithmen Endlosschleifen …?“ Vornberger fand das wohl ziemlich lustig und hat kurz losgelacht), dann hat Chimani mir das Stichwort Ackermann-Funktion gegeben. Ich konnte mich noch vage daran erinnern, dass es LOOP-Programme gibt, die die Ackermann-Funktion nicht berechnen können – daraus hat man geschlossen, dass sie nicht berechenbar ist – man dann aber herausgefunden hat, dass GOTO/WHILE sie berechnen kann. Chimani hat das gereicht und dann noch erklärt, dass GOTO/WHILE die Funktion berechnen können, dann aber eben Endlosschleifen erlauben. Ergo: wegen solcher Funktionen haben Algorithmen mit Endlosschleifen ihre Existenzberechtigung.
Gut, wir wissen jetzt also, dass es solche unentscheidbaren Probleme und unberechenbaren Funktionen gibt. Beispiele?
Unentscheidbar: Wang-Parkett, PCP, Halteproblem, Wortproblem, Busy Beaver. Unberechenbar: Schrittzahl des Busy Beaver (S(n)), Kolmogorov-Komplexität
Suchen sie sich mal Busy Beaver oder Kp(w) aus.
Hab den Busy Beaver genommen: Definition davon gegeben. Es ist unentscheidbar, ob eine TM ein Busy Beaver ist. S(n) unberechenbar, weil sie zu schnell wächst. Dann noch die Unentscheidbarkeit mit dem Widerspruchsbeweis zum Halteproblem erklärt.

Was mußte schriftlich gelöst werden?
Ich hab freiwillig den Aufbau der Türme von Hanoi aufgemalt, die Rekursiongleichungen für die Türme und QuickSort, und wie man neue Kanten beim Minimal Spanning Tree einfügt.

Wie waren Einstieg, Ablauf, Ende, Bewertung und Begründung?

Ich kam in Vornbergers Büro, der direkt Chimani angeklingelt hat, hab 1-2 Minuten mit Vornberger Smalltalk betrieben, dann gings auch direkt los. Die Nervosität hat sich schnell gelegt, weil die ersten Fragen erwartet & einfach beantwortbar waren, und beide waren entspannt und nett im Gespräch. Hab meistens von selbst alles gesagt, was sie hören wollten, aber wenn sie spezifischere Dinge wissen wollten, haben sie da einfach noch mal nachgefragt. Ein paar Mal (v.a. bei Chimani) wusste ich nicht sofort, worauf die Fragen hinauswollen, aber dann haben sie meistens noch ein Stichwort gesagt, mit dem ich dann was anfangen konnte. Man hat immer gemerkt, wenn sie zufrieden mit den Fragen waren, was ziemlich praktisch war, um zu wissen, ob man jetzt aufhören sollte zu reden oder nicht.
Bewertung war in ner Minute durch, dann haben sie mir die Note gesagt und sich noch erkundigt, wo‘s jetzt für mich nach dem Bachelor hingeht, etc.

Lässt sich der Prüfer von den Antworten leiten?

Ich hab freiwillig den Minimal Spanning Tree als Heap-Anwendung gewählt, in dem Wissen, dass ich danach bestimmt den MST auch erklären muss, aber sonst waren die Themengebiete, die sie abfragen wollten, ziemlich unrüttelbar.