BuK/IIm11/Studenten/simawiel/ue4

Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== Kreativaufgabe ==

Wenn zwei Mengen aufzählbar sind, so ist auch ihre Schnittmenge aufzählbar. Das heißt es muss eine Funktion geben, die eine natürliche Zahl n auf ein Element der Schnittmenge abbildet. Dafür widerum muss es einen Algorithmus geben.

<code id="4f84973ec5a20">
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Aufzählfunktionen für die Mengen m1 und m2 ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define m1
  (lambda (n)
    n
  )
)
(define m2 
  (lambda (n)
    (+ n 1)
  )
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Hilfsfunktionen und -variablen             ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define match-counter -1)

(define ++
  (lambda (c)
    (+ c 1)
  )
)

(define contains?
  (lambda (listx element)
    (cond
      ((null? listx) #f) 
      ((equal? (car listx) element) #t)
      (else (contains? (cdr listx) element))
    )
  )
)  

(define get-match
  (lambda (list1 list2)
    (cond 
      ((empty? list1) null)
      ((contains? list2 (car list1)) 
         (begin ((car list1)) (++ match-counter)))
      (else (get-match (cdr list1) list2))
    )
  )
)

(define get-m1
  (lambda (n)
    (if (= n 0)
      (list (m1 n))
      (append (get-m1 (- n 1)) (list (m1 n)))
    )
  )
)

(define get-m2
  (lambda (n)
    (if (= n 0)
      (list (m2 n))
      (append (get-m2 (- n 1)) (list (m2 n)))
    )
  )
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Hauptfunktion: F -> IntersectionElement(M1,M2) ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define intersec 
  (lambda (n)
    (let 
      ((p1 (get-m1 n))
       (p2 (get-m2 n))
       (last-match (get-match p1 p2))
      )
      (letrec
        ((helper 
           (lambda (list1 list2)
             (set! last-match (get-match list1 list2))
           )
        ))
        (cond 
          ((and (= n match-counter) (not (null? last-match))) last-match)
          ((and (= n match-counter) (null? last-match)) null)
          (else (helper (cdr p1) (cdr p2)))
        )
      )
    ) 
  )
)
</code>
<run id="4f84973ec5b47">(intersec 10)</run>

== Teilaufgabe 2 - Indirekter Beweis ==

zu zeigen: Nicht jede Teilmenge M2 einer aufzählbaren Menge M1 ist aufzählbar. Wenn M1 eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen M2⊆M1, dass sie aufzählbar sind.
BuK/IIm11/Studenten/simawiel/ue4

Suche
