Computer Science, 2009-10-15

Module: 
Computer Science
Examiner: 
Oliver Vornberger
Assessor: 
Sperschneider
Date: 
Thu, 2009-10-15

Vorbereitung

Was hast du zur Prüfungsvorbereitung benutzt?
Skript und Übungen Info A und Info D,
"Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie" von Hopcroft und Ullman

Was wir hilfreich, was war weniger hilfreich?
Hopcroft und Ullmann ist sehr Umfangreich, bietet aber oft gute Beispiele zu speziellen Ideen. Behandelt nicht so viele Beispiele von NP Problemen wie das Skript

Prüfung

Wiederholungsprüfung?
Bereiche nach Zeit: <15/15>

Fragensammlung: wie lauteten die Fragen im einzelnen?

Info A
Was fällt ihnen zum Thema Hashing ein? Laufzeit?
unterschiede zu Suchbäumen? Platzbedarf, Laufzeit, Suchen, Traversieren?
Preorder Iterativ, Rekursiv (Schriftlich)
Wie muss man den Algorithmus verändern wenn man nur in einem bestimmten Bereich traversieren will? Von Meier bis Schulze in einem Baum mit Elementen von a - z.
Wie sieht die Belegung des Kellers bei der preordertraversierung aus? Was liegt im Keller?

Info D

Wofür haben wir Keller in der Theoretischen Informatik benutzt?
Warum kann ein normaler Kellerautomat nicht unbedingt die Palindromsprache erkennen?
Unterschied zwischen deterministischen und nicht deterministischen Automaten?
Beweis dass deterministsiche und nicht deterministische Kellerautomaten nicht gleich stark sind.
Woran kann es liegen, dass der Kellerautomat zum Komplement einer kontextfreien Sprache falsch reagiert?

kennen sie zwei Probleme die sich sehr ähnlich sind, wovon eins aber in P und eins in NP liegt? (2SAT und 3SAT)
Warum gibt es dort diesen Unterschied?
Warum ist Maxcut NP vollständig und Mincut polynomiell lösbar?
Woran machen wir fest, dass ein Problem NP Vollständig ist?
Was wäre wenn zu einem der Probleme plötzlich ein effizienter Algorithmus gefunden würde?

Was mußte schriftlich gelöst werden?

Preorder im Suchbaum, Kellerbelegung.

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

Einstieg:
Sehr schnell und direkt. Nach einem bisschen vorgerede über Formalitäten die auf meinem Protokoll falsch eingetragen waren ging es ohne Übergang los.

Ablauf:
Info A sehr locker und flüssig und schnell vorbei.
Info D stockend. Herr Sperschneider hat gedacht ich wäre ein Informatik-Profi und wollte mich nicht nach Trivialitäten befragen, deswegen etwas anspruchsvollere Fragen.

Bewertung und Begründung:
Info A war sehr gut, Info D trotz starker Hilfen ziemlich schwach, insgesamt aber gut

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

Ja ich glaube schon etwas. Die Verbindung zwischen Hashing, Bäumen und Kellern lässt sich aber auch gut herstellen. Von Kellern in Info A zu denen in Info D ist es nur ein kleiner Schritt.

Zum Verhalten des Prüfers:

Beide Prüfer waren wirklich nett. Herr Sperschneider hat sehr lange versucht irgendetwas über deterministische und nicht deterministische Kellerautomaten aus mir herauszukitzeln bis Herr Vornberger sagte, es würde wohl nichts werden damit. Danach hat er es mit Komplexität versucht. Die Prüfung wäre für mich vielleicht besser verlaufen wenn ich zuerst in Info D und danach in Info A geprüft worden wäre, da Info D eindeutig mein schwächeres Fach war.