BuK-KA-Zeitbeschränkte-Prozesse

Aus ProgrammingWiki

Archivierte Version vom 2012-04-24T12:30:09+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Aufgabenstellung
2 Umsetzung

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

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

Umsetzung

Schritt 1:

Implementieren Sie die im Beweis definierte Aufzählfunktion für M \subseteq \text{ A*} unter Verwendung der Cantorschen Paarungsfunktion.

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};\\ a; & \text{wenn Proz. für } \chi^{'}_{M}(g(x)) \text{ innerhalb von y ohne Ergebnis} \end{cases}

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

(f (cantor-paar 38725 41))

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}$

z = \pi(x,y) = \frac{(x+y)(x+y+1)}{2} + y

(define cantor-paar
  (lambda (x y)
    (+ (/ (* (+ x y) (+ x y 1)) 2) y)))

(cantor-paar 17 5)

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

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

(getXCantorPaar 258)

(getYCantorPaar 258)

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:

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

(define fib
  (lambda (n)  
    (decrement-timer)
    (cond
      ((= n 0) 0)
      ((= n 1) 1)
      (else
       (+ (fib (- n 1)) (fib (- n 2)))))))

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

Schritt 3

(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 chi-strich-m
  (lambda (w)
    (letrec
        ((helper
          (lambda (i)   
            (decrement-timer)
            (if (= (countB w) (fib i))
                #t
                (helper (+ i 1))))))
      (helper 0))))

Schritt 4

Einsetzen eines Timer-Systems.

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

Schritt 5

Um Prozesse, die in eine bestimmten Vorgabezeit nicht terminieren, auch wirklich abbrechen zu können, benötigen Sie Continuations (Sprachelement call/cc).

(define end #f) 
(call/cc (lambda (cont) (set! end cont)))

BuK-KA-Zeitbeschränkte-Prozesse

Inhaltsverzeichnis

Aufgabenstellung

Umsetzung

Schritt 1:

Aufzählfunktion f für M \subseteq \text{ A*}

Definition der Cantorschen Paarungsfunktion

Schritt 2

Schritt 3

Schritt 4

Schritt 5

Suche