Алгоритмы на строкахЮрий ЛифшицМатериалы и ссылки находятся наhttp://logic.pdmi.ras.ru/~yura/strings.html1. Алгоритм Кнута-Морриса-ПраттаВозможно, самый знаменитый строковый алгоритм. Многие задачи поиска сводятся к одной и той же абстрактной постановке: в тексте (строке) T длины N найти шаблон (другая строка) S длины M. Первый приходящий в голову подход работает за MN шагов в худшем случае. Многие ученые вносили разные улучшения, и наконец, одновременно и независимо Кнут с Моррисом и Пратт придумали алгоритм работающий за O(M+N) в худшем случае. 2. Суффиксные деревьяИсследователи еще много лет назад поняли, что если мы хотим быстро искать много разных шаблонов в одном и том же тексте, то не стоит хранить текст, просто записанным справа налево. Напротив, стоит специальным образом “подготовить” его. Абсолютно идеальным было бы O(N) время для подготовки текста длины N и O(M) для поиска шаблона длины M в “подготовленном” тексте. Еско Уконнен придумал такой алгоритм. Суффиксное дерево – это и есть оптимальный способ представления текста для последующего многократного поиска в нем. 3. Преобразование Барроуза-ВилераЕще 15 лет назад казалось, что в области архивирования данных без потерь сделано все, что только можно. Тем более удивительным было открытие преобразования Барроуза-Вилера в 1994ом году. Эти ученые предложили проводить архивирования в два этапа: предварительная пересортировка текста (BWT, от слов Burrows-Wheeler Transform) и последующее применение одного из классических архиваторов.4. Введение в филогенетикуФилогенетика – один из разделов вычислительной биологии (биоинформатики), занимающийся анализом сходства генотипов и, в частности, восстановлением филогенетического дерева (кто от кого произошел). На математическом уровне задача состоит в определении “эволюционного расстояния” между длинными строками в алфавите AGCT и последующей кластеризации.В рамках курса будет представлен ряд легко-формулируемых открытых вопросов.