• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Тарасов Владимир Иванович
Распознавание интервальных графов и его приложения
Магистратура
2014
Граф называется интервальным, если его вершинам можно поставить в соответствие интервалы на прямой таким образом, что две вершины графа смежны тогда и только тогда, когда соответствующие интервалы имеют непустое пересечение. Изначально интервальные графы возникли как математическая модель при решении задач популяционной биологии, а впоследствии оказались полезными и во многих других областях, например, в генетике, биоинформатике, теории расписаний и др. Данная работа посвящена алгоритму распознавания интервальных графов, а также алгоритму поиска кратчайших путей между всеми парами вершин в интервальном графе. Во введении описывается актуальность изучаемых задач, приводится краткий обзор существующих подходов к их решению, а также формулируются цели работы. Основная часть работы состоит из трех разделов. Первый из них посвящен алгоритму распознавания интервальных и хордальных графов. Здесь приводится псевдокод каждого из этапов алгоритма, а также обсуждаются ошибки, допущенные в оригинальной статье. В частности, подробно анализируются и устраняются ошибки, выявленные в процедуре построения кликового дерева. Во втором разделе рассматривается алгоритм поиска кратчайших путей между всеми парами вершин в интервальном графе. Описывается псевдокод каждого из этапов алгоритма. Каждый из рассмотренных алгоритмов первого и второго разделов сопровождается подробной иллюстрацией его работы на конкретном примере. В третьем разделе экспериментально сравнивается время работы алгоритма Флойда-Уоршелла и алгоритма, основанного на интервальном представлении. Также в этом разделе проверяется, что результаты экспериментов соответствуют теоретическим оценкам сложности алгоритмов.

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Расширенный поиск ВКР