Das Philosophenproblem - Dining philosophers problem

Letztmalig dran rumgefummelt: 31.08.26 15:15:34

	Beim Philosophenproblem (englisch dining philosophers problem) handelt es sich um ein Fallbeispiel aus dem Bereich der theoretischen Informatik. Damit soll das Problem der Nebenläufigkeit und die Gefahr der Verklemmung von Prozessen veranschaulicht werden. Das Problem wurde von Edsger W. Dijkstra formuliert. Fünf Philosophen, nummeriert von eins bis fünf, leben in einem Haus, in dem der Tisch für sie gedeckt ist, wobei jeder Philosoph seinen eigenen Platz am Tisch hat. Ihr einziges Problem – neben dem der Philosophie – ist, dass es sich bei dem servierten Gericht um eine sehr schwierige Sorte Spaghetti handelt, die mit zwei Gabeln gegessen werden muss. Zwischen den Tellern befindet sich jeweils eine Gabel, sodass dies für einen einzelnen Philosophen kein Problem darstellt. Allerdings können zwei Nachbarn nicht gleichzeitig essen. Die Philosophen sitzen am Tisch und denken über philosophische Probleme nach. Wenn einer hungrig wird, greift er zuerst die Gabel links von seinem Teller, dann die auf der rechten Seite und beginnt zu essen. Wenn er satt ist, legt er die Gabeln wieder zurück und beginnt wieder zu denken. Sollte eine Gabel nicht an ihrem Platz liegen, wenn der Philosoph sie aufnehmen möchte, so wartet er, bis die Gabel wieder verfügbar ist. Solange nur einzelne Philosophen hungrig sind, funktioniert dieses Verfahren. Es kann aber passieren, dass sich alle fünf Philosophen gleichzeitig entschließen, zu essen. Sie ergreifen also alle gleichzeitig ihre linke Gabel und nehmen damit dem jeweils links von ihnen sitzenden Kollegen dessen rechte Gabel weg. Nun warten alle fünf darauf, dass die rechte Gabel wieder auftaucht. Das passiert aber nicht, da keiner der fünf seine linke Gabel zurücklegt. Die Philosophen verhungern. Bei der Ressourcenhierarchie-Lösung werden die Gabeln von eins bis fünf durchnummeriert. Jeder Philosoph muss immer zuerst versuchen, die Gabel mit der niedrigeren Nummer aufzunehmen, und nur wenn das erfolgreich war, versucht er, die Gabel mit der höheren Nummer aufzunehmen. Wenn nun alle Philosophen gleichzeitig essen möchten, können nicht alle gleichzeitig die Gabel mit der niedrigeren Nummer aufnehmen. Entweder nimmt der erste Philosoph die Gabel mit der Nummer eins (die zu seiner linken), oder der letzte Philosoph nimmt diese Gabel (die zu seiner rechten). Nimmt der erste Philosoph diese Gabel, so erhält er, der zweite und dritte Philosoph eine Gabel und warten auf die mit der höheren Nummer, der vierte Philosoph erhält zwei Gabeln und isst, und der letzte Philosoph erhält keine Gabel und wartet auf die mit der niedrigeren Nummer. Nimmt der letzte Philosoph diese Gabel, so erhält der erste Philosoph keine Gabel und wartet auf die mit der niedrigeren Nummer, der zweite und dritte erhalten eine Gabel und warten auf die mit der höheren Nummer, und der vorletzte und letzte Philosoph streiten sich um die Gabel mit der Nummer fünf, wer zuerst kommt, isst mit zwei Gabeln, der andere hat eine und wartet auf die Gabel mit der höheren Nummer.
	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 Philosophenproblem begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen

1. Problembeschreibung

	Das eigentliche Problem ist nicht das Feststellen der Kaprekartiefe - weder ist der Algorithmus komplex, noch ist das Problem mächtig. Wenn man das mit dem Taschenrechner überprüft, dauert's vielleicht etwas lange, aber lösbar isses innerhalb 'ner viertel Sunde für praktisch jede Zahl der Teilnehmermenge (man könnte auch Wertebereich sagen, aber ich hasse mathematische Begriffe)! Der Kern liegt eigentlich eher in der Ermittlung einer Formel und/oder eines Algorithmus, welcher(s) beschreibt, in welcher Folge und Abstand welche Kaprekartiefe gilt.
	die Kaprekartiefe liegt im Bereich von 0 bis 7 - dabei ist sie nur bei der Zahl 6174 selbst gleich 0, sonst mindestens 1
	nimm eine beliebige vierstellige Zahl, deren einzelne Stellen nicht alle gleich sein dürfen (1111, 2222, ... , 9999 entfallen also)
	nicht vierstellige Zahlen werden durch Auffüllen mit Vornullen vierstellig gemacht (aus 24 wird also 0024)
	bilde die die größtmögliche mit den vier Ziffern darstellbare Zahl (aus 0024 wird dann 4200)
	bilde die die kleinstmögliche mit den vier Ziffern darstellbare Zahl (0024 bleibt bei 0024)
	ermittle die Differenz zischen größtmöglicher und kleinstmöglicher Zahl
	wiederhole diese Schritte - es ergibt sich nach maximal sieben Wiederholungen 6174 - die Kaprekar-Zahl
	... und weil das ja klappen muss, probieren wir das gleich mal für die 24 ;-)
	ab der Zahl gibt es keine neue Lösung mehr - das ist ja das Phantastische

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

	Unter Annahme der Tatsache, dass wir nicht die Kaprekartiefe, sondern die Regelmäßigkeit der Wiederkehr der einzelnen Werte selbiger suchen, fällt die Aufgabe heute typischerweise in den Bereich der nicht entscheidbaren Probleme. Und diese Beschreibung selbst zu finden, dürfte dann schon in die Klasse der komplexen Probleme fallen.

3. Lösungsalgorithmus

	Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt).

4. Programmvorschläge

	Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen.

5. Zusammenfassung

6. Weiterführende Literatur

7. Links zum Thema

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

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 der Kaprekar-Algorithmus das PASCAL'sche Dreiecksproblem 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 2005