Mündliche Diplomvorprüfung: Theoretische Informatik A + B
| Prüfer: | Prof. Weihrauch |
| Termin: | 05.10.2000, 12.30 Uhr |
| Dauer: | ca. 25 Minuten |
| Note: | 1,0 |
Fragen zum Teil A:
Wann ist eine Zahlenfunktion f berechenbar?
- Wenn es eine RM M gibt, die f berechnet.
Ist f = 7x berechenbar?
- Ja, weil man leicht eine RM finden kann, die f berechnet.
Wann ist eine Wortfunktion g berechenbar?
- Wenn es eine TM M gibt, die g berechnet.
Wie kommt man von einer Turingmaschine zu einer Bandmaschine?
Was muss man machen, wenn man ein Zeichen vom ehemaligen Band 3 lesen will?
- Man muss die Kopfmarkierung auf dem Band suchen.
Wie ist der Zusammenhang zwischen Zahlen- und Wortfunktionen?
Ist die Menge Schnittmenge von A und B r. a., wenn A und B r. a. sind?
- Ja, da die r. a. Mengen unter Schnitt abgeschlossen sind.
- Beweisidee: 2 Maschinen, die nacheinander laufen.
Und wie ist das bei der Vereinigung von A und B?
- Die Vereinigungsmenge ist auch r. a..
- Beweisidee: 2 Maschinen, die parallel laufen.
Wann ist eine Menge r. a.?
- s. Kurstext + Charakterisierung durch Bild und Projektionssatz
Wann ist eine Menge rekursiv?
- Wenn die charakteristische Funktion berechenbar ist.
Welche Definition gibt es dafür noch?
- f ist total berechenbare Zahlenfunktion, A ist Urbild von f.
Ist die Menge der Zweierpotenzen rek.?
- Ja, da es eine TM gibt, die die char. Funktion berechnen kann.
Welche Menge ist nicht rek., aber r. a.?
N/Kj ist nicht r. a..Gibt es eine Menge, die nicht r. a. ist und deren Komplement auch nicht r. a. ist?
- Äquivalenzproblem, Korrektheitsproblem
Wie ist das Äquivalenzproblem definiert?
Wie ist die Standardnummerierung definiert?
- Nummerierung der berechenbaren Zahlenfunktionen, zusammengesetzt aus drei Funktionen - s. Kurstext
Was ist dabei die Syntax?
- Die Menge N der natürlichen Zahlen
Wir hatten Funktionen und Programme. Wie ist nun der Zusammenhang?
Welche Anforderungen an eine Programmiersprache hatten wir besprochen?
Wie ist das utm-Theorem definiert?
Eine Sprache kann in eine andere übersetzt werden. Welchen Satz hatten wir dazu erwähnt?
- Äquivalenzsatz von Rogers.
Wie lautet, denn der Äquivalenzsatz von Rogers?
- Formale Beschreibung reichte nicht ganz aus. Exakte Formulierung der "Übersetzer" wurde verlangt.
Fragen zum Teil B:
Beispiele: L1:= {w$wR}, L2:= {wwR}, L3:= {ww}
Was können Sie zu den Mengen bezüglich Kontextfreiheit sagen?
- Kurz erklärt, dass eine Menge kontextfrei ist, wenn sie von einem Kellerautomaten erkann wird.
- L1 ist kontextfrei, da Mitte bekannt ist und zweiter Teil gespiegelt ist, Vergleich mit Klammerproblem (gleich viele öffnende wie schliessende Klammern)
- L2 ist nur nichtdet. kontextfrei, da die Mitte geraten werden muss.
- L3 ist nicht kontextfrei, da ein Kellerautomat nur auf die Kellerspitze zugreifen kann (somit den nichtgespiegelten zweiten Wortteil nicht vergleichen kann) und die Mitte nicht kennt.
Wie kann man zeigen, dass L3 nicht kontextfrei ist?
- Mit dem Pumping-Lemma für kontextfreie Sprachen. (Musste nicht näher erklärt werden)
Wie lautet der Satz von Savitch?
- s. Kurstext (nur die Formulierung - keine weiteren Fragen zur Bedeutung etc.)
Was versteht man unter NP-vollständig?
- M ist NP-vollst., wenn M NP-hart und Element von NP ist.
Was versteht man unter NP-hart?
Wir hatten im Kurs die Kontrollturingmaschine eingeführt. Was versteht man unter x ist Element von L(M)?
- Def. der von einer KTM erkannten Sprache - s. Kurstext - und Hinweis, dass KTM nur beweisen und nicht entscheiden kann.
Mein Eindruck:
Prof. Weihrauch ist sehr freundlich, ruhig, fair, lässt ausreichend Zeit zum Antworten.
Ich kann ihn als Prüfer nur empfehlen!
Viel Erfolg bei Deiner Prüfung!