Quelle tâche Dijkstra a-t-il confiée à des volontaires, évoquée dans son article «The Humble Programmer»?

65

Dans son article "Humble Programmer" , Dijkstra mentionne qu'il a posé un problème à certains volontaires:

«J'ai mené une petite expérience de programmation avec des volontaires très expérimentés, mais quelque chose d'assez inattendu et d'inattendu s'est produit. Aucun de mes volontaires n'a trouvé la solution la plus évidente et la plus élégante. Après une analyse plus approfondie, il s’est avéré que leur origine était commune: leur notion de répétition était si étroitement liée à l’idée d’une variable contrôlée associée à augmenter, qu’ils étaient mentalement empêchés de voir ce qui était évident. Leurs solutions étaient moins efficaces et inutilement difficiles à comprendre, et il leur a fallu très longtemps pour les trouver. ”

Quel était le problème que Dijkstra avait posé aux volontaires? Quelles étaient les solutions?

algorithms history utilisateur712092
la source
3
Je parierais sur quelque chose de récursif. EWD654 "En l'honneur de Fibonacci" semble être un bon candidat
gnat
Cette question peut convenir tant que les gens ne l'utilisent pas comme une opportunité de deviner ou de spéculer: il peut être difficile à déterminer, mais elle a une réponse et des questions historiques sont à l'ordre du jour.
9
Cette citation est venue de EWD340 "Très humbles programmeurs". Je n'ai pas pu trouver une description exacte de l'expérience, mais voici un lien vers la transcription de son exposé complet. cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html
Tyler Ferraro
2
Quelqu'un peut-il trouver une citation de Dijkstra qui soit complémentaire? Ma citation préférée à son sujet est "L'arrogance en informatique se mesure en nano-Dijkstras" - Alan Kay
James Anderson
Nous devons faire très attention lorsque nous donnons des conseils à des jeunes: parfois, ils le suivent! ... heh :-) source: en.wikiquote.org/wiki/Edsger_W._Dijkstra
Robert Français

Réponses:

11

Le "problème des philosophes du restaurant" était le problème présenté.

Fondamentalement, il y a 5 philosophes qui ont besoin de manger. (imaginez une assiette de nourriture sans fin devant chaque philosophe), entre chaque assiette se trouve une fourchette (5 assiettes, 5 fourchettes, 5 philosophes).

Un philosophe ne peut manger que s’il tient la fourchette à droite et la fourche à gauche. (Seuls deux philosophes peuvent manger à un moment donné).

Une fourchette peut être ramassée à tout moment et disponible si elle est tenue. Chaque fourche doit être ramassée de manière interdépendante. (un à la fois).

Alors qu'un philosophe ne mange pas, il réfléchit (le besoin d'alterner les états est le moteur du problème).

Comment permettez-vous à chacun de manger et d'alterner sa pensée (pour que les autres puissent manger) sans créer un système bloqué (où un philosophe tient une fourchette et attend l'autre, empêchant un autre philosophe de manger).

Ceci a ses racines dans les systèmes concurrents et est une question universitaire typique présentée lors de la discussion sur la simultanéité.

Je crois que 4 ou 5 algorithmes "officiels" ont été développés pour résoudre le problème, mais une recherche rapide sur Google pour "Problème des philosophes du restaurant" vous permettra d'obtenir une multitude de résultats.

Si vous lisez la version originale du document dans les notes de bas de page de la page 866, elle déclare: "Actes du congrès de l'IFIP, 1965, 213-217." Solutions d'un problème dans le contrôle de la programmation simultanée. "

Le problème de la concurrence et des ressources partagées est le "problème des philosophes de salle à manger". :-)

J'espère que ça t'as aidé.

Robert French
la source
6
Puisqu'il s'agit principalement d'une question historique, des sources?
Yannis
1
En fait non, les sources que vous fournissez ne semblent pas faire référence au problème des philosophes de la salle à manger comme celui que Dijkstra a donné aux volontaires. Est-ce que je manque quelque chose? Ce que je recherche, ce sont des sources crédibles pour soutenir votre problème. Le "problème des philosophes du restaurant" était la revendication du problème présenté , et non une description du problème lui-même (bien que vos liens soient très informatifs et intéressants).
Yannis
@Robert Merci pour les liens. :) (ne les enlevez pas, ils pourraient être utiles aux autres) Je suis impatient de savoir si c'était le problème qu'il a donné.
user712092
4
@RobertFrench Ce que nous recherchons, c'est quel était le problème spécifique mentionné par Dijkstra dans la citation de la question, ainsi que des sources qui le prouvent, pas n'importe quel problème formulé par Dijkstra. Rien dans la citation ne suggère même que ce soit l'un de ses propres problèmes, ce pourrait être n'importe quel problème. Bien entendu, les philosophes de Dining sont l'un des originaux de Dijkstra (avec l'aide de CAR Hoare), personne ne discute de cela, mais cela n'a rien à voir avec la question .
Yannis
4
Ceci est tout simplement faux. "Solutions d'un problème dans le contrôle de la programmation concurrente" est le problème de Dining Philosophers et il est référencé dans Humble Programmer comme l'un des travaux antérieurs de Dijkstra dans la citation, mais affirmant que c'est également le problème dans la citation qui est invérifiable.
Yannis