Computer Science, 2014-09-18

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

VORBEREITUNG

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

Info A: Vorlesungsaufzeichnungen und Skript
Info D: Slides

PRÜFUNG

Prüfungsdatum: 18.09.2014
Wiederholungsprüfung? nein
Note: 2.0 Bereiche nach Zeit: 10 - 10

Fragensammlung: wie lauteten die Fragen im einzelnen?

Info A:

Was wissen Sie über den AVL-Baum?
- Spezieller binärer Suchbaum, alles ausgeglichen, deswegen Laufzeiten immer logarithmisch.

Wie muss man das verwalten, damit das immer wieder diese Struktur hat?
- Rotieren.

Welche Laufzeit hat das?
- Rotationen an sich O(1), da man nur Zeiger umbiegen muss (Single: 3; Double: 5). Beim Löschen muss man aber evtl. logarithmisch viele Rotationen durchführen.

Was macht man denn mit so einem AVL-Baum, wozu ist das gut?
- Objekte speichern und relativ schnell wiederfinden.

Welche andere Methode haben wir kennengelernt, um sowas zu machen?
- Hashing.

Und was ist das, wie funktioniert das?
- Offenes und geschlossenes Hashing..

Lassen Sie das offene Hashing mal weg!
- Hashfunktion, um Speicherplatz zu bestimmen, Array von Objekten und Array von Zuständen (leer, belegt, gelöscht), bei Kolision sondieren (linear, quadratisch, Double Hashing). Speichern und Wiederfinden ziemlich schnell möglich.

Was ist da so die Laufzeit, und wann wird die evtl. schlechter?
- Normalerweise konstant, wenn das Array voll ist, wird es aber linear.

Und wovon hängt die Laufzeit dann ab?
- Vom Auslastungsfaktor.

Wie ist der definiert?
- n/N.

Wissen Sie auch, wie man das dann für erfolgreiche Suche ausrechnen kann, sagen wir mal bei einer Belegung von 80%?
- Formel aufgesagt. Z.B. bei 1 Mio Objekten nur 2 Schritte.

Können Sie das mal mit der Laufzeit vom AVL-Baum vergleichen?
- O(log n), also bei 1 Mio Objekte 20 Schritte.

Also steht es jetzt 1:0 für das Hashing. Gibt es auch was, was der AVL-Baum besser kann?
- Sortierung mit Inorder-Traversierung, beim Hashing keine Sortierung möglich. Durch die Verweise Speicher dynamisch wachsend, beim Hashing muss man das Array vergrößern.

Um wie viel würden Sie das Array dann vergrößern? Und können Sie den zusätzlichen Platz einfach unten dranhängen?
- Verdoppeln. Nein, alles muss neu gehasht werden, da sich beim Sondieren im größeren Array ja andere Plätze ergeben.

Kommen wir mal zur Rekursion. MergeSort. Nee, lieber QuickSort. Wie funktioniert das?
- Pivot-Element, mit "Zeigern" links und rechts loslaufen und vergleichen, evtl. tauschen. Dann steht am Ende links alles was kleiner ist als das Pivot, rechts alles was größer ist. Dann für diese Teile das gleiche tun.

Welche Laufzeit hat das?
- Best und average O(n * log n), worst case O(n²), weil man das Array immer nur um eins verkürzt.

Info D

Dann kommen wir mal zur Theoretischen Informatik. Was ist denn der Unterschied zwischen P und NP?
- Entscheidungsprobleme deterministisch vs. nicht-deterministisch in polynomieller Zeit entscheidbar.

Und wieso macht man diese Unterscheidung?
- Da erzähle ich erst was davon, dass Algorithmen mit polynomieller Zeit noch nützlich sind, alles dadrüber kann man nicht mehr gebrauchen. Deterministisch in polynomieller Zeit ist quasi das, was ein Computer berechnen kann. -- Das reicht ihm aber nicht, er hakt noch ein paar mal nach, aber ich verstehe nicht so richtig, worauf er hinaus will. Hinterher erklärt er mir dann er wollte hören, dass ja Probleme in P mit dem Computer lösbar sind, während Probleme aus NP, wenn sie deterministisch gelöst werden sollen, mindestens eponentielle Laufzeit bekommen (z.B. Travelling Salesman). Das kam bei mir wohl nicht so raus.

Was ist stark und schwach NP-vollständig?
- Stark NP-vollständige Probleme sind auch dann noch NP-vollständig, wenn man die Eingabegröße durch ein Polynom beschränkt, sie sind also quasi auch für kleine Zahlen schwer; schwach NP-vollständige Probleme wären dann nicht mehr NP-vollständig, sie werden erst für große Zahlen schwer. -- Da hakt er auch noch mal nach und möchte genau wissen, was denn die Eingabe ist, und was es bedeutet, dass sie beschränkt ist, usw.

Kennen Sie ein nicht-berechenbares Problem?
- Busy Beaver: Funktion der maximalen Schritte nicht berechenbar, weil sie zu schnell wächst. -- Da fragt er noch ein paar mal nach, warum das nicht berechenbar ist. Ich versuche, es noch mal mit der Definition von Berechenbarkeit zu erklären. Im Endeffekt wollte er hören, dass der Busy Beaver nicht entscheidbar ist, weil sonst auch das Halteproblem entscheidbar ist (das konnte ich auch erklären, ich habe nur nicht verstanden, dass er darauf hinauswollte).

Was sind denn kontextfreie Sprachen?
- Links eine Variable, rechts muss mehr stehen als links (beliebig viele Symbole und Variablen).

Da gibt es ja den Begriff der Normalformen. Wie hängt das zusammen?
- Jede KF Sprache lässt sich ins Chomsky-Normalform und Greibach-Normalform darstellen.

Und wie sehen die aus?
- CNF: links eine Variable, rechts ein Symbol oder zwei Variablen. GNF: links eine Variable, rechts ein Symbol und beliebig viele Variablen.

Was ist das tolle an der Greibach-Normalform? Wozu kann man die verwenden?
- Da fällt mir nichts zu ein, sage dann, dass man damit das Endlichkeitsproblem lösen kann.

Joa, naja.. Aber wenn Sie schon Endlichkeitsproblem sagen: Was ist das, und wie löst man das?
- Fragt, ob die Sprache endlich ist, bzw. ob sie unendlich viele Wörter produzieren kann. Erst Leerheitstest (Regeln markieren, wo rechts nur ein Symbol oder markierte Variablen stehen), unmarkierte entfernen. Dann bei Startvariable anfangen und alles markieren, was man erreichen kann, unmarkierte entfernen. Hilfsgraph, Kreise suchen.

Was heißt es, wenn ein Kreis enthalten ist, und warum?
- Dass die Sprache unendlich ist, weil man diesen Kreis ja beliebig oft durchlaufen darf.

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

Beide waren sehr nett. Chimani hat versucht, mir zu helfen, aber ich wusste oftmals einfach nicht, worauf er hinauswill. Nach der Prüfung sagte Vornberger auch, dass sie beide überrascht waren, dass ich bei Info D solche Probleme hatte, weil Info A ja so gut gelaufen war. Dann hat Chimani auch noch kurz erklärt, was er mit seinen Fragen gemeint hatte bzw. was er von mir hören wollte.