s3damues

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Übungsaufgaben 1.1 Vorlesung 1: Vorbereitungen 1.2 Vorlesung 2: Berechenbarkeitsbegriff 1.2.1 abzählbare unendliche Menge 1.3 Vorlesung 3: Entscheidbarkeit und Aufzählbarkeit 1.3.1 Einfache Beispiele für $\chi_{M}$ 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))

ausführen

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

ausführen

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)

ausführen

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

ausführen

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

ausführen

Kreativaufgaben

In diesem Kapitel befinden sich die Kreativaufgaben aus den Vorlesungen.

Kreativaufgabe 1: Der Hilbertbus