Vordiplomsprüfung Theoretische
Informatik (1653, 1645)
Prüfer: Hr. Prof. Dr. Weihrauch
Datum: 26.04.99
Note: 1,0
-
Wann ist eine Zahlenfunktion berechenbar
-
Ist x² berechenbar
-
Zusammenhang zwischen eine Funktion "heißt" und
eine Funktion "ist" berechenbar -> Churchsche These
-
Datenmenge einer Bandmaschine mit Erklärung für
(u,a,v)
-
Befehlssatz einer Bandmaschine
-
Kommt eine Bandmaschine ohne Hilfssymbole aus -> Hilfssymbollemma
-
Zusammenhang zwischen Zahlen- und Wortberechenbarkeit
-
Anforderungen an Modellsprache phi -> Anforderungen
(U) und (S) erläutert, Hinweis auf utm- und smn-Theorem als formale
Anforderung
-
Definition von phi
-
Berechenbarkeit auf Q
-
Definition von (nrat, nrat) – berechenbar
-
Ausweitung auf Berechenbarkeitsbegriff in R
-
Definition Cauchy- Darstellung
-
Typ-2-Maschine, Arbeitsweise erläutern
-
Beispiele für Funktionen, die auf R berechenbar
sind -> x², Wurzel(x), x+y
-
Zwei Definitionen zu rekursiven Mengen
-
Drei Definitionen zu rekursiv aufzählbaren Mengen
-
Zusammenhang zwischen den Mengen
-
Menge, die r.a. aber nicht rekursiv ist -> K phi
-
Beweis, daß K phi r.a.
-
Beweis, daß N\K phi nicht r.a.
-
Ist die Menge der geraden Zahlen rekursiv
-
Ist L={w aus {0,1}* mit 010 als Teilwort} regulär
-> Angabe eines endlichen Automaten
-
Ist L={wwR} kontextfrei -> Erkennung durch nichtdeterministen
Kellerautomat
Komplexitätstheorie wurde nicht geprüft.