Теоретический семинар (осень 2015)

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

Существует гипотеза о том, что жадный алгоритм для задачи о надстроке является 2-приближенным (на текущий момент лучшим является $2^{\frac{11}{30}}$ - приближение). В докладе будет рассмотрено доказательство этой гипотезы для некоторого подмножества входов.

В докладе мы рассмотрим классическую задачу о надстроке и ее параметризованные варианты. В ней на вход мы получаем некий набор строк и пытаемся найти кратчайшую строку, которая содержит все строки из набора как подстроки.
Задача нашла и практическое применение в биоинформатике, но остается интересной с теоретической точки зрения.
Будут рассмотрены алгоритмические и сложностные результаты для этой задачи, с точки зрения различных параметризаций.

Дополнительных знаний от слушателя не требуется.

Страницы