BuK-Übung03
Inhaltsverzeichnis |
Aufgabe 1 (Felix Nitsche, Stefan Lüttke)
ÜA: Wie viele berechenbare charakteristische Funktionen gibt es? Hinweis: Potenzmenge unendlicher Mengen
Aufgabe 2 (Jens Heider, Daniel Tasche)
ÜA: Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki).
Aufgabe 3 (Max Wielsch, Raik Bieniek)
TODO Scheme Funktionen für die ersten beiden Teilaufgaben von Max rüberkopieren
ÜA: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.
Gesucht: f: ℕ ↦ G; berechenbar, surjektiv
$f(x) = \left\{\begin{array}{cc} x; wenn\ 2|x\\ (-1) \cdot x + 1; sonst\\ \end{array}\right. $
ÜA: Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist
Gesucht: f: ℕ ↦ P; berechenbar, surjektiv
$f(x) = \left\{\begin{array}{cc} x; wenn\ prime?(x)\\ 2; sonst\\ \end{array}\right. $
Existiert ein Algorithmus für f? wenn/sonst durch if/else implementierbar prime? Funktion existiert (siehe Folien)
↦ f ist berechenbar
ÜA: Wir wissen, dass A* eine abzählbar unendliche Menge ist. Zeigen Sie, dass A* auch aufzählbar ist. Hinweis: Hierzu ist es notwendig ein Aufbauschema für A* zu entwerfen und anschließend eine Prozedur dafür zu implementieren.
Gesucht: f: ℕ ↦ A^*; berechenbar, surjektiv
Für endliches Alphabet:
Bsp:
(als SVG)
Aufgabe 4 (Ingo Körner, Christof Ochmann)
ÜA: Zeigen Sie, dass jede endliche Menge aufzählbar ist.
ÜA: Die Menge G der Gitterpunkte (0, 0),(0, 1), ... einer x-y-Ebene ist aufzählbar.
1 Geben Sie eine Funktion f an, die \N_0 bijektiv auf G abbildet.
2 Definieren Sie eine Ordnungsrelation p_< in G.
3 Geben Sie eine Funktion k zur Berechnung der Platznummer k(x, y) des betrachteten Gitterpunktes (x, y) an.
4 Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.
Aufgabe 5 (Tobias Salzmann, Ronald Krause)
ÜA: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.
ÜA: Weisen Sie nach, dass die Menge M aller "Wörter aus {a, b}*, die mit a beginnen, semi-entscheidbar ist.
ÜA: Geben Sie fur die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass FIBS eine semi-entscheidbare Menge ist. Zeigen Sie, dass FIBS sogar entscheidbar ist.
ÜA: Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen QZ = \{n^2 |n \in \N\}.
Aufgabe 6 (Robert Rosenberger, Stefan Scheumann)
ÜA: Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki die 30 ersten Elemente der Vereinigungsmenge (in aufsteigender Sortierung) auszugeben.