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

1) совокупность возможных исходных данных;

2) совокупность возможных результатов;

3) совокупность возможных промежуточных результатов;

4) правило начала;

5) правило непосредственной переработки;

6) правило окончания;

7) правило извлечения результата.

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

Алгоритмы прослеживаются в математике в течение всего времени ее существования. Общее понятие алгоритма сформировалось, однако, лишь в 20 веке и впервые появилось в трудах Э. Бореля (1912) и Г. Вейля (1921). Началом систематической разработки теории алгоритмов можно считать 1936 год, когда А.Черч опубликовал первое понятие вычислимой функции и привел первый пример функции, не являющейся вычислимой, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, машин Тьюринга), их конструкции во многом предвосхитили идеи, заложенные в основу современных цифровых вычислительных машин. В дальнейшем теория алгоритмов получила развитие в трудах С. Клини, Э. Поста, А.А. Маркова, А.Н. Колмогорова и других. В частности, А.А. Марков предложил уточнять понятие алгоритма с помощью введенного им понятия нормального алгорифма. Наиболее общий подход к уточнению понятия алгоритма предложил А.Н. Колмогоров: трактовать конструктивные объекты как топологические комплексы определенного вида, что дало возможность уточнить свойство "локальности" преобразования.

Областью применимости² алгоритма называется совокупность тех объектов, к которым он применим, т.е. в применении к которым дает результат.  Про алгоритм А говорят, что он

1) "вычисляет функцию f", коль скоро его область применимости совпадает с областью определения f, и А перерабатывает всякий x из своей области применимости в f(x);

2) "разрешает множество A относительно множества X", коль скоро он применим ко всякому x из X, и перерабатывает всякий x из XA в слово "да", а всякий x из X\A - в слово "нет";

3) "перечисляет множество B", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть B.

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

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

Имеют место следующие основные теоремы:

·        функция f вычислима тогда и только тогда, когда перечислим ее график;

·        Подмножество A перечислимого множества X тогда и только тогда разрешимо относительно X, когда A и X\A перечислимы;

·        Если A и B перечислимы, то AB и AB также перечислимы;

·        В каждом бесконечном перечислимом множестве X существует перечислимое подмножество с не перечислимым дополнением;

·        Для каждого бесконечного перечислимого множества X существует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем X.

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

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

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

Неразрешимые алгоритмические проблемы встречаются: в алгебре (проблема тождества для полугрупп и, в частности, групп; первые примеры полугрупп с неразрешимой проблемой тождества были найдены в 1947 году независимо А.А. Марковым и Э. Постом,      а пример группы с неразрешимой проблемой тождества - в 1952 году П.С. Новиковым); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 году А.А.Марковым); в теории чисел (проблема разрешимости диофантовых уравнений, неразрешимость которой была установлена в 1970 Ю.В. Матиясевичем) и в других разделах математики.

Теория алгоритмов тесно связана:

1) с математической логикой, поскольку в терминах теории алгоритмов может быть изложено одно из центральных понятий математической логики - понятие исчисления (и потому, например, теорема Геделя о неполноте формальных систем может быть получена как следствие теорем теории алгоритмов);

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

3) с кибернетикой, в которой важное место занимает изучение алгоритмов управления;

4) теория алгоритмов образует теоретический фундамент для рядя вопросов вычислительной математики

Прежде чем дать математическое (формальное) определение понятия алгоритма, постараемся придать более точный смысл его содержательному описанию. Будем считать, что допустим алгоритм, пригодный для решения бесконечного множества задач так же, как алгоритм, решающий только одну задачу, и даже алгоритм, не решающий ни одной задачи. Процесс выполнения алгоритма должен состоять из отдельных шагов. Под шагом понимают выполнение некоторой операции. Этот процесс, состоящий из отдельных шагов, может либо заканчиваться после конечного числа шагов получением искомого результата, либо после конечного числа шагов останавливаться из-за невозможности выполнения операции, либо неограниченно продолжаться. В первом случае мы будем говорить, что процесс потенциально осуществим⁴ (так как реально он может быть и не осуществим из-за слишком большого числа шагов или из-за слишком большого числа букв и связей в получаемых конструкциях). При этом будем говорить, что алгоритм применим к тому исходному данному, для которого он потенциально осуществим. Во втором и третьем случае будем говорить, что алгоритм не применим к соответствующему исходному данному. Операции, выполняемые на каждом шагу, должны быть как-то ограничены в смысле их сложности. Целесообразность такого требования естественна. Если бы мы не ограничивали сложности операций, то можно было бы ограничиться такими алгоритмами, с помощью которых задача решается за один шаг. По существу всякую формулировку задачи в общем виде можно было бы считать алгоритмом, во всяком случае, если задача разрешима. Например, алгоритмом было бы предписание: "Найти общий наибольший делитель Z целых положительных чисел х и у ". Требованию простоты нужно придать разумный и определенный характер: выбрать некоторый набор конкретных операций, назвав их простыми; но, чтобы не сузить понятия алгоритма, необходимо далее определить процедуру получения новых операций. Простыми следует считать исходные операции и операции, полученные из них с помощью указанной процедуры.

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

<состояние Исполнителя, текущая страница><действия Исполнителя>

где <действия Исполнителя> - это новое содержание текущей страницы и куда должен Исполнитель пролистать тетрадь - к началу или к концу.

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

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

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

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

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

Примеры: 1) алгоритм умножения двух многозначных чисел; 2) алгоритм извлечения квадратного корня; 3) алгоритм вычисления сложного арифметического выражения, состоящий в последовательном выполнении арифметических действий; 4) алгоритм перехода из десятичной системы счисления в двоичную; 5) алгоритм определения истинного значения некоторого высказывания.

Характерные свойства алгоритма⁶.

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

2.    Определенность (детерминированность). Программа преобразований в каждом такте однозначно определена.

3.    Результативность (направленность). Алгоритм направлен на получение определенного результата; в частности, если вычисляемая функция в данной точке не определена, совокупность правил точно определяет, что нужно считать результатом применения алгоритма.

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

Примеры. 1. Неизвестен алгоритм, позволяющий для любого n=1, 2, 3,… определить, имеет ли уравнение целочисленное решение, в то время как для n=2 такое решение известно (x=3k, y=4k, z=5k, где k-произвольное число).

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

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

В алгоритмических проблемах обычно речь идет о существовании алгоритма для вычисления целочисленных значений функции, зависящей от целочисленных аргументов – числовой функции. Такими функциями являются, например, арифметические функции: сумма, произведение, целая часть частного, определенные на множестве натуральных чисел. Другой пример – функции алгебры логики. Однако этими примерами не исчерпываются возможности алгоритмов, вычисляющих целочисленные функции. На самом деле к вычислению таких функций сводятся и более общие проблемы. Например, вычисление функции, определенной на каком-либо счетном множестве и принимающей значения из некоторого счетного множества, - эта задача может быть сведена к предыдущей путем «нумерации» - процесса, состоящего в применении раз навсегда определенного алгоритма. Благодаря нумерации действия над элементами счетного множества сводятся к действиям над целочисленными номерами.

Числовые функции⁷, значение которых можно вычислить посредством применения некоторого (единого для заданной функции) алгоритма, называется вычислимыми функциями. Поскольку понятие алгоритма в этом определении – интуитивное, то и понятие вычислимой функции оказывается интуитивным. Функции, определенные для всех значений аргументов, называются частными функциями. Исследования показали, что совокупность частных вычислимых функций для самых разных трактовок алгоритма оказывается одной и той же. Все частные функции, алгоритмы вычислений которых известны, оказались частично-рекурсивными. Частично-рекурсивные функции – это функции, определяемые особым образом с достаточной математической строгостью. Клини высказал гипотезу от том, что класс алгоритмически вычислимых частичных функций совпадает с классом всех частично рекурсивных функций. Ранее аналогичную гипотезу относительно всюду определенных вычислимых функций выдвинул А. Черч. Гипотезы Черча и Клини обычно объединяют под названием тезиса Черча. Тезис Черча оперирует с нестрогим интуитивным понятием вычислимой функции, поэтому его доказать нельзя. Тем не менее тезис Черча является достаточным, чтобы придать необходимую строгость формулировками алгоритмических проблем. Причина этого заключается в том, что в силу тезиса Черча вопрос о вычислимости функции равносилен вопросу о ее рекурсивности. Но понятие рекурсивности – строгое, поэтому, в известных случаях, можно доказать, что решающая задачу функция не может быть рекурсивной, и, следовательно, алгоритм не может быть построен.

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

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