• 18 октября, четверг
  • Санкт-Петербург, Кантемировская 2 (Бизнес-центр «Таймс», 2 этаж)

Открытая лекция «Жадная гипотеза для задачи о надстроке»

Регистрация на событие закрыта

Извините, регистрация закрыта. Возможно, на событие уже зарегистрировалось слишком много человек, либо истек срок регистрации. Подробности Вы можете узнать у организаторов события.

Другие события организатора

53 дня назад
18 октября c 20:00 до 21:30
Санкт-Петербург
Кантемировская 2 (Бизнес-центр «Таймс», 2 этаж)

Лектор — Александр Куликов (ПОМИ РАН, CS клуб)

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

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

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

Доклад по совместной работе с Александром Головнёвым, Александром Логуновым и Иваном Михайлиным:
https://arxiv.org/abs/1809.08669
Веб-сервис с пошаговой визуализацией всех алгоритмов из статьи: https://compsciclub.ru/scs
(используя его, можно проверить сформулированные гипотезы на произвольном датасете).

Регистрация

Рекомендуемые события

Организуете события? Обратите внимание на TimePad!

Профессиональная билетная система, статистика продаж 24/7, выгрузка списков участников, встроенные инструменты продвижения, личный кабинет для самостоятельного управления и еще много чего интересного.

Узнать больше