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>

<language>Scheme</language>
= 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.
$
<div align="right">$\square$</div>

Ü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)
<div align="right">$\square$</div>

↦ 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:

[[Bild:Sirabien_A_oben_Stern.png]]

([http://www.inf.hs-zigr.de/~sirabien/A_oben_Stern.svg als SVG])

<code id="4f7b4263a8e6d">
(define pow
  (lambda (number exp)
    (if (= exp 0)
      1
      (* number (pow number (- exp 1))))))

(define getElement
  (lambda (set index)
    (if (= index 1)
      (car set)
      (getElement (cdr set) (- index 1)))))
      
(define cardinalNumber
  (lambda (set)
    (if (null? set)
      0
      (+ 1 (cardinalNumber (cdr set))))))


      
(define calculateWordSize
  (lambda (set index)
    (letrec ((calculateWordSizeReal
      (lambda (cardinalNumber index sum exp)
        (if (>= sum index)
          0
          (+ 1 
            (calculateWordSizeReal
              cardinalNumber
              index
              (+ sum (pow cardinalNumber exp))
              (+ 1 exp)))))))
  (calculateWordSizeReal (cardinalNumber set) index 0 1))))

;Berechnet die Anzahl der Wörter mit Länge <= letterCount
(define numberOfWords
  (lambda (cardinalNumber letterCount)
    (if (= letterCount 0)
      0
      (+
        (pow cardinalNumber letterCount)
        (numberOfWords cardinalNumber (- letterCount 1))))))
    
(define createWord
  (lambda (set wordnumber cardinalNumber lettersRemaining)
    (if (= 0 lettersRemaining)
      ""
      (let ((sectionSize (pow cardinalNumber (- lettersRemaining 1))))
        (let ((rest (modulo wordnumber sectionSize))
            (result (quotient wordnumber sectionSize)))
          (if (= 0 rest)
            (string-append
              (string (getElement set result))
              (createWord set sectionSize cardinalNumber (- lettersRemaining 1)))
            (string-append
              (string (getElement set (+ result 1)))
              (createWord set rest cardinalNumber (- lettersRemaining 1)))))))))
                
(define f
  (lambda (set index)
    (if (= index 0)
      ""
      (let((cardinalNumber (cardinalNumber testSet))
          (lettersRemaining (calculateWordSize testSet index)))
        (createWord testSet (- index (numberOfWords cardinalNumber (- lettersRemaining 1))) cardinalNumber lettersRemaining)))))
</code>

<run id="4f7b4263a8f05">
(define testSet
  '(#\a #\b #\c))

(f testSet 30)
</run>