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
Регистрация

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

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

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

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

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

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

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

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

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

Химикам удалось сделать шаг вперед на пути создания переключаемых реакторов

Лунные похождения искусственного спутника

Lunar Reconnaissance Orbiter — самый молодой лунный зонд НАСА — собрал целую сокровищницу данных.

В клетке. С чего начинается начало.

С ЧЕГО НАЧИНАЕТСЯ НАЧАЛО.

Материалы, которые навсегда изменили историю человечества

Место находки: Сентгабель, Верхняя Гаронна, Франция. // commons.wikimedia.org
 

Быть стройным, не быть на диете. Часть II

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