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

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

Основные понятия

Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм [math]\displaystyle{ \cal A }[/math] говорят, что он:

1) "вычисляет функцию [math]\displaystyle{ f }[/math]", коль скоро его область применимости совпадает с областью определения [math]\displaystyle{ f }[/math] и [math]\displaystyle{ \cal A }[/math] перерабатывает всякий [math]\displaystyle{ x }[/math] из своей области применимости в [math]\displaystyle{ f(x) }[/math],

2) "разрешает множество [math]\displaystyle{ A }[/math] относительно множества [math]\displaystyle{ X }[/math]", коль скоро он применим ко всякому [math]\displaystyle{ x }[/math] из [math]\displaystyle{ X }[/math] и перерабатывает всякий [math]\displaystyle{ x }[/math] из [math]\displaystyle{ X\cap A }[/math] в слово "да", а всякий [math]\displaystyle{ x }[/math] из [math]\displaystyle{ X\setminus A }[/math] в слово "нет";

3) "перечисляет множество [math]\displaystyle{ B }[/math]", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть [math]\displaystyle{ B }[/math].

Функция называется вычислимой, если существует вычисляющий её алгоритм. Множество называется разрешимым относительно [math]\displaystyle{ X }[/math], если существует разрешающий его относительно [math]\displaystyle{ X }[/math] алгоритм. Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм.

Детальный анализ понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее — областью применимости. Имеют место следующие основные теоремы: (III) функция [math]\displaystyle{ f }[/math] вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида [math]\displaystyle{ \lt x,f(x)\gt }[/math]; (IV) Подмножество [math]\displaystyle{ A }[/math] перечислимого множества [math]\displaystyle{ X }[/math] тогда и только тогда разрешимо относительно [math]\displaystyle{ A }[/math], когда [math]\displaystyle{ A }[/math] и [math]\displaystyle{ X\setminus A }[/math] перечислимы; (V) Если [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] перечислимы, то [math]\displaystyle{ A\cap B }[/math] и [math]\displaystyle{ A\cup B }[/math] также перечислимы; (VI) В каждом бесконечном перечислимом множестве [math]\displaystyle{ X }[/math] существует перечислимое подмножество с неперечислимым дополнением [в силу (IV) это перечислимое подмножество будет неразрешимым относительно [math]\displaystyle{ X }[/math]]; (VII) Для каждого бесконечного перечислимого множества [math]\displaystyle{ X }[/math] существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём [math]\displaystyle{ X }[/math]. Утверждения (VI) и (II) в совокупности дают пример алгоритма алгоритма с неразрешимой областью применимости.

Алгоритмические проблемы

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

Метрическая теория алгоритмов

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

Приложения теории алгоритмов

Теорию алгоритмов имеет приложения во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают в математической логике и теории моделей; для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех её предложений (теории подразделяются на разрешимые и неразрешимые — в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Чёрч установил неразрешимость проблемы разрешения для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А. Тарскому, А. И. Мальцеву и др. Алгоритмические проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп: первые примеры полугрупп с неразрешимой проблемой тождества были найдены в 1947 независимо А. А. Марковым и Э. Л. Постом, а пример группы с неразрешимой проблемой тождества — в 1952 П. С. Новиковым); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 А. А. Марковым); в теории чисел (остающаяся до сих пор открытой проблема разрешимости диофантовых уравнений) и других разделах математики.

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

Литература

Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965.

Марков А. А., Теория алгорифмов, М. — Л., 1954 (Тр. Матем. института АН СССР, т. 42).

Колмогоров А. Н., Три подхода к определению понятия "количество информации", "Проблемы передачи информации", 1965, т. 1, в. 1.

Ершов Ю. Л. [и др.], Элементарные теории, "Успехи математических наук", 1965, т. 20, в. 4.

Марков А. А., О нормальных алгорифмах, связанных с вычислением булевых функций, "Известия АН СССР. Серия математическая", 1967, т. 31, в. 1.

Трахтенброт Б. А., Сложность алгоритмов и вычислений, Новосиб., 1967.

Успенский В. А. Алгоритмов теория, Большая советская энциклопедия: В 30 т., М.: "Советская энциклопедия", 1969-1978.