Алгоритмы - построение и анализ (1021735), страница 227
Текст из файла (страница 227)
Конкатенацией (сопсагепайоп) двух языков Ь| и Ьз является язык Ь = (хзхз '. хз с Ь| и хз Е Ьз) . Замыканием (с1озпге), или замыканием Клинц (К!еепе згаг), языка Ь называется язык Ь* = (е) ОЬОЬ~ОЬ О где Ьь — язык, полученный в результате lс-кратной конкатенации языка Ь с самим собой. С точки зрения теории языков множество экземпляров любой задачи принятия решения 1,> — это просто множество Е', где Е = (О, Ц.
Поскольку множество () полностью характеризуется теми экземплярами задачи, в которых выдается ответ 1 (да), это множество можно рассматривать как язык Ь над множеством Е = = (О, Ц, где Е = (х Е Е': Я (х) = Ц. Например, задаче принятия решения Рлтн соответствует язык Рлтн = ((С, и, с, к): С = (К Е) — неориентированный граф, и,оба к > 0 — целое число, и в С существует путь от и до с, состоящий не более чем из )с ребер). (Для удобства иногда одно и то же имя (в данном случае это имя РАтн) будет употребляться и для задачи принятия решения, и для соответствующего ей языка.) Схема формальных языков позволяет в сжатом виде выразить взаимоотношение между задачами принятия решения и алгоритмами их решения. Говорят, что 1098 Часть Ч!!.
Избранные темы алторитм А принимает (ассер!з) строку х е (О, Ц*, если для заданных входных данных х выход алгоритма А (х) равен 1. Язык, принимаемый (ассер!ед) алгоритмом А — это множество строк Ь = (х е (О, Ц': А (х) = Ц, т.е. множество строк, воспринимаемых алгоритмом. Алгоритм А отвергает (ге!ее!з) строку х, если А(х) = О. Если язык Ь принимается алгоритмом А, этот алгоритм не обязательно отвергает строку х ф г,, предоставляемую в качестве его входных данных.
Например, алгоритм может быть организован в виде бесконечного цикла. Язык й распознаетсп (оесЫед) алгоритмом А, если каждая бинарная строка этого языка принимается алгоритмом А, а каждая бинарная строка, которая не принадлежит языку Ь, отвергается этим алгоритмом. Язык Е принимаетсл за пвлиномиольное время (ассар!еб ш ро1упоппа1 йпе) алгоритмом А, если он принимается алгоритмом А и, кроме того, если существует такая константа lс, что для любой и-символьной строки х Е Ь алгоритм А принимает строку х за время О (пь). Язык й распознаетсл за поли«ам«аль«ее время (оесЫеб ш ро!упоппа1 пше) алгоритмом А, если существует такая константа «, что для любой и-символьной строки х е (О, Ц' алгоритм за время 0 (и") правильно выясняет, принадлежит ли строка х языку Ь.
Таким образом, чтобы принять язык, алгоритму нужно заботиться только о строках языка Ь, а чтобы распознать язык, он должен корректно принять или отвергнуть каждую строку из множества (О, Ц'. Например, язык Рлтн может быть принят в течение полиномиального времени. Один из принимающих алгоритмов с полиномиальным временем работы проверяет, что объект С закодирован как неориентированный граф, убеждается, что и и о — его вершины, с помощью поиска в ширину находит в графе С кратчайший путь из вершины и к вершине о, а затем сравнивает количество ребер в полученном кратчайшем пути с числом «. Если в объекте С закодирован неориентированный граф, и путь из вершины н к вершине о содержит не более й ребер, алгоритм выводит значение 1 и останавливается. В противном случае он работает бесконечно долго. Однако такой алгоритм не распознает язык РАТН, поскольку он не выводит явно значение 0 для экземпляров, длина кратчайшего пути в которых превышает 1с ребер.
Предназначенный для задачи Рлтн алгоритм распознавания должен явно отвергать бинарные строки, не принадлежащие языку Рлтн. Для такой задачи принятия решения, как задача Рлтн, подобный алгоритм распознавания разработать легко: вместо того чтобы работать бесконечно долго, если не существует пути из вершины и в вершину о, количество ребер в котором не превышает /с, этот алгоритм должен выводить значение 0 и останавливаться. Для других задач, таких как задача останова Тьюринга, принимающий алгоритм существует, а алгоритма распознавания не существует.
Можно неформально определить класс сложности (сошр!ехйу с1аза) как множество языков, принадлежность к которому определяется мерой слоисности (сошр!ех!!у шеааше), такой как время работы алгоритма, определяющего, принад- Глава 34. МР-полнота 1099 лежит ли данная строка я языку Ь. Фактическое определение класса сложности носит более технический характер. Интересующийся читатель найдет его в статье Хартманиса (Напгпашз) и Стирнса (Ягеагпз) (140~.
Воспользовавшись описанным выше формализмом теории языков, можно дать альтернативное определение класса сложности Р: Р = (Ь С (О, 1)": существует алгоритм А, разрешающий язык ь за полиномиальное время). Фактически, Р также является классом языков, которые могут быть приняты за полиномиальное время. Теорема 34.2. Р = (Ь: Ь принимается алгоритмом с полиномиальным временем работы) . Доказательство.
Поскольку класс языков, которые распознаются алгоритмами с полиномиальным временем работы, — это подмножество класса языков, которые принимаются алгоритмами с полиномиальным временем работы, остается лишь показать, что если язык Ь принимается алгоритмом с полиномиальным временем работы, то он также распознается алгоритмом с полиномиальным временем работы. Пусть Ь вЂ” язык, который принимается некоторым алгоритмом с полиномиальным временем работы А.
Воспользуемся классическим "модельным" аргументом, чтобы сконструировать другой алгоритм с полиномиальным временем работы А', который бы распознавал язык Ь. Поскольку алгоритм А принимает язык Ь за время О (и"), где к — некоторая константа, существует такая константа с, что алгоритм А принимает язык Ь не более чем за Т = сп" шагов. Для любой входной строки х алгоритм А' моделирует действие алгоритма А за время Т.
По истечении интервала Т алгоритм А' проверяет поведение алгоритма А. Если он принял строку х, то алгоритм А' также принимает эту строку, выводя значение 1. Если же алгоритм А не принял строку х, то алгоритм А' отвергает эту строку, выводя значение О. Накладные расходы алгоритма А', моделирующего алгоритм А„приводят к увеличению времени работы не более чем на полиномиальный множитель, поэтому А' — алгоритм с полиномиальным временем работы, распознающий язык Ь. И Заметим, что доказательство теоремы 34.2 является неконструктивным.
Для данного языка ЬеР граница для времени работы алгоритма А, который принимает язык Ь, на самом деле может быль неизвестна. Тем не менее, известно, что такая граница существует, поэтому существует алгоритм А', способный проверить эту границу, даже если не всегда удается легко найти такой алгоритм. Часть ЧП. Избранные темы 1100 Упражнения 34.1-1. Определим задачу оптимизации Ьонаезт РАтн Ьенстн как отношение, связывающее каждый экземпляр задачи, состоящий из неориентированного графа и двух его вершин, с количеством ребер в самом длинном пути между этими двумя вершинами.
Определим задачу принятия решения ЬОхбезт РАтн Ьенстн = ((С, и, о, к): С = (Ъ", Е) — неорнентированный граф, и, и Е 1", Й > 0 — целое число, существует пугь из вершины и в вершину о, состоящий не менее чем из к ребер). Покажите, что задачу оптимизации ЬОМОЕБТ РАТН ЬЕХОТН можно решить за полиномиальное время тогда и только тогда, когда Ьонпезт РАтн Ьенстн е Р. 34.1-2. Дайте формальное определение задачи поиска самого длинного простого цикла в неориентированном графе. Сформулируйте соответствующую задачу принятия решения.
Опишите язык, соответствующий этой задаче принятия решения. 34.1-3. Разработайте формальное кодирование для ориентированного графа в виде бинарных строк для представления при помощи матриц смежности. Выполните то же самое для представления с использованием списка смежных вершин. Покажите, что эти два представления полиномиально связаны. 34.1-4. Является ли алгоритм динамического программирования для решения дискретной задачи о рюкзаке, который предлагалось разработать в задаче 16.2-2, алгоритмом с полиномиальным временем работы? Обоснуйте ваш ответ. 34.1-5. Покажите, что алгоритм, который содержит не больше некоторого постоянного количества вызовов процедуры с полиномиальным временем работы, сам работает полиномиальное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
