Предложение (свойство операции минимизации)

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

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

Если на -ом этапе вычислено значение функции и , то полагаем значение функции равным . Если на -ом этапе вычислено значение функции и , то переходим к следующему этапу и т.д.

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

Процесс вычисления , описанный выше, показывает, что если функция интуитивно вычислима, то значение (если оно существует) может быть вычислено эффективно.

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

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

Далее рассмотрим примеры общерекурсивных функций.

Пример 1. Простейшие функции , , для всюду определены, поэтому они являются общерекурсивными функциями.

Пример 2. Все примитивно рекурсивные функции являются общерекурсивными функциями.

Пример 3. Минимизируем примитивно рекурсивную функцию

Составим минимизирующее уравнение

Найдем значения функции при различных значениях .

При нужно найти минимальное значение , которое удовлетворяет условию .

· Полагаем и находим значение . Оно не совпадает со значением .

· Полагаем и находим значение .Таким образом, такое существует и и .

При нужно найти минимальное значение , которое удовлетворяет условию .

· Полагаем и находим значение .Таким образом, такое существует и и .

При нужно найти минимальное значение , которое удовлетворяет условию .

· Полагаем и находим значение . Оно не совпадает со значением .

· Полагаем и находим значение . Оно не совпадает со значением .

· Полагаем и находим значение . Оно не совпадает со значением .

· Полагаем и находим значение . Таким образом, такое существует и и .

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

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

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

Пример 2. Рассмотрим функцию, заданную уравнением:

Результат операции минимизации не определен даже для точки х =0.

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

Пример 3. Рассмотрим функцию, заданную следующим образом

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

Пример 4. Минимизируем функцию .

Уравнение, определяющее новую функцию выглядит так

Поскольку функция принимает только 3 значения (2,4,3), то функция определена только при этих значениях, в остальных точках значение функции не определено. Найдем значение . Решая уравнение последовательной подстановкой, находим, что первое удовлетворяющее уравнению значение равно 5, т.е. .Аналогично определяем, что , . Таким образом,

Обозначим K_ПРФ – множество всех примитивно рекурсивных функций, K_ЧРФ – множество всех частично рекурсивных функций, K_ОРФ – множество всех общерекурсивных функций, а K_ВФ – множество всех интуитивно вычислимых функций.

Связь между этими множествами функций показывает следующее.

Предложение (о иерархии классов рекурсивных функций)

K_ПРФÌК_ОРФÌК_ЧРФÌК_ВФ.

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

Из определений частичной рекурсивности и общерекурсивности функций следует, что K_ОРФÌК_ЧРФ. Выше был приведен пример нигде не определённой частично рекурсивной функцией, а любая общерекурсивная функция является всюду определённой. Таким образом, имеет место строгое включение K_ОРФÌК_ЧРФ.

Очевидно, что K_ЧРФÌК_ВФ, т.е. любая частично рекурсивная функция интуитивно вычислима.

Сделаем два важных замечания:

· в современной теории рекурсивных функций считают, что верно и обратное включение, т.е. любая вычислимая функция является частично рекурсивной (тезис Чёрча-Клини);

· существуют функции, не являющиеся частично рекурсивными, а следовательно,если принять тезис Чёрча-Клини, то существуют функции, не являющиеся вычислимыми.

Предложение доказано.

2.7 Характеристики сложности алгоритмов

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

При решении некоторой задачи алгоритмом обычно рассматривают такие характеристики

· количество шагов , которое необходимо сделать алгоритму для получения результата при использовании входных данных . Величина (максимум берется по всем входным данным объема ) называется временной сложностью алгоритма .

· объем памяти , необходимый для хранения всех входных и промежуточных данных в процессе выполнения алгоритма при использовании входных данных . Величина (максимум берется по всем входным данным объема ) называется емкостной сложностью алгоритма .

Для определения временной сложности алгоритма вместо общего числа шагов алгоритма можно также использовать количество операций определенного вида. Аналогично можно определить средние величины временной и емкостной сложности алгоритма. Сложность задачи – это сложность наилучшего алгоритма, известного для ее решения, т.е. (минимум берется по всем алгоритмам для задачи ).

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

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

Арифметическая функция – функция одного порядка с функцией , если она одного верхнего и одного нижнего порядка с функцией , т.е. и

Пример. Пусть и . тогда существует положительная константа , что при , т.е. .

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

Арифметические функции и называются полиномиально-связанными или полиномиально-эквивалентнтными, если существуют такие многочлены и и некоторое натуральное , что и для всех .

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

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

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

Определим сложность задачи сложения двух натуральных чисел при вычислении на машине Тьюринга. На вход МТ подаются две последовательности десятичных чисел. Внешний алфавит такой МТ содержит десятичные цифры и пустой символ, т.е. , где * – пустой символ.

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

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

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

Пример. Арифметическая функция является примитивно рекурсивной, поскольку получена при помощи операции примитивной рекурсивной функции. Действительно,

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

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

2.8 Классы сложности и

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

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

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

Теория сложности алгоритмов определяет классы алгоритмов по сложности. Обозначим – класс, содержащий все полиномиальные алгоритмы; – класс, содержащий все экспоненциальные алгоритмы. Нетрудно видеть, что .

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

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

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

Особенно хорошо применимы недетерминированные алгоритмы для задач распознавания, т.е. в качестве результата такие алгоритмы должны выдавать ответ «ДА» или «НЕТ». Недетерминированный алгоритм для задач распознавания состоит из двух стадий – стадия угадывания и стадия проверки. По заданным входным данным задачи на первой стадии происходит угадывание или генерация некоторой структуры . Для решения задачи генерируется столько копий алгоритма, сколько существует различных структур . Затем в каждой копии алгоритма для структуры происходит проверка, которая выполняется обычным детерминированным алгоритмом и либо заканчивается ответом «ДА», либо ответом «НЕТ», либо продолжает работать бесконечно (два последних случая можно не различать).

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

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

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

Литература

1. Клини С. К. Математическая логика. – М.:Мир, 1973.

2. Лавров И. А ., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1975.

3. Нефедов В. Н ., Осипова В. А. Курс дискретной математики: Учеб. пособие. – М.: Изд-во МАИ, 1992

4. Капитонова Ю.В. и др. Лекции по дискретной математике. – СПб.: БЧВ-Петербург, 2004.

5. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.

6. Калюжнин Л.А. Что такое математическая логика? – М.: Наука, 1964.

7. Зюзьков В.М., Шелупанов А.А. Математическая логика и теория алгоритмов. – М. Горячая линия – Телеком, 2007.