FestivalNauki.ru
En Ru
cентябрь-ноябрь 2020
176 городов
September – November 2020
312 cities
09-11 октября 2020
МГУ | Экспоцентр | 90+ площадок
14–16 октября 2016
Центральная региональная площадка
28–30 октября 2016
ИРНИТУ, Сибэскпоцентр
14–15 октября 2016
Центральная региональная площадка
23 сентября - 8 октября 2017
«ДонЭкспоцентр», ДГТУ
ноябрь-декабрь 2018
МВДЦ «Сибирь»,
Вузы и научные площадки города
6-8 октября 2017
Самарский университет
27-29 октября
Кампус ДВФУ, ВГУЭС
30 сентября - 1 октября
Ледовый каток «Родные города»
21-22 сентября 2018 года
ВКК "Белэкспоцентр"
9-10 ноября 2018 года
Мурманский областной Дворец Культуры
21-22 сентября 2019 года
22-23 октября 2019 года
29-30 ноября 2019 года
7-8 сентября 2019 года
27-29 сентября 2019 года
4-5 октября 2019 года
10-12 октября 2019 года

Задача о марьяже

Если тебе уже чуть-чуть не за двадцать или чуть-чуть не за тридцать, то выйти замуж в Южной Корее даже с хорошим приданым - задача явно не из разряда простых. Об этом свидетельствует случай с 49-летней одинокой бизнесвуман, которой не смогла оказать содействие в сватовстве даже известная в стране брачная контора "Сонъу". Не помогло даже то, что невеста обладает приданным, превышающим 16 млн долларов. Камнем преткновения стало условие клиентки, чтобы будущий муж был на десять лет моложе. В огромном списке потенциальных женихов не оказалось никого, кто бы согласился на такое условие.

 Массовая свадьба в Южной Корее

Задача о марьяже — математическая задача из области кооперативных игр. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. В более простой формулировке: составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам. Решение задачи было описано в 1962 году математиками Девидом Гейлом и Ллойдом Шепли в статье «Поступление в колледж и стабильность браков» в журнале American Mathematical Monthly. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия».

Множество практических механизмов на основе алгоритма Гейла-Шепли разработал нобелевский лауреат Элвин Рот.

Ллойд Шепли и Элвин Рот

Решение задачи:

  • мужчины делают предложение наиболее предпочитаемой женщине;
  • каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;
  • мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
  • если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
  • шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.

Для алгоритма требуется порядка n² шагов, где n — число мужчин и женщин.

Прикрепленные материалы: 
ФайлФайлРазмер
priz-450-267.jpgJPG, 450x267px, 141.33 КБ
kimhongji.jpgJPG, 600x400px, 245.81 КБ

Добавьте свой комментарий

Plain text

  • Переносы строк и абзацы формируются автоматически
  • Разрешённые HTML-теги: <p> <br>
LiveJournal
Регистрация

Другие статьи в этой рубрике

Графен в медицине

Ксения Рыкова для ПостНауки

Астрономы поймали длинный гамма-всплеск от взрыва далекой сверхновой

Астрономы смогли достоверно обнаружить новую пару сверхновая—гамма-всплеск в далекой галактике. Подобные открытия позволяют понять связь между этими катаклизмами и более детально разобраться в механизмах генерации гамма-всплесков.

Взрыв сверхновой разложили на этапы

Сверхновые звёзды — основной источник элементов жизни во Вселенной. Существование человечества и всего живого стало возможно благодаря тем химическим элементам, которые были получены в результате взрыва сверхновых звёзд.

Новости в фейсбук

Случайные статьи

Выявлена еще одна связанная с инфарктом молекула микроРНК

НАСА объявило имя нового марсохода

До сих пор новый марсоход НАСА называли просто Mars 2020, но теперь НАСА объявило его официальное имя.

Крыс научили водить машинку

Американским психологам удалось научить крыс управлять транспортным средством — небольшой машинкой из пластикового контейнера на колесиках, которую можно направлять вперед, а также вправо и влево с помощью управляющих рычагов.

Российские ученые усовершенствовали метод химического анализа проб сложного состава

Ученые химического факультета МГУ имени М.В.Ломоносова вывели новые уравнения, которые позволяют проводить рентгенофлуоресцентный анализ с большей точностью, чем это по

Учёные ГАИШ МГУ определили процессы звездообразования в дисках галактик