Hagen-Vordiplom-Informatik-Theoretische Informatik A/B

Prüfungsprotokoll

17.08.2000

Art der Hochschule:
Prüfungsort:
Studienfach:
Art der Prüfung:
Prüfer:
Prüfungsfach:

Universität
Hagen
Informatik
Vordiplom
Weihrauch
Theoretische Informatik A/B

Dauer der Prüfung:
Note:
Konntest du mit einem selbst
gewählten Thema beginnen?
Versucht der Prüfer bei
Schwierigkeiten zu helfen?

30-40 Minuten
2

Nein.

Ja.

Prüfungsablauf
Tipps

Eindruck

Alles in allem ist Herr Weihrauch ein sehr angenehmer und netter Prüfer, der es versteht,
seinem Prüfling die Nervosität zu nehmen.
Er leitet seine Fragen meist mit einigen Sätzen ein, so daß einem recht schnell klar wird, um
was es ihm geht. Man merkt ihm auch recht gut an, ob eine Frage zu seiner Zufriedenheit
beantwortet wurde oder ob ihm noch etwas fehlt.

Da ich aufgrund meiner recht kurzen Vorbereitungszeit einige
Unsicherheiten hatte und öfter etwas geschwommen bin, fand ich die Benotung recht fair.

Tips zur Vorbereitung

Zur Prüfungsvorbereitung ist außer alten Prüfungsprotokollen
(1) <http://www.stud.fernuni-hagen.de/q1471341/docs/01653.html> (2) <http://www.fernuni-hagen.de/FACHSCHINF/1654/Weihrauch.pdf>
das einwöchige Seminar in Bad Bevensen <http://www.fernuni-hagen.de/FACHSCHINF/VeranstaltungenWS2000.htm> wärmstens zu empfehlen.

Sehr hilfreich dürfte auch das Lernskript <http://www.joerg-schwerdtfeger.de/studium/1653/SkriptGrundlagenTheoretischeInformatik.pdf> von Thomas Schwarze, der Themenüberblick <http://www.joerg-schwerdtfeger.de/studium/1653/themen.pdf> von Thorsten Rood und die FAQ <http://www.joerg-schwerdtfeger.de/studium/1653/pruef.pdf> von Simone Jandt sein.

Prüfungsfragen:

Berechenbarkeit

Wann heißt eine Zahlenfunktion berechenbar?

Eine Zahlenfunktion f : Í IN^k®IN
heißt berechenbar, gdw. sie von einer Registermaschine berechnet wird.

Wäre denn die Funktion f : IN×IN®IN, f (x, y) : = x^y berechenbar?

Ja, denn sie ist offensichtlich primitiv rekursiv (Die Exponentiation ist ja bereits per Definition eine primitiv rekursive Grundfunktion). Alternativ könnte man natürlich auch eine Registermaschine dazu angeben.

Wann heißt eine Wortfunktion berechenbar?

Eine Wortfunktion g : Í (S*)^k®S*
heißt berechenbar, gdw. sie von einer Turing- oder Bandmaschine berechnet wird.

Ist denn Turingberechenbarkeit das gleiche wie Bandberechenbarkeit?

Ja, denn jede Bandmaschine ist trivialerweise auch eine Turingmaschine (mit nur einem Band) und
umgekehrt läßt sich eine k-band Turingmaschine mit einer Bandmaschine simulieren,
indem man die einzelnen Bänder jeweils als Spuren eines einzelnen Bandes interpretiert. Man muß natürlich das Bandalphabet erweitern, da ein
Zeichen des neuen Bandalphabets nun aus k Zeichen des ursprünglichen besteht, sowie
eine zusätzliche Markierung der ursprünglichen Zeichen notwendig ist, um sich die Kopfposition der Bänder zu merken.

Wir hatten jetzt berechenbare Zahlen- und berechenbare Wortfunktionen. Hängen die irgendwie miteinander zusammen?

Zunächst ordnet eine bijektive Nummerierung n : IN®S* jedem Wort (genau) eine natürliche Zahl zu und umgekehrt.
Nun gilt: Ist f : Í IN^k®IN
berechenbar, so ist auch g : Í (S*)^k®S*
definiert durch g := n^-1 f n berechenbar
und entsprechend umgekehrt mit f := n g n^-1.
Der Vektor n ist dabei einfach n komponentenweise angewendet.

Wir haben die ganze Zeit von Funktionen gesprochen, die berechenbar heißen, wann ist denn so eine Funktion nun berechenbar?

Mit der Churchen These folgt ja letztendlich, daß Funktionen, die per Definition berechenbar heißen,
genau den intuitiven Berechenbarkeitsbegriff bilden, somit also (maschinell) berechenbar sind.

Kann man diese These denn beweisen?

Nicht wirklich, da man "intuitiv berechenbar" ja formal nicht ausdrücken kann.
Im Allgemeinen wird die Churchsche These allerdings als richtig angesehen.

Wir haben im Kurstext eine Programmiersprache für einstellige Funktionen definiert. Wie sieht die aus?

j : IN®P⁽¹⁾ mit j_i(n) : = j (i) (n) := i^-1 ° f_M ° i ° n_M ° n_P (i) (n),
wobei i die Unärcodierung von n
und n_M ° n_P die Bandmaschine des i-ten Bandprogramms darstellen.
j_i(n) ist
dann also der vom i-ten Programm berechnete Funktionswert
mit dem Argument n.

Was sind da jetzt die Programme von j?

Die natürlichen Zahlen, denen eine partielle Funktion aus P⁽¹⁾ zugeordnet wird.

Welche zwei Anforderungen stellt man an eine vernünftige Programmiersprache?

(U) Man möchte mit dem Programm P auf einer Maschine S(P) ausrechnen können, also "x Î Def (S (P) ) den Wert
S (P) (x).
Formal wird das durch das utm-Theorem ausgedrückt:

Sei u_j : Í IN²®IN, u_j (i, x) : = j_i(x).
Dann ist u_j (die universelle Funktion) berechenbar.
Anschaulich heißt das, daß
es eine universelle "Maschine" u_j gibt, die anhand der Eingabe
von i und x das i-te Programm
mit der Eingabe x ausführt.

Nochmal zu den Anforderungen an eine Programmiersprache: Sie haben jetzt eine erläutert, wie sieht es mit der anderen aus?

(S) Man möchte zu je zwei Programmen P, Q ein Programm R für die Komposition effektiv konstruieren können, so daß
j (R) = j (P) ° j (Q) gilt...
(Hier unterbrach mich Prof. Weihrauch)

Was sagt das smn-Theorem über die effektive Komposition von Programmen aus? Da gibt es doch einen Satz.

Der Satz besagt, daß sich Programme lassen genau dann effektiv hintereinander schalten lassen, wenn das smn-Theorem erfüllt ist.

Es gibt ja unheimlich viele Programmiersprachen. Sind die völlig anders als unser j oder hängen die irgendwie alle zusammen?

Nach dem Äquivalenzsatz von Rogers sind genau die Programmiersprachen äquivalent, die das utm- und das
smn-Theorem erfüllen. Also wenn man eine weitere Programmiersprache y : IN®P⁽¹⁾ hat,
die ebenfalls (utm) und (smn) erfüllt, gilt (notwendig und hinreichend) y º j.

Was heißt jetzt genau äquivalent? Wie haben wir die Relation º im Kurstext formal definiert?

Da mußte ich passen. Auch ein kleiner Tip half mir nicht wesentlich weiter. Herr Weihrauch
erkläre dann selbst die Äquivalenz von y und j mit Hilfe zweier
Übersetzungsfunktionen, die y in j übersetzen und umgekehrt.

Wann ist eine Teilmenge der natürlichen Zahlen rekursiv?

Eine Menge A Í IN^k ist rek.

Û Die charakteristische Funktion cf_A ist berechenbar

Û A und IN^k \ A sind rekursiv aufzählbar (*)

Û $ f Î R^(k) : A = f ^-1 {0}

Hier hatte ich versehentlich noch eine Definition angegeben, die die rekursive Aufzählbarkeit charakterisiert, was mir aber bei der Beantwortung der nächsten Frage selbst aufgefallen ist.

Hmm, dann schreiben Sie doch mal auf, wann eine Teilmenge der natürlichen Zahlen rekursiv aufzählbar ist!

Eine Menge A Í IN^k ist r. a.

Û $ f Î P^(k) : A = Def (f)

Û $ f Î R^(k) : A = Bild (f) oder A = Ø

Gegenüber welchen Mengenoperationen sind denn rekursive Aufzählbarkeit und Rekursivität abgeschlossen?

Die rekursive Aufzählbarkeit ist bezüglich Vereinigung und Durchschnitt abgeschlossen, während die Rekursivität darüber hinaus noch bezüglich Komplementbildung abgeschlossen ist.

Kennen Sie ein Beispiel für eine nicht rekursiv aufzählbare Menge?

Das Komplement von K_j, denn wäre das rekursiv aufzählbar, dann wäre K_j ja wegen (*) rekursiv. Widerspruch!

Kennen Sie auch ein Beispiel für eine nicht rekursiv aufzählbare Menge, deren Komplement ebenfalls nicht rekursiv aufzählbar ist?

Nach kurzem Überlegen: Nein. Prof. Weihrauch hat mir dann eine solche Menge definiert.

Formale Sprachen

Wann ist eine Sprache regulär?

Wenn sie von einer rechtslinearen Grammatik erzeugt bzw. von einem endlichen Automaten erkannt wird.

Wenn man einen nichtdeterministischen Automaten hat, wie kann man dazu einen deterministischen bauen, der genau das gleiche macht?

Man konstruiert den Potenzautomaten zu dem nichtdeterministischen Automaten.

Wie konstuiert man den?

(kurze Erklärung)

Was steht in den Knoten eines Potenzautomaten?

Eine Teilmenge der ursprünglichen Knotenmenge.

Welche Knoten im Potenzautomaten werden zu Endzuständen des Potenzautomaten?

Jeder Knoten, der ein Element der ursprünglichen Knotenmenge enthält, das im ursprünglichen
Automaten bereits Endzustand war.

Kennen Sie eine kontextfreie Sprache, die nicht kontextsensitiv ist?

Ja, {aⁿbⁿ | n Î IN}

Begründen Sie das bitte kurz!

Naja, man baut einen Kellerautomaten, der zuerst alle a's auf den Stack legt und dann für alle b's wieder ein a von Stack nimmt... (Das reichte ihm schon)

Was ist mit {ww^R | w Î S*} ?

Die Sprache ist kontextfrei. Hätte man {w#w^R | w Î S*},
also die gleiche Sprache mit einem Trennsymbol # zwischen dem Wort und seinem Spiegelbild, dann könnte man einfach
einen Kellerautomaten bauen, der zuerst das Wort bis zum Trennsymbol auf den Keller schreibt und dann das Spiegelbild
zeichenweise mit dem obersten Element im Keller vergleicht und dieses bei Übereinstimmung entfernt.

Da man jedoch in {ww^R | w Î S*}
kein solches Trennzeichen hat, muß der Kellerautomat eben nichtdeterministisch umschalten.

Wie funktioniert das? Wann akzeptiert der nichtdeterministische Kellerautomat?

Bereits wenn es eine Möglichkeit (einen Pfad im Baum) gibt, die Sprache zu erkennen.

Komplexitätstheorie

Gut, wir machen jetzt mal einen riesen Sprung und kommen zur Komplexitätstheorie.
Kennen Sie den Satz von Savage? Was besagt dieser Satz bezüglich des Nichtdeterminismusses?

Mir ist der Satz entfallen. Ich habe zuerst versucht, mich mit LOGSPACE Í NLOGSPACE Í P Í NP Í PSPACE = NPSPACE Í U_cÎIN ZEIT (cⁿ) etwas rauszureden,
um vom Thema abzulenken, aber das ging natürlich in die Hose. Letztendlich hat Herr Weihrauch den gewünschten Satz selbst
skizziert (wie im Kurstext).