BuK-Kreativaufgabe05 G1
Aus ProgrammingWiki
Inhaltsverzeichnis |
Das POSTsche Korrespondenzproblem
Problembeschreibung
Das Postsche Korrespondenzproblem (nach Emil Leon Post, abgekürzt auch PKP oder englisch PCP) ist ein Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik. Es wird häufig verwendet, um mittels Reduktion die Unentscheidbarkeit anderer Probleme zu zeigen.
Gegeben ist eine endliche Folge P von Paaren von nicht-leeren Wörtern
über einem endlichen Alphabet. Man nennt P auch einen Problemfall oder eine Instanz.
Eine nicht-leere Folge von Indices aus
heißt eine Lösung zum Problemfall P, falls die Konkatenation (Verkettung) der Wörte
gleich der Konkatenation der Wörter
ist.
Das Korrespondenzproblem ist dann die Aufgabe, zu einem beliebigen Problemfall anzugeben, ob er eine Lösung besitzt oder nicht. Das Korrespondenzproblem ist unentscheidbar, das heißt, es gibt keinen Algorithmus, der zu einem beliebigen Problemfall die richtige Antwort gibt.
(Quelle: Wikipedia)
Aufgabenstellung
Entwickeln Sie ein Scheme-Programm, das eine zugehörige Indexfolge mit den im Problem gegebenen Eigenschaften findet, falls eine solche Indexfolge existiert.
Testen Sie die unter anderem mit: .
Lösung: Die gesuchte Indexliste enthält 66 Elemente.
Lösung
Zur Vereinfachung der Lösung, ist es zunächst sinnvoll, einige Hilfsprozeduren zu implementieren.
Zunächst benötigen wir eine Prozedur, die die Paarliste sowie die Indexliste entgegennimmt und die Verkettung aller bzw. aller
zurückgibt.
Diese Funktion nimmt dafür zusätzlich noch einen Parameter entgegen. Erwartet wird dabei entweder car, um auf
zuzugreifen oder cdr, um auf
zuzugreifen.
Ein Beispielaufruf sieht hierbei wie folgt aus:
Desweiteren benötigen wir eine Funktion, die uns die nächste Indexliste, zu einer gegebenen Indexliste gibt. Dazu muss der Funktion natürlich noch der maximale Index übergeben werden. Diese Funktion benötigt zudem noch 2 weitere Hilfsfunktionen. Zum Einen eine Funktion, die überprüft ob eine gegebene Indexliste 'voll' ist, das heißt, ob alle Elemente, den höchstmöglichen Wert haben. Zum Anderen eine Funktion die eine neue Liste mit der vorgegebenen Anzahl an Elementen erzeugt. In unserem Fall sollen diese mit 0 vorbelegt werden.
Zum anzeigen der ersten Indexlisten (hier für Listen mit einem maximalen Index von 2) verwenden wir Streams:
Nun ist es kein Problem mehr, eine Funktion anzugeben, die, in diesem Fall sogar eine der kürzesten Indexlisten, ab einer bestimmten 'Start-Indexliste' zurückgibt.
Als Beispiel sei hier ein Aufruf mit einer weniger komplexen Lösung genannt:
Zum Beweis der Lösung, kann man sich auch nochmal die Ausgabe von create-string ansehen. (Probieren Sie den Aufruf auch mit cdr)
Da die Lösung für die oben genannte Paarliste, mit einer 66-Elemente großen Indexliste sehr komplex ist und somit die Berechnung enorm viel Zeit in Anspruch nehmen würde. Haben wir uns dazu entschieden, eine Indexliste vorzugeben, die nicht weit von der eigentlichen Lösung entfernt ist (tatsächlich muss nur ein Index geändert werden). Die Ausführungsdauer des folgenden Aufrufs, wird somit auf ein annehmbares Maß reduziert.
Zum Vergleich können nun noch die beiden Wörter manuell verglichen werden, indem man den folgenden Aufruf wieder zunächst mit car und daraufhin mit cdr ausführt.
