Vordiplom Theoretische Informatik
Kurs 1653/1654
| Termin: | 22.09.98, 13:30 |
| Prüfer: | Prof. Dr. Weihrauch |
| Dauer: | 25 min. |
| Note: | 1,0 |
Allgemeiner Eindruck:
Herr Professor Weihrauch ist ein sehr freundlicher Prüfer, der nicht nach Lücken sondern nach Wissen sucht.
Ich war sehr aufgeregt, da ich wegen einer Erkältung nicht ganz fit war. Zudem verspätete ich mich noch, weil ich das Arbeitszimmer des Professors nicht finden konnte.
Herr Weihrauch stellte zunächst einige auflockernde Fragen nach der Anreise.
Diese Prüfung war meine erste Vordiplom - Prüfung. Ich kann Herrn Professor Weihrauch als Prüfer nur empfehlen. Er versucht alles, eine beruhigende Atmosphäre zu schaffen. Die Reihenfolg e der Fragen entspricht der Behandlung der Themen im Kurs. Dabei leitet Herr Weihrauch jede Frage mit ein paar Sätzen ein. An seinem Gesicht kann man ablesen, ob er mit einer Antwort zufrieden ist. Bei unvollständigen Antworten fragt er nach. Bei Unsicherheiten hilft er weiter.
Mit der Benotung war ich sehr zufrieden.
Verlauf:
Frage: Wann ist eine Zahlenfunktionen berechenbar?
Antwort: wenn, es eine Registermaschine gibt, die diese Funktion berechnet oder wenn sie m-rekursiv ist.
Frage: Sehr schön, da haben wir ja schon beide Definitionen. Wissen Sie auch wann eine Funktion m-rekursiv ist?
Antwort: Eine Funktion ist m-rekursiv gdw. sie sich aus den primitiv rekursiven Grundfunktionen mit Hilfe der Operatoren SUB = Substitution, PRK = primitive Rekursion und m = Minimalisierung in endlich vielen Schritten erzeugen läßt. Die Aufzählung der Funktionen aus Gr war nicht erforderlich.
Frage: Wir hatten auch die Wort - berechenbaren Funktionen kennengelernt. Wie sehen denn die Bandalphabete aus?
Antwort: Da gibt es zunächst das Ein-/Ausgabealphabet, das im Kurs S genannt wurde. Das Bandalphabet, das im Kurs G genannt wurde, besteht aus S und zumindest einem weiteren Zeichen, dem Blank, im Kurs mit B bezeichnet. Weitere Hilfsymbole können enthalten sein, um die Programmierung zu vereinfachen.
Frage: Weshalb kann man auf diese Hilfssymbole verzichten? Kennen Sie einen Satz dazu?
Antwort: Ich habe das Hilfssymbol Lemma zitiert.
Frage: Nun brauchen wir noch eine Beweisidee!
Antwort: Ich habe die Codierung der Zeichen von ' durch Wörter über '‘ erklärt. Dabei habe ich erwähnt, daß man aus technischen Gründen dazu Wörter geeigneter fester Länge wählt. (Problem beim Schreibbefehl!)
Frage: Gibt es denn einen Zusammenhang zwischen den berechenbaren Zahlenfunktionen und den berechenbaren Wortfunktionen?
Antwort: Ich habe zunächst die Standardnumerierung n von W(S) angegeben. Dann habe ich die Skizze aus dem Kurs aufgezeichnet und erläutert, daß für jede berechenbare Zahlenfunktion f gilt: fn = ng. Dabei vergaß ich offenbar, anzugeben daß g berechenbare Wortfunktion ist. Herr Weihrauch fragte nach einem Satz. Ich wußte überhaupt nicht, worauf er hinaus wollte und erklärte die Beweisidee: Register - berechenbar = Keller - berechenbar. Herr Weihrauch versuchte zwar, mich in die richtige Richtung zu lenken, aber ich begriff nicht, was er wollte. Als ich schließlich am Ende des Beweises erklärte, daß nun gezeigt ist, daß, wenn f berechenbar ist, auch g berechenbar ist, sagte er nun sei das entscheidende Wort endlich gefallen.
Frage: Was ist n ?
Antwort: die Standardnumerierung der einstelligen partiell rekursiven Funktionen.
Frage: Wir haben im Kurs viele Aussagen mit Hilfe von n gemacht. Gibt es denn auch andere solche Numerierungen.
Antwort: Äquivalenzsatz von Rogers zitiert und nach Rückfrage exakt aufgeschrieben.
Frage: Kennen Sie eine nicht berechenbare Funktion?
Antwort: Die Funktion g, die über die Folge der (n i) diagonalisiert angegeben. Es mußte detailliert erläutert werden, warum g nicht berechenbar ist.
Frage: Definition der rekursiven Mengen?
Antwort: A f ù heißt entscheidbar oder rekursiv gdw. es eine total - rekursive Funktion f gibt, so A das Urbild von {0} unter dieser Funktion f ist. Anschaulich bedeutet dies, daß es ein Verfahren gibt, um für jedes x 0 ù zu entscheiden, ob x 0 A gilt oder x ó A gilt.
Frage: Ist {y| y = x2} entscheidbar?
Antwort: Ja.
Frage: Wie verhält sich die Registermaschine, die diese Menge entscheidet?
Antwort: Die Registermaschine hält mit 0, falls die Eingabe eine Quadratzahl ist und mit irgend einem anderen Ergebnis sonst. Eine genauere Angabe war nicht gewünscht (elementare Programmierung)
Frage: Definition rekursiv aufzählbarer Mengen?
Antwort: A f ù heißt beweisbar oder rekursiv aufzählbar gdw. es eine partiell rekursive Funktion f gibt mit A = Def(f). Alternativ: A = i oder es gibt eine total rekursive Funktion g mit A = Bild(g).
Frage: Gibt es einen Zusammenhang zwischen rekursiven und rekursiv aufzählbaren Mengen?
Antwort: Ja, rekursiv ist stärker. Wenn A rekursiv ist, dann ist A auch rekursiv aufzählbar. Äquivalenz gilt zwischen A und das Komplement von A rekursiv aufzählbar gdw. A rekursiv
Frage: Sind die rekursiv aufzählbaren Mengen abgeschlossen gegenüber Durchschnitt?
Antwort: Ja: Seien A1, A2 rekursiv aufzählbar. Dann gibt es f1, f2 0 P(1) mit A1 = Def(A1), A2 = Def(A2). Für g: ù --> ù g(x) := f1(x) + f2(x) gilt: Def(g) = Def(f1)1 Def(f1) = A11 A2, also ist die Schnittmenge rekursiv aufzählbar.
Frage: Sind die rekursiv aufzählbaren Mengen abgeschlossen bezügl. Komplement?
Antwort: Nein, ein Gegenbeispiel ist Kn .
Frage: Wie ist Kn definiert?
Antwort: Kn := {i| i 0 Def(n i)}
Frage: Wie sind die rechtslinearen Grammatiken definiert ?
Antwort: (H. Weihrauch bevorzugt die Schreibweise mit Pfeilen) A à wB, A à w.
Frage: Wie sind die rechtslinearen Grammatiken in Normalform definiert?
Antwort: A à aB, A à g .
Frage: Wir haben ein Verfahren kennengelernt, wie man aus einer rechtslinearen Grammatik eine rechtslineare Grammatik in Normalform erzeugen kann. Können Sie dieses Verfahren angeben?
Antwort: Ich denke schon. Herr Weihrauch unterbrach: " Gut, das glaube ich Ihnen!"
Frage: Wie erzeugt man aus einem endlichen Automaten einen determinierten Automaten?
Antwort: Man konstruiert den Potenzautomat. Die Angebe des Verfahrens war nicht nötig.
Frage: Sind die regulären Sprachen gegenüber Komplementbildung abgeschlossen?
Antwort: keine Ahnung!
Frage: (schmunzelnd) Nun, da Sie das nicht auswendig gelernt haben, will ich Ihnen helfen. Wie verhält sich denn ein endlicher Automat, der w 0 L erkennt?
Antwort: Er kommt auf einen Endzustand, wenn die Eingabe zu Ende gelesen ist. Geistesblitz: Man muß Endzustandsmenge F und Q\F invertieren und man erhält den Automaten, der das Komplement erkennt.
Frage: Kennen Sie eine kontextfreie Grammatik, die nicht regulär ist?
Antwort: Ich behauptete, daß die kontextfreien Sprachen die regulären Sprachen umfassen, worauf H. Weihrauch korrigierte, daß es umgekehrt ist.
(Anmerkung des RuF-Teams: Die Menge der kontextfreien Sprachen ist eine echte Obermenge der regulären Sprachen. Z.B. ist die Sprache anbn zwar kontextfrei, aber nicht regulär, da sie nicht durch einen endlichen Automaten erkannt werden kann.)
Frage: können Sie denn eine kontextfreie Sprache angeben?
Antwort: L = {wwR| w 0 W(E )}
Frage: Wie beweist man das?
Antwort: mündl. Erklärung eines Kellerautomaten, der L erkennt.
Frage: Woher weiß denn Ihr Kellerautomat, wann er umschalten muß?
Antwort: Hm, ich brauche ein Trennzeichen!
Frage: Geht es auch ohne? Denken Sie an die Definition des Kellerautomaten?
Antwort: Ja, der Automat muß nichtdeterministisch umschalten.
Frage: Ist diese Sprache regulär?
Antwort: Nein.
Frage: Können Sie eine Sprache angeben, die nicht kontextfrei ist?
Antwort: L = {akblcm| | k = l = m}
Frage: Nun muß ich noch etwas zur Komplexitätstheorie fragen. Ist A= ZEIT(n2) entscheidbar?
Antwort: Ja, denn ZEIT(n2) bezeichnet die Sprachen, die in O(n2) Zeit deterministisch entscheidbar sind.
Frage: Ist A= NZEIT(n2) entscheidbar?
Antwort: Ja, aber nicht in O(n2) Zeit. Ich habe dann noch erklärt, warum man zur Kontrollturingmaschine eine deterministische Turingmaschine findet und die Zeitabschätzung angegeben.
Die Fragen sind gekürzt wiedergegeben. Sie wurden präziser gestellt.
Viel Glück, wenn Du dran bist!!!