sirabien

Aus ProgrammingWiki

Archivierte Version vom 2012-04-17T13:07:35+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Woche 2
- 1.1 Aufgabe 4
2 Woche 3
- 2.1 Aufgabe 3
3 Kreativaufgabe Schnittmenge zweier aufzählbarer Mengen
4 Woche 4
- 4.1 Teilaufgabe 2 - Indirekter Beweis (Max Wielsch, Raik Bieniek)

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)	…
\|…	…	…	…	…

\square

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)	…
\|…	…	…	…	…

;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))))))

(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. $

\square

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

\square

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

(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)))))

(define testSet
  '(#\a #\b #\c))

(f testSet 30)

Kreativaufgabe Schnittmenge zweier aufzählbarer Mengen

;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))

(fOut 1)

Woche 4

Teilaufgabe 2 - Indirekter Beweis (Max Wielsch, Raik Bieniek)

zu zeigen: Nicht jede Teilmenge M2 einer aufzählbaren Menge M1 ist aufzählbar.

oder: Wenn M1 eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen M2⊆M1, dass sie aufzählbar sind.

Indirekter Beweis: Behauptung: Jede Teilmenge M2 ⊆ M1 ist aufzählbar, wenn M1 aufzählbar.

Gegeben:

f: ℕ ↦ M1; aufzählbar (surjektiv; berechenbar)
M2 ⊆ M1

Gesucht:

g: ℕ ↦ M2; aufzählbar

$g(x) = \left\{\begin{array}{cc} f(x); wenn\ f(x) ∈ M2\\ a; wenn f(x) ∈ M1\setminus M2\\ \end{array}\right. $

- wenn g existiert, denn M2 semientscheidbar (weil g aufzählbar ist)

sirabien

Inhaltsverzeichnis

Woche 2

Aufgabe 4

Woche 3

Aufgabe 3

Kreativaufgabe Schnittmenge zweier aufzählbarer Mengen

Woche 4

Teilaufgabe 2 - Indirekter Beweis (Max Wielsch, Raik Bieniek)

Suche