1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 80
Текст из файла (страница 80)
9.12. С помощью алгоритма 9.3 постройте машины для цепочек у, равных (а) аЬЬЬЬаЬЬЬаЬЬаЬа, (б) аЬсаЬсаЬ. 9.!3. Докажите теорему 9.8. 9.14. Пусть Я=(уи у„..., у„) — множество цепочек. На- пишите алгоритм, который находил бы все вхождения цепочек из 5 в цепочку-текст х. Какова временная сложность вашего алгоритма? *9.15. Постройте 2ДМА, допускающие языки (а) (хсу,су,...су ~тХ, хЕ (а, Ь)*, у, Е (а, Ь)* для 1 =1<т и хотя бы одна из цепочек у„у„..., у„входит в х), (б) (хуу"!х, уЕ 1* и !у!)1), (в) (х,сх,...сх„(х,~ (а, Ь)Р для 1(1е н и все х, различны), (г) (х ох,...схьду,су,...су,~ все х, и у, принадлежат (а, Ь)* и х„=у~~ для некоторых 1 и 1).
9.16, Рассмотрим 2ДМА Р с правилами: 6(я„а, Л,) =6(я„а, А) =(я„+1, рця1я А), 6(я„3, А) =(я„— 1), Гл. а АлГОРитмы идентиФикАции 6(е„а, А)=6(з„а, 2,) =(з„— 1, рор), 6(з„4, г,)=(,, О). (а) Запишите все поверхностные конфигурации автомата Р для входа аа. (б) Примените алгоритм 9.4 для вычисления массива ТЕРМ. *9.17. Предположим, что 2ДМА может из позиции 1 перейти за один шаг в любую из позиций (а) и — 1, (б) 1/2, (в) и/2, (г) !Оя и, где а — длина входа. Покажите, что ни одна из этих модификаций не увеличивает распознающей силы 2ДМА. Какие операции вы можете добавить, чтобы не увеличить прн этом допускающей силы 2ДМА? **9.18.
Постройте 2ДМА, допускающий язык (в,влв,влв,в,"и! ви вм вА Е (а, Ь)+ и и Е (а, Ь)ч). Указание: Пусть х — входная цепочка. Напишите подпрограмму для нахождения такой кратчай- шей цепочки в„что в1в",у=х. Затем примените вашу подпрограмму к у и т. д. "*9.19. Постройте алгоритмы, распознающие за линейное время языки (а) ~нлол!вЕ?")Г, (б) ввли!в, и Е?А, )ваап!), (в) (в, в,...
в„!в, Е (а, Ь)Р и каждая цепочка в, является непустым палиндромом четной длины). 9.20. Напишите алгоритм, который по двум цепочкам а,а,... . а„ и Ь,Ь,... Ьр отыскивает за линейное время такое наибольшее число 1, что а,а,...а, — подцепочка цепочки Ь,Ь,...Ь . Как с помощью этого алгоритма проверить, является ли данная цепочка палиндромом? В следующих четырех упражнениях обсуждаются некоторые ва- рианты магазинных автоматов. Ф9.21. л-голоечатым 2ДМА называют 2ДМА с й независимыми читающими головками на входной ленте. Покажите, как распознать за время 0(л"), допускается ли входная цепочка длины и й-голов- чатым 2ДМА. 9.22.
Односторонним магазинным автоматом называют магазинный автомат, никогда не сдвигающий свою входную головку влево. Недеглерминироеаннмм магазинным автоматом (НМА) называют автомат, у которого есть нуль или более возможностей для выбора УПРАЖНЕНИЯ очередного шага. Таким образом, различаются четыре семейства магазинных автоматов: 1ДМА, 1НМА, 2ДМА и 2НМА.
Язык, до- пускаемый 1НМА, называется бесконтекстным. (а) Покажите, что (мапл(в~ (а, Ь)е) допускается некоторым 1ДМА. (б) Покажите, что (ипил!в Е (а, Ь)") допускается некоторым 1НМА. (Этот язык не может допускаться никаким 1ДМА.) (в) Покажите, что (иппх(еп, х Е (а, Ь)е, !в!)1) допускается некоторым 2НМА. (Этот язык не может допускаться никаким 1НМА.) *9.23.
Покажите, что язык Ь порождается бесконтекстной грам- матикой в нормальной форме Хомского ') тогда и только тогда, когда он допускается некоторым 1НМА. "9.24. Покажите, что за время 0(не) можно распознать, допус- кается ли входная цепочка длины п некоторым 2НМА. 9.26.
Постройте позиционные деревья для цепочек (а) ЬааааЬ3, (б) аЬаЬаЬа$. 9.26. Покажите, что позиционное дерево для аеЬ"аеЬ"3 содер- жит не+ба+1 узлов. *9.27. Покажите, что позиционное дерево для случайной входной цепочки х содержит О(!х!) узлов при условии, что символы во всех позициях выбираются из фиксированного алфавита равновероятно и независимо. 9.28. Для позиционных деревьев из упр. 9.25 найдите (а) вспомогательные деревья, (б) двоичные векторы В, для каждого узла и.
9.29. Покажите, что для каждого позиционного дерева суще- ствует вспомогательное дерево. 9.30. Завершите доказательство леммы 9.4, показав, что Т; и А; правильно строятся по ТР, и А;+,. "9.31. Покажите, что с помощью позиционного дерева для х можно проверить, является лн какая-то цепочка из рн уе,..., у подцепочкой в х, за время порядка (р !+!и*!+ +!и !. 9.32.
Напишите алгоритм, который находил бы длиннейшую общую подцепочку двух данных цепочек х и у. Какова временная сложность вашего алгоритма? е) См. определение перед упр. 2.34. да! ГЛ. К АЛГОРИТМЫ ИДЕНТИФИКАЦИИ 9.33. Напишите эффективный алгоритм, который по данным цепочкам х и Ь,Ь,...Ь, находил бы для каждого 1, 1(((р, длиннейшую подцепочку в х, являющуюся префиксом цепочки Ь;Ь|+Р ..Ь . 9.34. Напишите эффективный алгоритм, который по данным двум цепочкам х=а,а,...а„ и у=-Ь,Ь,...Ь„ в алфавите 7 находил бы кратчайшее представление для у в виде с,с,...с, где с; — символ из 7 или символ, обозначающий подцепочку цепочки х.
Например, если х=аЬЬДЬЬ и у=аЬаЬЬаа, то [1: 2)[4: 6)аа — представление для у длины 4 ([(: )) обозначает надцепочку а;а,+,...а~ цепочки х). Указание: Воспользуйтесь упр. 9.33. 9.35. Докажите, что уплотненное позиционное дерево для це. почки длины и содержит не более 4п — 2 узлов. **9.36. Напишите алгоритм, который за время 0(п) находил бы уплотненное позиционное дерево для цепочки длины и. 9.37. Цепочка х=а,а,...а„называется подпоследсвательностью цепочки у=Ь,Ь,...Ь, если а,а,...а„=Ь,,Ь,,...Ь;„для некоторых 1,«',(...(1„(т. е. х получается из у вычеркиванием нуля или более символов).
Напишите алгоритм сложности 0([х[.ф[) для нахождения самой длинной общей подпоследовательности цепочек х и у. 9.38. Напишите алгоритм, который по двум данным цепочкам х и у находил бы кратчайшую последовательность вставок и удалений одного символа, превращающую х в у. Проблемы для исследования 9.39. Можно ли улучшить оценку времени в упр. 9.10? 9.49. Необходимо ли время 0([а[ [х[) для распознавания вхождения в х цепочки из языка, представленного регулярным выражением а? 9.41. я-головчатый 2ДМА можно промоделировать на РАМ за время 0(п") (упр. 9.21).
Может ли каждый бесконтекстный язык допускаться некоторым 2-головчатым 2ДМА? Если да, то каждый бескоитекстный язык можно было бы распознать на некоторой РАМ за время 0(п~. 9.42. Существует ли бесконтекстный язык, не допускаемый никаким 2ДМА? 9.43. Существует ли язык, допускаемый некоторым 2НМА, но не допускаемый никаким 2ДМА? 9.44. Можно ли улучшить оценку времени в упр. 9.37? (См. Ахо, Хиршберг, Ульман [1974), где для получения оценок использована модель дерева решений.) ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ Замечания пе ннтературе Эквквалеитиость конечных автоматов н регулярных выражений установлена Клини [1956!. Недетерминнрованные конечные автоматы изучались Рабиным, Скоттом [1959), которые доказали их эквивалентность детерминированным. Алгоритм иденткфнкации цепочек, задаваемых регулярным выражением (алгоритм 9.1), построен на основе алгоритма Томпсона [1968]. Эренфойхт, Цайгер [1974] обсуждают сложность НКА как устройства для илассификацик образов.
Распознавание вхождения одной цепочки в другую эа линейное время (алгоритм 9.3) взято у Морриса, Пратта [1970] '). Моделирование 2ДМА за линейное время, а также обобщение и упр. 9.21 принадлежат Куку [197(а). Свойс ва 2ДМА нзучалн Грей, Харрисон, Ибарра [1967). Моделирование 2НМА за время 0(лз) (упр. 9.24) описано у Ахо, Хопкрофта, Ульмана [1968[.
Упр. 9.15 (б) принадлежит Честеру, а упр.9.19(в) — Пратту. Решение уцр.9.19(в) приведено в работе Кнута, Пратта [19711. Материал равд. 9.5, касающийся позиционных деревьев, а также понятие уплотненного позиционного дерева можно найти у Вайнера [1973). Там же содержатся решения упр.9.20 и 9.31 — 9.36 вместе с некоторыми другкми пркложениямн; см.
также Ккут [19736). Карп, Миллер, Розенберг [1972] дают не сколько алгоритмов ндентнфикацки, касающихся повторяющихся цепочек. Упр. 9.9 и 9.10 о совпадении цепочек с несущественнымн символами принадлежаг Фишеру, Патерсону [1974]. Вагнер, Фишер [1974) приводят решение упр.9.36. В нх статье и статье Хиршберга [1973] обсуждаются алгоритмы для задачи об общей подпоследовательности (см. упр.9.37). т) Более сильный результат о распознавании вхождения одной цепочки в другую был получен Ю.
В. Матиясевичем в 1969 г. (См. его статью [1971].) Для обычной постановки задачи вопрос о сложности идентификации цепочек символов и близких задач решен в работе Слисенко [1977).— Прим. перев. Сколько вычислений должка требовать задача, чтобы мы сочли ее действительно трудной? Общепринято, что если задачу нельзя решить быстрее, чем за экспоненциальное время, то ее следует рассматривать как безусловно трудно разрешимую. В втой "схеме классификации" задачи, решаемые алгоритмами полиномиальной сложности, будут легко разрешимыми. Но нужно иметь в виду, что, хотя экспоненциальная функция (такая, как 2") растет быстрее любой полиномиальной функции от л, для небольших значений и алгоритм, требующий 0(2") времени, может оказаться эффективнее многих алгоритмов с полиномиально ограниченным временем работы.
Например, сама функция 2" не превосходит и" до значения и, равного 59. Тем неменее скорость роста экспоненциальной функции столь стремительна, что мы будем называть задачу трудно разрешимой, если у всех алгоритмов, решающих ее, сложность по меньшей мере экспоненциальна. В этой главе мы приведем соображения, показывающие, что некоторый класс задач, а именно задач, полных для недетерминированного полиномиального времени (называемых ИР-полными), вероятно, содержит только трудно разрешимые задачи.
Этот класс включает в себя многие "классические" задачи из комбинаторики (такие, как задачу о коммивояжере, о гамильтоновом цикле, задачу целочисленного линейного программирования), и можно показать, что все задачи из этого класса "эквивалентны" в том смысле, что если хотя бы одна из них оказалась легко разрешимой, то таковы же и все остальные. Поскольку многие из этих задач изучались математиками и специалистами по вычислениям в течение десятилетий и ни для одной из них не удалось найти алгоритма полиномиальной сложности, естественно предположить, что таких полиномиальных алгоритмов и не существует, и, значит, можно рассматривать все задачи из этого класса как трудно разрешимые.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
