name: РАЗРАБОТКА АЛГОРИТМОВ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ ДЛЯ АНАЛИЗА ГРАФОВЫХ И ГИПЕРГРАФОВЫХ СЕТЕЙ
keyword_list: ОПТИМИЗАЦИЯ АЛГОРИТМЫ ГИПЕРГРАФ ГРАФ МАРШРУТИЗАЦИЯ МАКСИМАЛЬНЫЕ ИНДУЦИРОВАННЫЕ БИКЛИКИ
abstract: Целью диссертации является разработка алгоритмов комбинаторной оптимизации для решения задач маршрутизации и перечислительных задач, возникающих при анализе графовых и гиперграфовых сетей. В диссертации разработаны, реализованы в виде комплекса программ и протестированы на случайных и реальных данных новые алгоритмы для решения следующих задач: задачи о кратчайшем пути в нестационарной метрической сети с условием FIFO и ресурсоограниченной сети с одним ресурсом, задача поиска всех максимально полных подматриц матрицы инцидентности гиперграфа, задача перечислениях всех максимальных индуцированных биклик гиперграфа. Доказаны теоремы о временной сложности и корректности предложенных алгоритмов. Даны рекомендации по их практическому использованию для различных сетей. Разработанные алгоритмы могут применяться в геоинформационных, телекоммуникационных, навигационных системах. Представлен анализ модельной дорожной сети.
chairman_dissertation_council.name: Геннадий
chairman_dissertation_council.surname: Цибульский
chairman_dissertation_council.patronymic: Михайлович
chairman_dissertation_council.position: Заведующий кафедрой систем искусственного интеллекта
chairman_dissertation_council.degree: Доктор технических наук
chairman_dissertation_council.rank: Профессор
chairman_dissertation_council.wos_research_id: В-2733-2014
chairman_dissertation_council.scopus_author_id: 26647106000
chairman_dissertation_council.rinc_id: 99902
chairman_dissertation_council.url: http://ikit.sfu-kras.ru/employees/28
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Галина
organization_supervisor.surname: Баранова
organization_supervisor.patronymic: Павловна
organization_supervisor.position: Начальник отдела диссертационных советов и докторантуры
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.45.17
rubrics.name: Теория графов
rubrics.code: 27.45.15
rubrics.name: Общая теория комбинаторного анализа
oecds.code: 01.02.EX
oecds.name: COMPUTER SCIENCE, THEORY & METHODS
oecds.code: 01.01.PN
oecds.name: MATHEMATICS, APPLIED
speciality_codes.name: Теоретические основы информатики
speciality_codes.code: 05.13.17
supervisors.fio: Семенова Д.В.
supervisors.scientific_degree: Кандидат физико-математических наук
supervisors.speciality_code: Системный анализ, управление и обработка информации (по отраслям)
supervisors.responsible_type: Научный руководитель
opponents.fio: Цициашвили Г.Ш.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Системный анализ, управление и обработка информации (по отраслям)
opponents.responsible_type: Оппонент
opponents.fio: Задорожный В.Н.
opponents.scientific_degree: Доктор технических наук
opponents.speciality_code: Математическое моделирование, численные методы и комплексы программ
opponents.responsible_type: Оппонент
protection_organization.short_name: ФГАОУ ВО "СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ",СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ,СФУ
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ"
protection_organization.ogrn: 1022402137460
protection_organization.supervisor_name: МАКСИМ
protection_organization.supervisor_surname: РУМЯНЦЕВ
protection_organization.supervisor_patronymic: ВАЛЕРЬЕВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: ФГАОУ ВО "СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ",СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ,СФУ
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ"
author_organization.ogrn: 1022402137460
author_organization.supervisor_name: МАКСИМ
author_organization.supervisor_surname: РУМЯНЦЕВ
author_organization.supervisor_patronymic: ВАЛЕРЬЕВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные автономные учреждения