Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 114
Текст из файла (страница 114)
Я вЂ” выражение, говорящее о "правильном старте", т.е. что 1е действительно является начальным МО М с и на входе. 3. У вЂ” выражение, которое говорит о "правильных переходах'*, совершаемых М при преобразовании 1е к 1ь 4. 1' — выражение, говорящее о "правильном финише", т.е. что 1г является допускающим МО. Отметим, что хотя выражение в целом не имеет свободных переменных, переменные из 1, будут появляться как свободные в о, переменные из 1.— как свободные в Е; а обе группы переменных будут свободны в Ж.
Правильный старт 5 является логическим И литералов; каждый литерал — это одна из переменных МО 1,. 5 имеет литерал уж если в1-й позиции начального МО со входом и находится символ А, и литерал уи, если нет. Таким образом, если и = апяь ..и„, то Уяев, Уьн, Уеаг, "' Ума 496 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ все у,л для ! = и+ 1, л+ 2, ..., р(и) появляются без отрицания, а все остальные переменные МО 1, — с отрицаниями. Здесь предполагается, что 9, — начальное состояние М, а  — пробел. Правильный финиш !! является допускающим МО, если содержит допускающее состояние. Следовательно, Р' записывается как логическое ИЛИ тех переменных ум, выбранных из пропознциональных переменных МО 1д для которых А является допускающим состоянием.
Позиция 1 произвольна. Правильные переходы Выражение )т' строится рекурсивно с помощью метода, который позволяет удвоить число рассматриваемых переходов, добавив лишь О(р(л)) символов в конструируемое выражение и (что важнее) затратив для написания выражения время 0(р(л)).
Для логического И выражений, в которых приравниваются соответствующие переменные МО ! и .1, полезно использовать сокращение 1= Х Таким образом, если 1 состоит из переменных у,, и Х состоит из переменных зя, то 1= Х вЂ” это И выражений (умзм + у „гм ), где! изменяется от О до р(л), а А — любой ленточный символ или состояние М. Теперь для обозначения того, что 1 ~- Х за 1 или менее переходов, построим выражения Ф(1, Х), где ! = 1, 2, 4, 8, .... В этих выражениях свободны только пропозициональные переменные переменных МО 1 и.1; все остальные пропозициональные переменные связаны.
Такое построение Жа не работает Первым инстинктивным побуждением, связанным с построением Кя по Ф„может быть непосредственное применение подхода "разделяй и властвуй": если 1 ~- Х за 2! или менее переходов, то должно существовать МО К, для которого! (- К и К ~- .!за ! или менее переходов. Однако, если записать формулу, которая выражает эту идею, например, Фл(1,./! = (ЗК)(Ф(1 К) о Ф(К,./)), то длина выражения удвоится при удвоении й Чтобы выразить все возможные вычисления л1, ~ должно быть экспоненциальным относительно л, поэтому для написания Ф будет затрачено слишком много времени, н У будет иметь экспоненциальную длину.
Базис. Для ) = 1 выражение !т',(1, Х) устанавливает, что 1= Х или 1 )- Х Мы только что обсудили, как выразить условие 1= Х Для условия 1 (- Х сошлемся на часть "правильные переходы" из доказательства теоремы 10.9, где также возникала проблема утверждения, что очередное МО следует из предыдущего. Выражение Фг является логическим ИЛИ этих двух выражений. Заметим, что оно записывается за время 0(р(л)). Индукция.
По М, построим Фь(1, Х!. Во врезке "Такое построение )9а не работает" отмечается, что прямой метод построения Фл с помощью двух копий )т', не дает нужного времени и пространства. Корректный способ записи Фя состоит в том, чтобы в выраже- 497 11.3. ПРОБЛЕМА, ПОЛНАЯ ДЛЯ РБ нии записывать одну копшо Л'„подставляя как (1, К), так и (К,./) в одно и то же выражение. Таким образом, в Ли(1,./) используется одно подвыражение Х(Р, Д).
Хг(1,./) записывается для утверждения, что сушествует МО К, при котором для всех МО Р и Д выполняется хотя бы одно из следующих условий. 1. (Р,Я'л(/,К) (Р,0)е(К,Л. 2. Х(Р, Д) истинно. Иными словами, Х(1,К) и Х(К,Л истинны, а для других пар МО (Р, Д) истинность Х(Р, Д) не имеет значения. Итак, КБФ для Х„(1,./) имеет следующий вид. Хг,(1, ./) = ЯК)(УР)(УД)(Х(Р, Д) и (-(1 = Р л К = Д) л — (К = Р л ./ = Д))) Отметим, что на запись Х„уходит время, необходимое для записи Хо а также О(р(п)) для дополнительной работы.
Чтобы завершить построение Х, нужно записать Х для наименьшего и, которое является степенью 2 и не меньше с ' — максимально возможного числа переходов, со- 1 рао вершаемых МТ М перед тем, как допустить вход го длиной л. Количество применений шага индукции, описанного выше, равно !ойг(с~ о~"'), или О(р(п)).
Поскольку каждое использование шага индукции занимает время О(р(п)), приходим к выводу, что Х можно построить за время О(р~(п)). Завершение доказательства теоремы 11.11 Выше показано, как преобразовать вход зо в КБФ (В/о)(В//)(Я л Х л Р) за время, полиномиальное относительно (и ~. Обосновано также, почему выражения Я, Х и Р' истинны тогда и только тогда, когда нх свободные переменные представляют МО /о н 1/, которые являются начальным и заключительным МО в вычислении М со входом го, причем 1, !- 1/. Таким образом, данная КБФ имеет значение! тогда и только тогда, когда Мдопускает и.
! ) 11.3.5. Упражнения к разделу 11.3 11.3.1. Дополните доказательство теоремы 11.10, рассмотрев варианты: а) Р= Р;ЕБ б) Р'= (1/х)(Е); В) р= — ~(Е); г) Р=(Е). 11.3.2. (о!!) Докажите, что следующая проблема является РБ-полной. По данному регулярному выражению Е определить, эквивалентно ли оно Х*, где Х вЂ” множество символов, встречающихся в Е. Указание. Вместо сведения КБФ к данной проблеме можно показать, что любой язык из РБ сводится к ней. Для каждой МТ М 498 ГЛАВА 11.
ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ с полиномиально ограниченным пространством покажите, как взять вход и для М и построить за полиномиачьное время регулярное выражение, порождающее все цепочки, которые не являются последовательностями МО машины М, веду- шими к допусканию и. 11.3.3. (1!) Переключатвльная игра Шеннона состоит в следующем. Дается граф 6 с двумя терминальными узлами л и ь Есть два игрока, называемых БНЕТ и С))Т. По очереди каждый игрок выбирает узел графа 6, не равный л и А который до конца игры будет принадлежать этому игроку.
Игру начинает БНЕТ. Ои выигрывает, если выбирает множество узлов, которое вместе с л и г образует путь в графе б из л в г. С))Т выигрывает, если все узлы выбраны, но ГНОИТ не выбрал путь в графе б из л в и Покажите Рэ-полноту проблемы; по данному графу 0 определить, может ли ГНОИТ выиграть независимо от ходов СПТ. 11.4.
Классы языков, основанные на рандомизации Теперь обратимся к двум классам языков, определяемых машинами Тьюринга, способными при вычислениях использовать случайные числа. Возможно„читатель знаком с алгоритмами на обычных языках программирования, использующими генератор случайных чисел. Функция с названием, подобным хаос) ( ), возвращающая число, которое кажется "случайным" или непредсказуемым, в действительности выполняет специальный алгоритм.
Его можно проимитироватгн хотя в порождаемой им последовательности чисел очень трудно увидеть закономерность. Простой пример такой функции (не используемый на практике) — взять предыдущее число последовательности, возвести его в квадрат и взять средние биты этого квадрата. Числа, порождаемые сложным механическим процессом подобного рода, называются псевдослучайными. В этом разделе определяется тип машины Тьюринга, моделирующей генерацию случайных чисел и их использование в алгоритмах. Далее определяются два класса языков, РР и аРР, использующих эту случайность и полиномиальное время различными способами. Может показаться, что эти классы содержат совсем немного проблем вне 'Р, однако их отличие от Р весьма важно. В частности, в разделе 11.5 будет показано, почему некоторые наиболее существенные проблемы, связанные с безопасностью компьютеров, в действительности являются вопросами о соотношении этих классов с классами Р и ЛР.
11.4.1. Быстрая сортировка — пример рандомизированного алгоритма Возможно, читатель знаком с алгоритмом сортировки, который называется "Быстрая сортировка" (''Оц)с)гзоп"). Сущность алгоритма такова. Из сортируемого списка элементов аь аь ..., а„выбирается один, скажем, ан и элементы списка делятся на те, которые меньше или равны аь и на те, которые больше ан Выбираемый элемент называется вв- 11.4. КЛАССЫ ЯЗЫКОВ, ОСНОВАННЫЕ НА РАНДО)ч)ИЗАЦИИ 499 дущнм (р/во/). Тщательный подбор представления данных позволяет разделить список длиной п на два за время 0(п).
Далее можно рекурсивно отсортировать по отдельности список нижних (которые меньше или равны ведущему) и список верхних (больше ведущего) элементов и в результате получить отсортированный список из всех и элементов. Если нам повезет, то ведущий элемент окажется числом в середине сортируемого списка, и оба подсписка будут иметь длину примерно и/2. Если нам повезет на каждом рекурсивном шаге, то после примерно!оягп уровней рекурсии у нас будут уже отсортированные списки длиной 1. Таким образом, каждый из 0(!од и) уровней требует О(и) времени, а вся работа — 0(и 1оя п). Однако нам может не повезти. Например, если список изначально отсортирован, то выбор первого элемента в каждом списке делит его на нижний подсписок с одним этим элементом и верхний — со всеми остальными.
В данном случае быстрая сортировка ведет себя, как сортировка выбором, и при упорядочении п элементов занимает время, пропорциональное п . Таким образом, хорошие реализации быстрой сортировки не выбирают механически никаких определенных позиций в списке для ведущих элементов. Ведущий элемент выбирается в списке случайно, т.е. вероятность выбора каждого из п элементов в качестве ведущего равна 1/и. Ожидаемое время выполнения быстрой сортировки с использованием такой рандомизации равно О(п 1од и), хотя данное утверждение здесь не доказывается.е Однако из-за ненулевого шанса того, что каждый ведущий элемент окажется наибольшим или наименьшим, время выполнения быстрой сортировки в худшем случае остается 0(и'). Тем не менее, быстрая сортировка является основным методом сортировки во многих приложениях (например, в ()Х1Х), поскольку ожидаемое время ее выполнения в действительности гораздо меньше, чем у других методов, имеющих 0(и 1оя и) в худшем случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
