|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Быстрое решение задачи связности графа и ее применение.курсовая работа (Специалист)
- Научный руководитель: Рыжов А.П.
- Автор: Спиркин Р.О.
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Кафедра математической теории интеллектуальных систем
- Год защиты: 2017
- Курс: 3
- Аннотация: В работе Спиркина Р.О. анализируется задача связности графа. Такие задачи возникают во многих областях - телекоммуникациях, социотехнических системах, анализе генома и многих других. Решение задачи известно, но часто требуется быстрое решение. Именно поиск такого быстрого решения за счет использования специальных структур данных (систем непересекающихся множеств) и эвристик составляет фокус работы. Сказанное определяет актуальность темы исследования. В ходе выполнения работы автором были изучены соответствующие разделы теории графов, структуры данных, используемые эвристики. Предложена реализация алгоритмов в среде Python. Продемонстрировано решение задачи о числе компонент связности графа за логарифмическое время и с помощью этого - задачи о минимальном остовном дереве. Сформулированы возможные направления улучшения алгоритма, что может составить основу дальнейших исследований.
- Добавил в систему: Рыжов Александр Павлович