s3damues

Aus ProgrammingWiki

< BuK < IIm14 < Studenten

Inhaltsverzeichnis

1 Übungsaufgaben
2 Kreativaufgaben
- 2.1 Kreativaufgabe 1: Der Hilbertbus

Übungsaufgaben

In diesem Kapitel befinden sich die Übungsaufgaben aus den ersten vier Vorlesungen.

Vorlesung 1: Vorbereitungen

Vorlesung 2: Berechenbarkeitsbegriff

abzählbare unendliche Menge

(define f 
  (lambda (n) 
    (if (= n 1)
        1
        (if (= (modulo n 2) 0)
            (+ 1 (f (/ n 2)))
            (/ 1 (f (- n 1)))
            )
        )
    )
  )

(map f '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20))

Umkehrfunktion

(define f-umkehr 
    (lambda (n) 
        (if (= n 1)
            1
            (if (> n 1)
                (* 2 (f-umkehr (- n 1)))
                (+ 1 (f-umkehr (/ 1 n)))
            )
        )
    )
)

(map f-umkehr '(1 2 1/2 3 1/3 3/2 2/3 4 1/4 4/3 3/4 5/2 2/5 5/3 3/5 5 1/5 5/4 4/5 7/3))

Prozedur mit memoizing

(import hashtable)
(define table (make-hashtable))
(define false (lambda () #f))
(define f-mem
    (lambda (n) 
        (let ([resultat (hashtable/get table n false)])
            (cond
                [(= n 1) 1]
                [(number? resultat) resultat]
                [else 
                  (let([res-berechnet 
                    (if (= (modulo n 2) 0)
                        (+ 1 (f-mem (/ n 2)))
                        (/ 1 (f-mem (- n 1)))
                    )])
                    (hashtable/put! table n res-berechnet)
                    res-berechnet
                  )
                ]
            )
        )
    )
)

(f-mem 999)

Vorlesung 3: Entscheidbarkeit und Aufzählbarkeit

Einfache Beispiele für \chi_{M}

(define chi
  (lambda (w)
    (cond
      [(not (string? w)) #f]
      [(= (string-length w) 3) #t]
      [(not (= (string-length w) 3)) #f]
    )
  )
)

(chi "aba")

(define chi
  (lambda (w)
    (cond
      [(not (string? w)) #f]
      [(equal? (string-ref w 0) #\a) #t]
      [(not (equal? (string-ref w 0) #\a)) #f]
    )
  )
)

(chi "ababababa")

Kreativaufgaben

In diesem Kapitel befinden sich die Kreativaufgaben aus den Vorlesungen.