Das Hamiltonproblem history menue Letztmalig dran rumgefummelt: 09.12.07 15:06:12

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ösungsverfahren

Logo für das Hamiltonproblem

Informatik-Profi-Wissen

Quellen:


1. Problembeschreibung history menue scroll up

 
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 history menue scroll up

 
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 history menue scroll up
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):
Nun ist dieser Quelltext in PASCAL schlecht anschaulich, deswegen werde ich den gesuchten Algorithmus graphisch darstellen. Dazu muss aber folgendes klar sein:
  • die Fächerreihe wird von rechts nach links bearbeitet:
  • es wird immer nur die Farbe des Steinchens bestimmt, auf welches Marke w zeigt
  • zeigt Marke w auf ein rotes Steinchen, dann wird das Steinchen bei Marke w mit dem Steinchen bei Marke r getauscht; als zweites wird Marke r eine Stelle nach rechts gerückt
  • zeigt Marke w auf ein weißes Steinchen, dann wird nur Marke w eine Stelle nach links gerückt
  • zeigt Marke w auf ein blaues Steinchen, dann wird das Steinchen bei Marke w mit dem Steinchen bei Marke b getauscht; als zweites werden Marke w und Marke b eine Stelle nach links gerückt

 


4. Programmvorschläge history menue scroll up

 
 
 
 


5. Zusammenfassung history menue scroll up

 
 
 
 
 
 


6. Weiterführende Literatur history menue scroll up

 
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 history menue scroll up

 
 
 
 


8. Verwandte Themen history menue scroll up

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 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 April 2003

... 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 ;-)