Какое задание Дейкстра дал волонтерам, о чем упоминалось в его статье «Смиренный программист»?

65

В статье Дейкстры «Смиренный программист» он упоминает, что дал волонтерам задачу, которую нужно решить:

«Я провел небольшой программный эксперимент с действительно опытными волонтерами, но случилось нечто совершенно непреднамеренное и совершенно неожиданное. Никто из моих добровольцев не нашел очевидного и самого элегантного решения. После более тщательного анализа выяснилось, что у них есть общий источник: их представление о повторении было настолько тесно связано с идеей связанной контролируемой переменной, которую нужно усилить, что они были умственно заблокированы от того, чтобы видеть очевидное. Их решения были менее эффективными, излишне трудными для понимания, и им потребовалось очень много времени, чтобы найти их ».

В чем заключалась проблема, которую Дейкстра дала волонтерам? Какие были решения?

user712092
источник
3
Я бы сделал ставку на что-то рекурсивное. EWD654 «В честь Фибоначчи», кажется, хороший кандидат
комнат
Этот вопрос может быть хорошим, если люди не используют его как возможность угадать или предположить: это может быть трудно выяснить, но у него есть ответ, и здесь уместны исторические вопросы.
9
Эта цитата взята из EWD340 "Очень скромные программисты". Я не смог найти точное описание эксперимента, но вот ссылка на стенограмму его полного выступления. cs.utexas.edu/~EWD/transcription/EWD03xx/EWD340.html
Тайлер Ферраро
2
Может кто-нибудь найти цитату Дейкстры, которая о чем-нибудь говорит? Моя любимая цитата о нем: «Высокомерие в информатике измеряется в нано-Дейкстре» - Алан Кей
Джеймс Андерсон
Мы должны быть очень осторожны, когда даем советы молодым людям: иногда они им следуют! ... хе :-) источник: en.wikiquote.org/wiki/Edsger_W._Dijkstra
Роберт Френч,

Ответы:

11

«Проблема столовых философов» была представленной проблемой.

В основном есть 5 философов, которые должны есть. (представьте тарелку бесконечной еды перед каждым философом), между каждой тарелкой есть вилка (5 тарелок, 5 вилок, 5 философов).

Философ может есть, только если он держит вилку справа и вилку слева. (только два философа могут есть в любой момент времени).

Вилка может быть поднята в любое время, когда она доступна, и отложена, если ее удерживают. Каждая вилка должна быть подобрана взаимозависимо. (один за раз).

Пока философ не ест, он думает (проблема состоит в необходимости чередования состояний).

Как вы позволяете каждому из них есть и чередовать мышление (чтобы другие могли есть), не создавая тупиковую систему (где один философ держит одну вилку и ждет другого, не позволяя другому философу есть).

Это имеет свои корни в параллельных системах и является типичным университетским вопросом, обсуждаемым при обсуждении параллелизма.

Я полагаю, что 4 или 5 «официальных» алгоритмов были разработаны для решения проблемы, но быстрый поиск в «Google» для «Обеденной философской проблемы» даст вам множество результатов.

Если вы читаете оригинальную версию статьи в сносках на стр. 866, в ней говорится: «Труды Конгресса IFIP 1965, 213-217.« Решение проблемы в управлении параллельным программированием ».

Проблема параллелизма и общих ресурсов - это «проблема столовых философов». :-)

Надеюсь, это поможет.

Роберт Френч
источник
6
Поскольку это в основном исторический вопрос, какие источники?
Яннис
1
На самом деле нет, источники, которые вы предоставляете, похоже, не ссылаются на проблему философов-столовых, как тот, который Дейкстра дал волонтерам. Я что-то пропустил? То, что я ищу, - это заслуживающие доверия источники, подтверждающие вашу «проблему обедающих философов», которая была заявленной проблемой , а не описания самой проблемы (хотя ваши ссылки очень информативны и интересны).
Яннис
@ Роберт Спасибо за ссылки. :) (не удаляйте их, они могут быть полезны для других) Я с нетерпением жду, если это была проблема, которую он дал.
user712092
4
@RobertFrench То, что мы ищем, это то, что было конкретной проблемой, упомянутой Дейкстрой в цитате в вопросе, и источниками, которые доказывают это, а не просто какой-либо проблемой, сформулированной Дейкстрой. В цитате нет ничего, что бы даже указывало на то, что это была одна из его собственных проблем, это действительно может быть любая проблема. Конечно, философы «Столовая» - один из оригиналов Дейкстры (с некоторой помощью К. А. Хоара), никто не обсуждает это, но это не имеет никакого отношения к вопросу .
Яннис
4
Это просто неправильно. «Решения проблемы в управлении параллельным программированием» - это проблема «Обедающих философов», и она упоминается в Humble Programmer как одна из ранних работ Дейкстры в цитате, но утверждение, что это также проблема в цитате, не поддается проверке.
Яннис