08.09.2015 Задача о надстроке (Николай Карпов)

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

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