Происшествие Авария Пожар ДТП

Сообщи нам
Проблемы Тюмени
Обсуждаем
Мнения тюменцев
Ronaldo72
25.09.2017 в 18:38
Единственный человек, с которым общался последние лет 5, уехал в другую страну работать. Вот прошвырнулся я сегодня по центру, пока солнышко греет, понял,…
30 6333
Rusuranu
13.09.2017 в 12:28
Республики 94. Говорят, будет парковка. Экскаватор уже вплотную подобрался к относительно недавно посаженным деревцам. Когда-то здесь было так Фото…
1 6151
Все мнения тюменцев
Новости от Нашгород.ру
Добавить на Яндекс
27.07.2009 / 19:51
Математики придумали алгоритм честного деления пирога на троих
Ученые из Стэнфордского университета создали алгоритм так называемого «честного деления пирога» на трех человек. Статья исследователей пока ещё не принята к публикации, однако её препринт доступен на сайте arXiv.org.

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

В 1980 году американский математик Уолтер Стромкуист (Walter Stromquist) доказал, что для любого набора критериев, которых придерживаются эти N человек, пирог можно разрезать справедливо ровно за N-1 разрезов. Однако доказательство Стромкуиста не было конструктивным, то есть он не предъявил конкретный алгоритм.

В рамках новой работы математики занимались именно поиском конкретного алгоритма, то есть последовательности действий разрезающего. В полном объеме им решить задачу не удалось, однако они построили алгоритм, который позволяет примерно делить пирог между тремя людьми всего за два разреза. Кроме этого исследователям удалось доказать важное свойство, что задача принадлежит к классу так называемых PPAD-задач.

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

Источник: Лента.ру
Просмотров: 1048 | Версия для печати
Читайте новости по темам: Ученые, Еда
Увидели опечатку или ошибку?
Выделите ее и нажмите
Комментарии 0 Читать на форуме
Чтобы добавить комментарий необходимо зарегистрироваться или войти на сайт.