Алгоритмы

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

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

Например, решение квадратного уравнения:

1. Привести уравнение в каноническую форму \(a x^2 + b x + c = 0\)
2. Если \(a=0\), то это линейное уравнение с решением \(x=\frac{-c}{b}\). Задача решена. Иначе, перейти к шагу 3.
3. Вычислить дискриминант \(D=b^2-4 a c\)
4. Вычислить решения уравнения \(x_{1,2} = \frac{-b\pm\sqrt{D}}{2 a}\). Задача решена.

Можно ввести следующее интуитивное понятие алгоритма:

Алгоритм

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

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

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

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

Выделяются следующие свойства алгоритмов:

Дискретность

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

Детерминированность

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

Понятность

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

Конечность

алгоритм должен завершаться за конечное число шагов.

Массовость

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

Результативность

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

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

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

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

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

Строгое определение алгоритма

Определение алгоритма, приведенное выше, не является строгим. Это создает некоторые трудности. В частности, с таким определением невозможно строго доказать, является ли данный класс задач решаемым при помощи алгоритма.

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

В 20-30 годах XX века, над проблемой строгого определения алгоритма работали разные математики, в частности Алан Тьюринг, Эмиль Леон Пост, Андрей Андреевич Марков, Андрей Николаевич Колмогоров, Алонзо Чёрч и другие. Их работа в итоге привела к возникновению и развитию теории алгоритмов, теории исчислимости и различных подходов к исчислению, и, кстати, программированию в целом. Одним из результатов их работы стало появление нескольких строгих определений алгоритма, введенных различным образом, но эквивалентных друг другу.

Мы подробно остановимся на определении Тьюринга, и поверхностно разберем эквивалентные определения Поста, Чёрча и Маркова.

Машина Тьюринга

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

Алан Тьюринг (1912-1954)

Английский математик, логик, криптограф, возможно первый в мире “хакер”, стоял у истоков информатики и теории искуственного интеллекта. Внес существенный вклад в победу союзных войск во второй мировой войне.

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

Результатом работы машины Тьюринга так же являются слова.

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

Набор слов, к которым применим алгоритм, называется областью применимости алгоритма.

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

Описание машины Тьюринга

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

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

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

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

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

Команда, в свою очередь, может иметь следующую структуру:

\[ a_k \left\lbrace \begin{matrix} Л \\ Н \\ П \end{matrix}\right\rbrace q_m \]

Сначала идет символ алфавита, который должен быть записан в текущую ячейку \(a_k\), затем, указывается перемещение автомата влево (Л), вправо (П) или никуда (остаться на месте, Н). В конце указывается новое состояние, в которое должен перейти автомат \(q_m\).

Ячейка таблицы, ясно, определяется текущим символом \(a_i\) и текущим состоянием автомата \(q_j\).

Условимся, что в начале работы, машина Тьюринга находится в начальном состоянии, обозначаемом \(q_1\), а при переходе в состояние останова \(q_0\) работа алгоритма завершена и машина останавливается.

Пример

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

Будем считать, что в начальном состоянии автомат находится слева от входного слова.

Тогда, описательно, алгоритм можно сформулировать следующим образом:

1. Перемещаясь вправо, найти начало входного слова
2. Перемещаясь вправо, найти конец входного слова
3. Прибавить один к текущему разряду входного слова. Если там цифра от 0 до 8, завершить работу. Иначе, записать 0, переместиться влево, и вернуться к шагу 3.

Запишем этот алгоритм в виде таблицы. Алфавит состоит из цифр от 0 до 9 и “пустого символа” \(\Lambda\). Так же нам потребуется 4 состояния автомата, считая состояние останова, соответствующих шагам описания алгоритма.

Условимся, что начальное состояние \(1\) – поиск начала входного слова, \(2\) – поиск конца входного слова, \(3\) – прибавление 1.

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

В состоянии 1, автомат находится над пустой ячейкой. Соответствующая команда из таблицы “ΛП1”, то есть, оставить ячейку пустой, переместиться вправо и остаться в состоянии 1:

Теперь автомат наблюдает значение “1”. Соотвествующая команда “1Н2”, то есть оставить в ячейке “1”, не перемещаться, и перейти в состояние “2”:

В состоянии “2”, автомат наблюдает значение “1”. Соответствующая команда “1П2”, то есть оставить “1”, переместиться вправо и остаться в состоянии “2”:

Аналогично, команда для состояния “2” и символа “9” – “9П2”:

Ситуация повторяется:

Наконец, в состоянии 2 автомат наблюдает пустой символ. Команда “ΛЛ3”:

Теперь, в состоянии 3 и наблюдая символ “9”, автомат выполняет команду “0Л3”:

Ситуация повторяется:

Наконец, выполняется команда “2Н0”:

Состояние “0” – состояние остановки. Работа алгоритма завершена.

Формальное описание

Математически, машину Тьюринга можно описать следующим образом:

Машина Тюринга (МТ)

это система вида \(\{A, a_0, Q, q_1, q_0, T, \tau\}\), где

• \(A\) – конечное множество символов алфавита МТ
• \(a_0 \in A\) – пустой символ алфавита
• \(Q\) – конечное множество состояний МТ
• \(q_1 \in Q\) – начальное состояние МТ
• \(q_0 \in Q\) – конечное состояние МТ (состояние останова)
• \(T = \{Л, П, Н\}\) – множество сдвигов МТ
• \(\tau\) – программа МТ, то есть функция, задающая отображение \(\tau: A\times Q\backslash \{q_0\} \rightarrow A\times T \times Q\)

Ключевым в теории алгоритмов является тезис Тьюринга.

В вольной формулировке, тезис Тьюринга формулируется следующим образом:

Тезис Тьюринга

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

иначе, для любого алгоритма существует эквивалентная ему машина Тьюринга.

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

Альтернативные определения алгоритма

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

В частности, определение через машину Поста, через лямбда-исчисление Чёрча, нормальный алгоритм Маркова.

Рассмотрим эти способы.

Машина Поста

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

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

В остальном, машина Поста аналогична машине Тьюринга: есть автомат, и есть бесконечная лента с ячейками.

Машина Поста может выполнять следующие команды:

1. Записать 1, перейти к i-той строке программы
2. Записать 0, перейти к i-той строке программы
3. Выполнить сдвиг влево, перейти к i-той строке программы
4. Выполнить сдвиг вправо, перейти к i-той строке программы
5. Условный переход: если в наблюдаемой ячейке 0, перейти к i-той строке программы, иначе – перейти к j-той строке программы.
6. Останов.

Так же машина Поста имеет несколько запрещенных команд:

1. Запись в ячейку 1, когда там уже 1.
2. Запись в ячейку 0, когда там уже 0.

Подобные события приводят к аварийному завершению работы.

Для написания программ для машины поста можно использовать следующие обозначения:

1. ∨ i – записать 1, перейти к i-той строке программы
2. × i – записать 0, перейти к i-той строке программы
3. ← i – выполнить сдвиг влево, перейти к i-той строке программы
4. → i – выполнить сдвиг вправо, перейти к i-той строке программы
5. ? i; j – условный переход: если в наблюдаемой ячейке 0, перейти к i-той строке программы, иначе – перейти к j-той строке программы.
6. ! – останов.

Пример программы:

1. → 2
2. ? 1; 3
3. × 4
4. ← 5
5. !

Эта программа сотрет первую метку (1), находящуюся справа от начального положения автомата, и остановит автомат в ячейке слева от нее.

По большому счету, машина Поста является предшественником императивных языков программирования, например, C, Fortran и пр.

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

Одним из важных следствий этой эквивалентности является то, что любой алфавит можно свести к двоичному коду.

Аналогично тезису Тьюринга, существует так же и тезис Поста.

Тезис Поста

всякий алгоритм представим в виде машины Поста.

Нормальный алгоритм Маркова

Нормальные алгоритмы Маркова предназначены для применения к словам в различных алфавитах.

Определение всякого нормального алгоритма состоит из двух частей:

1. Алфавита алгоритма
2. Схемы алгоритма

Сам алгоритм применяется к словам, то есть последовательностям символов алфавита.

Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются выражения вида \(L\to D\), где \(L\) и \(D\) – два произвольных слова, составленных из алфавита алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются выражения вида \(L\to\cdot D\), где \(L\) и \(D\) – два произвольных слова, составленных из алфавита алгоритма.

При этом предполагается, что вспомогательные символы \(\to\) и \(\to\cdot\) не принадлежат алфавиту алгоритма.

Процесс применения нормального алгоритма к произвольному слову \(V\) представляет собой следующую последовательность действий:

1. Пусть \(V'\) – слово, полученное на предыдущем шаге работы алгоритма (или исходное слово, если текущий шаг является первым).
2. Если среди формул подстановки нет такой, левая часть которой входила бы в \(V'\), то работа алгоритма считается завершенной, и результатом этой работы считается слово \(V'\).
3. Иначе среди формул подстановки, левая часть которых входит в \(V'\), выбирается самая первая.
4. Из всех возможных представлений слова \(V'\) в виде \(RLS\) (где \(R\)– префикс, а \(L\) – суффикс) выбирается такое, при котором \(R\) – самое короткое, после чего выполняется подстановка \(V'=RDS\).
5. Если формула подстановки была конечной, то алгоритм завершен с результатом \(V'\). Иначе, переход к пункту 1 (следующему шагу).

Любой нормальный алгоритм эквивалентен некоторой машине Тьюринга, и наоборот – любая машина Тьюринга эквивалентна некоторому нормальному алгоритму.

Аналог тезиса Тьюринга для нормальных алгоритмов принято называть принципом нормализации.

Пример

Данный алгоритм преобразует двоичные числа в “единичные” (в которых записью целого неотрицательного числа N является строка из N палочек). Например, двоичное число 101 преобразуется в 5 палочек: |||||.

Алфавит:

{ 0, 1, | }

Правила:

1. 1 → 0|
2. |0 → 0||
3. 0 → (пустая строка)

Исходная строка:

101

Выполнение:

1. 0|01
2. 0|00|
3. 00||0|
4. 00|0|||
5. 000|||||
6. 00|||||
7. 0|||||
8. |||||

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

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

• примитивно рекурсивные функции
• общерекурсивные функции
• частично рекурсивные функции

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

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

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

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

К базовым функциям относятся:

• Нулевая функция \(O()=0\) – функция без аргументов, которая всегда возвращает \(0\).
• Функция следования \(S(x)=x+1\) – функция, которая любому натуральному числу \(x\) ставит в соответствие следующее число \(x+1\)
• Функции \(I_n^m(x_1,\ldots,x_n) = x_m\), где \(0<m\leq n\) – функции от \(n\) переменных, которые любому набору натуральных чисел \(x_1, \ldots, x_n\) ставят в соответствие число \(x_m\) из этого набора.

Для конструирования остальных функций класса используются операторы:

• Подстановки. Для функции \(f\) от \(m\) переменных и \(m\) функций \(g_1,\ldots,g_m\) от \(n\) переменных каждая, результатом подстановки \(g_k\) в \(f\) является функция \(h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n))\) от \(n\) переменных.
• Примитивной рекурсии. Пусть \(f(x_1,\ldots,x_n)\) – функция от \(n\) переменных, а \(g(x_1,\ldots,x_{n+2})\) – функция от \(n+2\) переменных. Тогда результатом применения оператора примитивной рекурсии к функциям \(f\) и \(g\) является функция \(h\) от \(n+1\) переменной вида: \[ h(x_1,\ldots,x_n,0) = f(x_1,\ldots,x_n) \] \[ h(x_1,\ldots,x_n,y+1) = g(x_1,\ldots,x_n, y, h(x_1,\ldots,x_n,y)) \]

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

Класс частично рекурсивных функций включает примитивно рекурсивные функции, и, плюс к этому, все функции, которые получаются из примитивно рекурсивных с помощью оператора минимизации аргумента:

Оператор минимизации аргумента

Пусть \(f\) – функция от \(n\) переменных \(x_i \in \mathbb{N}\). Тогда результатом применения оператора минимизации аргумента к функции \(f\) является функция \(h\) от \(n-1\) аргумента, определяемая как:

\[ h(x_1,\ldots,x_{n-1}) = \min y, \] где \[f(x_1,\ldots,x_{n-1},y)=0.\] То есть, \(h\) возвращает минимальное значение последнего аргумента функции \(f\) при котором значение \(f\) равно нулю.

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

Более строго частично рекурсивные функции следовало бы называть “частично определенные рекурсивные функции”, поскольку они определены только на части возможных значений аргументов.

Общерекурсивные функции

Общерекурсивные функции – это подкласс всех частично рекурсивных функций, которые определены для любых значений аргументов. Задача определения того, является ли данная частично рекурсивная функция общерекурсивной является алгоритмически неразрешимой. Это подводит нас к теме теории вычислимости и проблеме останова.

Теория вычислимости и проблема останова

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

Исследованием таких задач занимается теория вычислимости.

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

Проблема останова

По описанию алгоритма A и входным данным \(x\) необходимо выяснить, остановится ли алгоритм \(A\) на входных данных \(x\).

Проблема останова является алгоритмически неразрешимой. Докажем это.

\(\Delta\)

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

В силу существования универсального алгоритма решения проблемы останова, существует алгоритм, который определяет, остановится ли алгоритм из упомянутого класса на собственном тексте, или нет. Обозначим такой алгоритм \(B\).

Построим алгоритм \(C\), входными данными для которого является текст алгоритма \(A\), обрабатывающего свой текст:

1. Выполнить алгоритм \(B\) над \(A\).
2. Если алгоритм \(B\) определил, что \(A\) остановится на своем тексте, перейти к шагу 1. Иначе – к шагу 3.
3. Конец алгоритма \(C\).

Попытавшись применить алгоритм \(C\) к алгоритму \(C\), придем к очевидному противоречию: если \(C\) остановится на собственном тексте, то он не может остановиться, и наоборот. Следовательно, не существует алгоритма \(B\). \(\blacksquare\)

Более общей формулировкой проблемы останова является проблема определения выводимости.

Проблема распознавания выводимости

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

Существует ли для любых двух слов \(R\) и \(S\) дедуктивная цепочка, ведущая от \(R\) к \(S\) в рамках данного логического исчисления?

В 1936 году Алонзо Чёрч доказал теорему Чёрча.

Теорема Чёрча

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

Чёрч использовал для доказательства формализм лямбда-исчисления. В 1937 независимо от него ту же теорему доказал Тьюринг, используя формализм машины Тьюринга.

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

Вычислимая функция

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

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

Пример невычислимой функции

Возьмем функцию \(h(n)\), определенную для \(\forall n \in \mathbb{N}\) следующим образом:

\[ h(n) = \begin{cases} 1, & \text{если в }\pi\text{ есть последовательность из ровно }n\text{ 9-к} \\ 0, & \text{в противном случае} \end{cases} \]

Мы можем получить значение \(1\) для этой функции, однако, чтобы получить значение \(0\), нужно проверить бесконечное десятичное разложение числа \(\pi\), что, очевидно, невозможно за конечное время. Эта функция, таким образом, является невычислимой.