Königsberger Brückenproblem

Letztmalig dran rumgefummelt: 02.05.08 20:44:42

	Das Post'sche Korrespondenzproblem ist ein wichtiges Entscheidbarkeitsproblem. Die Nichtentscheidbarkeit des Post'schen Korrespondenzproblems wurde erstmals 1946 von dem Mathematiker E. L. Post (1897 - 1954) bewiesen. Korrespondenz ist eine eindeutige Zuordnung!!! Voraussetzungen: Gegeben sind: ein Alphabet A und Wörter xi und yi A+ (A+ ist die Menge aller Wörter, die sich mit dem Alphabet A bilden lässt) eine endliche Liste von Paaren (x1, y1), ... (xn, yn) die endliche Liste hat eine Korrespondenz, wenn es eine Indexfolge (x1, y1), ... (xn, yn)
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für das Königsberger-Brückenproblem begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	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
	Es begann eigentlich ganz harmlos im Jahr 1736 mit der Frage Leonhard Eulers (1707 - 1783), ob durch die Stadt Königsberg (heute Kaliningrad) ein Rundgang möglich sei, bei dem man jede der sieben Brücken genau einmal passieren würde (ohne ein Boot zu benutzen). Die sieben Brücken von Königsberg mit einer ungeraden Anzahl von Brücken bei dieser Anordnung von Knoten lässt sich das Problem nicht lösen Diese Animation demonstriert einen erfolglosen Versuch. Aus diesem Problem entwickelte sich einige Zeit später die Graphentheorie, ein Teilgebiet der Mathematik. Auch wenn es zunächst sehr abstrakt wirkt, lassen sich damit viele Probleme lösen. Eine Biografie Eulers finden Sie unter homepages.compuserve.de/thweidenfeller/mathematiker/euler.htm.
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

1. Problembeschreibung

	ztrgilt.
	Blick auf das heutige Kaliningrad und die Insel zwischen den Flussläufen - einige Brücken sind so heute nicht mehr vorhanden

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. Lösungsalgorithmus

	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

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, löst jedoch kein einziges 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.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem der Kaprekar-Algorithmus das Post'schen Korrespondenzproblem das Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im März 2004