| SUDOKU |
|
|
Letztmalig dran rumgefummelt: 11.02.14 16:28:28 |
 |
||||||||
 |
1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Hexadzimal-Sudokus 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen |
|||||||
|
|
|||||||
 |
Quellen:
|
|||||||
|
der "Worst-Case" liegt hier sicher nicht in der Komplexität zum Aufwand für den Lösungsalgorithmus - er ist hier allein in der Mächtigkeit des Problems zu suchen | |||||||
|
die Anzahl der Zwischenwerte, die zur Lösung für ein Argument benötigt werden ist schlichtweg enorm und steigt mit n-polinomial |
|||||||
|
Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer |
| 1. Problembeschreibung |
|
|
 |
|
Das Post'sche Korrespondenzproblem ist definiert: Gibt es zu einer gegebenen endlichen Relation R A* A* ein Paar (x, y) A+ mit x = y? x heißt dann Korrespondenz. Anders formuliert wird versucht, aus der Menge der möglichen Wortpaare von x und y ein gleiches Wort zu bilden. Dabei muss aber aus jeder Menge das Wort mit dem gleichen Index zugeordnet werden. Bei Gleichheit ist Korrespondenz gegeben. |
|
|
| 2. Hintergründe, Zusammenhänge - Einordnung in Klassen |
|
|
|
|
|
Der Lösungsalgorithmus für die Türme von Hanoi |
|
effiziente Lösung nur als rekursiver Algorithmus |
| 3. Hexadzimal-Sudokus |
|
|
|
|
|
Wenn es mindestens einen Lösungsansatz gibt, dann versuche, aus den gegebenen Wortpaaren identische Sätze auf beiden Seiten der Gleichung zu bilden. Wiederhole dies solange, bis keine weitere Möglichkeit mehr existiert. | |||||||||||||||||||||
|
|
| 4. Programmvorschläge |
|
|
|
|
|
Das erste und vorläufig einzige Beispiel stellt ein PASCAL-Programm vor, welches die Unentscheidbarkeit immerhin bis 64 KByte Zeichen hinauszögert, Lösungen im oben genanten Sinne kann es für nicht unentscheidbare Kombinationen keine geben - auch der größte Computerspeicher ist endlich in seinem Speichervolumen :-( |
|
Dokumentation zum Programm |
| 5. Zusammenfassung |
|
|
|
|
|
|
|
der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig - er ist n-polinomial |
|
es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen |
|
| 6. Weiterführende Literatur |
|
|
|
|
|
|
|
der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig |
|
es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen |
|
| 7. Links zum Thema |
|
|
|
|
|
Viele gibt es - die meisten sind JAVA-basierte Spiele, um den erkannten Lösungsalgorithmus nach zu vollziehen. Wie gesagt, wenn Du vor hast, das Spiel noch am laufenden Tag zu beenden, verwende keine Scheibenzahl größer 20 - das ist dann schon nicht mehr zu schaffen. |
|
http://www.blinde-kuh.de/spiele/hanoi/ |
|
http://www.cut-the-knot.org/recurrence/hanoi.shtml |
| 8. Verwandte Themen |
|
|
|
|
|
Das Vorangestellte hilft wirtschaften für genau dieses Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft. | |||||||||||||||||||||
|
|
|||||||||||||||||||||
|
|
|||||||||||||||||||||
|
|
|||||||||||||||||||||
|
 zur Hauptseite |
© Samuel-von-Pufendorf-Gymnasium Flöha | © Frank Rost im November 2007 |
|
... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-) „Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“ Diddi Hallervorden, dt. Komiker und Kabarettist |
|
Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-) |
