Das Dominoproblem

Letztmalig dran rumgefummelt: 04.01.08 08:50:09

	Das Flaggenproblem ist eine aus der Informatik stammende Problemstellung, die der niederländische Wissenschaftler E. W. Dijkstra entwickelte. Es ist auch unter dem Namen "3 - Farben - Problem" bekannt. Ursprünglich formulierte Dijkstra das Flaggenproblem folgendermaßen: "Ein Roboter erhält die Aufgabe, eine Anzahl von gefärbten Kieselsteinen, die in einer Reihe von Eimern liegen, zu sortieren. Die Eimer stehen vor dem Roboter und jeder von den Eimern enthält genau einen Kieselstein, der entweder rot, weiß oder blau ist. Der Roboter besitzt zwei Arme, die an den Enden jeweils ein Auge haben. Mit diesen Augen kann der Roboter die Farbe des Kieselsteines bestimmen, mit den Armen kann er die Inhalte zweier Eimer vertauschen."
	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ösunsverfahren Logo für das Dominoproblem 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 ???
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

1. Problembeschreibung

	Nun, diese recht praxisnahe Problemstellung läst sich folgendermaßen kurz umschreiben:  Gegeben ist eine Folge von n Fächern, jedes Fach enthält ein Steinchen. Folge von n Fächern

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	effiziente Lösung nur als rekursiver Algorithmus

3. Lösungsalgorithmus

Dies war die zweite Aufgabe des Flaggenproblems, nämlich nicht nur das Umsortieren der Steinchen, sondern auch das Umsortieren so effizient wie möglich zu machen. E. W. Dijkstra, der Entwickler des Flaggenproblems, ist dabei folgendermaßen vorgegangen. Er schrieb ein Programm in PASCAL in dem der gesuchte Algorithmus als Prozedur dargestellt wird. Hier eine vereinfachte Version seines entworfenen Algorithmus in PASCAL (blau sind die Erklärungen):

4. Programmvorschläge

5. Zusammenfassung

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

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 das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem 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 Mai 2007