Computer Science, 2005-07-28

Module: 
Computer Science
Examiner: 
Volker Sperschneider
Assessor: 
Ralf Kunze
Date: 
Thu, 2005-07-28

Vorbemerkung

Herr Vornberger war zum Zeitpunkt meiner Prüfung schon in den Ferien, deswegen war meine Prüfung ausnahmsweise nur mit Herr Sperschneider und Ralf Kunze (dem Übungsleiter von Info A).
Ralf Kunze hat aber nur Protokoll geschrieben, die Fragen hat alle Herr Sperschneider gestellt, entsprechend ist diese Prüfung wahrscheinlich nicht repräsentativ für eine Info A Prüfung und dieses Protokoll eher zu Vorbereitung auf Info D Prüfungen relevant.

Fragensammlung: wie lauteten die Fragen im einzelnen?

Was gibt es den so für Sprachklassen?
Zu welcher Sprachklasse gehören "ww" (copy) und "ww^mi" (w und w mirror) (mit w aus (ab)^*)?
Zeige das ww^mi nicht regulär ist.
Kontext-freie Grammatik für ww^mi angeben? (schriftlich)
Zeigen das ww nicht kontext-frei ist.
Grammatik für ww? (schwierig) Hilfestellung, gemeinsam erweiternde Grammatik entwickelt. (schriftlich)
Da gab es doch noch diese beiden besonderen Kellerautomaten (LL und LR Automaten), erklären sie doch mal.
Was kann man bei kontext-freien Sprachen den so zeigen?(unendlich, leer, wort enthalten)
Was nicht? ("Ähm, hmm, na ja, ob das Komplement einer Sprache zum Beispiel auch kontext-frei
ist....?" - "jaja, gut, also alles mögliche halt. Kommen wir zu was anderem.")
Zeige Wortenthalten in einer kontextfreien Sprache.
Komplexität von Cocker-Casami-Younger Algorithmus? Warum, erklären. (gemeinsam überlegt) Wo muss ich hier was mit was mit was Verknüpfen in der Tabelle?
Was für ein NPC Problem kennen sie den so? (ein beliebiges Vorstellen. Knapsack)
Wie zeigt man das das in NPC? (Was reduziert man denn nun auf was? ;)
Knapsack ist ein bisschen kompliziert die Reduktion, zeigen sie doch mal eine Reduktion, die man so in zwei Minuten schnell erklären kann. (Sat -> 3Sat)
Was gibt es den mal so führ ein Problem das nicht NPC ist, wo man es vielleicht gedacht hätte? (Eulerkreis)
(Herr Sperschneider holt ein Bild von einem Graphen) Ist hier ein Eulerkreis drin, wie überprüft man das den? (Fahre ein bisschen planlos mit meinem Finger den Graphen ab, auf der Suche nach einem Eulerkreis - ok)

Was für Komplexitätsklassen haben wir denn in Info A so kennen gelernt? (+Beispielprobleme)
Ist die Multiplikation zweier nxn-Matrizen wirklich in O(n^3)? (nebenbei, n^3 ist keine untere Schranke,
es geht in n^(log_2(7)) = ca. n^2,8, war aber nicht schlimm, das nicht zu wissen.)
Beim sortieren hatten wir ja oft O(n log(n)) ist das eine untere Schranke? Erläutern (Andere Sortieralgorithmen wie Bucket Sort schneller, aber bei sortieren durch vergleichen schon, weil so
Baum und so, bla)
Was für Sachen muss man den mit Daten so machen wenn man sie verwaltet? (abspeichern, wiederfinden, löschen)
Was für einen Baum könnte man den da so nehmen?
(Suchbaum und AVL-Baum erklärt, vorteile von AVL-Baum, wenn man sortierte Liste nacheinander eingibt.)
Den Aufbau eines solchen AVL-Baums, aus sortierter Liste (zwei single RR-Rotationen) vorgemacht. (schriftlich)
Wieviel Aufwand hat man bei einem AVL-Baum so?

Soll Herr Kunze sie noch etwas zu Java fragen?

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

Das Klima war sehr nett, die wollen einem wirklich nichts böses. Wenn man bei einer Frage mal nicht so wirklich weiter weiss, geben sie in der Regel recht schnell Hilfestellung, oder leiten auf ein anderes Thema um, sie lassen also keine Möglichkeit irgendwo länger hängen zu bleiben, es scheint aber
auch nicht so schlimm zu sein, nicht alles sofort perfekt runter rasseln zu können. Wenn sie das Gefühl haben das man etwas sowieso kann, geht es auch sehr schnell weiter. Insgesamt scheinen sie also recht schnell so einen groben Überblick darüber bekommen zu wollen, ob man das meiste so Verstanden hat, und irgendwie auf die Reihe bekommt.

Man sollte die verschiedenen Algorithmen, wie Cocker-Casami-Younger und so aber schon auch anwenden können,
nicht nur theoretisch. (Achtung, ich mache nur eine Aussage über
Herr Sperschneider, nicht über Herr Vornberger, der steht in dem Ruf, mehr Wert auf Details zu legen)
Der Umgang war recht entspannt. Ich musste nur relativ wenig schriftlich machen, man sitzt aber zusammen an dem Tisch mit Papier und Stift vor sich, und kann immer wenn man gerade will auch irgendwas aufschreiben oder zeichnen um es noch zu veranschaulichen.

Zumindest bei den Fragen zu NPC-P hat man die Möglichkeit sich auszusuchen, worüber man spricht, aber auch bei anderen Fragen konnte man durchaus Einfluss nehmen, ob man zum Beispiel jetzt gerade lieber mehr zum Suchbaum allgemein oder zu irgendwelchen Rotationen im AVL-Baum erzählt. Es war nicht so, das es eine fertige Fragenliste gab, die abgearbeitet wurde, sondern es kam schon viel darauf an, was Herr Sperschneider so für ein Gefühl hatte, was ich verstanden hatte und was nicht. Aber wie gesagt, sie wollen einen dabei auch nicht in die Pfanne hauen.

Am Schluss, nach der Prüfung, hat mir Her Sperschneider dann auch noch erklärt, wie das mit den nxn Matrizen funktioniert.

Anton Flügge
afluegge@uos.de