Computer Science, 2012-02-23

Module: 
Computer Science
Examiner: 
Oliver Vornberger, Volker Sperschneider
Date: 
Thu, 2012-02-23

FORMALIA

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. Die Videos kann man sich runterladen. Zum betrachten benötigt ihr wahrscheinlich den Real-Time Player, den man aber kostenlos downloaden kann. Hier die Links zu den Lecture-Videos:

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? nein
Note: 5.0 Bereiche nach Zeit: Habe nicht so drauf geachtet, war aber glaub ich gleich viel, also 15 Min Info A, 15 Min Info D

Fragensammlung: wie lauteten die Fragen im einzelnen?

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

Graphen, erzählen sie mal.
- Kann man als Adjazensliste oder Adjazensmatrix darstellen. (Hätte wohl eher allgemeiner definieren sollen, was ein Graph ist)
Was war da z.B. ein schönes Problem?
- Dijkstra Algorithmus
Wie funktioniert der?
- Beispiel aufgemalt und unter Vorbergers Hilfe grob erklärt.
Nächstes Thema: Rekursion: Was ist das?
- So gut es geht, Definition gegeben.
Nehmen wir mal Mergesort, wie würde da eine rekursive Implementation aussehen?
- Erkläre etwas und schreibe paar Zeilen hin, nachdem er mich darum bittet. Er reitet auf einer bestimmten Sache rum
und nach dem halbieren?
- Weiß immer noch nicht genau was er wollte, hatte das Gefühl Rekursion gut zu verstehen.
Machen Sie mal Fibonacci.
- gezeichnet und erklärt.
Beim Fibonacci können sie es ja, wie geht es also beim Mergesort?
- komme nicht so wirklich drauf was er will.
Naja, anderes Thema: Sortieren.
- In welcher Zeit läuft denn MergeSort?
O(n*logn)
- Ist das eine gute Zeit?
Es geht nicht besser. Untere Schranke für das Suchen mit Vergleichen erklärt.

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

Was ist ein Optimierungsproblem?
- Frage erst paarmal nach bis ich verstehe was er will. Hier hat er mich komplett auf dem falschen Fuß erwischt.
Da gibt es 4 Dinge und 3 Voraussetzungen.
- Ich stammele was von Input und Output zusammen. (Er wollte die Definition aus dem Skript hören)
Geben Sie mal ein Beispiel für ein Optimierungsproblem.
- Traveling Salesman Problem
Wie würden Sie das jemandem erklären, der damit nichts anfangen kann?
- mit seiner Hilfe halbwegs erklärt.
Was wäre ein naiver Ansatz um das Problem zu lösen? Wie schnell wäre das?
- Alle verschiedenen Wege ausprobieren. O(n!)
Geht es auch schneller?
- Sieht nicht so aus. (Was man hier hätte sagen können: Man könnte den Algorithmus wohl etwas tunen, aber in polynomieler Zeit wird man damit wohl nicht kommen, weil das Problem in NPC liegt.)
Was wäre etwas einfacher als den optimalen Pfad zu finden? Was würde denn eine LKW Spedition gerne wissen wollen, nur noch soundsoviel Sprit.
- Ja, es wäre einfacher zu gucken, ob es solch einen Pfad überhaupt gibt.
Wäre das wirklich einfacher?
- Nein, weil ....
Als was werde denn die Probleme auch angesehen?
- Als Sprachen.
Wir reden hier von Optimierungsproblemen, aber das Reduzieren geht auf Sprachen zurück. Was hat das alles miteinander zu tun?
- An dieser Stelle bitte ich die beiden, die Prüfung abzubrechen, weil ich komplett raus bin und mich wegen den groben Patzern vorhin nicht konzentrieren kann.

Was mußte schriftlich gelöst werden?

siehe oben

Welche Beispiele wurden wofür abgefragt?

Graphenalgorithmus, Optimierungsproblem

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

Es geht den beiden sehr wenig um technische Details. Aber wenn es um das Verständnis geht, wollen beide schon, dass man die Dinge bis ins Detail versteht.

Bewertung und Begründung:

Habe mich freiwillig durchfallen lassen, um es nochmal an einem besseren Tag zu versuchen.

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

Wenn man Beispiele nennen soll gewiss, ansonsten wussten sie schon was sie wollten und haben sich vorher schon überlegt, in welche Richtung die Prüfung gehen soll. Bei Algorithmen fragt Vornberger manchmal danach, wie das jetzt in Java implementiert ist, aber er will da nicht viel technisches hören, sondern wo da welcher Aufruf ist, in welcher Zeit das alles geschieht, was wann im Keller steht usw.
Auch bei Beweisen zählt die Beweisidee. Man muss z.B. die Abschätzungen nicht genau kennen, nur wie die Abschätzung anfängt und wie sie endet.