4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 36: | Строка 36: | ||
Квадратичные алгоритмы, разработанные, с одной стороны, Берманом и Ханненхалли [5], а с другой – Капланом, Шамиром и Тарьяном [10], основаны на распознавании безопасных обращений за линейное время. На данный момент не известно улучшенных алгоритмов распознавания безопасных обращений, и представляется, что нижняя граница уже была достигнута, | Квадратичные алгоритмы, разработанные, с одной стороны, Берманом и Ханненхалли [5], а с другой – Капланом, Шамиром и Тарьяном [10], основаны на распознавании безопасных обращений за линейное время. На данный момент не известно улучшенных алгоритмов распознавания безопасных обращений, и представляется, что нижняя граница уже была достигнута, что было замечено Озери-Флато и Шамир в работе [14], в которой они сообщили, что «главный вопрос в исследованиях перестановок геномов заключается в том, можно ли получить субквадратичный алгоритм для сортировки при помощи обращений». Этот алгоритм был получен Танье и Сагот [17], которые доказали, что распознавание безопасного обращения на каждом этапе не является необходимым; требуется только распознавание ориентированных обращений. | ||
Строка 42: | Строка 42: | ||
Теорема 1. Если последовательность S является максимальной, но не является последовательностью сортировки ориентированных обращений для перестановки, то существует непустая последовательность S' ориентированных обращений, такая, что S может быть разбита на две части <math>S = S_1, S_2</math>, и <math>S_1, S', S_2</math> является последовательностью ориентированных обращений. | '''Теорема 1. Если последовательность S является максимальной, но не является последовательностью сортировки ориентированных обращений для перестановки, то существует непустая последовательность S' ориентированных обращений, такая, что S может быть разбита на две части <math>S = S_1, S_2</math>, и <math>S_1, S', S_2</math> является последовательностью ориентированных обращений.''' | ||
правок