Файл: 5.docx

25. Примитивно рекурсивные функции

Примитивно рекурсивными называют функции, которые можно получить с помощью операций подстановки и рекурсии из следующих базисных функций: константы 0, операции прибавления единицы s : x  x+1 и семейства функций проекции: это семейство для каждого k содержит k штук k -местных функций .

Функции проекции позволяют выполнять " неоднородные" подстановки: скажем, можно получить функцию  из функций f и h, комбинируя их с функциями проекции: сначала получаем функцию  (подстановка  в g ), затем  (подстановка  в h ), затем полученные две функции вместе с функцией  подставляем в f.

Подставляя константу 0 в функцию прибавления единицы, получаем константу (функцию нуля аргументов) 1. Затем можно получить константы 2, 3 и т.д.

Примеры примитивно рекурсивных функций

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

Сложение. Функция  получается с помощью рекурсии:

sum(x,0)=x;

sum(x,y+1)=sum(x,y)+1.

Надо, конечно, представить правую часть второго равенства как результат подстановки. Формально говоря, h(x,y,z) в определении рекурсии надо положить равным s(z), где s функция прибавления единицы.

Умножение. Функция  получается с помощью рекурсии (с использованием сложения):

prod(x,0)=0;

prod(x,y+1)=prod(x,y)+x.

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

Усеченное вычитание. Мы говорим об " усеченном вычитании"  при  и  при , поскольку мы имеем дело только с натуральными (целыми неотрицательными) числами. Одноместная функция усеченного вычитания единицы определяется рекурсивно:

(Рекурсия здесь формальна, так как предыдущее значение не используется.) После этого усеченное вычитание для произвольных аргументов можно определить так:

26 Частично рекурсивная функция

Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор — минимизации аргумента.

• Оператор минимизации аргумента. Пусть  — функция от n  натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции  называется функция  от  переменной, задаваемая следующим определением:

, при условии 

То есть функция  возвращает минимальное значение последнего аргумента функции , при котором её значение равно 0.

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

---

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

Тезис Чёрча –Класс алгоритмически(машинно) вычислимых частичных функций совподает с классом всех частично рекурсивных функций.

27. Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятияалгоритма.

Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.

Устройство машины Тьюринга

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

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

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

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

[править]Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <q_i, a_j> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

---

Тезис Тьюринга- все вычислимые частичные функции вычисляются на машинах Тьюринга Поста.

28. АЛГОРИТМА СЛОЖНОСТЬ

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

Чаще всего рассматриваются временные и пространственные характеристики алгоритмич. процессов. Так, для Тьюринга машины М сигнализирующая функция времени (время работы)  есть число tтактов работы Мпри преобразовании исходных слои Рв заключительные; сигнализирующая памяти (или емкое т и) определяется как количество ячеек ленты, в к-рых хотя бы раз побывала головка машины при работе над Р. Сходным образом определяются сигнализирующие времени и емкости для нормальных алгорифмов, итеративных сетей, многоголо-вочиых и многоленточных машин Тьюринга и т. п.

Общей особенностью этих двух конкретных типов сигнализирующих является наличие эффективной процедуры, позволяющей для любого алгоритма  (т. е., в частности, для машины Тьюринга, или, точнее, для ее программы), всякого исходного данного хи натурального числа tустановить, верно ли, что процесс применения  к хзаканчивается со сложностью t. Это обстоятельство положено в основу аксиоматич. построения теории сложности вычислений (см. [1]). Эффективная процедура г наз. мерой вычислений, если она: 1) всегда заканчивается результатом 0 или 1 применительно к тройкам вида (алгоритм, исходное данное, натуральное число), 2) обладает тем свойством, что для любого алгоритма  и исходного данного хравенство  верно не более чем при одном натуральном t, причем такое tсуществует тогда и только тогда, когда процесс применения a к хзаканчивается. Вводится сигнализирующая функция  по мере r для ':  тогда и только тогда, когда 

Таким образом, последнее равенство объявляется эквивалентом высказывания "сложность вычисления  на хравна t(по мере r)".

Фиксируя ту или иную меру вычислений, можно ставить задачи о сложности вычисления конкретных функций f, напр, об отыскании алгоритма , вычисляющего f "лучше других алгоритмов". Однако, как показывает теорема ускорения (см. ниже), подобная постановка не всегда правомерна, и речь может идти скорее об описании скорости роста тех сигнализирующих , для к-рых  вычисляет f [напр., об отыскании верхней и нижней границ сложности вычисления f - двух функций  таких, что существует вычисление  функции f, для к-рого  , и для всякого алгоритма , вычисляющего f, функция  в каком-то смысле мажорирует g].

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

---

Укажем нек-рые фундаментальные результаты, не зависящие от выбора меры сложности (в том числе и от выбора конкретного уточнения понятия алгоритма) - лишь бы существовала, напр., эффективная возможность взаимного моделирования алгоритмов рассматриваемого типа и обыкновенных машин Тьюринга. (Для простоты можно представить себе дело так, что речь идет о времени вычисления на машинах Тьюринга натураль-нозначных функций натурального аргумента.) Пусть Ти hсуть вычислимые натуральнозначные функции (см. Вычислимая функция).на объектах применения алгоритмов, f - функция, определенная на тех же объектах и принимающая лишь два значения (например, 0 и 1).

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

неверно лишь в ограниченном числе случаев.

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

в случае  это приводит к 

для почти всех .

Класс P

Основная статья: Класс P

Класс P вмещает все те проблемы, решение которых считается «быстрым», то есть полиномиально зависящим от размера входа. Сюда относится сортировка, поиск во множестве, выяснение связности графов и многие другие.

[править]Класс NP

Основная статья: класс NP

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

[править]Проблема равенства классов P и NP

Основная статья: Равенство классов P и NP

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

---