• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Вороная Ксения Эдуардовна
Эффективные алгоритмы решения квадратичной задачи о назначениях для некоторых типов графов
2015
Работа представляет собой изучение квадратичной задачи о назначениях (КЗН) в терминах теории графов и фокусируется на трех полиномиально-разрешимых подзадачах общей КЗН. В общем случае КЗН является NP-трудной задачей. Одной из основных особенностей работы является тот факт, что проблема рассматривается в терминах теории графов, когда неориентированный взвешенный по ребрам граф представляет собой структуру связей между объектами. Рассматривались три эффективно разрешимые подзадачи общей КЗН, а именно: размещение невзвешенной цепи на взвешенном дереве произвольной структуры, размещение взвешенного графа произвольной структуры на взвешенной звезде, размещение взвешенной звезды на взвешенной сети произвольной структуры. Результатом работы является первичная реализация полиномиальных алгоритмов для рассмотренных подзадач. Языком программирования является Python. В частности, были проведены вычислительные эксперименты, подтвердившие на тестовых данных правильность работы алгоритмов и соответствие времени работы заявленным верхним оценками сложности.

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

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

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

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

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

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