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