Теория алгоритмов
Содержание
Теория алгоритмов как раздел математики возникла в начале 30-х годов XX столетия в связи с необходимостью уточнения понятия алгоритма. Ранее, решая различные задачи, математики использовали интуитивное понятие алгоритма (см. статью “Алгоритм”). Но в связи с усложнением ставящихся задач у математиков стала возникать мысль, что не для всех задач можно найти процедуру решения, которая являлась бы алгоритмом, что впоследствии подтвердилось получением результатов о существовании алгоритмически неразрешимых проблем. Для доказательства факта отсутствия алгоритма необходимо было дать точное определение алгоритма. Ведь одно дело найти разрешающий алгоритм — это можно сделать, используя интуитивное понятие алгоритма. Другое дело — доказать несуществование алгоритма, для этого нужно знать точно, отсутствие чего мы доказываем. Попытки сформулировать такое определение привели в рамках математической логики к возникновению теории алгоритмов.
В теории алгоритмов используются различные подходы к формализации понятий алгоритма и вычислимой функции. Поиск таких подходов проходил в трех направлениях. В первом всякий алгоритм вычисляет значение некоторой числовой функции, а его элементарные шаги — это арифметические операции. Последовательность шагов определяется с помощью суперпозиции — подстановки функций в функции, рекурсии — определения значения функции через ранее вычисленные значения этой же функции, и оператора минимизации, благодаря которому из всюду определенной функции можно получить не всюду определенную вычислимую функцию. Класс функций, порождаемый этими тремя операторами, называется классом частично-рекурсивных функций. Второе направление основано на определении алгоритмического процесса как процесса, осуществимого на конкретной теоретической машине. Примерами таких алгоритмических моделей являются “машина Тьюринга” и “машина Поста”. Третье направление отвлекается от конкретных машин (т.е. в этих моделях отсутствуют понятия “память”, “состояние машины” и т.п.). Наиболее известная алгоритмическая модель этого типа — нормальные алгоритмы Маркова.
Все эти подходы привели к одному и тому же классу алгоритмически вычислимых функций. Указанные результаты составляют основу так называемой дескриптивной теории алгоритмов, основным содержанием которой является классификация задач по признаку алгоритмической разрешимости, т.е. получение высказываний типа “Задача П алгоритмически разрешима” или “Задача П алгоритмически неразрешима” (см. статью “Алгоритмически неразрешимые проблемы”). В данном направлении получен ряд фундаментальных результатов. Среди них доказательство Ю.В. Матиясевичем в 1970 году алгоритмической неразрешимости знаменитой десятой проблемы Гильберта.
Применение теории алгоритмов осуществляется как в использовании самих результатов (особенно это касается использования разработанных алгоритмов), так и в обнаружении новых понятий и уточнении старых. С ее помощью исследуются доказуемость, эффективность, разрешимость и др. Всякому алгоритму соответствует задача, для решения которой он предназначен. В обратную сторону это неверно — задача может решаться различными алгоритмами. Тем не менее задача определения эквивалентности двух алгоритмов является алгоритмически неразрешимой.
Применение ЭВМ послужило стимулом развития теории алгоритмов и изучения алгоритмических моделей, самостоятельного изучения алгоритмов с целью их сравнения по рабочим характеристикам (числу действий, расходу памяти), а также их оптимизации. Возникло важное направление в теории алгоритмов — сложность алгоритмов и вычислений. Начала складываться так называемая метрическая теория алгоритмов, основным содержанием которой является классификация задач по классам сложности. Сами алгоритмы стали объектом точного исследования, как и те объекты, для работы с которыми они предназначены.
Формальное определение алгоритма и вычисление функции *
Все задачи принято делить на два класса: задачи, связанные с вычислением функций, и задачи, связанные с распознаванием принадлежности объекта заданному множеству (или ответом на вопрос: обладает ли объект заданным свойством?). В первом случае алгоритм A вычисляет функцию fA, т.е., начав работать с входными данными x, он должен через некоторое время остановиться и выдать результат y = fA (x). Функция fA не обязательно числовая. Например, функция “телефонный справочник” может по фамилии абонента выдать его телефонный номер. Алгоритм вычисления этой функции заключается в поиске нужной фамилии в упорядоченном по алфавиту списке абонентов. Во втором случае алгоритм отвечает на вопрос: “Истинно ли высказывание x 
M?” — и выдает один из двух возможных результатов: да или нет. Мы также можем считать это функцией, принимающей два значения. Многие практические задачи включают в себя оба случая. Например, при решении квадратного уравнения сначала нужно выяснить вопрос о существовании действительных корней уравнения, и только при положительном ответе на этот вопрос вычисляются корни. Первое из понятий приводит к так называемым вычислимым функциям.
Теория вычислимых функций появилась в 1930-е годы благодаря усилиям нескольких авторов почти одновременно (под разными названиями). Возникли понятия общерекурсивной функции, -определимой функции (Черч: 1933 г., Клини: 1935 г.), вычислимой функции по Тьюрингу (Тьюринг: 1936 г., 1937 г.), представимой функции в формальной системе (Гедель: 1936 г.), комбинаторно определимой функции (Шейнфинкель, Карри, Россер: 1924–1936 гг.), а также понятия канонической системы (Пост: 1943 г.), нормального алгоритма (Марков: 1950 г.).
При всех известных подходах к формализации понятия вычислимости сначала вводится в рассмотрение множество конструктивных объектов, которые в конечном счете могут быть представлены словами конечной длины в конечном алфавите. В частности, конструктивными являются конечные натуральные числа, которые можно трактовать как слова в алфавите “0”..”9”.
Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм A, что
· если f(n) определено для какого-либо натурального n, то алгоритм A, получая на вход n, останавливается и печатает fA(n) = f(n);
· если f(n) не определено, то алгоритм A не останавливается, получив на входе n, т.е. fA(n) не определено.
Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определенная функция вычислима (в качестве A надо взять программу, которая всегда зацикливается).
Любые конструктивные объекты реального мира также можно изображать словами в различных конечных алфавитах. Это позволяет считать, что объектами работы алгоритмов могут быть только слова. Слово, которое подается на вход алгоритма, называется входным словом; слово, получаемое в результате работы алгоритма, называется выходным. Совокупность слов, к которым применим алгоритм, называется областью применимости алгоритма.
Алан Матисон Тьюринг
(Alan Mathison Turing)
Утверждение о том, что та или иная алгоритмическая модель универсальна, означает, что для любой вычислимой функции существует алгоритм, описываемый средствами этой модели. В теории алгоритмов была доказана равносильность всех известных формализаций понятия алгоритма.
До сих пор неизвестно ни одного алгоритма из числа алгоритмов, изобретенных человечеством за свою многотысячелетнюю историю, который не был бы эквивалентен ни одному из формализованных алгоритмов (например, алгоритму Маркова, машине Тьюринга или частично рекурсивной функции — функции, не являющейся всюду определенной).
Андрей Андреевич Марков
Оказалось, что все эти понятия эквивалентны между собой и каждое из них можно рассматривать в качестве одного из способов точного определения понятия алгоритма.
Машина Тьюринга и Поста
Машиной Тьюринга (МТ) называется упорядоченный набор вида {A, a0, Q, q1, q0, T, 
}, где
A — конечное множество, называемое основным алфавитом МТ,
a0 A и называется пустой буквой алфавита,
Q — конечное множество, называемое алфавитом состояний МТ,
q1 Q — начальное состояние МТ,
q0 Q — заключительное, или состояние останова МТ,
T = {Л, Н, П} — множество сдвигов МТ,
t — программа МТ, то есть
.: A x Q \ {q0} 
A x T x Q
Нетрудно убедиться, что в этом определении фигурируют только математические и логические термины (или символы), например, множество, конечное множество, элемент множества, принадлежность множеству, произведение множеств.
Для любого наугад взятого алгоритма, работающего не над словами, его объекты можно закодировать так, что они становятся словами в некотором алфавите, а суть алгоритма от этого не меняется.
Что же представляет собой машина Тьюринга? В каждой машине Тьюринга есть две части:
1) неограниченная в обе стороны лента, разделенная на ячейки;
2) головка для считывания/записи, управляемая программой.
С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов A = {a1, a2, …, am}и алфавит состояний Q = {q1, q2, …, qm}. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q.) Состояние q0 называется заключительным, или состоянием останова. Считается, что если машина попала в это состояние, то она заканчивает свою работу. Состояние называется начальным. Находясь в этом состоянии, машина начинает свою работу.
Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (в алфавит А всегда входит “пустая” буква а0 — признак того, что ячейка пуста).
Автомат может двигаться вдоль ленты влево или вправо, читать содержимое ячеек и записывать в ячейки буквы своего алфавита. Ниже схематично нарисована машина Тьюринга, автомат которой обозревает первую ячейку с данными.
Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую букву он видит, а также в зависимости от своего состояния , автомат может выполнять следующие действия:
· записать новую букву в обозреваемую ячейку;
· выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
· перейти в новое состояние.
Программа для машины Тьюринга представляет собой таблицу, в каждой клетке которой записана команда.
Клетка (qj, ai) определяется двумя параметрами — символом алфавита и состоянием машины. Команда представляет собой указание: какой символ записать в текущую ячейку, куда передвинуть головку чтения/записи, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или “Н” (неподвижен).
После выполнения очередной команды МТ переходит в состояние qk (которое может в частном случае совпадать с прежним состоянием qj). Следующую команду нужно искать в k-й строке таблицы на пересечении со столбцом, соответствующим букве, которую автомат видит после сдвига. В процессе работы автомат перескакивает из одной клетки программы, записанной в виде таблицы, в другую, пока не дойдет до клетки, в которой записано, что автомат должен перейти в состояние q0, т.е. остановиться. Будем говорить, что такие клетки содержат команду останова.
Если клеток останова в программе вообще нет или в процессе работы над входным словом МТ никогда не окажется в заключительном состоянии, то считается, что машина Тьюринга неприменима к данному входному слову. Машина Тьюринга применима к входному слову только в том случае, если, начав работу над этим входным словом, она окажется в заключительном состоянии.
Пример. Пусть требуется построить машину Тьюринга, которая прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанных в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа.
Решение. Машина должна прибавить единицу к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре. Программа для данной машины Тьюринга может выглядеть так:
Тезис Тьюринга состоит в том, что всякий алгоритм может быть реализован соответствующей машиной Тьюринга. Тезис Тьюринга является основной нематематической гипотезой теории алгоритмов, понимаемых по Тьюрингу. Одновременно этот тезис приводит к формальному определению алгоритма.
Алгоритм (по Тьюрингу) — программа для машины Тьюринга, приводящая к решению поставленной задачи.
В статье “Исполнители алгоритмов” 2 говорилось, что у каждого исполнителя есть своя система команд, свой круг задач. Тьюрингом же был описан универсальный исполнитель — машина Тьюринга, этот исполнитель способен решить любую алгоритмически разрешимую задачу. Этот фундаментальный результат был получен в то время, когда универсальных вычислительных машин еще не существовало. Более того, сам факт математического построения воображаемого универсального исполнителя позволил высказать предположение о целесообразности построения универсальной вычислительной машины, которая бы могла решать любые задачи при условии соответствующей кодировки исходных данных и разработки соответствующей программы действий исполнителя.
Почти одновременно с А.Тьюрингом (1937 г.) американский математик Эмиль Пост предложил иную абстрактную машину, характеризующуюся еще большей простотой, чем машина Тьюринга. Это строгое математическое построение было также предложено в качестве уточнения понятия алгоритма.
Эмиль Леон Пост
(Emil Leon Post)
В машине Поста в ячейках бесконечной ленты можно записывать всего два знака: 0 и 1 (ставить метку в ячейку или стирать метку). Это ограничение не влияет на ее универсальность, так как любой алфавит может быть закодирован двумя знаками. Кроме ленты, в машине Поста имеется каретка (головка чтения/записи), которая:
· умеет двигаться вперед, назад и стоять на месте;
· умеет читать содержимое, стирать и записывать 0 или 1;
· управляется программой.
Как и машина Тьюринга, машина Поста может находиться в различных состояниях, но каждому состоянию соответствует не строка состояния с клетками, а некоторая команда одного из следующих шести типов (все строки в программе пронумерованы):
1. Записать 1 (метку), перейти к i-й строке программы;
2. Записать 0 (стереть метку), перейти к i-й строке программы;
3. Сдвиг влево, перейти к i-й строке программы i;
4. Сдвиг вправо, перейти к i-й строке программы;
5. Останов;
6. Если 0, то перейти к i, иначе перейти к j.
Состояние машины — это состояние ленты и положение головки чтения/записи. Тезис Поста заключается в том, что: “Всякий алгоритм представим в форме машины Поста”. Отсюда следует другое формальное определение алгоритма.
Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи. Тезис Поста невозможно строго доказать, так же, как и тезис Тьюринга.
Как уже говорилось выше, в теории алгоритмов доказано, что машина Поста и машина Тьюринга эквивалентны по своим возможностям. Более того, для каждого неформализованного алгоритма A существует формализованный алгоритм B (например, машина Тьюринга). В этом состоит полнота формализации понятия вычислимой функции.
Универсальная функция
В теории алгоритмов установлен важный факт: во всех алгоритмических моделях всегда существует универсальный алгоритм, т.е. алгоритм, который способен моделировать работу любого другого алгоритма, описанного в этой же модели. Покажем существование универсальной функции для вычислимых функций одного аргумента.
Теорема. Существует вычислимая функция двух аргументов U, являющаяся универсальной функцией для класса вычислимых функций одного аргумента.
Алгоритм, вычисляющий саму функцию U, есть, по существу, интерпретатор для используемого языка программирования (если отождествлять программу и ее номер, то он применяет первый аргумент ко второму).
Аналогично можно ввести универсальные функции для произвольного числа аргументов. Концепция универсального алгоритма еще в 30-е годы XX века показала возможность создания универсального устройства (компьютера), способного выполнять любые алгоритмы.
Индуктивное определение объектов **
В одной из наиболее общих форм индуктивное определение какого-либо класса (множества) объектов K осуществляется по следующей схеме. 1) Задается класс исходных (атомарных, простейших) объектов A определяемого класса K [Базис индуктивного определения].) Задается система правил R, позволяющих из уже определенных (или построенных, порожденных) объектов получать (строить, порождать) новые объекты определяемого класса K [Шаг индуктивного определения]. 3) Объектами определяемого класса K считаются те и только те объекты, которые могут быть получены (построены, порождены) согласно пунктам 1) и) этого определения. При этом пункт 3) данного определения часто только подразумевается, но не формулируется явно.
С приведенным выше индуктивным определением класса объектов связан обобщенный принцип индукции (называемый также индукцией по построению объектов), который состоит в следующем. Для того чтобы доказать, что любой объект из класса, задаваемого данным индуктивным определением, обладает каким-либо свойством P, достаточно доказать, во-первых, что каждый исходный (атомарный, простейший) объект, задаваемый пунктом 1) данного индуктивного определения, обладает этим свойством P [Базис индукции], и, во-вторых, что этим свойством P будет обладать любой объект, который может быть получен (построен, порожден) по какому-либо правилу пункта) данного индуктивного определения, из объектов, уже обладающих этим свойством P [Шаг индукции].
Пример 1. Индуктивное определение класса высказывательных формул, принятое в математической логике (см. “Логические выражения”).
Мы предполагаем, что нам дано множество высказывательных переменных: p1, p2, ..., pn, ... , а также символы логических операций: 
(конъюнкция), 
(дизъюнкция), 
(импликация), 
(эквивалентность), 
(отрицание). Теперь мы даем следующее индуктивное определение:
1) Высказывательные переменные: p1, p2, ..., pn, ... считаются формулами (атомарными формулами) [Базис индуктивного определения].
2) Если 
и 
какие-то уже построенные высказывательные формулы, то формальные выражения 
— также высказывательные формулы.
3) Высказывательными формулами считаются те и только те формальные выражения, которые могут быть построены согласно пунктам 1) и) этого определения.
Пример 2. Индуктивное определение класса термов (говоря нестрого, терм — это формальный аналог имени существительного).
Мы предполагаем, что нам даны попарно непересекающиеся множества:
1) множество предметных переменных: x1, x2, ..., xn, ... ,
2) множество предметных констант: c1, c2, ..., cn, ... , а также
3) для каждого целого положительного n нам дано множество символов n-местных функций f1n, f2n, ..., fkn, ... ,.
Теперь мы даем следующее индуктивное определение класса термов.
1) Предметные переменные x1, x2, ..., xn, ... и предметные константы c1, c2, ..., cn, ... считаются термами (и притом атомарными термами) [Базис индуктивного определения].
2) Для любых целых положительных чисел n и k, если t1, t2, ..., tn — какие-либо n уже построенных термов, то формальное выражение fkn(t1, t2, ..., tn ) также является термом.
3) Термами считаются те и только те формальные выражения, которые могут быть получены (построены, порождены) согласно пунктам 1) и) этого определения.
Это определение используется, в частности, для построения грамматик различных языков программирования (см. “Языки программирования”).
Сложность алгоритма
Сложность алгоритма — это количественная характеристика, которая говорит либо о том, сколько времени он работает (временная или вычислительная сложность), либо о том, какой объем памяти он использует. Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого алгоритма.
Вычислительная сложность алгоритма — количество элементарных шагов в вычислительном процессе этого алгоритма. Обратите внимание: именно в вычислительном процессе, а не в самом алгоритме. Очевидно, для сравнения сложности разных алгоритмов необходимо, чтобы сложность подсчитывалась в одних и тех же элементарных действиях.
Временная сложность алгоритма — это время Т, необходимое для его выполнения. Оно равно произведению числа элементарных действий на среднее время выполнения одного действия: Т = kt. Поскольку t зависит от исполнителя, реализующего алгоритм, то естественно считать, что сложность алгоритма в первую очередь зависит от k. Очевидно, что в наибольшей степени количество операций при выполнении алгоритма зависит от количества обрабатываемых данных. Действительно, для упорядочивания по алфавиту списка из 100 фамилий требуется существенно меньше операций, чем для упорядочивания списка из 100 000 фамилий. Поэтому сложность алгоритма выражают в виде функции от объема входных данных. Пусть есть алгоритм А. Для него существует параметр n, характеризующий объем обрабатываемых алгоритмом данных, этот параметр часто называют размерностью задачи. Обозначим через T(n) время выполнения алгоритма, через f — некую функцию от n.
Будем говорить, что T(n) алгоритма имеет порядок роста f (n) при n 
, или, по-другому, алгоритм имеет теоретическую сложность O (f (n)) (читается “о большое от f (n)”), если найдется такая константа с > 0 и число n0, что T(n) 
сf (n) при всех n 
n 0. Здесь предполагается, что f (n) неотрицательно, по крайней мере при n n0.
Так, например, алгоритм, выполняющий только операции чтения данных и занесения их в оперативную память, имеет линейную сложность O(n). Алгоритм сортировки методом “пузырька” (см. “Операции с массивами”) имеет квадратичную сложность O (n2), так как при сортировке любого массива надо выполнить (n 2 - n)/2 операций сравнения (при этом операций перестановок вообще может не быть, например, на упорядоченном массиве).
Для решения задачи могут быть разработаны алгоритмы различной сложности. Логично воспользоваться лучшим среди них, т.е. имеющим наименьшую сложность.
Сложность алгоритма по памяти определяется числом ячеек памяти, используемых в процессе его работы. Число шагов алгоритма может сколь угодно сильно превосходить объем памяти за счет циклов по одним и тем же объектам. Поэтому временная сложность считается основной характеристикой алгоритма.
Методические рекомендации
Материал данной темы носит теоретический характер и достаточно сложен для понимания. Он включен в Стандарт профильной школы. Цель раскрытия данной темы — проследить вместе со школьниками цепочку
формальное определение алгоритма алгоритмически неразрешимые задачи вычислимые функции универсальный исполнитель
Проще всего объяснить школьникам формальное определение алгоритма можно с помощью машины Поста или машины Тьюринга. Полезно рассмотреть и примеры решения задач с помощью одной из этих машин. Программирование машины Поста учащимся дается легче, чем программирование машины Тьюринга. Во-первых, это связано с тем, что все действия, выполняемые машиной Поста, прописаны в командах, которые выполняются в привычном нам порядке (последовательное выполнение + условный переход) (не надо блуждать по таблице-программе машины Тьюринга). В пользу машины Поста говорит простота ее описания (хотя многие задачи в силу ограниченных возможностей машины по сравнению с машиной Тьюринга решать становится сложнее), а в пользу машины Тьюринга — то, что на ее примере учащиеся могут познакомиться с таким новым для них и очень важным понятием, как конечный автомат.
Полезным может оказаться и выполнение упражнений на индуктивное определение объектов. Зачастую это единственный способ достаточно просто описать не только весьма непростые вещи, такие, как грамматика языка программирования, но и арифметические или логические выражения. Индуктивные определения объектов непосредственно связаны с рекурсивными описаниями подпрограмм в языках программирования.
В теории алгоритмов важным является и следующий факт: в любой алгоритмической модели всегда существует универсальная вычислимая функция, т.е. алгоритм, который способен моделировать работу любого другого алгоритма, описанного в этой же модели. Этот результат, установленный еще в 30-е годы прошлого века, показывает, что в основе работы компьютера как универсального вычислителя лежат не только физические, но и математические принципы.
После введения точного определения алгоритма в разных областях математики стали обнаруживать алгоритмически неразрешимые проблемы. Знание примеров неразрешимостей предостерегает от увлечения глобальными проектами всеобщей алгоритмизации точно так же, как знание основных законов физики предостерегает от попытки создать вечный двигатель.
Понятие сложности алгоритма позволяет сравнивать алгоритмы между собой, а также ставит проблему решения так называемых “переборных задач”, число действий в алгоритме решения которых выражается так называемой “экспоненциальной функцией”, например, 2n, n! или даже nn. Использование таких алгоритмов возможно лишь для маленьких значений n (приблизительно 20, 10 и 7 для приведенных функций для 1 секунды работы современного персонального компьютера). Причем увеличение производительности компьютера или времени счета в 100 раз приводит к увеличению возможной размерности задачи приблизительно на 7, 2 и 2 соответственно. То есть для больших размерностей такие алгоритмы не только не применимы сейчас, но и не будут применимы в обозримом будущем.
* Использованы материалы энциклопедии “Информатика” под ред. Д.А. Поспелова и книги Е.В. Андреевой, Л.Л. Босовой, И.Н. Фалиной “Математические основы информатики”, а также материалы, подготовленные Г.И. Сыркиным.
** Автором данного пункта является Г.И. Сыркин.
