Que tarefa Dijkstra deu aos voluntários, mencionado no artigo "O humilde programador"?

65

No artigo de Dijkstra, "Humble Programmer" , ele menciona que deu a alguns voluntários um problema para resolver:

“Realizei um pequeno experimento de programação com voluntários realmente experientes, mas algo inesperado e inesperado apareceu. Nenhum dos meus voluntários encontrou a solução óbvia e mais elegante. Após uma análise mais minuciosa, isso acabou tendo uma fonte comum: a noção de repetição estava tão intimamente ligada à idéia de uma variável controlada associada a ser intensificada, que eles foram mentalmente impedidos de ver o óbvio. Suas soluções eram menos eficientes, desnecessariamente difíceis de entender e levaram muito tempo para encontrá-las. ”

Qual foi o problema que Dijkstra deu aos voluntários? Quais foram as soluções?

algorithms history user712092
fonte
3
Eu apostaria em algo recursivo. EWD654 "Em honra de Fibonacci" parece ser um bom candidato
mosquito
Essa pergunta pode ser boa desde que as pessoas não usem isso como uma oportunidade de adivinhar ou especular: pode ser difícil descobrir, mas ela tem uma resposta e perguntas históricas estão no tópico aqui.
9
Essa citação veio do EWD340 "Very Humble Programmers". Não consegui encontrar uma descrição exata do que foi o experimento, mas aqui está um link para a transcrição de sua palestra completa. cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html
Tyler Ferraro,
2
Alguém pode encontrar uma citação de Dijkstra que seja complementar sobre qualquer coisa? Minha citação favorita sobre ele é "a arrogância na ciência da computação é medida em nano-Dijkstras" - Alan Kay
James Anderson
Devemos ter muito cuidado quando damos conselhos aos mais jovens: às vezes eles o seguem! ... heh :-) fonte: en.wikiquote.org/wiki/Edsger_W._Dijkstra
Robert French

Respostas:

11

O "problema dos filósofos do jantar" foi o problema apresentado.

Basicamente, existem 5 filósofos que precisam comer. (imagine um prato de comida sem fim diante de cada filósofo), entre cada prato há um garfo (5 pratos, 5 garfos, 5 filósofos).

Um filósofo só pode comer se estiver segurando o garfo à direita e o garfo à esquerda. (apenas dois filósofos podem comer a qualquer momento).

Um garfo pode ser retirado a qualquer momento e disponível, se estiver sendo segurado. Cada garfo deve ser recolhido interdependentemente. (um por vez).

Enquanto um filósofo não está comendo, eles estão pensando (a necessidade de estados alternados é o que impulsiona o problema).

Como você permite que cada um coma e alterne o pensamento (para que os outros possam comer) sem criar um sistema de impasse (onde um filósofo está segurando um garfo e esperando pelo outro, impedindo que outro filósofo coma).

Isso tem suas raízes em sistemas concorrentes e é uma pergunta típica da universidade apresentada ao discutir a simultaneidade.

Acredito que 4 ou 5 algoritmos "oficiais" foram desenvolvidos para resolver o problema, mas uma rápida pesquisa no google por "Problema dos filósofos de jantar" fornecerá a você uma variedade de resultados.

Se você ler a versão original do documento nas notas de rodapé na página 866, declara: "Anais do Congresso IFIP 1965, 213-217." Soluções de um problema no controle de programação simultâneo. "

O problema na simultaneidade e nos recursos compartilhados é o "Problema dos filósofos do jantar". :-)

Espero que ajude.

Robert French
fonte
6
Como essa é principalmente uma questão histórica, existem fontes?
yannis
11
Na verdade não, as fontes que você fornece parecem não fazer referência ao problema dos filósofos do jantar como o que Dijkstra deu aos voluntários. Estou esquecendo de algo? O que estou procurando são fontes confiáveis ​​para apoiar seu problema "O problema dos filósofos de jantar" foi a alegação apresentada , não as descrições do problema em si (embora seus links sejam altamente informativos e interessantes).
yannis
@ Robert Obrigado pelos links. :) (não os remova, eles podem ser úteis para outras pessoas) Estou ansioso para saber se foi o problema que ele deu.
user712092
4
@RobertFrench O que estamos procurando é qual foi o problema específico que Dijkstra menciona na citação da pergunta e as fontes que provam isso, não apenas qualquer problema formulado por Dijkstra. Não há nada na citação que sugira que fosse um de seus próprios problemas, poderia ser realmente um problema. É claro que os filósofos do jantar são um dos originais de Dijkstra (com alguma ajuda do CAR Hoare), ninguém está discutindo isso, mas isso não tem nada a ver com a questão .
yannis
4
Isto é simplesmente errado. "Soluções de um problema no controle de programação simultâneo" é o Problema dos Filósofos do Jantar, e é mencionado no Humble Programmer como um dos trabalhos anteriores de Dijkstra na citação, mas alegando que também é o problema na citação não é verificável.
yannis