BuK/IIm11/Studenten/sirabien

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
= 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:

{| border="1" cellpadding="5" cellspacing="0"
|-
||$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)$ || …
|-
||…|| … || … || … || …
|-
|}
<div align="right">$\square$</div>

Alternativ:

{| border="1" cellpadding="5" cellspacing="0"
|-
||$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)$ || …
|-
||…|| … || … || … || …
|-
|}

<code id="4f71955fd2de0">
;Gibt die Abzählfunktion M_n zurück
(define m 
  (lambda (setIndex) 
    (lambda (elementIndex)
      (string-append
        "Menge "
        (number->string setIndex)
        " Element "
        (number->string elementIndex)))))

; basiert auf
; http://de.wikipedia.org/w/index.php?title=Cantorsche_Paarungsfunktion&oldid=95121801#Pascal-Programm_zur_Berechnung_der_Umkehrung
;   function F(Z : Integer) : Integer;
;   begin
;      F := Z * (Z + 1) div 2
;   end;

(define f
  (lambda (z)
    (* z (/ (+ z 1) 2))))
    
;   function Q(Z : Integer) : Integer;
;   var
;      V : Integer;
;   begin
;      V := 0;
;      while F(V) <= Z do
;         V := V + 1;
;      Q := V - 1
;   end;

(define tmp
  (lambda (v z)
    (cond
      ((<= (f v) z) (tmp (+ v 1) z))
      (else (- v 1)))))
  
(define q
  (lambda (z)
    (tmp 0 z)))

; begin
;   J := Q(I);
;   Y := I - F(J);
;    X := J - Y;
; end;
(define n
  (lambda (i)
    (let ((j (q i)))
      (let  ((y (- i (f j))))
        (let ((x (- j y)))
          ((m x) y))))))
</code>

<run id="4f71955fd2e4c">(n 24)</run>

= 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.

Ü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.