Реферат: Алгоритмы на строках Юрий Лифшиц Материалы и ссылки находятся на

Алгоритмы на строках

Юрий Лифшиц


Материалы и ссылки находятся на

http://logic.pdmi.ras.ru/~yura/strings.html


1. Алгоритм Кнута-Морриса-Пратта


Возможно, самый знаменитый строковый алгоритм. Многие задачи поиска сводятся к одной и той же абстрактной постановке: в тексте (строке) T длины N найти шаблон (другая строка) S длины M. Первый приходящий в голову подход работает за MN шагов в худшем случае. Многие ученые вносили разные улучшения, и наконец, одновременно и независимо Кнут с Моррисом и Пратт придумали алгоритм работающий за O(M+N) в худшем случае.





2. Суффиксные деревья


Исследователи еще много лет назад поняли, что если мы хотим быстро искать много разных шаблонов в одном и том же тексте, то не стоит хранить текст, просто записанным справа налево. Напротив, стоит специальным образом “подготовить” его. Абсолютно идеальным было бы O(N) время для подготовки текста длины N и O(M) для поиска шаблона длины M в “подготовленном” тексте. Еско Уконнен придумал такой алгоритм. Суффиксное дерево – это и есть оптимальный способ представления текста для последующего многократного поиска в нем.





3. Преобразование Барроуза-Вилера


Еще 15 лет назад казалось, что в области архивирования данных без потерь сделано все, что только можно. Тем более удивительным было открытие преобразования Барроуза-Вилера в 1994ом году. Эти ученые предложили проводить архивирования в два этапа: предварительная пересортировка текста (BWT, от слов Burrows-Wheeler Transform) и последующее применение одного из классических архиваторов.





4. Введение в филогенетику


Филогенетика – один из разделов вычислительной биологии (биоинформатики), занимающийся анализом сходства генотипов и, в частности, восстановлением филогенетического дерева (кто от кого произошел). На математическом уровне задача состоит в определении “эволюционного расстояния” между длинными строками в алфавите AGCT и последующей кластеризации.





В рамках курса будет представлен ряд легко-формулируемых открытых вопросов.