BuK/IIm11/Studenten/sirabien
Aus ProgrammingWiki
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.
$
<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>
= Kreativaufgabe Schnittmenge zweier aufzählbarer Mengen =
<code id="4f847dc146ab6">;Test sets
(define testSet1
'(#\c #\b #\d #\a))
(define testSet2
'(#\d #\f #\a #\c))
(define fCreator
(lambda (set)
(lambda (index)
(letrec
((helper
(lambda (set index)
(if (= index 0)
(car set)
(helper (cdr set) (- index 1))))))
(helper set index)))))
(define f1 (fCreator testSet1))
(define f2 (fCreator testSet2))
;algorithm
(define contains?
(lambda (set element)
(if (null? set)
#f
(if (equal? (car set) element)
#t
(contains? (cdr set) element)))))
(define algo
(lambda (set1 set2 f1 f2 index counterElementsFound counterFIndex)
(let (
(use1 (= (modulo counterFIndex 2) 0))
(indexReal (quotient counterFIndex 2)))
(let ((element (if use1 (f1 indexReal) (f2 indexReal))))
(let (
(contains (if use1 (contains? set2 element) (contains? set1 element)))
(set1next (if use1 (cons element set1) set1))
(set2next (if use1 set2 (cons element set2))))
(if contains
(if (= counterElementsFound index)
element
(algo set1next set2next f1 f2 index (+ counterElementsFound 1) (+ counterFIndex 1)))
(algo set1next set2next f1 f2 index counterElementsFound (+ counterFIndex 1))))))))
(define intersectionFCreator
(lambda (f1 f2)
(lambda (i)
(algo '() '() f1 f2 i 0 0))))
(define fOut (intersectionFCreator f1 f2))</code>
<run id="4f847dc146b72">(fOut 1)</run>
= Woche 4 =
== Teilaufgabe 2 - Indirekter Beweis (Max Wielsch, Raik Bieniek) ==
zu zeigen: Nicht jede Teilmenge $M_2$ einer aufzählbaren Menge $M_1$ ist aufzählbar.
oder: Wenn M1 eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen $M_2$ ⊆ $M_1$, dass sie aufzählbar sind.
Indirekter Beweis: Behauptung: Wenn $M_1$ aufzählbar, dann jede Teilmenge $M_2$ ⊆ $M_1$ ist aufzählbar.
Gegeben:
* f: ℕ ↦ $M_1$; aufzählbar (surjektiv; berechenbar)
* $M_2$ ⊆ $M_1$
* Satz 1: Wenn $M_2$ entscheidbar ⇔ $M_2$ und $M_1 \setminus M_2$ aufzählbar.
* Satz 2: Wenn $M_2$ aufzählbar → dann ist $M_2$ semientscheidbar.
Gesucht:
* g: ℕ ↦ $M_2$; aufzählbar (surjektiv; berechenbar), d. h. es gilt Satz 1.
$g(x) = \left\{\begin{array}{cc}
f(x); wenn\ f(x) ∈ M_2\\v
a; wenn f(x) ∈ M1\setminus M_2\\
\end{array}\right.
$
laut Satz 2:
$Χ'_{M_2,M_1}(w) = \left\{\begin{array}{cc}
wahr; (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\
⊥; sonst\\
\end{array}\right.
$
$Χ_{M_2,M_1}(w) = \left\{\begin{array}{cc}
wahr; (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\
falsch; (f(i) = w) ∈ M_1\setminus M_2 \\
\end{array}\right.
$
$Χ'_{M_2,M_1}$ vs. $Χ_{M_2,M_1}$; entscheidbar ☇ semi-entscheidbar. → Behauptung falsch → Satz wahr.
<div align="right">$\square$</div>
= Woche 5 =
Eine Menge M ⊆ Σ* heißt Turing-entscheidbar, wenn es eine Turing-Maschine P gibt, so dass
* für ∀w ∈ M gilt: q0 w $⊢^*$ qe x, qe ∈ E, x ∈ Γ.
* für ∀w ∉ M gilt: ¬(q0 w $⊢^*$ qe x).
Eine Menge M ⊆ Σ heißt Turing-aufzählbar, wenn es eine Turing-Maschine P gibt, so dass für ∀w ∈ Σ* gilt q0 w $⊢^*$ qe x, qe ∈ E, x ∈ M.
* Idee: Σ* ist aufzählbar und wird anstelle der natürlichen Zahlen verwendet.
<language>Scheme</language>
<language>Scheme</language>
= Woche 7 =
<language>Scheme</language>
<language>Scheme</language>
== Gödelisierung ==
Die Gödelisierung bezeichnet das Verfahren, ein Wort aus einer Wortmenge ($A^*$) auf die Menge der Zahlen abzubilden. Dadurch sind Probleme der "Wort-Welt", also Probleme, die mit Programmiersprachen beschrieben werden können, ebenso in der Zahlenwelt (Mathematik) darstellbar und lösbar.
=== Hilfsprozeduren ===
==== Stream-Prozeduren ====
<code id="4fb2a5ea19c0b">
(define stream-car car)
(define stream-cdr
(lambda (stm)
(force (cdr stm))))
(define-syntax stream-cons
(syntax-rules ()
((_ head tail) (cons head (delay tail)))))
(define stream?
(lambda (stm)
(and (pair? stm)(promise? (cdr stm)))))
(define stream-item
(lambda (str nr)
(if(<= nr 0)
(stream-car str)
(stream-item (stream-cdr str) (- nr 1)))))
(define print-stream
(lambda (stm n)
(cond
((<= n 0) (display "...\n"))
(else
(display (stream-car stm))
(display ", ")
(print-stream (stream-cdr stm) (- n 1))))))
</code>
==== Prozeduren für Wortmengen-Stream ====
<code id="4fb2a5ea19cd2">
(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 (testSet index)
(if (= index 0)
""
(let((cardinalNumber (cardinalNumber testSet))
(lettersRemaining (calculateWordSize testSet index)))
(createWord testSet (- index (numberOfWords cardinalNumber (- lettersRemaining 1))) cardinalNumber lettersRemaining)))))
</code>
==== Prozeduren für Primzahlenverschlüsselung ====
<code id="4fb27830b9d1e">;; from presention nr. 3
(define prim?
(lambda (n)
(letrec
((helfer
(lambda (t)
(cond
((> t (sqrt n)) #t)
((= (remainder n t) 0) #f)
(else
(helfer (+ t 2)))))))
(cond
((= n 1) #f)
((= n 2) #t)
((= (remainder n 2) 0) #f)
(else
(helfer 3))))))
;; returns the next prime number that is larger than number
(define nextPrime
(lambda (number)
(let ((nextNumber (+ number 1)))
(if (prim? nextNumber)
nextNumber
(nextPrime nextNumber)))))
(define letterToindexGenerator
(lambda (list)
(lambda (letter)
(letrec ((worker (lambda (list letterNumber)
(if (equal? (car list) letter)
letterNumber
(worker (cdr list) (+ 1 letterNumber))))))
(worker list 1)))))
(define GGenerator
(lambda (letterFkt)
(lambda (word)
(letrec ((worker (lambda (word lastPrime)
(if (null? word)
1
(let (
(primeNr (nextPrime lastPrime))
(letterIndex (letterFkt (car word))))
(* (expt primeNr letterIndex) (worker (cdr word) primeNr)))))))
(worker (string->list word) 0)))))
</code>
<language>Scheme</language>
== Hauptprozedur ==
Die Hauptprozedur für die Gödel-Funktion ist nun mit den Hilfsfunktionen realisiert.
<code id="4fb2aba78234f">
(define some-alphabet (list #\a #\b #\c #\d))
(define letterToindexOfSomeAlphabet (letterToindexGenerator some-alphabet))
(define G (GGenerator letterToindexOfSomeAlphabet))
; Erzeuge Stream von A*
(define a-stream-maker
(lambda (index)
(stream-cons (f some-alphabet index) (a-stream-maker (+ index 1)))))
(define a-stream (a-stream-maker 1))
(define some-word (stream-item a-stream 333))
</code>
<run id="4fb2aba7823b8">
(display some-word)
(display "\n")
(G some-word)
</run>
== Umkehrung der Gödelisierung ==
Für die "Ent-Gödelisierung" muss nun aus einer Gödelnummer ein Wort aus der Wortmenge (Das Urbild der Abbildung) erzeugt werden, das mit der Gödel-Funktion benutzt wieder genau dieselbe Gödelnummer ergibt.
=== Hilfsprozeduren ===
<code id="4fb27830b9d87">(define indexToLetterGenerator
(lambda (list)
(lambda (number)
(letrec ((worker (lambda (list letterNumber)
(if (= number letterNumber)
(car list)
(worker (cdr list) (+ 1 letterNumber))))))
(worker list 1)))))
(define getExponents
(lambda (number base)
(letrec ((worker (lambda (number)
(if (< number base)
(list number)
(let ((digit (if
(= (modulo number base) 0)
base
(modulo number base))))
(cons digit (worker (quotient number base))))))))
(worker number))))
(define numberToWord
(lambda (indexFkt number base) 0
(letrec ((worker (lambda (letterNumberList)
(if (null? letterNumberList)
'()
(cons (indexFkt (car letterNumberList)) (worker (cdr letterNumberList)))))))
(list->string (worker (getExponents number base))))))
(define primeProduktForBase
(lambda (number base)
(letrec ((worker (lambda (exponentList currentPrime)
(if (null? exponentList)
1
(let ((calculatedNextPrime (nextPrime currentPrime)))
(* (expt calculatedNextPrime (car exponentList)) (worker (cdr exponentList) calculatedNextPrime)))))))
(worker (getExponents number base) 1))))
(define GInvertedGenerator
(lambda (indexFkt letterCount)
(lambda (number)
(letrec ((worker (lambda (index)
(if (= (primeProduktForBase index letterCount) number)
(numberToWord indexFkt index letterCount)
(worker (+ 1 index))))))
(worker 0)))))
</code>
== Hauptprozedur ==
<code id="4fb299efd591c">
(define indexToLetterOfSomeAlphabet (indexToLetterGenerator someAlphabet))
(define GInverted (GInvertedGenerator indexToLetterOfSomeAlphabet (length someAlphabet)))
</code>
<run id="4fb27830b9e4f">(GInverted 294000)</run>