42
правки
Изменения
Нет описания правки
'''Алгоритм Ландау-Шмидта''' {{---}} алгоритм на строках, позволяющий найти все тандемные повторы в строке <tex>S[1..n]</tex> за <tex>O( n \log n + z)</tex>, где <tex>z</tex> — полное число всех тандемных повторов в <tex>S</tex>. Было опубликовано в журнале Journal of Computational Biology 2001 году.
== Определения ==
{{Определение
== Алгоритм ==
Метод нахождения всех тандемных повторой за время <tex>O( n \log n + z)</tex>, где <tex>z</tex> — полное число всех тандемных повторов в <tex>S</tex>. Метод разработали Ландау и Шмидт.
Рещение Ландау-Шмидта — это рекурсивный алгоритм типа "разделяй и властвуй", который основан на возможности вычислять запросы о наибольшем общем продолжении за константное время. Пусть <tex>h = [n/2]</tex>. В укрупненном масштабе метод Ландау-Шмидта делит задачу нахождения всех тандемных повторов на четыре подзадачи:
Для подсчета времени сначала отметим, что при фиксированном <tex>h</tex> методу нужно константное время на один выбор <tex>l</tex> для того, чтобы выполнить общие запросы о продолжении, и, таким образом, время <tex>O( n/2)</tex> на все такие запросы. Для любого фиксированного <tex>l</tex> методу нужно константное время на обнаруживаемый тандем, и никакой тандем не обнаруживается дважды, так как у всех обнаруживаемых тандемов длины <tex>2l</tex> стартовые точки различны. Поскольку сообщение о каждом повторе состоит из начальной точки и длины, то алгоритм никогда не сообщает о тандемном повторе дважды. Следовательно, время, расходуемое на вывод информации о тандемных повторах, пропорционально <tex>z_h</tex> — числу повторов, у которых первая копия покрывает позицию <tex>h</tex>.}}
{{Теорема
|statement = Каждый тандемный повтор в <tex>S</tex> находится решением подзадач 1-4 и при этом только единожды. Время работы алгоритма равно <tex>O( n \log n + z)</tex>, где <tex>z</tex> — полное число всех тандемных повторов в <tex>S</tex>.
|proof=
То, что алгоритм находит все тандемные повторы, прямо следует из факта, что каждый тандем имеет форму, предусмотренную одной из подзадач 1 —4. Чтобы показать, что никакой тандемный повтор не выводится дважды, вспомним, что для <tex>h = n/2</tex> никакой из тандемов не принимает формы, предусмотренной более чем одной из четырех подзадач. Рекурсивно это выполняется для подзадач 1 и 2. Далее, при доказательстве Леммы мы установили, что решение подзадачи 3( а также 4) никогда не получает один и тот же тандем дважды. Следовательно, при полном решении четырех подзадач никакой тандемный повтор не выводится дважды. Отсюда следует, что время вывода всех тандемных повторов равно <tex>O( z)</tex>. Чтобы завершить анализ, рассмотрим время, расходуемое на запросы о продолжении. Это время пропорционально числу выполняемых запросов. Пусть <tex>T( n)</tex> — число запросов при длине строки <tex>n</tex>. Тогда <tex>T( n) = 2T( n/2) + O( n)</tex> и <tex>T( n) = O( n \log n)</tex>, как и утверждалось.}}
