8_2 (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004), страница 2

В качестве примера можно рассмотреть функцию Dec =  (S), где S(x) — функция из базового набора, S(x) = х + 1. Соответству­ющее уравнение имеет вид S(y) = х и оно имеет решение у = х - 1 при х > 0 и не имеет решения при х = 0. Следовательно, Dec(x) = х - 1 при х > 0 и Dec(0) не существует.

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

Приведенный пример показывает, что оператор минимизации может превратить всюду определенную функцию в частичную, т. е. выводить за пределы множества примитивно-рекурсивных функ­ций. Множество функций, получаемых применением кбазовому набору Р конечного числа операций типа суперпозиции, при­митивной рекурсии и минимизации называется множе­ством частично-рекурсивных функций и обозначается Р_чр.

Множество Р_р всюду определенных функций из Р_чр называ­ется множеством рекурсивных (или общерекурсивных) функций. Очевидно, что выполняются следующие соотношения:

P_пр  P_р  P_чр  P_ч 

где Р_ч — множество всех частичных функций.

В частности, приведенные выше функции Аккермана являют­ся общерекурсивными.

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

1. Класс Р_яыч замкнут относительно операции суперпозиции .
   Иными словами, если в качестве операндов операции суперпози­
   ции взять вычислимые функции, то результат обязательно будет
   вычислимой функцией.

2. Класс Р_выч замкнут относительно операции примитивной
   рекурсии .

3. Класс Р_выч замкнут относительно операции минимизации .
Следствием этих трех утверждений является вложение

Р_чр  Р_выч

4. Всякая функция, вычислимая на машине Тьюринга, частич­но-рекурсивна.

Более того, существует теорема Клини о нормальной форме: Любая вычислимая функция f(х₁, х₂, ..., х_n) представима в форме

f(х₁, ..., х_n) = F_f (х₁, х₂, ..., х_n, _y (G_f(х₁, х₂, ..., х_n,y) = 0)),

где F_f, G_f — примитивно-рекурсивные функции.

Из четвертого утверждения следует, что Р_выч  Р_чр. Таким об­разом, классы частично-рекурсивных функций и функций, вычис­лимых машинами Тьюринга, совпадают: Р_чр = Р_выч.

Вспомним, что класс вычислимых по Тьюрингу функций в со­ответствии с тезисом Тьюринга является формализацией нечетко очерченного класса алгоритмически (в интуитивном смысле) вы­числимых функций. Тогда можно вслед за А. Черчем сформули­ровать следующий тезис: «Класс алгоритмически (или машинно) вычислимых частичных функций совпадает с классом всех частично-рекурсивных функций».

8.5 Алгоритмически неразрешимые проблемы.

Далеко не все задачи решаются алгоритмически или, как принято говорить в математике, конструктивно.

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

Следовательно, существуют функции, не вычисляемые никакой машиной Тьюринга. Такие функции называются невычислимыми. Если теперь сказать, что вычисление функции — это решение зада­чи, а программа машины Тьюринга — алгоритм, то мы делаем вы­вод о существовании алгоритмически неразрешимых задач.

В теории алгоритмов известно много таких задач. Перечис­лим наиболее важные из них.

1. Проблема остановки. При обсуждении машин Тьюринга
было сказано, что на некоторых исходных данных машина может не останавливаться, т. е. не давать результата. Любая ма­шина Тьюринга может быть представлена некоторым кодом (номером), отличающимся от всех других. Например, каждое состояние можно закодировать числом, символы движения за­ кодировать различными числами. Тогда каждая команда пред­ ставляет собой строку чисел, которую можно интерпретировать как одно большое число, а последовательность всех команд — как еще большее число N. Эта или какая-либо другая процедура устанавливает однозначное соответствие между множеством
натуральных чисел и множеством алгоритмов. Функция  : Natur —> Algorithmus, называется нумерацией алгоритмов, а ее аргу­мент N — номером алгоритма при нумерации . Функция  по номеру N восстанавливает описание алгоритма,  (N) = а. Об­ратная функция по описанию алгоритма определяет его номер. Введение нумераций позволяет работать с алгоритмами как с натуральными числами, что особенно удобно при исследовании алгоритмов над алгоритмами: алгоритм, закодированный чис­лом, может рассматриваться как входные данные другого алго­ритма. Проблема остановки состоит в построении машины Тью­ринга М, которая получая на входе код (номер) N произвольной машины Т и входные данные этой машины X, определяет, оста­новится ли машина Т на данных X. Иначе говоря,

M(N,X) = 1, если Т останавливается на X,

M(N,X) = О, если Т не останавливается на X.

Доказано, что машину М построить нельзя, т. е. проблема остановки алгоритмически неразрешима.

2. Проблема эквивалентности. Для вычисления одной и той
же функции можно построить две различные машины Тьюринга,
отличающиеся набором команд, а значит, и последовательностью действий. Тем не менее для любых исходных данных обе ма­шины будут вычислять одинаковые результаты. Такие машины естественно считать эквивалентными. Проблема эквивалентности состоит в построении машины Тьюринга, получающей на входе описания (коды) двух машин Т1 и Т2 и определяющей, эквивалентны ли Т1 и Т2. С практической точки зрения можно поста­вить аналогичный вопрос: можно ли написать программу, кото­рая по текстам двух программ на Паскале определяет, закончатся ли они одинаковыми результатами.

Ответ отрицательный — проблема эквивалентно­сти алгоритмически неразрешима. Это не означает, что для двух конкретных программ нельзя выяснить, эквивалент­ны ли они. Просто не существует общего метода. Для каждой пары программ придется применять собственные методы, завися­щие от существа этих программ.

Понятие вычислимой функции (т. е. той, для которой сущест­вует вычисляющая ее машина Тьюринга — алгоритм) и собствен­но алгоритма не следует смешивать. Различие между вычислимой функцией и алгоритмом — это различие между функцией и спо­собом ее задания. Для одной и той же функции может существо­вать бесконечное число способов задания — текстов алгоритмов. Тривиальный пример: к тексту алгоритма, вычисляющего функ­цию, припишем текст тождественного алгоритма (результат ко­торого всегда равен его входным данным); новый алгоритм пред­ставляет ту же самую функцию; теперь припишем текст тождест­венного алгоритма еще раз, затем еще раз; получим бесконечную последовательность различающихся алгоритмов, представляю­щих одну функцию. Подобные факты и порождают множество проблем в теории алгоритмов, связанных с разрешимостью. Су­ществует даже теорема Раиса, утверждающая, что «никакое не­тривиальное свойство вычислимых функций не является алгорит­мически разрешимым».

Тривиальное свойство означает принадлежность функции либо множеству всех функций, либо пустому множеству. Нетри­виальное свойство — «функция f принадлежит классу C», где С — такой непустой класс, что существуют функции, не принад­лежащие ему. Нумерация всех алгоритмов является одновремен­но и нумерацией всех вычислимых функций: функции можно приписать номер одного из вычисляющих ее алгоритмов. Теперь теорему Раиса можно сформулировать иначе: «Не существует алгоритма, который по номеру функции f определял бы, принадле­жит эта функция заданному классу С или нет».

Из изложенного видно, что проблема алгоритмической не­разрешимости достаточно серьезна. На практике это означает, что если ставится проблема построения алгоритма, имеющего общий (универсальный) характер, например, автоматического синтеза программ по описанию произвольной задачи, то скорее всего такая проблема не может быть решена. Но если проблему ограничить, не ориентируясь на синтез программ для произволь­ных задач, а очертить более узкий круг задач и задать простые правила описания таких задач, то, вероятно, проблема может быть решена.

8.6 Меры сложности алгоритмов. Классы задач Р, ЕХР и NP. NP полные задачи

Хотя теория алгоритмов развивается только несколько десятков лет, а решением задач человечество занималось всегда, задача, как математический объект представляется более загадочной, чем алгоритм.

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

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

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

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

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

Некоторые часто встречающиеся классы функций приведены в таблице. В этой таблице приведены значения функций из данного класса на широком диапазоне значений аргумента. Видно, что при небольших размерах входных данных значения функций отличаются незначительно, однако при росте этих размеров разница существенно возрастает. Во-вторых, быстродействующие функции доминируют над функциями с более медленным ростом. Поэтому если мы обнаружим, что сложность алгоритма представляет собой сумму двух или нескольких таких функций, то будем часто отбрасывать все функции кроме тех, которые растут быстрее всего. Если, например, установлено, что алгоритму нужно х³-30х операций, то будем считать, что сложность алгоритма растёт как х³. Причина этого в том, что уже при 100 входных данных разница между х³ и х³ -30х составляет лишь 0,3%.

Таблица классов роста функций

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