Welche Aufgabe hat Dijkstra Freiwilligen gegeben, was in seiner Arbeit „The Humble Programmer“ erwähnt wurde?

65

In Dijkstras Artikel "Humble Programmer" erwähnt er, dass er einigen Freiwilligen ein Problem zur Lösung gab:

„Ich habe ein kleines Programmier-Experiment mit wirklich erfahrenen Freiwilligen durchgeführt, aber es ist etwas völlig Unbeabsichtigtes und Unerwartetes aufgetaucht. Keiner meiner Freiwilligen fand die offensichtliche und eleganteste Lösung. Bei näherer Betrachtung stellte sich heraus, dass dies eine gemeinsame Quelle hatte: Ihr Begriff der Wiederholung war so eng mit der Idee einer zu verstärkenden Regelgröße verbunden, dass sie mental daran gehindert wurden, das Offensichtliche zu sehen. Ihre Lösungen waren weniger effizient, unnötig schwer zu verstehen und es dauerte sehr lange, bis sie gefunden wurden. “

Was war das Problem, das Dijkstra den Freiwilligen stellte? Was waren die Lösungen?

algorithms history user712092
quelle
3
Ich würde auf etwas Rekursives wetten. EWD654 „Zu Ehren von Fibonacci“ scheint ein guter Kandidat zu sein
gnat
Diese Frage könnte in Ordnung sein, solange die Leute dies nicht als Gelegenheit zum Erraten oder Spekulieren nutzen: Es mag schwierig sein, sie herauszufinden, aber sie hat eine Antwort und historische Fragen sind hier zum Thema.
9
Dieses Zitat stammt von EWD340 "Very Humble Programmers". Ich konnte keine genaue Beschreibung des Experiments finden, aber hier ist ein Link zum Protokoll seines ganzen Vortrags. cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html
Tyler Ferraro
2
Kann jemand ein Dijkstra-Zitat finden, das für alles kostenlos ist? Mein Lieblingszitat über ihn ist "Arroganz in der Informatik wird in Nano-Dijkstras gemessen" - Alan Kay
James Anderson
Wir müssen sehr vorsichtig sein, wenn wir jüngeren Menschen einen Rat geben: Manchmal folgen sie ihm! ... heh :-) Quelle: de.wikiquote.org/wiki/Edsger_W._Dijkstra
Robert French

Antworten:

11

Das "Dining Philosophen Problem" war das präsentierte Problem.

Grundsätzlich gibt es 5 Philosophen, die essen müssen. (Stellen Sie sich einen Teller mit endlosem Essen vor jedem Philosophen vor), zwischen jedem Teller befindet sich eine Gabel (5 Teller, 5 Gabeln, 5 Philosophen).

Ein Philosoph kann nur essen, wenn er die Gabel rechts und die Gabel links hält. (Nur zwei Philosophen können zu einem bestimmten Zeitpunkt essen).

Eine Gabel kann jederzeit aufgenommen und abgelegt werden, wenn sie festgehalten wird. Jede Gabel muss voneinander abhängig aufgenommen werden. (eins nach dem anderen).

Während ein Philosoph nicht isst, denkt er nach (die Notwendigkeit, Zustände zu wechseln, ist der Grund für das Problem).

Wie lässt man zu, dass jeder von ihnen isst und denkt (damit die anderen essen können), ohne ein festgefahrenes System zu schaffen (wobei ein Philosoph eine Gabel in der Hand hält und auf den anderen wartet und einen anderen Philosophen am Essen hindert)?

Dies hat seine Wurzeln in gleichzeitigen Systemen und ist eine typische universitäre Frage, die bei der Diskussion der Nebenläufigkeit gestellt wird.

Ich glaube, dass 4 oder 5 "offizielle" Algorithmen entwickelt wurden, um das Problem zu lösen, aber eine schnelle Suche auf Google nach "Dining Philosophen Problem" wird Ihnen eine Vielzahl von Ergebnissen bringen.

Wenn Sie die Originalversion des Papiers in den Fußnoten auf Seite 866 lesen , heißt es: "Proceedings of the IFIP Congress 1965, 213-217."

Das Problem bei Parallelität und gemeinsam genutzten Ressourcen ist das "Dining Philosophers Problem". :-)

Ich hoffe, das hilft.

Robert French
quelle
6
Da dies hauptsächlich eine historische Frage ist, gibt es Quellen?
Yannis
1
Nein, die Quellen, die Sie zur Verfügung stellen, scheinen sich nicht auf das Problem der Essensphilosophen zu beziehen, wie es Dijkstra den Freiwilligen gegeben hat. Vermisse ich etwas? Was ich suche, sind glaubwürdige Quellen, um Ihr Problem zu unterstützen. Das "Problem der Essensphilosophen" war die Behauptung des Problems , nicht die Beschreibung des Problems selbst (obwohl Ihre Links sehr informativ und interessant sind).
Yannis
@ Robert Danke für die Links. :) (Entferne sie nicht, sie könnten für andere nützlich sein) Ich freue mich darauf, ob es das Problem war, das er gab.
User712092
4
@RobertFrench Was wir suchen ist, was war das spezifische Problem, das Dijkstra in dem Zitat in der Frage erwähnt, und Quellen, die es beweisen, nicht irgendein Problem, das Dijkstra formuliert hat. Das Zitat enthält nichts, was darauf hindeutet, dass es eines seiner eigenen Probleme war. Es könnte wirklich jedes Problem sein. Natürlich ist der Essensphilosoph eines von Dijkstras Originalen (mit etwas Hilfe von CAR Hoare), niemand diskutiert das, aber das hat nichts mit der Frage zu tun .
Yannis
4
Das ist einfach falsch. "Lösungen für ein Problem bei der gleichzeitigen Programmsteuerung" ist das Problem der Dining Philosophen, auf das im Humble Programmer als eines der früheren Werke von Dijkstra verwiesen wird. Die Behauptung, dass es sich auch um das Problem im Zitat handelt, ist jedoch nicht überprüfbar.
Yannis