Computer Science, 2013-08-13

Module: 
Computer Science
Examiner: 
Prof. Vornberger, Prof. Chimani
Date: 
Tue, 2013-08-13

Prüfungsdatum: 13.08.2013
Wiederholungsprüfung? nein.
Beisitzer: Vornberger und Chimani haben für den jeweils anderen protokolliert
Note: 1.0
Bereiche nach Zeit: 15/15

Fragensammlung: wie lauteten die Fragen im einzelnen?

Was ist eine Hash-Tabelle?
- ich hab von offenem und geschlossenem Hashing erzählt, linearem und quadratischem Sondieren und vom Double-Hashing

Und wie ist da so die Laufzeit (bei geschlossenem), bzw. wovon hängt die ab?
- normalerweise konstant, aber abhängig davon, wie voll das Array ist

Was ist der direkte Konkurrent von der Hash-Tabelle?
- AVL-Baum

Dann vergleichen Sie die beiden doch mal.
- die Tabelle aus der Vorlesung runtergerattert

Mit welcher Methode vom AVL-Baum kann man denn sortieren?
- da wusste ich erst nicht so richtig, was er wollte. Nach etwas nachhaken kam ich dann aufs Traversieren.

Und mit welcher Traversierung geht das?
- Inorder.

Dann schreiben Sie doch mal public static void inorder auf. Nee, lieber preorder, dann wird's etwas spannender.
- Hab ich gemacht

Und mal angenommen, Rekursion wäre jetzt aus irgendeinem Grund verboten, wie macht man das dann?
- Iterativ mit Keller, da sollte ich Verweise in den Keller malen, was wann im Keller liegt

Was für ne Laufzeit hat das?
- linear

Dann schwenken wir jetzt mal zu den Graphen um. Was für Algorithmen gibt es da so? Welcher gefällt Ihnen besonders?
- Single Source Shortest Path.

Was berechnet der?
- Den kürzesten Weg zwischen einem Knoten s und einem Knoten t.

Wie ist der implementiert?
- In einer Adjazenzliste

Was ist die andere große Möglichkeit, sowas zu implementieren?
- Adjazenzmatrix

Was sind da die Vor- und Nachteile?
- da kam ich erst nicht drauf, nachdem er's aufgemalt hat, fiel mir dann ein, dass ich im Array direkt auf die richtige Stelle zugreifen kann, es aber mehr Platz wegnimmt und sich deswegen eher für vollständige Graphen eignet. Die Liste ist besser bei dünn besetzen Graphen.

Dann erklären Sie mal Single Source Shortest Path.
- Knotenwerte werden nach und nach aufgefüllt, am Anfang haben alle außer dem ersten unendlich (auch hier musste er ein bisschen nachhaken)

____

Dann ging es mit Info D weiter.

Was ist ein nicht-berechenbare Funktion?
- da hab ich erst sehr rumgedruckst und was von unentscheidbaren Problemen erzählt, das wollte er natürlich nicht hören. Dann fiel mir die Funktion der Schritte des Busy Beavers ein. Den sollte ich dann erklären und sagen, warum er nicht berechenbar ist (die Funktion wächst zu schnell)

Wir haben ja gesagt, der Busy Beaver ist unentscheidbar. Woran haben wir das festgemacht?
- sonst könnten wir auch das Halteproblem lösen.

Und wie ginge das?
- wir wüssten, wann jedes Problem spätestens terminiert und wenn es bis dahin nicht gehalten hat, hält es nicht

Was ist der Unterschied zwischen P und NP?
- deterministisch vs. nicht-deterministisch in poly. Zeit

Was ist NP-Vollständigkeit? (nach zu ungenauer Antwort nachgehakt) Was für Eigenschaften muss ein NP-vollständiges Problem haben?
Jedes andere NP-vollständige Problem muss darauf reduzierbar sein.

Suchen Sie sich mal ein NP-vollständiges Problem aus, da haben wir ja ein paar kennen gelernt. Suchen Sie sich mal eins aus.
- ich hab mir 3SAT ausgesucht

Was ist 3SAT?
- Logische Formel in KNF mit max. 3 Literalen pro Klausel, wir suchen eine Begelegung, sodass die Formel true ist

Und wie beweisen wie, dass das NP-vollständig ist?
- 3SAT liegt in NP, weil wir eine Lösungsinstanz polynomiell in deterministicher Zeit verifizieren können und es ist NP-schwer, weil wir SAT darauf reduzieren können (und wir wissen, dass SAT NP-vollständig ist.

Und wie geht so eine Reduktion?
- Wir müssen zeigen, dass wir eine ja-Instanz für SAT haben gdw. wir eine ja-Instanz für 3SAT haben.

Gut, dann wechseln wir jetzt mal das Thema. In den regulären Sprachen, was haben wir da für Beschreibungen kennen gelernt?
- NDEA, DEA, Reguläre Grammatik & Regulärer Ausdruck

Wir haben ja gezeigt, dass die alle das gleiche beschreiben. Geben Sie doch mal ein Beispiel, wie.
- Ich hab DEA -> Reg. Grammatik grob erklärt, indem ich einen Übergang & dazu die Regel aufgeschrieben hab

Und was sagt uns das jetzt?
- dass es zu jedem DEA auch eine Reg. Grammatik gibt und indem wir das für alle möglichen Kombinationen zeigen, zeigen wir, dass alle genau die regulären Sprachen beschreiben.

Warum reichen diese Beschreibungen nicht auch für die nächste Sprachenklasse?
- für KF brauchen wir einen Speicher, bei den Automaten den Keller und das kann der endliche Automat nicht. Weil ich bei der regulären Grammatik rechts nicht so viel hinschreiben kann, wie ich will, klappt es da auch nicht.

Dann sollte ich noch die Einschränkungen der Regeln x->y für die Chomsky-Hierarchie aufzählen und was zu Normalformen erzählen. Da hab ich einfach die CNF erklärt, das reichte ihm.

Was musste schriftlich gelöst werden?

Preorder rekursiv und iterativ (was liegt wann im Keller)

Welche Beispiele wurden wofür abgefragt?

Beschreibungen für reguläre Sprachen, nicht-berechenbare Probleme, Normalformen

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

Es war gut, dass sie gleich angefangen haben, sonst wäre ich vermutlich noch nervöser geworden. Ich hatte auch das Gefühl, dass die beiden einem helfen wollen, auf die richtige Antwort zu kommen. Es hat ja auch nicht gestört, dass ich bei ein paar Fragen etwas gebraucht hab, um auf die richtige Antwort zu kommen.

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

Einstieg:

Als ich reinkam, meinte Vornberger nur "kommen Sie rein, setzen Sie sich und beantworten Sie alle Fragen", dann ging's auch gleich los.

Ablauf:

Ende:

Am Ende sollte ich kurz rausgehen, damit sie sich besprechen können, dann gab's auch gleich die Note und noch ein bisschen Smalltalk ("Und wie geht's jetzt weiter?")

Bewertung und Begründung:

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

Ich hatte das Gefühl, Vornberger wusste sehr genau, was er fragen wollte, hat aber nachgehakt und Tipps gegeben, wenn ich was nicht auf Anhieb wusste. Chimani hat seine Fragen etwas eher auf meine Antworten angepasst hat (ich durfte mir ja zum Beispiel ein Problem aussuchen, anhand dessen ich den NP-Vollständigkeitsbeweis erklären sollte).

Zum Verhalten des Prüfers:

Beide waren sehr nett und haben Tipps gegeben, wenn ich nicht gleich die richtige Antwort parat hatte.