Теория алгоритмов

ТЕМА ТЕОРИЯ АЛГОРИТМОВ Теория алгоритмов – это раздел математики, который изучает общие свойства алгоритмов. Различают качественную и метрическую теорию алгоритмов. Основной проблемой качественной теории алгоритмов является проблема построения алгоритма, обладающего заданными свойствами (ее называют алгоритмической). Метрическая теория алгоритмов исследует алгоритмы с точки зрения их сложности (алгоритмическая теория сложности). Алгоритм – это общий, единообразный, точно установленный способ решения любой задачи из данной массовой проблемы. Приведенное понятие алгоритма нестрогое. Характерные черты алгоритма: - дискретность – каждая последующая величина получается из значений предыдущей по определенному закону; - детерминированность – последующие значения величин зависят от предыдущих; - элементарность шагов алгоритма – закон получения последующей системы величин из предшествующей должен быть простым; - массовость – начальные условия могут варьироваться в бесконечных пределах; - результативность – конечный результат всегда должен быть получен. В уточнении понятия алгоритма выделяются три направления: 1. Уточнение понятия эффективно вычислимой функции. В результате был выделен класс частично математическое определение. рекурсивных функций, имеющих строгое 2. Машинная раскрывается арифметика. путем Здесь рассмотрения сущность процессов, понятия алгоритма осуществляемых в вычислительной машине. 3. Направление, связанное с понятием нормальных алгоритмов из работ А. Маркова. Первое направление – уточнение понятия алгоритма – связано с точным описанием специального класса функций, называемых рекурсивными. Функция y = f (x1, x2, …, xn) называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения. Простейшие эффективно вычислимые функции: 1. λ (x) = x + 1 – оператор сдвига; 2. О(х) = 0 – оператор аннулирования; 3. Inm f (x1, x2, …, xn) = xm, 1≤m≤n – оператор проектирования. Совокупность вычислимых функций, удовлетворяющих характерным чертам алгоритма, называется совокупностью рекурсивных функций. Примитивно-рекурсивными функциями называются функции, полученные по схеме примитивной рекурсии: Пусть имеются две функции φ ( x2, …, xn) и ψ (x1, x2, …, xn+1 ), n>1. 𝑓(0,x ,x ,...,x )=ϕ(𝑥2 ,x ,...,x ) 3 𝑛 3 𝑛 Определим новую функцию {𝑓(y+1,x ,x ,...,x2 )=ψ(y,f(y,x } ,x ,...,x ),x 2 3 𝑛 𝑛 2 ,x3 ,...,x𝑛 ), 2 3 где функция φ зависит от n-1 аргументов, ψ – от n+1 аргумента, а примитивнорекурсивная функция f – от n аргументов. Функция y = f (x1, x2, …, xn) называется частично рекурсивной, если она может быть получена за конечное число шагов из трех простейших эффективновычислимых функций при помощи операции суперпозиции, схем примитивной рекурсии и операции минимизации. Функция y = f (x1, x2, …, xn) называется общерекурсивной, если она частично рекурсивна и всюду определена. При доказательстве примитивной рекурсивности функций можно использовать не только три простейших эффективно-вычислимых функции, но и те функции, рекурсивность которых уже доказана. Например, операцию сложения F(x, y) = x + y. Задача №1. Доказать, что функция f(x) = 2 x примитивно-рекурсивная. Так как заданная функция f(x) есть функция одного аргумента, то для использования операции примитивной рекурсии мы должны иметь функцию φ, зависящую от 1 аргумента, т.е. константу, и ψ – зависящую от 2 аргументов. Имеем: 𝑓(0) = 20 = 1, { } 𝑓(x+1) = 2x+1 = 2 ⋅ 2𝑥 = 2 ⋅ 𝑓(𝑥). Первая из этих функций есть функция константы φ ( x ) = 1, а вторая ψ (x, y) = 2y – функция двух аргументов. Проверим, что функции выбраны правильно. Из определения операции примитивной рекурсии, имеем: f ( 0 ) = φ ( 0 ) = 1, f ( 1 ) = 2 f ( 0 ) = 2, f ( 2 ) = 2 f ( 1 ) = 4, f ( 3 ) = 2 f ( 2 ) = 8, … Следовательно, f ( x ) = 2 x. Второе направление, связанное с машинной арифметикой, заключается в том, что алгоритмические процессы могут имитироваться на подходяще построенных машинах, которые описываются в точных математических терминах. Машиной Поста или машиной Тьюринга называется абстрактная машина, которая «механически» выполняет вычисления. Тезис Тьюринга: для всякой вычислимой функции может быть построена машина Тьюринга. Машина Тьюринга представляет собой бесконечную в обе стороны ленту, разбитую на ячейки. В каждой ячейке ленты может быть записан один из символов алфавита А = {a0, a1, a2, …, am }, называемого внешним алфавитом машины М. Один из символов алфавита А выделяют, например, а 0 и называют его пустым. Часто этот символ обозначают также как 0, λ или Ø. Его наличие в ячейке означает, что она пустая. Кроме того, машина М имеет универсальную головку (УГ), которая в каждом такте работы машины обозревает одну ячейку ленты. По сигналам с устройства управления (УУ) универсальная головка обозревает символ, записанный в ячейке, либо записывает один из символов алфавита А в ячейку. По сигналам с УУ головка может перемещаться вдоль ленты на одну ячейку вправо, влево или оставаться на месте. УУ машины М управляет всеми процессами в машине и может находиться в одном из состояний множества Q = { q0, q1, …, qn }. Множество Q называют внутренним алфавитом машины М. В этом множестве выделяют два символа: q0 – заключительное состояние машины и q1 – начальное состояние машины. Схематически устройство машины Тьюринга представлено на рисунке. УГ УУ Работа машины происходит по программе, состоящей из отдельных команд. Структура команды имеет вид: ak qi → aj ql W, где ak – символ, обозреваемый головкой на ленте; qi – состояние, в котором находится УУ машины; aj – символ, который УГ записывает в обозреваемую ячейку; ql – состояние, в которое переходит УУ машины; W – команда перемещения головки. Это может быть один из следующих символов: R – перемещение вправо на одну ячейку, L – влево на одну ячейку, S – головка остается на месте. Построить машину Тьюринга – означает написать программу ее работы. Существуют различные варианты построения машины Тьюринга: одно-, двух- и многоленточные, используются различные алфавиты. В дальнейшем рассмотрении и при выполнении контрольной работы будем полагать, что алфавит машины Тьюринга состоит из двух символов: { 0, | }, где 0 – пустой символ, а | («вертикальная черта») – символ занятости ячейки. В этом алфавите любое целое неотрицательное число х представляется х+1 символами |, записанными в соседних ячейках ленты. В этом случае число 0 будет записано так: …0|0… Для сокращения записи число х записывают также следующим образом: … 0 | x+1 0 … Композицией машин Тьюринга М1 и М2 называется машина Тьюринга М, которая первоначально функционирует как машина Тьюринга М 1, заключительное состояние которой q0 изменяют на начальное состояние машины Тьюринга М2. И далее машина М функционирует как машина Тьюринга М 2. Композицию машин Тьюринга обозначают: М = М1 ◦ М2. Задача №2. Имеется машина Тьюринга с внешним алфавитом А = { 0, | }, алфавитом внутренних состояний Q = { q0, q1 } и программой, записанной в виде последовательности из двух команд: q1 0 → q0 | , q1 | → q1 | R. Определите, в какое слово перерабатывает машина слово | 0 | | 0 0 | |, если она находится в начальном состоянии q1 и обозревает ячейку 4, считая слева. Изобразим схематически начальную конфигурацию машины: q1 | | | | | Схема означает, что машина находится в состоянии q1 и обозревает ячейку, в которой записан символ |, в соседней ячейке слева записан тот же символ, а в соседней ячейке справа ничего не записано и т.д. На первом такте работы согласно команде q1 | → q1 | R машина остается в прежнем состоянии 1, в обозреваемую ячейку вписывает символ | и переходит к обозрению следующей ячейки справа. Изобразим схематически положение, в котором оказалась машина: q1 | | | | | На втором такте работы согласно команде q1 0 → q0 | машина записывает в обозреваемую ячейку 5 символ |, продолжает обозревать ту же ячейку и переходит в состояние q0, т.е. останавливается. Создавшаяся конфигурация имеет вид: q1 | | | | | | Таким образом, из данного начального положения слово | 0 | | 0 0 | | перерабатывается машиной в слово | 0 | | | 0 | | . Задача №3. Построить машину Тьюринга с внешним алфавитом А = { 0, | }, вычисляющую функцию f(x) = x + y, исходя из предположения, что перед началом работы на ленте машины записаны исходные значения аргументов и универсальная головка (УГ) обозревает первый слева значащий символ, а после выполнения вычислений УГ останавливается перед первым значащим символом результата. Аргументы функции записаны на ленте машины в виде последовательности символов «|» (х+1 символ – для первого аргумента и у+1 символ – для второго аргумента) и отделяются друг от друга пустым символом. q1 | | … | | | | … | | Определим способ функционирования машины Тьюринга для получения результата. Поскольку результат представляет собой массив занятых ячеек числом х+у+1, определяющих число х+у, машина будет читать символы первого аргумента х, оставляя их неизменными. Как только машина прочтет пустой символ, разделяющий два аргумента, в ячейку, содержащую этот символ, будет записан символ «|». В результате на ленте будет получен сплошной массив занятых ячеек. Число занятых ячеек: х+1+у+1+1, очевидно, не две больше, чем необходимо для представления результата – суммы двух чисел. Одна «лишняя» ячейка будет занятой, так как машина заполнит пустую ячейку, разделяющую первоначально два аргумента. Далее, для представления каждого числа используется один дополнительный символ «|». Поэтому при объединении двух массивов занятых ячеек, представляющих два числа, один из дополнительных символов «|» следует удалить. Таким образом, после заполнения пустой ячейки, разделяющей два аргумента, машина должна вернуться к началу полученного сплошного массива занятых ячеек ленты и в две из них записать пустой символ, после чего остановиться напротив первой слева занятой ячейки. Программа работы машины имеет следующий вид: | q1 → | q1 R 0 q1 → | q2 L | q2 → | q2 L 0 q2 → 0 q3 R | q3 → 0 q4 R | q4 → 0 q0 R Рассмотрим, что означают состояния, в которые переходит устройство управления в процессе работы машины. Когда машина находится в состоянии q1 и читает символ «|», то это состояние означает чтение ячеек, занятых аргументом х. Как только, находясь в состоянии q1, будет прочитана пустая ячейка, машина перейдет в состояние q2. Это состояние означает, что машина читает ячейки, занятые полученным сплошным массивом ячеек ленты. Когда, находясь в состоянии q2, машина прочитает пустую ячейку, УУ перейдет в состояние q3. Это состояние означает, что головка машины уже нашла первую пустую ячейку перед сплошным массивом занятых ячеек и движется вправо, чтобы записать пустой символ вместо символа «|». Наконец, состояние q4 означает, что удален только один из двух символов «|». Состояние q0 – заключительное.