Computer Science, 2012-04-17

Module: 
Computer Science
Examiner: 
Oliver Vornberger, Volker Sperschneider
Date: 
Tue, 2012-04-17

FORMALIA

Modulprüfung: Info A und Info D Fachsemester: 7.

VORBEREITUNG

Was hast du zur Prüfungsvorbereitung benutzt?
Was wir hilfreich, was war weniger hilfreich?

Info A: Info A Skript + Info A Vorlesungsvideos online. Ab und zu Wikipedia.
Info D: Habe hauptsächlich das Skript durchgearbeitet und versucht jeden Beweis zu verstehen. Das war oft ziemlich schwer. Dazu haben mir die Lectures von Shai Simonson sehr weitergeholfen! Dank der Lectures habe ich auch viele Beweise im Skript erst richtig verstanden. Die Videos machen Spaß und ich kann sie allen sehr ans Herz legen!

Theory of Computation:
http://www.aduni.org/courses/theory/index.php?view=cw
Algorithmus (enthält 4 lectures über das Reduzieren von NP-vollständigen Problemen):
http://www.aduni.org/courses/algorithms/index.php?view=cw

PRÜFUNG

Wiederholungsprüfung? ja
Note: 1.0 Bereiche nach Zeit: Info A 15 Min, Info D 15 Min

Fragensammlung: wie lauteten die Fragen im einzelnen?

Die mit einem Bindestrich markierten Zeilen geben das wieder, was ich gesagt habe. Ich gebe keine Garantie drauf ob das alles so stimmt und noch weniger Garantie, ob es das war, was sie in dem Moment hören wollten.

Sperschneider und Vornberger am Anfang sehr freundlich.

----------- INFO A

Als Vorni Papier von seinem Schreibtisch holt, fragt er mich schon, was für Bäume ich denn so kenne.
- Haben oft binäre Bäume benutzt, dann fallen mir noch Suchbaum und AVL-Baum ein. In Bäumen kann man zum Beispiel auch traversieren.
Für was kann man denn Suchbäume gebrauchen und was zeichnet sie aus?
- Kann damit zum Beispiel sortieren, einfach eine Inorder-Traversierung durch die Knoten machen. Danach Definiton von Suchbaum gegeben.
Malen sie mal so einen Suchbaum auf, mit so zwei Ebenen.
- gemacht.
Wie funktioniert denn hier eine Pre-Order Traversierung?
- Erstmal wird das Element ausgegeben, dann tauche ich den linken Baum ab, dann den rechten.
Wie sieht denn dazu ein Java-Programm aus? Schreiben sie mal public static void preorder
-gemacht.
Was kommt da jetzt als Parameter rein?
- Da kommt der ganze Baum rein, also die oberste Wurzel.
Ja, und wie geht es dann weiter?
- Wenn der Baum nicht leer ist, dann steige nach links ab
Moment mal, es geht hier um Preorder
- Ahh, ja, ich schreibe erstmal den Inhalt des Knoten raus, also b.value(). Danach schreibe ich den rekursiven Pre-Order Algorithmus aus der Vorlesung 1 zu 1 auf.
Gut, kann man eine Pre-Order Traversierung auch iterativ lösen?
- Ja, mit einer Tiefensuche mit einem Keller.
Wie funktioniert das?
- Es wird in einer while-Schleife jeweils erst der Wert des Knoten ausgegeben, dann der rechte Sohn in den Keller gesteckt, dann taucht man im Baum nach links ab.
Wenn man so einen Keller hat (malt einen Keller aufs Blatt), wie sieht dann die Keller belegung aus, wenn man hier (zeigt auf den linkesten Knoten in der untersten Ebene meines gemalten binären Baumes) angekommen ist?
- Gehe den Algorithmus laut bis zu der Stelle durch und schreibe die entsprechenden rechten Knoten in den Keller.
Was genau sind denn diese Einträge im Keller?
- Das sind die gesamten Teilbäume, nicht nur der Knoten.
Wie schnell ist denn der Algorithmus, wenn man jetzt zum Beispiel n Knoten hat?
- Ich bin irgendwie verwirrt und stammele was von "ich muss also jeweils log(n) Felder runter und das muss ich ähhm."
Sie denken da viel zu kompliziert. Wie viel Knoten haben Sie? (zeigt aufs Bild) Wenn sie mal an einem Knoten sind, wieviel Arbeit haben sie dann?
- O(1), weil ich ja einfach den Wert rausschreibe.
Genau. Und wieviele Knoten haben sie?
- Ach, klar, der Algorithmus braucht O(n). Ich lauf ja einfach durch und hab jedes Mal O(1) Aufwand.

Gut. Wir hatten in der Vorlesung noch einen Baum kennengelernt, nämlich den Heap. Was macht diesen Baum zu einem besonderen Baum?
- Er ist vollständig (erkläre genau was das bedeutet und veranschauliche es mit einer Zeichnung) und Söhne sind immer gröߟer als Wurzel.
Findet man denn in einem Heap genauso, wie in einem Suchbaum die Söhne? (Hier kann ich mich mehr ganz genau an die Frage erinnern, waren irgendwie paar Fragen zum Unterschied des Söhne-Findens)
- In Suchbaum findet man Söhne durch Referenzen in den Knoten, im Heap liegt alls in einem Array. Knoten sind folgendermaߟen durchnummeriert (schreibe Nummerierung in Knoten).
Wie findet man jetzt zu einer Wurzel seinen linken Sohn?
- Stammele erstmal biߟchen, kombiniere mit meinem aufgemalten Suchbaum und mach es genau falschrum, nämlich Wert/2
Also, dass ist nicht ganz richtig.
- Achso, den Sohn der Wurzel, dann ist es Wert*2 für den linken und Wert*2+1 für den rechten Sohn. (Hier ist noch ein kleiner Fehler, ein paar Zeilen weiter unten sagt Vorni die Lösung)
Wieso haben wir das beim Suchbaum nicht auch mit einem Array gemacht?
- Hmm, dann könnte man nicht dynamisch Knoten hinzufügen.
Das stimmt, ist aber nicht so wichtig. Was ist der entscheidende Punkt, warum man bei einem Heap ein Array nutzen kann, bei einem Suchbaum aber nicht? Mit Wert*2+1 bekommt man ja den linken Sohn, mit Wert*2+2 den rechten Sohn. Wieso kann das beim Suchbaum schief laufen?
- ich grüble noch ein wenig und komm dann drauf, dass es an der Vollständigkeit des Heaps liegt, denn im Suchbaum könnte es ja passieren, dass dann ein Platz nicht da ist und man die Söhne nicht mehr findet.

Gut, gibt es noch eine ganz andere Struktur mit der man Daten verwalten kann?
- Hash-Tabelle
Erklären sie mal dafür das geschlossene Hashing.
- Es kann ja vorkommen, dass die Hashfunktion einem Objekt, den selben Hashwert zuordnet, dann ... erkläre wie lineares Sondieren, quadratisches Sondieren und Double-Hashing funktionieren.
Wie ist denn da so die Laufzeit?
- Konstant.
Das ist so nicht ganz richtig. Die Laufzeit hängt von was anderem ab.
- Ja, vom Auslastungsfaktor.
Genau.
- Erkläre die Werte 2 und 5 bei "Laufzeit bei geschlossenem Hashing" in Kapitel 10.2 Geschlossenes Hashing im Info Skript (Skript zur Vorlesung 08/09)
Verlgeichen sie mal Hashfunktion und AVL-Baum nach Laufzeit, Speicherplatz usw.
- Also, beim Suchen eines Objektes oder Einfügen läuft ja die Hash-Funktion in konstanter Zeit...
Vorni blickt auf die Uhr und sagt Danke.

----------- INFO D

Sperschneider: Traversieren sie mal für mich die ganze Chomsky Hierarchie durch und sagen mir so die wichtigsten Begriffe, die da jeweils gefallen sind.
- Puh, also da gibt es erstmal die regulären Sprachen, die durch endliche Automaten erkannt werden können, durch links- oder rechtslineare Grammatiken generiert werden können. Auߟerdem sind die regulären Sprachen für sehr viele wichtige Operationen abgeschlossen.
Na, da gibt es noch eine wichtige Sache
- Reguläre Ausdrücke.
Schreiben sie mal einen regulären Ausdruck hin, der so alles enthält was in regulären Ausdrücken drin ist.
- Schreibe nen sinnlosen regulären Ausdruck über dem Binäralphabet {0,1} hin, der alle 3 Elemente enthält und erkläre dabei was was ist. (Das groߟe Delta, dessen Sprache die leere Sprache ist, hat er abgewunken).
Machen sie das auch mal für Automaten, schreiben sie einfach einen hin.
- Mache es ähnlich wie vorhin, schreibe den Automaten, der mit zwei Nullen endet auf (habe ich mir vorbereitet). Als ich ihn noch ganz fertig machen will, stopt Sperschneider mich.
Können sie auch einen endlichen Automaten für die Sprache der Palindrome finden?
- Nein.
Warum?
- Ich könnte als ersten Versuch das Pumping Lemma heranziehen, aber das funktioniert leider nicht. (Schreibe ein Beispiel Palindrom auf und zeige, dass ich egal bei welcher uvw Konstellation mind. einen u-Abschnitt finde, dass ich pumpen kann ohne aus der Sprache rauszufliegen.)
Jaja, (er will das ich nicht mehr übers Pumping Lemma spreche) was machen sie dann?
- Ich kann es mit den Abgeschlossenheitseigenschaften probieren. Da müsste man ...
Danke, wir glauben ihnen, dass sie das können.
Vorni: Haben sie gewusst, dass das drankommt?
- Ne, aber kam mal in der Vorlesung vor (Das hat er mal in der Vorlesung gezeigt und habs mitgeschrieben. Lohnt sich also doch manchmal hinzugehen.., auߟerdem kam das Beispiel glaub ich auch in dem Online-Kurs vor).
Sperschneider fährt fort. Gut, die Sprache ww^mi ist also kontextfrei. Wie schaut es mit ww aus?
- Bei ww^mi kann ich ja lokal immer gucken, sind die gleich und dann das aus dem Keller schmeiߟen, also ich muss da...
Naja, sie können ja indeterministisch die Mitte raten und dann für jedes Eingabezeichen das oberste Kellerelement löschen.
- Jaja, und bei ww ist das Problem, dass ich da einmal vorne das eine und hinten das andere vergleichen muss. (Veranschauliche es auf dem Papier)
Genau, was wäre also die nächste Stufe, in die ww passt?
- Kontextsensitiven Sprachen
Schaffen sie es da, eine kontextsensitive Grammatik zu bauen, die Wörter der Copy-Sprache ww generiert? Ich kann ihnen auch gerne etwas helfen.
- (Hab glücklicherweise genau diese Grammatik ca. 1 Stunde vor der Prüfung zu Hause gemacht) und fange an sie aufzuschreiben. Währenddessen unterbricht mich Sperschneider die ganze Zeit und fragt immer, was jetzt noch zu tun ist, was jetzt noch stört, wie weit wir mittlerweile sind etc. Komme dadurch etwas durcheinander, finde dann aber wieder auf den richtigen Weg und schreibe die restlichen Produktionen auf und erkläre die ganze Zeit, was ich so mache. (Diese Grammatik haben wir auf einem Hausaufgabenblatt gelöst).

Gut, die letzte Stufe, die Turingmaschinen lassen wir mal aus, da geht eh alles. Nächstes Thema: NP-Vollständigkeit. Gibt es da ein Problem, das Ihnen gut gefällt?
- 3 SAT finde ich ganz gut.
Ja, damit fängt es so an. Was ist den mit 2 SAT?
- 2 SAT ist nicht NP-vollständig, denn dazu gibt es einen polynomiellen Lösungsalgorithmus, der die konzentrischen Kreise findet. (Das hat Sperschneider auch mal in der Vorlesung gezeigt und kam nochmal in den Online-Videos vor). Das nutzt aus, dass man die Disjunktionen mit nur 2 Disjunkten in eine Impklikation umwandeln kann. (Schreibe das auf)
Zeigen Sie mal wie man das schriftlich löst?
- Schreibe es auf und kommentiere. Sperschneider hilft mir auch an einer kleinen Stelle. (Die Lösung findet ihr in einem der Online-Videos der Algorithmen Veranstaltung, die über NP gehen, den konzentrischen Kreis nennt man auf Englisch "strongly connected components", auf Wikipedia findet ihr so auch die Lösung, sie ohne Grafiken aufzuschreiben ist hier etwas schwer).
Gut, wenn man ein neues Problem als NP-vollständig klassifizieren will, wie geht man da vor?
- Ich könnte direkt Diagonalisierung anwenden oder (Sperschneider ist nicht ganz zufrieden) ein NP-vollständiges Problem auf das neue Problem reduzieren.
Auf was kann man denn 3 SAT direkt reduzieren?
- ߄hm, Hamilton Kreis oder Knapsack
Es gibt ja auch Optimierungsprobleme. Wie kann man da was machen?
- Man kann Optimierungsprobleme auf Entscheidungsprobleme zurückführen, Entscheidungsprobleme sind ja fast schon Sprachen.
Welches Optimierungsproblem gefällt ihnen denn am besten?
- Traveling Salesman Problem
Stellt mir einige Fragen darüber, wie das Entscheidungsproblem zum TSP-Suchproblem lautet und hilf mir etwas.
Das Problem, die optimale Rundfahrt zu finden, wirkt doch erstmal schwerer, als nur zu entscheiden, ob die optimale Streckenlänge kleiner gleich einem bestimmten Wert ist.
- Ist aber nicht viel schwerer, weil ich da wenn ich weiߟ wie groߟ der optimale Wert maximal sein kann, mit einer binären Suche das optimum finden kann.
Binäre Suche war das Stichwort. (unterbricht mich). Und dann, wenn ich den optimalen Wert für einen Graphen berechnen kann, wie finde ich dann den schnellsten Weg?
- Erkläre den Algorithmus vom Skript
(Ich glaube das war die letzte Frage) Bitte warten sie kurz drauߟen.
Danach gabs noch einen Smalltalk, wo es darum ging warum ich meiner ersten Prüfung so grottig war.

Was mußte schriftlich gelöst werden?

siehe oben

Welche Beispiele wurden wofür abgefragt?

siehe oben

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

Prüfung lief sehr harmonisch ab. Haben auch geholfen, als ich zweimal nicht sofort die Antwort wusste.

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

siehe oben

Bewertung und Begründung:

1.0, gab keine große Begründung. Habe eigentlich alles gewusst. Waren verwundert, dass ich beim ersten Versuch so schlecht war.

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

Nicht wirklich. Sie haben beide schon vorher gewusst, was sie fragen wollen. Wenn man mal ein Thema durch eine bestimmte Antwort anreißt, wollen sie meistens mehr Details wissen.

Zum Verhalten des Prüfers:

Beide sehr nett!