Глава IV. ТЕОРИЯ АЛГОРИТМОВ




Неформально понятие алгоритма, как последовательности действий направленных на решение некоторой задачи, вводилось ещё в курсе информатики. Далее в курсах технологии программирования, дискретной математики, математической логики рассматривались алгоритмы решения различных типов задач. В данном разделе мы формализуем понятие алгоритма, введём понятие вычислительной сложности алгоритма, классифицируем алгоритмы.

Вид формальной модели алгоритма зависит от тех понятий, которые положены в основание модели.

1) Первый подход основан на представлении об алгоритме, как о программе для некоторого детерминированного устройства. К моделям этого типа относятся машины Тьюринга, канонические системы Поста, нормальные алгорифмы Маркова.

2) Второй подход основан на понятии вычисления и числовой функции, основная теоретическая модель этого вида – рекурсивные функции.

Перед введением формальных определений алгоритма сформулируем понятия, необходимые для дальнейшего изложения.

Всюду далее будет рассматриваться некоторая массовая задача P. Массовая задача P определяется следующей информацией:

1) общим списком параметров задачи;

2) формулировкой свойств, которым должно удовлетворять её решение.

Напомним, что этот набор называют ещё спецификацией задачи.

Индивидуальная задача I получается подстановкой в массовую задачу P данного вида конкретных значений параметров. Будем говорить, что алгоритм решает массовую задачу P, если применим к произвольной индивидуальной задаче I, соответствующей задаче P, и даёт решение задачи I.

В качестве массовой задачи P будем рассматривать задачу распознавания, т.е. задачу решением которой могут быть ответы “да” или “нет”. Например, задачей распознавания является задача определения – делится ли заданное натуральное число нацело на 4. Это не ограничивает общности, так как любая задача может быть сформулирована в терминах задачи распознавания.

Обозначим через

– множество всех индивидуальных задач, соответствующих задаче P,

– множество индивидуальных задач с ответом “да”.

Таким образом, задача распознавания состоит в определении этих двух множеств.

Для записи задачи распознавания используется естественный формальный эквивалент, называемый языком. Обозначим

S – конечное множество символов (алфавит),

S* – множество всех конечных цепочек, составленных из S (слова),

– подмножество S*, называемое языком.

Соответствие между задачами распознавания и языками устанавливается с помощью схем кодирования. Схема кодирования e записывает каждую индивидуальную задачу из P словом в фиксированном алфавите S.

Множество S* делится задачей P и схемой кодирования e на 3 класса:

1) слова, не являющиеся кодами индивидуальных задач из P;

2) слова, являющиеся кодами с отрицательным ответом;

3) слова, являющиеся кодами с положительным ответом.

Третий класс слов обозначим .

  1. Машины Тьюринга

Одноленточная детерминированная машина Тьюринга (ДМТ) представляет собой логическое устройство, которое состоит из:

1) неограниченной в обе стороны ленты, разделенной на одинаковые пронумерованные ячейки;

2) читающей/пишущей головки;

3) управляющего устройства с конечным числом состояний.

Схематически ДМТ можно представить в виде рисунка

Программу для ДМТ определяют следующие компоненты:

1) G – конечное множество символов, записываемых на ленте, – множество входных символов, – выделенный пустой символ;

2) Q – конечное множество состояний, в котором выделено начальное состояние и два конечных – ;

3) функция переходов .

Т.е. .

Порядок работы ДМТ под управлением программы .

1. Входное слово записывается на ленте в ячейках с номерами ( – длина слова x), все другие ячейки содержат пустой символ. Управляющее устройство находится в состоянии , а читающая/пишущая головка – над ячейкой с номером 1.

2. Если текущее состояние q не совпадает с одним из конечных состояний, то машина переходит в следующее состояние, определяемое согласно функции переходов. Пусть , где s – считанный головкой символ из текущей ячейки. Тогда управляющее устройство переходит в состояние , головка вместо символа s записывает символ и сдвигается на одну ячейку влево, если , или вправо, если . Затем, текущим становится состояние .

3. Если , то вычисления заканчиваются с результатом “да”, если , то – с результатом “нет”.

В качестве примера рассмотрим упоминавшуюся выше задачу распознавания “делимость на 4”. Построим ДМТ-программу для решения этой задачи.

Для представления чисел будем использовать символы 0 и 1, а в качестве схемы кодирования – двоичную запись числа. Значит, , .

Опишем словесно действия ДМТ, а затем формализуем в виде программы . Число делится нацело на 4, если два последних символа в его двоичном представлении являются нулями. Поэтому, вначале машина будет считывать, повторять все символы входного слова и двигаться вправо, пока не дойдёт до пустого символа. После чего будет выполняться движение влево и анализ последнего и предпоследнего символа с последующей заменой его на символ b. Если хотя бы один из этих символов не равен 0, то результирующее состояние – , в противном случае – . При любом конечном состоянии результатом на ленте будет частное от целочисленного деления, причём, если , то им является пустое слово, т.е. 0.

Представим функцию переходов наглядно в виде ориентированного графа. Вершинами графа будут являться состояния управляющего устройства, дуги графа означают переход из одного состояния в другое, причём, над каждой дугой будем писать символ(ы), по которому выполняется переход, а после знака ® – замещающий символ(ы) и направление движения головки.

Следовательно, .

 

 


Функцию переходов d можно также задать табличным способом.

q s
    b
q 0 (q 0, 0, 1) (q 0, 1, 1) (q 1, b, -1)
q 1 (q 2, b, -1) (q 3, b, -1) (qN, b, -1)
q 2 (qY, b, -1) (qN, b, -1) (qN, b, -1)
q 3 (qN, b, -1) (qN, b, -1) (qN, b, -1)

 

Программа , имеющая входной алфавит S, принимает слово в том и только том случае, когда, будучи применённой ко входу x, она останавливается в состоянии . Язык , распознаваемый программой , определяется следующим образом

.

Если , то работа программы может либо завершиться в состоянии , либо бесконечно продолжаться без остановки. Будем говорить, что ДМТ-программа решает задачу распознавания P при схеме кодирования e, если останавливается для любых и .

Работу ДМТ-программы можно рассматривать, как вычисление некоторой функции . Если слово и программа останавливается на любом входе из S*, то результатом вычисления будет слово, составленное из символов, записанных на ленте после остановки машины в ячейках с 1-ой по последнюю непустую ячейку.

Функция называется вычислимой (по Тьюрингу), если существует вычисляющий её алгоритм, т.е. $ программа , такая что .

Свойства вычислимых функций.

1. Суперпозиция вычислимых функций вычислима.

2. Любая вычислимая функция вычислима на машине Тьюринга с правой полулентой.

3. Если функции вычислимы, то разветвление также вычислимо.

Выше мы каждому алгоритму поставили в соответствие функцию. Является ли верным обратное утверждение: можно ли для произвольной функции построить алгоритм её вычисляющий? Ответ на этот вопрос отрицательный, т.е. произвольная функция не является вычислимой. Выделим класс функций, для которых вычисляющий их алгоритм существует, таким образом, мы дадим другое определение алгоритма в терминах функций.

Рекурсивные функции

Очевидно, что вычислимыми являются все натуральные константы. Как и в формальной арифметике натуральных чисел, определим их с помощью константы 0 и функции следования .

Также вычислимыми являются функции тождества. Через обозначим множество функций, вычисляемых по правилу

.

Мощным средством построения новых функций является их суперпозиция.

Определение. Оператором суперпозиции называется подстановка в функцию от m переменных m функций от одних и тех же n переменных, т.е. , где и .

Функции тождества и оператор суперпозиции задают всевозможные операторы подстановки функции в функцию, а также переименования, перестановки и отождествления переменных.

Оператор примитивной рекурсии определяет n +1-местную функцию f через n -местную функцию g и n +2-местную функцию h.

Определение. Система равенств

называется схемой примитивной рекурсии, а оператор оператором примитивной рекурсии.

Если , то . Например, так определяется хорошо знакомая функция факториал.

Здесь .

Определение. Функция называется примитивно рекурсивной, если она может быть построена из 0, функций и с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

Примеры.

1) Функция суммы, определяемая равенством , является примитивно рекурсивной, так как она задаётся схемой примитивной рекурсии

,

т.е. , где , причём функции g и h являются примитивно рекурсивными.

2) Функция арифметического вычитания . (Проверить самостоятельно).

Арифметизированные логические функции также являются примитивно рекурсивными, так, например, . Также с помощью арифметического вычитания можно выразить Ù и Ú (самостоятельно). Из функциональной полноты множества функций следует примитивная рекурсивность всех логических функций.

Определение. Отношение называется примитивно рекурсивным, если его характеристическая функция

примитивно рекурсивна.

Так как существует взаимно однозначное соответствие между отношениями и предикатами, то будет характеристической функцией и для соответствующего отношению R предиката.

Например, предикат делимости нацело числа x на n является примитивно рекурсивным, так как его характеристическая функция , где – функция, вычисляющая остаток от целочисленного деления x на n, примитивно рекурсивна.

Определение. Оператор называется примитивно рекурсивным, если он сохраняет примитивную рекурсию функций.

Например, условный оператор , где

,

является примитивно рекурсивным. Примитивно рекурсивными являются также операторы конечного суммирования и конечного произведения

,

.

Определение. Ограниченный оператор наименьшего числа, называемый ограниченным оператором минимизации (ограниченный m-оператор), определяется равенством

.

Пример. Пусть задан предикат , который принимает значение 1, если число y нацело делится на . Применение ограниченного оператора минимизации к предикату имеет результатом функцию .

Ограниченный оператор минимизации примитивно рекурсивен, он является средством построения обратных функций. Функция является обратной к функции . Например, функция целочисленного деления z на x определяется ограниченным оператором минимизации

.

В результате рассмотрения примеров функций, которые все являлись примитивно рекурсивными, возникает вопрос: существуют ли не примитивно рекурсивные функции. В данном случае ответ положительный, класс примитивно рекурсивных функций не исчерпывает класс всех вычислимых функций.

Функция Аккермана. Построим функцию, которая является вычислимой, но не примитивно рекурсивной.

Определим последовательность функций по правилу . Функции обладают общими свойствами , ,

, .

Продолжим последовательность по этому рекуррентному правилу

() (2)

Функции примитивно рекурсивны и растут очень быстро. Так, например, , , , ¼, , ¼

Зафиксируем и рассмотрим последовательность функций , , ¼, , ¼ Определим функцию , которая обладает свойствами

(3)

Функция Аккермана определяется как диагональ функции , т.е. = .

Функция Аккермана является вычислимой, так как соотношения (2), (3) позволяют построить программу для её вычисления. Однако данная функция не является примитивно рекурсивной, так как она в силу (3) является двукратно рекурсивной. Поэтому средства построения вычислимых функций нуждаются в расширении. Оператор кратной рекурсии не замыкает класс вычислимых функций, так как для любого n можно построить функцию, которая является -рекурсивной, но не n -рекурсивной. Средством завершающим построение вычислимых функций является m-оператор.

Определение. Неограниченный m-оператор для функции , который обозначается как , определяется как минимальное из значений y,являющихся решением уравнения .

Неограниченный m-оператор часто называют просто m-оператором. Также используют представление m-оператора в виде , где . Алгоритм вычисления состоит в вычислении значений , , ¼ до тех пор пока не получим 0-го значения. Также как и ограниченный оператор минимизации, m-оператор используют для построения обратных функций.

Определение. Функция называется частично рекурсивной, если она может быть построена из 0, функций и с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и m-оператора.

Частично рекурсивная функция может быть определена не для всех значений. Например, функция обратная к функции следования , задаваемая равенством , не определена при .

Определение. Частично рекурсивная функция называется общерекурсивной, если она всюду определена.

Классы вычислимых и частично рекурсивных функций совпадают.


3. Временная сложность алгоритма. Классы P и NP

При решении массовой задачи P требуется не просто найти алгоритм, решающий эту задачу, но построить наиболее эффективный алгоритм.

Под эффективностью алгоритма понимают все вычислительные ресурсы, необходимые для работы алгоритма. Так как ограничения по времени являются детерминирующими, то основное внимание сосредотачивается на этом ресурсе. Временная сложность алгоритма является одной из важнейших характеристик алгоритма, которая определяет затраты машинного времени на его реализацию. Кроме временной сложности алгоритма анализируется еще и сложность по памяти.

Временная сложность алгоритма отражает требующиеся для его работы затраты времени. Время работы алгоритма удобно выражать в виде функции от переменной, характеризующей размер индивидуальной задачи (размерности задачи) т.е. объём данных, требуемых для описания этой задачи. Например, для графа, задаваемого списками инцидентности, размерность задачи представляется как пара (n,m). Эта функция каждой входной длине n ставит в соответствие максимальное время, затрачиваемое алгоритмом на решение индивидуальной задачи этой длины. Значение времени зависит от схемы кодирования и вычислительного устройства, определяющего время работы. Нас же будет в дальнейшем интересовать не точная временная сложность алгоритма, а асимптотическая сложность, которая определяется скоростью роста числа шагов алгоритма при неограниченном увеличении размерности задачи.

Для сравнения скорости роста двух функций и будем использовать обозначения или .

Будем говорить, что функция имеет порядок роста не более, чем функция , что обозначается , тогда и только тогда, когда существуют и , такие, что

Будем говорить, что функция имеет порядок роста не менее, чем функция , что обозначается , тогда и только тогда, когда существуют и , такие, что

Например, для функции

в силу принятых обозначений, можно записать, что или . В общем случае, если - многочлен степени: , то

Непосредственно из определения вытекают следующие свойства:

;

;

.

Если рассматривается представление алгоритма, как ДМТ-программа M, то временная сложность алгоритма определяется равенством .

ДМТ-программа M называется полиномиальной, если существует полином некоторой степени k, такой что , т.е. . С помощью этого понятия введём класс языков P.

Класс языков P образуют языки, для которых существует полиномиальная ДМТ-программа распознавания, т.е.

.

Будем говорить, что задача распознавания P принадлежит классу задач P при схеме кодирования e, если язык принадлежит классу языков P.

Однако не для любой задачи полиномиальная программа существует. Рассмотрим, например, задачу коммивояжера. Как задача распознавания она формулируется следующим образом: дано множество городов, расстояния между ними и граница B, существует ли проходящий через все города маршрут длины, не превосходящей B. Полиномиальный алгоритм решения этой задачи неизвестен. Опишем вначале неформально класс задач, к которому она принадлежит, а потом формализуем это определение.

Неформально класс NP можно определить с помощью недетерминированного алгоритма. Он состоит из 2-х стадий: угадывания и проверки. По индивидуальной задаче I происходит угадывание структуры S, для задачи о коммивояжере такой структурой является вариант пути между вершинами графа. Затем I и S подаются на стадию проверки, которая выполняется детерминированным образом. В нашем примере проверяется, является ли предъявленный путь гамильтоновым циклом, вычисляется его длина и сравнивается с границей B.

Недетерминированный алгоритм решает задачу распознавания P, если выполняются свойства:

1) Если , то $ структура S, угадывание которой приводит к положительному ответу;

2) Если , то такой структуры не существует.

Таким образом, класс задач NP – это класс всех задач распознавания, которые при разумном кодировании могут быть решены недетерминированным алгоритмом за полиномиальное время.

Формальным эквивалентом для недетерминированного алгоритма является программа для недетерминированной одноленточной машины Тьюринга (НДМТ). Структура НДМТ отличается от ДМТ наличием угадывающего модуля со своей читающе/пушущей головкой, связанного с управляющим устройством. Программа для НДМТ задаётся тем набором , что и для ДМТ.

Порядок работы НДМТ под управлением программы .

1. Входное слово записывается на ленте в ячейках с номерами ( – длина слова x), все другие ячейки содержат пустой символ. Читающая/пишущая головка управляющего устройства находится над ячейкой с номером 1, а угадывающего модуля – над ячейкой -1.

2. Управление передаётся угадывающему модулю, который записывает результат работы на левую полуленту и переходит в пассивное состояние.

3. Управляющее устройство начинает работу в состоянии .

4. Если текущее состояние q не совпадает с одним из конечных состояний, то машина переходит в следующее состояние, определяемое согласно функции переходов. Пусть , где s – считанный головкой символ из текущей ячейки. Тогда управляющее устройство переходит в состояние , головка вместо символа s записывает символ и сдвигается на одну ячейку влево, если , или вправо, если . Затем, текущим становится состояние .

5. Если , то вычисления заканчиваются с результатом “да”, если , то – с результатом “нет”.

НДМТ-программа может иметь бесконечное число вычислений при заданном входе x, по одному для каждого слова-догадки из G*. НДМТ-программа принимает x, если по крайней мере одно из вычислений на входе x является принимающим.

Временная сложность НДМТ-программы определяется равенством

.

НДМТ-программа называется НДМТ-программой с полиномиальным временем работы, если существует полином некоторой степени k, такой что .

Класс языков NP формально определяется как

.

Задача называется труднорешаемой, если для неё не существует полиномиального алгоритма. Все задачи, труднорешаемость которых доказана, являются либо алгоритмически неразрешимыми, либо труднорешаемыми недетерминированной машиной.

Не существует алгоритма, который по номеру x любого алгоритма и исходным данным y определяет, остановится ли данный алгоритм при этих данных.

Алгоритмически неразрешимой является 10-я проблема Гильберта: существует ли целочисленное решение произвольного заданного полиномиального уравнения.

4. Полиномиальная сводимость. NP -полные языки и задачи

Какова связь между определёнными выше классами задач P и NP? Очевидно, что (стадия угадывания отсутствует). Естественным кажется предположить, что включение является строгим, однако это утверждение в настоящее время не доказано. Самым сильным доказанным фактом является утверждение

Теорема 4.1. Если , то существует полином , что P может быть решена детерминированным алгоритмом с временной сложностью .

Поэтому все утверждения в теории NP -полных задач формулируются, исходя из предположения, что . Цель теории NP -полных задач заключается в доказательстве более слабых результатов вида: «Если , то ». Данный условный подход основывается на понятии полиномиальной сводимости.

Определение. Язык полиномиально сводится к языку , что обозначается , если существует функция , удовлетворяющая условиям:

1) Существует ДМТ-программа M, вычисляющая f с временной сложностью, ограниченной полиномом, т.е. при некотором k;

2) Для любого в том и только том случае, если .

Пусть – задачи распознавания, а – их схемы кодирования, то задача P1 полиномиально сводится к задаче P2 (обозначается ), если .

Например, задача существования гамильтонова цикла полиномиально сводится к задаче коммивояжера. Для сведения задачи достаточно положить , если , и , в противном случае. Граница B для длины искомого пути берётся равной , где .

Рассмотрим свойства полиномиальной сводимости.

Лемма 4.1. Если , то из следует, что .

Доказательство. Пусть – алфавиты языков соответственно. Так как , то существует отображение . Обозначим через:

– полиномиальную ДМТ-программу, реализующую это отображение;

– программу распознавания языка ;

– программу распознавания языка .

Программа распознавания языка может быть построена как композиция программ и . Ко входу применяется программа , которая строит , затем к применяется программа , определяющая верно ли, что . Так как Û , то эта программа является программой распознавания языка .

Оценим временную сложность этой программы. Так как , то . Если , то . Тогда = = , где . Следовательно, . Лемма доказана.

Лемма 4.2. Если и , то .

Доказательство аналогично, выполнить самостоятельно.

Определение. Язык L называется NP -полным, если и любой другой язык полиномиально сводится к L ().

Аналогично определяются NP -полные задачи.

Лемма 4.3. Если , является NP -полным и , то является NP -полным.

Доказательство. Так как , то достаточно показать, что для любого языка справедливо . Язык является NP -полным, а, следовательно, . По условию , поэтому, в си



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-03-31 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: