Computer Science, 2017-02-15

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

Info A

- Rekursion, was ist das?
Standard Definition gegeben

- Quicksort, wie wird Rekursion hier angewendet?
Quicksort eine Iteration erklärt (Aufsplitten an einem Median)
Im vergleich zu Mergesort erklärt wo da der Unterschied ist (nicht explizit erklärt wie die Rekursion genau funktioniert)
- Wo genau kommt dann die Rekursion?
Quicksort auf dem vorderen und dem hinteren Teil
Ausdrücklich darauf hingewiesen, dass es keine Hälften sind
- Angenommen wir garantieren, dass es Hälften sind, wie ist dann die Rekursionsformel?
f(n) = f(n/2) + f(n/2) + n
Auf das n am Ende kam ich erst als er gefragt hat wie ich denn nochmal auf die Hälften komme.
- Laufzeit von Quicksort?
best average und worst case gegeben
(kein Beweis)

- Was sind denn andere Sortieralgorithmen die immer n*log(n) schaffen?
Heapsort and Mergesort

- Was ist denn ein Heap?
Standard Definition gegeben

- Wo wird denn ein Heap genutzt?
Minimaler Spannbaum

- Dann erklären sie doch mal das Problem und den Algorithmus
Problem beschrieben und Algorithmus beschrieben (ohne genaue Implementation)
Erklärt wo der Heap benutzt wird

- Wie genau stellt man jetzt sicher das 2 Knoten nicht im selben Segment sind?
Das Prinzip mit dem Representanten und Path-Halving erklärt

- Wie weiß denn jetzt der Algorithmus wie er die Kanten in dem Heap arangieren soll?
Wusste nicht genau was er meint. Gefragt ob er meint wie man einen Heap baut.
- Nein. So eine Kante ist ja ein Objekt. Wie funktioniert das denn mit dem Vergleichen?
Das Objekt muss Comparable sein.
Dann hat er immer einzeln genau nachgefragt, wie denn das jetzt in Java aussieht mit dem Comparable und wie die Signatur der Klasse aussieht und der Methode compare_to und was die Methode für Rückgabewerte hat.

Info D

- P und NP was ist den das?
Definitionen gegeben und gesagt dass es Komplexitätsklassen sind
- Warum macht man denn die Unterscheidung
Hab angefangen mit polynomiell und exponentieller Laufzeit und warum das hilfreich ist zu unterscheiden.
Hab kurz gestoppt weil NP und P ja noch nichts mit polynomiell und exponentiell zu tun hat. Er meinte ich soll trotzdem erst mal fertig erklären.
- Okay und NP und P sind ja beide polynomiell haben sie gesagt also was ist jetzt der Unterschied.
Auf den Unterschied zwischen deterministisch und nicht deterministisch hingewiesen und dass es noch keinen nicht deterministischen Computer im real life gibt. War dann genug...

- Was ist denn NP-vollständig
Entscheidungsproblem in NP und NP-schwer
NP schwer definiert
reduzieren erklärt
- Dann gibts da noch ne Unterscheidung in NP-vollständig. Wie ist die denn?
stark vs schwach NP-vollständig
definition gegeben
- Was sind denn starke und schwache Probleme
Als schwaches Subsetsum genannt und erwähnt dass wir dafür die pseudopolynomiellen Algorithmus besprochen hatten.
Bei starkem hab ich jurz überlegt und dann Bin-Packing gesagt.
- Ja das ist richtig aber nicht sehr einfach zeigen. Es gibt eine Eigenschaft die das relativ einfach macht...
Probleme bei denen keine Zahlen eine Rolle spielen sind immer stark.

- Berechenbarkeit und Entscheidbarkeit was ist denn das?
Bei beidem die Definitionen gegeben
- Und was ist dieses Co-semi-entscheidbar
Definition für semi-entscheidbar und co-semi-entscheidbar gegeben

- Was sind denn Unentscheidbare Probleme
Wang, N-busy-beaver und Kolmogorov waren genug (Hätte sicher noch Halteproblem als klassiker hören wollen)

- Dann sagen Sie doch mal was das mit dem Kolmogorov soll.
Das Problem erklärt
- Warum ist das denn überhaupt interessant?
Kompression
- Und warum ist das jetzt unentscheidbar
Erklärt wie die Funktion funktioniert die mir das kürzeste Wort für eine Komplexität gibt
Erklärt, wie das dann so zu einem Widerspruch führt

ENDE

Feedback:
War alles ganz gut aber Sie hätten an ein paar Stellen ja schon nochmal nachhaken müssen
-> 1,3

Sonstiger Eindruck:
Es ist wichtig, dass man die Definitionen, wo es welche gibt, genau(!!!) kennt besonders in Info D. Versucht man eine sinngemäße Definition in eigenen Worten, ist die meistens nicht klar genug (oder auch falsch, weil ein kleiner aber wichtiger Teil fehlt), sodass genau nachgehakt wird, bis die wichtigen Begriffe fallen. Also die Definitionen besser genau so wie sie sind lernen (Funktionsformeln kann man natürlich umschreiben). Hab ich in meiner ersten Prüfung nicht gemacht und bin durchgefallen! Vornberger und Chimani sind beide sehr nett und weisen dich darauf hin, wenn was nicht komplett stimmt, aber man hat dann keine Zeit und nicht die Ruhe darüber nachzudenken, wo der Haken ist.