BuK-KA-Zeitbeschränkte-Prozesse

Aus ProgrammingWiki

Archivierte Version vom 2012-04-24T11:46:22+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).

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

Definition der Cantorschen Paarungsfunktion

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

Schritt 4

Einsetzen eines Timer-Systems.

Schritt 5

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

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