¿Qué tarea le dio Dijkstra a los voluntarios, que se mencionó en su artículo "El programador humilde"?

65

En el artículo de Dijkstra "Programador humilde" , menciona que dio a algunos voluntarios un problema para resolver:

“He realizado un pequeño experimento de programación con voluntarios realmente experimentados, pero apareció algo bastante inesperado y bastante inesperado. Ninguno de mis voluntarios encontró la solución obvia y más elegante. Tras un análisis más detallado, esto resultó tener una fuente común: su noción de repetición estaba tan estrechamente relacionada con la idea de una variable controlada asociada que se intensificaría, que fueron bloqueados mentalmente para que no vieran lo obvio. Sus soluciones fueron menos eficientes, innecesariamente difíciles de entender, y les llevó mucho tiempo encontrarlas ”.

¿Cuál fue el problema que Dijkstra le dio a los voluntarios? ¿Cuáles fueron las soluciones?

usuario712092
fuente
3
Apostaría a algo recursivo. EWD654 "En honor de Fibonacci" parece ser un buen candidato
mosquito
Esta pregunta podría estar bien siempre que las personas no la utilicen como una oportunidad para adivinar o especular: puede ser difícil de averiguar, pero tiene una respuesta y las preguntas históricas son sobre el tema aquí.
99
Esa cita vino de EWD340 "Programadores muy humildes". No pude encontrar una descripción exacta de lo que fue el experimento, pero aquí hay un enlace a la transcripción de su discurso completo. cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html
Tyler Ferraro
2
¿Alguien puede encontrar una cita de Dijkstra que sea complementaria sobre cualquier cosa? Mi cita favorita sobre él es "la arrogancia en informática se mide en nano-Dijkstras" - Alan Kay
James Anderson
Debemos tener mucho cuidado cuando damos consejos a las personas más jóvenes: ¡a veces lo siguen! ... heh :-) fuente: en.wikiquote.org/wiki/Edsger_W._Dijkstra
Robert French el

Respuestas:

11

El "problema de los filósofos gastronómicos" fue el problema presentado.

Básicamente hay 5 filósofos que necesitan comer. (imagine un plato de comida interminable frente a cada filósofo), entre cada plato hay un tenedor (5 platos, 5 tenedores, 5 filósofos).

Un filósofo solo puede comer si sostiene el tenedor a la derecha y el tenedor a la izquierda. (solo dos filósofos pueden comer en un momento dado).

Se puede levantar un tenedor en cualquier momento que esté disponible y soltarlo si lo está sosteniendo. Cada tenedor debe recogerse de forma interdependiente. (uno a la vez).

Mientras un filósofo no está comiendo, está pensando (la necesidad de alternar estados es lo que impulsa el problema).

¿Cómo les permite a cada uno comer y alternar el pensamiento (para que los demás puedan comer) sin crear un sistema estancado (donde un filósofo sostiene un tenedor y espera el otro, evitando que otro filósofo coma)?

Esto tiene sus raíces en los sistemas concurrentes y es una pregunta universitaria típica que se presenta cuando se discute la concurrencia.

Creo que se han desarrollado 4 o 5 algoritmos "oficiales" para resolver el problema, pero una búsqueda rápida en Google para "Problema de los filósofos gastronómicos" le dará una gran variedad de resultados.

Si lee la versión original del documento en las notas al pie de la página 866, dice: "Actas del Congreso de la IFIP 1965, 213-217." Soluciones de un problema en el control de programación concurrente ".

El problema en la concurrencia y los recursos compartidos es el "Problema de los filósofos gastronómicos". :-)

Espero que ayude.

Robert French
fuente
66
Dado que esta es principalmente una pregunta histórica, ¿alguna fuente?
Yannis
1
En realidad no, las fuentes que proporciona no parecen hacer referencia al problema de los filósofos de la comida como el que Dijkstra dio a los voluntarios. ¿Me estoy perdiendo de algo? Lo que estoy buscando son fuentes creíbles para apoyar su "El problema de los filósofos de la comida" fue el reclamo presentado , no descripciones del problema en sí (aunque sus enlaces son muy informativos e interesantes).
Yannis
@Robert Gracias por los enlaces. :) (no los elimines, podrían ser útiles para otros) Estoy deseando saber si fue el problema que me dio.
user712092
44
@RobertFrench Lo que estamos buscando es cuál fue el problema específico que Dijkstra menciona en la cita de la pregunta, y las fuentes que lo prueban, no cualquier problema que Dijkstra haya formulado. No hay nada en la cita que incluso sugiera que fue uno de sus propios problemas, podría ser realmente un problema. Por supuesto, los filósofos de Dining es uno de los originales de Dijkstra (con la ayuda de CAR Hoare), nadie está debatiendo eso, pero eso no tiene nada que ver con la pregunta .
yannis
44
Esto esta simplemente mal. "Soluciones de un problema en el control de programación concurrente" es el Problema de los Filósofos de Comedor, y se menciona en el Programador Humilde como uno de los trabajos anteriores de Dijkstra en la cita, pero afirmar que también es el problema en la cita no es verificable.
Yannis