BuK/IIm11/BuK-KA-Zeitbeschränkte-Prozesse
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== Aufgabenstellung ==
Implementieren Sie die im Beweis definierte Aufzählfunktion für $M \subseteq \text{ A*}$ unter Verwendung der Cantorschen Paarungsfunktion. Wählen Sie im Fallbeispiel A = $\{a,b,c\}, g: \N \mapsto A^*$ und M = $\{w |w \in A^* \text{ und } w \text{ enthält Fibonacci-zahlig viele} "b's"\}$.
Machen Sie bei der Konstruktion von $\chi^'_M$ nur von der Semi-Entscheidbarkeit der Menge der Fibonacci-Zahlen Gebrauch, obwohl doch deren Entscheidbarkeit durch Beschränkung des Suchraumes gegeben ist.
'''Hinweis:''' Sie benötigen keine ''engines''. Das einfache Timer-System reicht aus. Um Prozesse, die in eine bestimmten Vorgabezeit nicht terminieren, auch wirklich abbrechen zu können, benötigen Sie '''Continuations''' (Sprachelement ''call/cc'').
<code id="4f969506c37ed" hidden>
(define end #f)
(call/cc (lambda (cont) (set! end cont)))
(define start-timer #f)
(define stop-timer #f)
(define decrement-timer #f)
(let ([clock 0] [handler #f])
(set! start-timer
(lambda (ticks new-handler)
(set! handler new-handler)
(set! clock ticks)))
(set! stop-timer
(lambda ()
(let ([time-left clock])
(set! clock 0)
time-left)))
(set! decrement-timer
(lambda ()
(when (> clock 0)
(set! clock (- clock 1))
(when (= clock 0) (handler))))))
(define fib
(lambda (n)
(decrement-timer)
(cond
((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1)) (fib (- n 2)))))))
(define cantor-paar
(lambda (x y)
(+ (/ (* (+ x y) (+ x y 1)) 2) y)))
(define wortmenge_Zeichenlaenge
(lambda (n alphabet)
(if (= n 0)
'("")
(apply
append
(map
(lambda (zeichen)
(map
(lambda (wort)(string-append (string zeichen) wort))
(wortmenge_Zeichenlaenge (- n 1) alphabet)))
alphabet)))))
(define wortmenge
(lambda (n alphabet)
(if (= n 0)
(wortmenge_Zeichenlaenge 0 alphabet)
(append
(wortmenge (- n 1) alphabet)
(wortmenge_Zeichenlaenge n alphabet)))))
(define A '(#\a #\b #\c))
(define g
(lambda (i)
(let* ((n (if (< i 2) 1 (ceiling (/ (log i)(log (length A))))))
(wortmenge-n (wortmenge n A)))
(list-ref wortmenge-n i))))
(define f
(lambda (z)
(let* ((x (getXCantorPaar z))
(y (getYCantorPaar z))
(fibwort (g x)))
(start-timer y (lambda () (end "b")))
(when (chi-strich-m fibwort)
fibwort))))
(define chi-strich-m
(lambda (w)
(letrec
((helper
(lambda (i)
(decrement-timer)
(if (= (countB w) (fib i))
#t
(helper (+ i 1))))))
(helper 0))))
(define countB
(lambda (w)
(letrec
((helper
(lambda (chars)
(cond
((null? chars) 0)
((char=? (car chars) #\b)(+ 1 (helper (cdr chars))))
(else
(helper (cdr chars)))))))
(helper (string->list w)))))
(define getXCantorPaar
(lambda (z)
(let* (( w (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2)))
( t (/ (* w (+ w 1)) 2))
( y (- z t)))
(inexact->exact (- w y)))))
(define getYCantorPaar
(lambda (z)
(let* (( w (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2)))
(t (/ (* w (+ w 1)) 2)))
(inexact->exact (- z t)))))
</code>
== Umsetzung ==
=== Schritt 1 ===
Implementieren Sie die im Beweis definierte Aufzählfunktion für $M \subseteq \text{ A*}$ unter Verwendung der Cantorschen Paarungsfunktion.
==== Definition der Cantorschen Paarungsfunktion ====
$$\begin{array}{c|cccccc}
x\backslash y & 0 & 1 & 2 & 3 & 4 & \dots\\\hline
0 & 0 & 2 & 5 & 9 & 14 & \dots \\
1 & 1 & 4 & 8 & 13 & \dots & \\
2 & 3 & 7 & 12 & \dots & & \\
3 & 6 & 11 & \dots & & & \\
4 & 10 & \vdots & \vdots & \vdots & \vdots &
\end{array}$$
<br/>
$x$ bestimmt das $x$-te Element, also $g(x)=w_x$, in der Aufzählung von $A^*$ durch $g$. Und $y$ bestimmt die zur Berechnung von $\chi^'_M(w_x)$ bereitgestellten Zeiteinheiten (Takte, ticks) - entweder für die Berechnung ausreichend oder Abbruch nach Zeit y.
<br/>
$$
z = \pi(x,y) = \frac{(x+y)(x+y+1)}{2} + y
$$
<code id="4f968e5d40c8e">
(define cantor-paar
(lambda (x y)
(+ (/ (* (+ x y) (+ x y 1)) 2) y)))
</code>
<run id="4f96a535bb0f2">(cantor-paar 286 5)</run>
Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist als erstes $w = \left\lfloor \frac{\sqrt{8z+1}-1}{2} \right\rfloor $ zu berechnen. Dann ergeben sich
$t = \frac{w(w+1)}{2}$ und
$y = z -t$ sowie
$x = w - y$
<code id="4f968fc1beadf">
(define getXCantorPaar
(lambda (z)
(let* (( w (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2)))
( t (/ (* w (+ w 1)) 2))
( y (- z t)))
(inexact->exact (- w y)))))
(define getYCantorPaar
(lambda (z)
(let* (( w (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2)))
(t (/ (* w (+ w 1)) 2)))
(inexact->exact (- z t)))))
</code>
<run id="4f96a535bb15c">(getXCantorPaar 42491)</run>
<run id="4f96a535bb1b8">(getYCantorPaar 42491)</run>
==== Aufzählfunktion $f$ für $M \subseteq \text{ A*}$ ====
$$
f(z) = \begin{cases}
g(x); & \text{wenn } \chi^{'}_{M}(g(x))=\text{ wahr innerhalb von Zeit y};\\
b; & \text{wenn Proz. für } \chi^{'}_{M}(g(x)) \text{ innerhalb von y ohne Ergebnis}
\end{cases}
$$
$$b \in M$$
<code id="4f9691582de84">
(define f
(lambda (z)
(let* ((x (getXCantorPaar z))
(y (getYCantorPaar z))
(fibwort (g x)))
(start-timer y (lambda () (end "b")))
(when (chi-strich-m fibwort)
fibwort))))
</code>
<run id="4f96a4e6cf2a1">(f (cantor-paar 286 5))</run>
=== Schritt 2 ===
Wählen Sie im Fallbeispiel A = $\{a,b,c\}, g: \N \mapsto A^*$ und M = $\{w |w \in A^* \text{ und } w \text{ enthält Fibonacci-zahlig viele} "b's"\}$.
====Alphabet A====
<code id="4f96a5ef0964a">
(define A '(#\a #\b #\c))
</code>
====Berechnung einer Fibonacci-Zahl====
<code id="4f96a5ef096b3">
(define fib
(lambda (n)
(decrement-timer)
(cond
((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1)) (fib (- n 2)))))))
</code>
====Wörter der Länge $n$====
Ermittlung der Wörter mit der Länge $n$, aus der Wortmenge $A^*$.
<code id="4f96a5ef09729">
(define wortmenge_Zeichenlaenge
(lambda (n alphabet)
(if (= n 0)
'("")
(apply
append
(map
(lambda (zeichen)
(map
(lambda (wort)(string-append (string zeichen) wort))
(wortmenge_Zeichenlaenge (- n 1) alphabet)))
alphabet)))))
</code>
<run id="4f96ab018d693">(wortmenge_Zeichenlaenge 6 A)</run>
====Wörter bis zur Länge $n$====
Ermittlung der Wörter, aus der Wortmenge $A^*$, bis zur Länge $n$.
<code id="4f96a5ef0979f">
(define wortmenge
(lambda (n alphabet)
(if (= n 0)
(wortmenge_Zeichenlaenge 0 alphabet)
(append
(wortmenge (- n 1) alphabet)
(wortmenge_Zeichenlaenge n alphabet)))))
</code>
<run id="4f96ab018d702">(wortmenge 6 A)</run>
====Aufzählfunktion $g(x)$====
<code id="4f96a5ef0981c">
(define g
(lambda (i)
(let* ((n (if (< i 2) 1 (ceiling (/ (log i)(log (length A))))))
(wortmenge-n (wortmenge n A)))
(list-ref wortmenge-n i))))
</code>
<run id="4f96ab5537bb9">(g 286)</run>
=== Schritt 3 ===
Machen Sie bei der Konstruktion von $\chi^'_M$ nur von der Semi-Entscheidbarkeit der Menge der Fibonacci-Zahlen Gebrauch, obwohl doch deren Entscheidbarkeit durch Beschränkung des Suchraumes gegeben ist.
==== Anzahl von b's====
<code id="4f96a9bb894c4">
(define countB
(lambda (w)
(letrec
((helper
(lambda (chars)
(cond
((null? chars) 0)
((char=? (car chars) #\b)(+ 1 (helper (cdr chars))))
(else
(helper (cdr chars)))))))
(helper (string->list w)))))
</code>
<run id="4f96acabaf944">(countB "caaba")</run>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
====Semi-Entscheidbarkeit====
<code id="4f96a9bb89529">
(define chi-strich-m
(lambda (w)
(letrec
((helper
(lambda (i)
(decrement-timer)
(if (= (countB w) (fib i))
#t
(helper (+ i 1))))))
(helper 0))))
</code>
<run id="4f96acabaf9a2">(chi-strich-m "caaba")</run>
<run id="4f97ae8a0cffe">
(start-timer 40 (lambda () (end "b")))
(chi-strich-m "caabbbba")
</run>
=== Schritt 4 ===
====Einsetzen eines Timer-Systems====
<code id="4f96932f24386">
(define start-timer #f)
(define stop-timer #f)
(define decrement-timer #f)
(let ([clock 0] [handler #f])
(set! start-timer
(lambda (ticks new-handler)
(set! handler new-handler)
(set! clock ticks)))
(set! stop-timer
(lambda ()
(let ([time-left clock])
(set! clock 0)
time-left)))
(set! decrement-timer
(lambda ()
(when (> clock 0)
(set! clock (- clock 1))
(when (= clock 0) (handler))))))
</code>
=== Schritt 5 ===
Um Prozesse, die in eine bestimmten Vorgabezeit nicht terminieren, auch wirklich abbrechen zu können, benötigen Sie '''Continuations''' (Sprachelement ''call/cc'').
====Continuations====
<code id="4f96935662e0e">
(define end #f)
(call/cc (lambda (cont) (set! end cont)))
</code>
<language>Scheme</language>
==== Beispiel Timer-System====
<run id="4f97065b35d6d">
(start-timer 250 (lambda () (end "end time")))
(fib 10)
</run>