Тип работы:
 Предмет:
 Язык работы:


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

Работа №42894

Тип работы

Магистерская диссертация

Предмет

информатика

Объем работы53
Год сдачи2018
Стоимость5700 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
221
Не подходит работа?

Узнай цену на написание


ВВЕДЕНИЕ .................................................................................................................3
1. УСТОЙЧИВЫЕ ПАРОСОЧЕТАНИЯ И АЛГОРИТМЫ ИХ
НАХОЖДЕНИЯ .........................................................................................................4
1.1. Основные определения. ................................................................................4
1.2. Описание алгоритма поиска устойчивого паросочетания. .....................6
1.3. Реализация алгоритма поиска устойчивого паросочетания...................9
2. АЛГОРИТМ НАХОЖДЕНИЯ ВСЕХ УСТОЙЧИВЫХ ПАРОСОЧЕТАНИЙ
СЛОЖНОСТЬЮ O(n3|S|) (АЛГОРИТМ КНУТА)............................................... 12
2.1. Реализация алгоритма поиска всех устойчивых паросочетаний......... 12
2.2. Особенности реализации на языке Python............................................... 15
3. АЛГОРИТМ НАХОЖДЕНИЯ ВСЕХ УСТОЙЧИВЫХ ПАРОСОЧЕТАНИЙ
СЛОЖНОСТЬЮ O(n2+

Проблема устойчивых паросочетаний - это хорошо известная задача
нахождения «стабильного» соответствия для n мужчин и для n женщин;
решение задачи было описано в 1962 году математиками Дэвидом Гейлом
(Университет Брауна) и Ллойдом Шепли (Принстонский университет) в статье
«Поступление в колледж и стабильность браков» (College admissions and the
stability of marriage) в журнале American Mathematical Monthly. Алгоритм
позволяет найти два конкретных, но экстремальных, стабильных паросочетания
(из, возможно, экспоненциального числа устойчивых паросочетаний).
В настоящей работе рассматривается 2 способа нахождения устойчивых
паросочетаний, в частности, мы исследуем алгоритм сложностью O(n3S) (Кнут)
и алгоритм сложностью O(n2+

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
КУРСОВЫЕ СТАТЬИ ВКР

В ходе данной работы были реализованы алгоритмы нахождения всех
устойчивых паросочетаний сложностью O(n3S) – алгоритм Кнута, и
сложностью


Дональд Кнут, «Устойчивые паросочетания и другие комбинаторные
Задачи», М.:МЦНМО, 2014.
[2]. Крейг Леннон, «On the likely number of stable marriages», Dissertation, The
Ohio State University, 2007.
[3]. M. Dzierzawa, M.J. Omero, «Statistics of stable marriages», Physica A:
Statistical Mechanics and its Applications, Volume 287, Issues 1–2, рр 321–333,
2001.
[4]. Fréchet distribution, английская википедия,
https://en.wikipedia.org/wiki/Fr%C3%A9chet_distribution
[5]. R. Irving, P. Leather, «The complexity of counting stable marriages», pp. 655-
667, 1986.
[6]. S. Tsukiyama, M. Ide, M. Arioshi, «A new algorithm for generating all the
maximal independent sets», pp. 505-517, 1977.
[7]. E. Lawler, J. Lenstra, A. Rinooy Kan, «Generating all maximal independent sets:
NP.hardness and polynomial-time algorithms», SIAM Journal on Computing, 1980
[8]. D. E. Knuth, J. Szwarzfiter, «A structural program to generate all topological
sorting arrangements», IPL, pp. 153-157, 1974.
[9]. Е.Д.Шерман, Е.А. Беговатов, И.Н. Володин, Р.Ф. Салимов, «Краткий курс
математической статистики», Казань: Казан. ун-т, 2015.
[10]. Dan Gusfield, «Three fast algorithms for four problems in stable marriage»,
Journal SIAM Journal on Computing, Volume 16 Issue 1, рр. 111-125, Feb. 1987

Работу высылаем на протяжении 30 минут после оплаты.




©2025 Cервис помощи студентам в выполнении работ
.