BuK/IIm10/BuK-Kreativaufgabe05 G2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<language>Scheme</language>
= POSTsches Korrespondenzproblem =

== Aufgabe ==
Entwickeln Sie ein Scheme-Programm, das eine zugehörige Indexfolge mit den im Problem gegebenen Eigenschaften findet, falls eine solche Indexfolge existiert.

==Lösung ==

Das POSTsche Korrespondenzproblem lautet:
 
Gegeben ist eine endliche Liste von Paaren <math>(({x}_{1},{y}_{1}), ({x}_{2},{y}_{2}), ..., ({x}_{k},{y}_{k}))</math> mit <math>{x}_{i},{y}_{i} \in {A}^{*}. </math> A ist ein beliebiges Alphabet.

Gesucht ist eine (endliche) Indexliste <math>({i}_{1}, {i}_{2}, ..., {i}_{n})</math>, mit <math>{i}_{j} \in I = \{1, 2, ..., k\}</math> und <math>n\geq 1</math>, sodass <math>{x}_{{i}_{1}} \circ {x}_{{i}_{2}} \circ ... \circ {x}_{{i}_{n}} = {y}_{{i}_{1}} \circ {y}_{{i}_{2}} \circ ... \circ {y}_{{i}_{n}}. \circ</math> steht für die
bekannte Verkettungsoperation in <math>{A}^{*}</math>.

Für einfache Beispiele kann man Lösungen durch probieren herstellen.  Aber für große Indexlistes muss man systematisch suchen. Auf dieser Seite soll die Lösung des Problems mittels Breitensuche dargestellt werden. 

Die Tiefensuche eignet sich nicht, da in diesem Fall die Indexliste nur aus unendlich vielen Einsen bestehen würde: <math>(1,1,1,1,...)</math>. Mit der Breitensuche hingegen, werden alle Indexlisten einer Größe gebildet und geprüft, d.h. alle mit Länge 3, dann mit Läünge 4, usw. .

Dazu werden in jedem Iterationsschritt alle Folgeglieder gebildet und an eine "TODO-Liste" angehängt. Diese Liste enthält die gesuchten Indexlisten. Von der "TODO-Liste" wird das erste Element entnommen und auf die Richtigkeit geprüft. Ist die Indexliste korrekt, dann ist die Suche beendet. Andernfalls muss das nächste Element hinzugezogen werden.  

Wenn allerdings keine Lösung existiert, dann terminiert der Algorithmus nicht. Somit ist das POSTsche Korrespondenzproblem nicht entscheidbar. Es ist semi-entscheidbar.

Für 
<code id="4db9d938e73f7" hidden>

(define newlength 0)
;help procedures
(define list-correct?
  (lambda (liste res)
;    (display res)
;    (newline)
;    (if (not (= (length res) newlength)) 
;        (and 
;           (set! newlength (length res)) 
;           (display  (length res))
;           (newline)
;           )
;        #f)
    
    (if (= 0 (length res))
     #f
     (equal? (expand-listA liste res "")(expand-listB liste res ""))
    )
    ))
  
(define expand-listA
  (lambda (liste res in)     
    (if (not (= 0 (length  res)))
        (and 
          (set! in (string-append in (car (list-ref liste ( - (car res) 1)))))
          (expand-listA liste (cdr res) in))
        in 
    )))

(define expand-listB
  (lambda (liste res in)     
    (if (not (= 0 (length  res)))
        (and 
          (set! in (string-append in (cdr (list-ref liste (- (car res) 1)))))
          (expand-listB liste (cdr res) in))
        in
    )))
</code>

<code id="4db9d938e7469">

(define pcp
  (lambda (liste2 res todo-list)
    (define liste liste2)
    
    (if (not (= 0 (length todo-list))) 
        (set! todo-list (cdr todo-list))
        #f)    
   
    (if (list-correct? liste res) 
        res
        ;expand I-list 
        (and  
        (do ((i 0 (+ i 1))) ((> i (- (length liste) 1)))
           (set! todo-list 
                 (append 
                     todo-list
                    (list (append res (list ( + i 1))))
                 )
           ))
         (pcp liste (list-ref todo-list 0) todo-list)
        )) 
    
    ))
</code>
<run id="4db9d938e7505">
(equal? 
   (pcp  '(("1" . "101")("10" . "00")("011" . "11")) '() '())
   '(1 3 2 3))
</run>
<run id="4db9d938e758f">
(equal? 
   (pcp  '(("01" . "0")("110010" . "0")("1" . "1111")("11" . "01")) '() '())
   '(1 3 2 4 4 3))
</run>
<run>
;zu lange Ausführung! / TODO.
;(equal? 
;    (pcp '(("001" . "0")("01" . "011")("01" . "101")("10" . "001")) '() '()) 
;    '(2,4,3,4,4,2,1,2,4,3,4,3,4,4,3,4,4,2,1,4,4,2,1,3,4,1,1,3,4,4,4,2,1,
;       2,1,1,1,3,4,3,4,1,2,1,4,4,2,1,4,1,1,3,4,1,1,3,1,1,3,1,2,1,4,1,1,3))
</run>