Das Erfüllbarkeitsproblem

Letztmalig dran rumgefummelt: 31.12.07 17:07:56

	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 Erfüllbarkeitsproblem 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
	Die Steinchen bekommen die Farben rot, weiß oder blau. Dabei werden die Steinchen immer wieder in gleicher Reihenfolge angeordnet.   Regelmäßige Anordnung der hier 33 Farbenfelder
	Die Anordnung ist immer ein rotes Steinchen, rechts daneben ein weißes und rechts neben einem weißen Steinchen ein blaues   Anfangssituation beim Flaggenproblem
	Nun wird ein Roboter vor die Fächerreihe gestellt und der Roboter soll so programmiert werden, die Steinchen in den einzelnen Fächern so umzuordnen, dass zuerst (ganz links) alle roten, dann alle weißen und dann alle blauen Steinchen (rechts) in den Fächern liegen   Endsituation beim Flaggenproblem
	Nun ist auch logisch woher der Name "Flaggenproblem" rührt, nämlich davon, dass die Farbenfolge der Steinchen im geordneten Zustand (von links gesehen) der niederländischen Nationalflagge entspricht. Man kann aber die Problematik der niederländischen Nationalflagge auf jede andere Flagge, die ebenfalls 3 Farben hat, übertragen.

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

	effiziente Lösung nur als rekursiver Algorithmus
	gegenseitige Rekursion - die Funktionen für größer 100 und kleiner 100 für die Zwischenwerte rufen sich gegenseitig auf
	Das Flaggen-Problem wird in abgewandelter Form auf jedem Rangierbahnhof, in jedem Warenliefersystem, in der Postzustellung usw. praktisch gelöst

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 Domino-Problem das Entscheidbarkeitsproblem 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