sirabien
Inhaltsverzeichnis |
Woche 2
Aufgabe 4
Beweisen Sie den folgenden Satz: Wenn M_{1}, M_{2}, M_{3} ... abzählbare Mengen sind, dann ist auch die Menge \bigcup_{n=1}^\infty {M_{n}} abzählbar.
m_{1}(i), m_{2}(i), m_{3}(i) …; i ∈ ℕ seien Indexfunktionen für M_{1}, M_{2}, M_{3} …
n(i); i ∈ ℕ sei Indexfunktion für \bigcup_{n=1}^\infty {M_{n}} (gesucht)
Cantorsches Diagonalisierungsverfahren 1. Art:
| |m_{1}(0) = n(0) | m_{1}(1) = n(1) | m_{1}(2) = n(5) | m_{1}(3) = n(6) | … |
| |m_{2}(0) = n(2) | m_{2}(1) = n(4) | m_{2}(2) = n(7) | m_{2}(3) = n(13) | … |
| |m_{3}(0) = n(3) | m_{3}(1) = n(8) | m_{3}(2) = n(12) | m_{3}(3) = n(17) | … |
| |m_{4}(0) = n(9) | m_{4}(1) = n(11) | m_{4}(2) = n(18) | m_{4}(3) = n(24) | … |
| |… | … | … | … | … |
Alternativ:
| |m_{0}(0) = n(0) | m_{0}(1) = n(2) | m_{0}(2) = n(5) | m_{0}(3) = n(9) | … |
| |m_{1}(0) = n(1) | m_{1}(1) = n(4) | m_{1}(2) = n(8) | m_{1}(3) = n(13) | … |
| |m_{2}(0) = n(3) | m_{2}(1) = n(7) | m_{2}(2) = n(12) | m_{2}(3) = n(18) | … |
| |m_{3}(0) = n(6) | m_{3}(1) = n(11) | m_{3}(2) = n(17) | m_{3}(3) = n(24) | … |
| |… | … | … | … | … |
Woche 3
Aufgabe 3
Ü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.
Für endliches Alphabet:
Bsp:
(als SVG)
