Открытая лекция «Жадная гипотеза для задачи о надстроке» / События на TimePad.ru

Открытая лекция Александра Куликова (ПОМИ РАН, CS клуб) «Жадная гипотеза для задачи о надстроке» 18 октября в 20:00 в БЦ «Таймс».

Приглашаем всех желающих, но нужно зарегистрироваться: https://comscicenter.timepad.ru/event/826863/

Задача о (кратчайшей общей) надстроке — классическая труднорешаемая задача, являющаяся, в частности, математической моделью задачи сборки генома. В ней на вход даётся множество строк и требуется найти самую короткую строку, содержащую их все как подстроки. На сегодняшний день мы не знаем эффективных точных алгоритмов для её решения. Наилучший известный приближённый алгоритм для этой задачи находит решение, которое гарантированно не более чем в 2,5 раза длиннее оптимальной надстроки. Соответствующий алгоритм и его анализ довольно сложны. В то же время уже более тридцати лет остаётся открытой так называемая жадная гипотеза. Она утверждает, что следующий (до безобразия простой) жадный алгоритм является 2-приближённым: пока строк больше двух, взять две из них с максимальным наложением и заменить на их склейку (в итоге останется одно строка, которая обязательно будет надстрокой исходного набора).

Пытаясь доказать эту гипотезу, мы пришли к понятию иерархического графа, который в некотором смысле является обобщением графов де Брюйна (которые, с свою очередь, активно используются в современных геномных ассемблерах). В этом графе тоже легко строится жадный алгоритм, который обладает некоторыми замечательными свойствами. Например, в отличие от обычного жадного алгоритма он находит оптимальные решения для некоторых полиномиально разрешимых частных случаев. Для данного жадного алгоритма мы экспериментально установили, что всегда выполняется достаточно сильное условие, из которого, в частности, следует 2-приближение. Доказывать это сильное условие мы на сегодняшний день умеем только в случае, когда все исходные строки имеют длину три.

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

Лекция по совместной работе Александра Куликова с Александром Головнёвым, Александром Логуновым и Иваном Михайлиным:

https://arxiv.org/abs/1809.08669

Веб-сервис с пошаговой визуализацией всех алгоритмов из статьи: https://compsciclub.ru/scs

(используя его, можно проверить сформулированные гипотезы на произвольном датасете).

Источник: comscicenter.timepad.ru

Комментарии: