Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 246
Текст из файла (страница 246)
Поэтому предположим, что задачу е)(0) можно решить за время 0(п"), где /с — некоторая константа. Далее, предположим, что для любого экземпляра ! задачи кодирование е)(з) можно получить из кодирования еэ(з) за время 0(п'), где с — некоторая константа, а и = (ез(!)!. Чтобы решить задачу ез(Я) с входными данными еэ(в), сначала вычисляется е)(з), после чего алгоритм запускается для решения задачи е) (Я) с входными данными е)(в).
Сколько времени это займет? Для преобразования кодировки требуется время О(п'), поэтому выполняется равенство )еу(г)~ = 0(п'), поскольку объем выходных данных алгоритма на последователь- яхроме того, накладывается текннческое требованне, чтобы функции 1ю н 1зг "отображалн неэкземпляры в нююсмпллр" нююаннляр (оаптмыме) в коднровке е — зго строка х б (О, з !", таню, что нс суыествусг эюемпляра т, лля котпропз е(т) = х. Потребуем, гюбы равенюво 1гз(х) = у выполнялось лля каждого неэкэемпляра х в колнровке гг, где у — неюторый неэкземпляр в кодировке «э, а равенство 1зг (х') = у'— для каждого неэкземпляра х' в кодировке ез, где р' — некоторый неэкземпляр в кодировке ег. Пбб Часть УИ.
Избранные темы ном компьютере не может превосходить по величине время его работы. Решение задачи с входными данными ез(з) занимает время 0(1е1(г) ~~) = 0(псь), которое является полиномиальным, поскольку и с, и Й вЂ” константы. Таким образом, то, как закодированы экземпляры абстрактной задачи — в двоичной системе счисления или в троичной, — не влияет на ее "сложность", т.е. на то, разрешима ли она в течение полиномиального времени. Однажз, если эти экземпляры имеют унарную кодировку, сложность задачи может измениться. Чтобы иметь возможность осуществлять преобразование независимым от кодировки образом, в общем случае предполагается, что экземпляры задачи закодированы в произвольном рациональном и сжатом виде, если специально не оговаривается противное.
Точнее говоря, предполагается, что кодирование целых чисел полиномиаяьно связано с их бинарным представлением и что кодирование ограниченного множества полиномиально связано с его кодированием в виде списка элементов, заключенных в скобки и разделенных запятыми. (Одна из таких схем кодирования — АБС11.) Располагая таким "стандартным" кодом, можно получить рациональный код других математических объектов, таких как кортежи, графы н формулы.
Для обозначения стандартного кода объекта этот объект будет заключаться в угловые скобки. Таким образом, (О) обозначает стандартный код графа С. До тех пор, пока неявно используется код, полиномиально связанный с таким стандартным кодом, можно прямо говорить об абстрактных задачах, не ссылаясь при этом на какой-то отдельный код, зная, что выбор кода не повлияет на разрешимость абстрактной задачи в течение полиномиального времени. С этого момента в общем случае предполагается, что все экземпляры задачи представляют собой бинарные строки, закодированные с помощью стандартного кодирования, если явно не оговаривается противное. Кроме того, в большинстве случаев мы будем пренебрегать различием между абстрактными и конкретными задачами.
Однако на практике читателю следует остерегаться тех возникающих на практике задач, в которых стандартное кодирование не очевидно и выбор кодирования имеет значение. Структура формальных языков Один из аргументов в пользу удобства задач принятия решения заключается в том, что для них можно использовать алгоритмы из теории формальных языков. Здесь отбит привести некоторые определения из этой теории. Алфавит Е (а!рЬаЬе1 Е) представляет собой конечное множество символов. Языком Е (1апкпаяе Т), определенным над множеством Е, является произвольное множество строк, состоящих из символов из множества Е.
Например, если Е = (О, 1), то множество Т = (10, 11, 101, 111, 1011, 1101, 10001,... ) является языком бинарного представления простых чисел. Обозначим нусазую строку (ешр1у зпзпк) как е, а лусшай язык (ешргу 1апяцайе) — как И. Язык всех строк, заданных над множеством Е, обозначается как Е*. Например, если Е = (О, 1), то Е" = (е, О, 1, 00, 01, 10, 11, 000,... ) — множество всех бинарных строк. Любой язык Т, над множеством Е является подмножеством множества Е*. !!07 Глава Зк ФР-лалмома Над языками можно определить ряд операций. Наличие таких операций из теории множеств, как овьедииение (шпон) и пересечение (1пгегзесйоп), непосредственно следует из теоретико-множественной природы определения языков. Дополнение (сотр!ешепс) языка Е определим с помощью соотношения Х = Е* — Л.
Конкатенацией (сопса1епайоп) языков Ь1 н Е2 является язык .ь = (Х1Х2:Х1 Е:~1 И Хз Е Ь2) Замыканием (с!озпге), или замыканием Камни (К!еепе зшг), языка Ь называется язык Ь* = (е)иьиЕ20Ези где ь~ — язык, полученный в результате Й-кратной конкатенации языка Х с самим собой. С точки зрения теории языков множество экземпляров любой задачи принятия решения („2 — это просто множество Е', где Е = (О, 1).
Поскольку множество (~ полностью характеризуется теми экземплярами задачи, в которых выдается ответ 1 (да), это множество можно рассматривать как язык Ь над множеством Е = (О, 1), где Ь = (х Е Е': Я(х) = 1) Например, задаче принятия решения РАТН соответствует язык РАТН = ((С, и, с, к): 14 = ((Г, Е) — неориентированиый граф, и,ие)!, )с > 0 — целое число, и в С имеется путь из и в о, состоящий не более чем из )с ребер) .
(Для удобства иногда одно и то же имя (в данном случае это имя РАТН) будет употребляться и для задачи принятия решения, и для соответствующего ей языка.) Схема формальных языков позволяет в сжатом виде выразить взаимоотношение между задачами принятия решения и решающими их алгоритмами. Говорят, что алгоритм А принимает (ассергз) строку х Е (О, 1)*, если для заданных входных данных х выход алгоритма А(х) равен 1.
Язык, принимаемый (ассер1еб) алгоритмом А, представляет собой множество строк Ь = (х Е (О, 1)': А(х) = 1), т.е. множество строк, принимаемых алгоритмом. Алгоритм А отвергает (ге)есьз) строку х, если А(х) = О. Даже если язык Ь принимается алгоритмом А, этот алгоритм необязательно отвергает строку х ~ Ь, предоставляемую в качестве его входных данных. Например, алгоритм может быть организован в виде бесконечного цикла. Язык Е распознается (бес1беб) алгоритмом А, если каждая бинарная строка этого языка принимается алгоритмом А, а каждая бинарная строка, которая не принадлежит языку Ь, отвергается этим алгоритмом.
Язык Ь принимается за нолпномиальиое время (ассер1еб 1и ро1упоппа! 1ппе) алгоритмом А, если он принимается алгоритмом А и, кроме того, если существует такая константа к, что для любой и- символьной строки х Е Ь алгоритм А принимает строку х за время 0(пь). Язык Часть РИ Избранные немы иов Л распознается за нолананнальное время (десЫеб 1л ро!улопна1 !!ше) алгоритмом А, если существует такая константа !с, что для любой п-символьной строки х е (О, 1)' алгоритм за время 0(пй) правильно выясняет, принадлежит ли строка х языку Л.
Таким образом, чтобы принять язык, алгоритму нужно заботиться только о строках языка Е, а чтобы распознать язык, он должен корректно принять или отвергнуть каждую строку из множества (О, 1)'. Как пример, — язык РАТН может быть принят в течение полиномиапьного времени. Один из принимающих алгоритмов с полиномиапьным временем работы проверяет, закодирован ли объект С как неориентированный граф, убеждается, что и и и — его вершины, с помощью поиска в ширину находит в графе С кратчайший путь из вершины и к вершине и, а затем сравнивает количество ребер в полученном кратчайшем пути с числом к. Если в объекте С закодирован неориентированный граф и путь из вершины и к вершине и содержит не более !с ребер, алгоритм выводит значение 1 и останавливается. В противном случае он работает бесконечно долго. Однако такой алгоритм не распознает язык РАТН, поскольку он не выводит явно значение О для экземпляров, длина кратчайшего пути в которых превышает /с ребер.
Предназначенный для задачи РАТН алгоритм распознавания должен явно отвергать бинарные строки, не принадлежащие языку РАТН. Для такой задачи принятия решения, как задача РАТН, подобный алгоритм распознавания разработать легко: вместо того чтобы работать бесконечно долго, если не существует пути из вершины и в вершину и, количество ребер в котором не превышает lс, этот алгоритм должен выводить значение О и останавливаться. Для других задач, таких как задача останова Тьюринга, принимающий алгоритм существует, а алгоритма распознавания не существует.
Можно неформально определить класс сложности (сошр!ехзсу с!ака) как множеспю языков, принадлежность к которому определяется мерой сложности (сошр1ехйу шеазлге), такой, как время работы алгоритма, определяющего, принадлежит ли данная строка х языку Е. Фактическое определение класса сложности носит более технический характера. Воспользовавшись описанным выше формализмом теории языков, можно дать альтернативное определение класса сложности Р: Р = (Ь с (О, 1)' 1 существует алгоритм А, разрешающий язык Ь за полиномнальное время) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
