Computer Science, 2014-09-18

Module: 
Computer Science
Examiner: 
Chimani
Assessor: 
Vornberger
Date: 
Thu, 2014-09-18

Modulprüfung: Fachsemester: <6>

VORBEREITUNG

Was hast du zur Prüfungsvorbereitung benutzt?
Vorlesungsaufzeichnungen und Skripte

PRÜFUNG

Prüfungsdatum: 2014-09-18
Wiederholungsprüfung? nein
Note: 1,7 Bereiche nach Zeit: 10min:10min

Fragensammlung: wie lauteten die Fragen im einzelnen?

Info A

Was ist ein Suchbaum?
- binärer Baum, linker Teilbaum kleiner als Vater, rechter Teilbaum größer als Vater
Und wie implementiert man den?
- Durch Erben vom VerweisBaum und mit dem Interface Baum.
Welche Klassen benutzt man dabei?
- (zunächst war ich verwirrt, durch kleine Hilfe dann: ) Die Klasse Knoten. Ein Knoten besteht aus Inhalt und zwei Verweisen.
Wenn ich jetzt die Methoden insert, lookup und delete habe, wie mach ich das und in welcher Laufzeit geht das?
- Man steigt im Suchbaum bis zur passenden Stelle ab (insert, lookup), bei delete kommt es drauf an wie viele Söhne mein Knoten hat (das dann auch noch erklärt). Avg. case O(log n), worst case O(n)
Schwenk zum Sortieren. Erklären Sie doch bitte MergeSort. In welcher Laufzeit liegt der?
- Divide&Conquer, vordere Hälfte sortieren, dann hintere Hälfte sortieren, und dann ineinander mischen. Laufzeit O(n log n), log n fürs halbieren, n fürs zusammen mischen.
Bei MergeSort halbiere ich ja immer in der Mitte, gibt es einen Sortieralgorithmus der das nicht in der Mitte halbiert? Welche Laufzeit?
- QuickSort, falls Pivotelement kleinste/größte Element O(n2)
Welchen Suchalgorithmus gibt es denn, der kein Divide&Conquer ist, aber auch O(n log n) hat?
- HeapSort; ein Heap ist vollständig, Vater kleiner als Söhne.
Wie implementier ich den?
- Mit Hilfe eines Arrays (vorne Heap, hinten sortierte Folge)
Schwenk zum AVL-Baum: Was ist das? Wie lange dauert eine Rotation?
- Suchbaum, der balanciert ist (Höhe von linker/rechter Teilbaum max. um 1 unterschiedlich). Durch Rotation in konstanter Zeit erstellbar.
Schwenk zu geschlossenem Hashing: Was ist Hashing und wie funktioniert das?
- Möglichkeit Objekte zu speichern und leicht wiederzufinden. Hashfunktion ermittelt Speicherplatz, (linear, quadr., double Hashing) Sondieren falls Kollision, Zustandsarray und Comparablearray
Laufzeit? Von was hängt die ab?
- hängt vom Auslastungsfaktor ab (Berechnung: n/N), bei alpha = 0.8 in konstanter Zeit
Vergleichen Sie mit AVL-Baum
- s. Tabelle im Skript

Info D

Was ist P bzw. NP?
- Definition gegeben
Was bedeutet denn deterministisch/nicht-deterministisch?
- deterministisch bedeutet eindeutige Übergänge, nicht-deterministisch mehrere.
(hat als Antwort nicht gereicht, wusste nicht worauf er hinauswollte)
Nehmen wir doch mal Java. Ist das deterministisch oder nicht?
- nicht-deterministisch (rumgelabert bis ich dann gemerkt hab: ) nein, natürlich deterministisch, es ist ja vorgeschrieben, was als nächstes kommt.
Was für einen fiktiven Begriff müsste man einfügen, um Java nicht-deterministisch zu machen?
- „mache entweder-oder“ (hat gereicht)
Wie kann ich denn NP noch definieren ohne nicht-deterministisch zu verwenden?
- (bin nicht draufgekommen bis er mir das Stichwort „Zeugen“ gib) Wenn ich einen Zeugen in polynomieller Zeit auf Echtheit prüfen kann, liegt mein Problem in NP
Jetzt was anderes…was ist der Unterschied zwischen Berechenbarkeit und Entscheidbarkeit?
- Berechenbarkeit ist Voraussetzung für Entscheidbarkeit, Def. für Entscheidbarkeit gegeben
Was ist denn ein unentscheidbares Problem? Geben Sie ein Beispiel.
- PCP erklärt. Das ist unentscheidbar, weil ich jedes Tupel unendlich oft benutzen könnte, was nicht mehr berechenbar ist. Anschließend sind wir irgendwie noch aufs Halteproblem gekommen.
Und was ist das Wang-Parkett?
- Menge an Kacheln mit verschiedenfarbigen Seiten, unendliche Ebene damit füllen, was nicht berechenbar ist, wenn nur eine aperiodische Lösung existiert.
Was heißt aperiodisch und periodisch?
- periodisch bedeutet ich habe einen Block mit mehreren Kacheln, den ich wieder und wieder aneinanderfügen kann, aperiodisch muss ich immer wieder erneut schauen, welche Kachel ich jetzt verwenden kann.
Was ist NP-stark?
- ich habe ein NP-vollständiges (NPC) Problem und das gleiche Problem, das polynomiell beschränkt auf die Eingabe ist. Wenn dieses beschränkte Problem auch in NPC liegt, dann ist mein ursprüngliches NP-stark, wenn nicht NP-schwach.
Wie ist die Eingabe beschränkt? Die Länge der Eingabe ja nicht.
- (bin ich nicht draufgekommen, egal was er mir noch gesagt hat - richtige Antwort: Die Größe(Wert) der Binärzahlen ist beschränkt)

Was mußte schriftlich gelöst werden?

gar nichts

Persönlicher Kommmentar, Was war toll? Was war doof? Was war auffällig?

Beide waren nett und haben geholfen. Chimani hat viele Zusammenhänge gefragt, die in den Slides nur erwähnt wurden und die Vorlesung war bei mir schon über ein Jahr her.
Als kleiner Tipp: Redet viel, erzählt alles was ihr zu einem Thema wisst, dann kommen weniger schwierige Fragen dazu.

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

nicht wirklich, war alles kreuz und quer