Юрий Михайлович Лифшиц
Алгоритмы на строках
Ю.М.Лифшиц планирует провести 4 занятия (для 10-11 классников и первокурсников).
В последние пять лет интерес к строковым алгоритмам необычайно вырос. Дело в том, что основные задачи биоинформатики — восстановление генома и поиск наиболее вероятных мутаций от одного генома к другому, являются, по сути, задачами на строках. В этом курсе мы разберем самый знаменитый алгоритм поиска подстрок (Кнута-Морриса-Пратта), преобразование Берроуза-Вилера (совершившее революцию в алгоритмах архивирования) и обсудим применения строковых алгоритмов в биоинформатике. На первом занятии курса я представлю ряд открытых исследовательских вопросов (в том числе недавно поставленных), формулировки которых доступны любому десятикласснику.
Программа:
- 1.Алгоритм Кнута-Моррисона-Пратта
- 2.Суффиксные деревья
- 3.Преобразование Берроуза-Вилера
- 4.Текстовые задачи биоинформатики
Подробности смотрите на странице Ю.Лифшица на сайте ПОМИ РАН (http://logic.pdmi.ras.ru/~yura/strings.html)
Organization Committee e-mail:
dubna@mccme.ru