Сложность распознавания приближенного вхождения слов на машинах Тьюринга

• Автор: Иванов, Александр Геннадьевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 119 c. : ил

В настоящей работе рассматривается проблема временной сложности решения задачи распознавания приближенного вхождения слов в ряде известных метрик. Эта задача является обобщением "классической" задачи распознавания вхождения одного слова в другое, которая усиленно изучается в последнее время ([12], [І4І, [28],
[32І) . Задача распознавания приближенного вхождения отличается от последней тем, что выясняется не точное вхождение одного слова в другое, а существование такого подслова входного слова, которое в рассматриваемой метрике отличается от первого слова не более, чем на заданную величину <£. . При этом наибольший интерес представляют метрика Хемминга ( 8 ) , метрики 8 , 8 2 8 ,
которые находят практическое применение в теории кодирования [7], в системах структурного анализа Г 22 ] ив алгоритмах распознавания образов [ 4 3. Для указанных метрик задача распознавания приближенного вхождения неоднократно ставилась в работах [її], [зб],
[37], где обсуждались также трудности, встающие на пути построения эффективных алгоритмов решения этой задачи,
В качестве модели вычислительного устройства, для которого анализируется временная сложность решения задачи распознавания приближенного вхождения, здесь рассматриваются многоголовочные машины Тьюринга. Оценка временной сложности приводится в терминах вычислений в реальное время ( [в - 14], Е 25 — 29])
Вычисление функции , при котором алгоритм последовательно читает входное слово и при этом выдает значение 5Г на Я -буквенном начале слова до того, как будет прочитана Ш * 1 -ая буква слова, называется вычислением в реальное время, если время работы ( число шагов) алгоритма с момента прочтения П -ой буквы до момента прочтения Л * { -ой (называемое замедлением

данного алгоритма на префиксе входного слова длины п ) ограничено некоторой константой, не зависящей от входного слова.
Таким образом, общее время работы алгоритма реального времени на входном слове есть линейная функция от длины входного слова. Ясно, что для нетривиальных задач время их решения не меньше длины входного слова, так как алгоритм должен прочитать слово хотя бы один раз. С другой стороны, из существования алгоритма линейного времени, вычисляющего функцию & , не следует существование для этой функции алгоритма реального времени, ибо алгоритм мог существенно использовать знание конца входного слова.
Тем самым, в классе задач, решаемых за линейное время, целесообразно выделить подкласс задач, решаемых "предельно быстро", т.е. в реальное время (1ы1) . Тем более, что во многих прикладных задачах требуются алгоритмы, работающие в темпе поступления информации. К этим задачам относятся задачи обработки информации, задачи управления, распознавания образов.
Применительно к задаче распознавания приближенного вхождения мы интересуемся вычислением такой функции & , значение которой на словах V и I/ есть I или 0 в зависимости от того, существует ли в слове ЕГ подслово, которое в рассматриваемой метрике отличается от слова V не более, чем на заданную величину
Подробное определение расстояний между словами в метриках Хемминга, 8 и 8 (п €. /V ) , а также определение
понятия реального времени приведено в §1.
Обычно рассматриваются следующие три варианта поступления слов V и и на вход алгоритма в задачах идентификации вхождения ( [8І, Г25], [29]) , т.е. различаются три формулировки задачи:
а ) на вход подается слово V § I/ , где § не принадлежит алфавиту слов V и I/ ;

б ) на вход подается слово и§ V ;
в) слова I/ и V подаются на вход параллельно, т.е.
вход имеет вид
# (гг • * * (Гр
и4 » • • ир 9 • *
где Р = (Хр I
Тем самым, читая # -ую букву входного слова, алгоритм видит ^ -ые буквы слов V И и при $ - Я и видит / -ую букву слова при $ ^ Р • Различие этих вариантов проявляется при вычислениях в реальное время.
I. Внимание к задачам типа идентификации подслов было обращено в начале 60-х годов, когда теория сложности вычислений только начинала развиваться. При этом, конечно, особый интерес представляли наиболее простые и естественные задачи, решение которых могло привести к разработке новых методов. К этим задачам относилась задача распознавания вхождения и задача распознавания симметричности слова. Первые результаты в этом направлении (1963 - 1965г.) были получены при исследовании сложности решения этих задач на "классической" машине Тьюринга, имеющей ровно одну ленту с единственной головкой. Основу их составлял метод следов, предложенный Я.М. Барздинем [3] и дополненный Р.В. Фрейвальдом [к], который позволил получить квадратичную нижнюю оценку для временной сложности данных задач на таких машинах, что подтверждало интуитивное представление об их сложности. Но очевидно, что такая машина Тьюринга является весьма слабой моделью вычислительного устройства. Поэтому в дальнейшем исследовалась сложность решения этих задач на более мощных моделях вычислительного устройства, таких, как многоголовочные и многоленточные машины Тьюринга с лента-

Ь+1 , и числом периодов, не менее бЬ+12. , т.е. когда ни один
из алгоритмов %о,бЬ + 42., 6^+42, •••; Ті Н +4, +42.,
работающих параллельно основному алгоритму, не выставляет в конце слова пометки вида ' , Если размеченное разложение не регулярно, то дополнительные головки, оставленные на пометках +
двигаясь вдвое быстрее, чем читается входное слово, успевают вернуться к головке, переписывающей входное слово, до того, как алгоритм Wlh.6h.12 будет производить очередную разметку цветом }( , поскольку в правильной разметке, производимой алгоритмом ‘ЇЇУі Ь, £И +12. , длина меньшего из слов, размечаемых цветом % , составляет менее четверти периода большего слова. Это позволяет для очередной разметки цвета ^ применить описываемую процедуру.
Если же разложение регулярно, то в конец прочитываемой части слова выставляется еще одна головка, которая теперь будет указывать /] + і -ый элемент дефекта размечаемого слова. Кроме того, отступя влево' от конца на длину периода ( указываемую.дополнительной головкой, оставленной на пометке ) , выставляется еще одна
дополнительная головка, которая с этого момента будет двйгаться параллельно головке, переписывающей входное слово. По лемме 5, сравнивая конец прочитанной части слова с символами, просматриваемыми этой головкой, мы будем выяснять, имеет ли псевдопериодичес-кое разложение этой части слова по данному периоду величину дефекта л+ . Если при этом длина прочитанного слова превзойдет
в £ раз длину периода ( для определения этого момента выставляем дополнительную головку на расстоянии £ длин периода от начала слова и ждем, когда в то место будет переписана буква входного слова), то оставленными головками выставляются пометки
+ > ... , ^^ + 1 » и кснеп слова помечается знаком ' . В дальнейшем в конце слова делаем пометку ' до тех пор, пока разложение