Доклад Ирины Никитиной на семинаре From the Logical Point of View
7 апреля в 19:30 состоялось заседание научно-исследовательского семинара «From the Logical Point of View», Ирина Никитина выступила с докладом «Алгоритм Гейла-Шепли: стабильность брака и поступление в колледж».
Аннотация:
Данный доклад посвящён статье Дэвида Гейла и Ллойда Шепли 1962 года “College Admissions and the Stability of Marriage”. В статье рассматривается проблема стабильного паросочетания между участниками двух разных групп, имеющих предпочтения относительно друг друга: между мужчинами и женщинами, между высшими учебными заведениями и их потенциальными студентами. Предложенный авторами алгоритм решает эту проблему, при этом Гейл и Шепли доказывают, что при равном количестве участников обеих групп всегда существует хотя бы одно стабильное паросочетание.
