Алгоритм

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

Формальные свойства алгоритмов [в явной или неявной форме] включают следующий ряд общих требований:

1. Дискретность (разделённость на части) и упорядоченность. Алгоритм должен состоять из отдельных действий, которые выполняются последовательно друг за другом.
2. Детерминированность (однозначная определённость). Многократное применение одного алгоритма к одному и тому же набору исходных данных всегда даёт один и тот же результат.
3. Формальность. Алгоритм не должен допускать неоднозначности толкования действий для исполнителя.
4. Результативность и конечность. Работа алгоритма должна завершаться за определённое число шагов, при этом задача должна быть решена.
5. Массовость. Определённый алгоритм должен быть применим ко всем однотипным задачам.

Предписание алгоритма, как правило, фиксируется (записывается) в виде текста некотором формализованном языке (см. Язык формализованный), называемого программой. Понятие программы формулируется в чисто структурных терминах синтаксиса этого языка, без какого-либо обращения к смысловым категориям. Точно такой же характер носит и описание процедуры выполнения программы. Поэтому в роли исполнителя алгоритмов, записанных на формализованных [алгоритмических] языках, может выступать не только человек, но и наделённое соответствующими [вычислительными] возможностями автоматическое устройство, машина. Универсальным исполнителем алгоритмов является компьютер. С его помощью возможно выполнять все основные виды алгоритмов. Возможность машинного осуществления алгоритмических процедур, и, соответственно, машинного решения задач, стимулировала развитие вычислительной техники и создание математической теории алгоритмов. В современной науке теория алгоритмов является основой конструктивного направления в математике и логике, а также выступает одной из базисных дисциплин в области вычислительной техники и программирования, машинного решения разнообразных задач, моделирования различных процессов и других областях.

Слово «алгоритм» происходит от имени арабского учёного IX века Мухамеда бен Мусы аль-Хорезми, который впервые описал правила выполнения арифметических действий в десятичной системе счисления, придуманной в Индии. Впоследствии термином «алгоритм» стали обозначать эти правила вычислений. Однако с течением времени понятие алгоритма постепенно расширялось, наряду с его экспансией из чистой математики в другие сферы, и в XX веке под ним стали понимать точную последовательность действий, приводящую к решению поставленной задачи, при условии, что эта задача является заведомо решаемой.

Алгоритм — одно из основных понятий математической логики (см. Логика математическая) и математики. Хотя неформально математики всё время занимались поиском алгоритмов, данное понятие было уточнено лишь в 30-х годах XX века. Первыми такими уточнениями были абстрактные определения частично-рекурсивных и представимых функций в формальной теории чисел, появившиеся в связи с задачами теории доказательств. В 1936 году Э. Пост и А. Тьюринг независимо друг от друга предложили понятия абстрактных вычислительных машин и указали, что любой алгоритм в интуитивном смысле слова может быть реализован на данных машинах, несмотря на кажущуюся примитивность их элементарных действий.

В машине Тьюринга памятью является потенциально бесконечная лента, в каждой клетке которой записан символ из заранее заданного конечного алфавита. Более того, достаточно рассматривать ленту, каждая клетка которой содержит один бит информации, то есть либо пуста, либо содержит символ |. Процессор машины Тьюринга состоит из головки (каретки), которая в любой момент обозревает одну клетку, и программы, состоящей из конечного числа команд, обычно нумеруемых натуральными числами. Каждая команда представляет собой условное действие, зависящее от символа, записанного в клетке. Это действие имеет вид совокупности элементарных инструкций формы ab (L, R, S) i, в которой присутствует лишь одна из букв L, R, S. Буква L означает приказ сдвинуться на следующем такте на одну клетку влево, R — вправо, S — остаться на месте. Элементарная инструкция означает следующее: если машина видит a, записать в клетку b, передвинуться в соответствии с командой и перейти к исполнению команды i. Такая элементарность действий машины стала результатом проведённого Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов.

Машина Поста представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы. В машине имеются регистры, содержащие натуральные числа, элементарные операции увеличения и уменьшения числа на 1 и условный переход, если число в регистре равно 0. Машина Поста состоит из: а) бесконечной ленты, поделённой на одинаковые ячейки-секции (ячейка может быть пустой [0 или пустота] или содержать метку [1 или любой другой знак]; б) головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку. Состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты — это информация о том, какие секции пусты, а какие отмечены. Шаг — это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы. Элементарные действия (команды) машина Поста проще команд машины Тьюринга, поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга. Команды машины Поста предвосхитили систему команд современных вычислительных машин.

Одновременно А. Чёрч и X. Б. Карри создали одно из самых абстрактных уточнений алгоритма: λ-определимость, выразимость с помощью терма комбинаторной логики (см. Логика комбинаторная). Выяснилось, что и ранее созданные теоретические понятия, и самые элементарные, и самые абстрактные, из вновь появившихся уточнений алгоритма оказались эквивалентны. Этот факт, подтверждённый в дальнейшем для всех вновь появлявшихся точных определений алгоритма, послужил основой утверждения, скромно называемого в математике тезисом Чёрча, хотя степень его подтверждённости ныне выше, чем у любого физического «закона». Содержательное понятие алгоритма эквивалентно по объёму любому из имеющихся в данный момент математических уточнений этого понятия, в частности вычислимости на машине Тьюринга.

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

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

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

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

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

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

Например, определение алгоритма может быть записано как слово в некотором алфавите, а если взять определение алгоритма, в котором рассматриваются лишь натуральные числа, такое слово может быть естественно представлено как число в системе счисления, основанием которой является количество букв в алфавите. Тогда имеется универсальный алгоритм U, перерабатывающий любую пару (ϕ, P), где ϕ — конструктивный объект, называемый записью или программой (относительно U) алгоритма ϕ, в результат применения ϕ к P. Универсальный алгоритм не может быть всюду определён. Если рассматривать лишь конструктивные объекты, то алгоритм естественно отождествить с его программой относительно некоторого U. То, что такое отождествление является ограниченным, показывают проблемы современной теории и практики программирования. Одной из самых трудных возникающих в этом случае проблем является восстановление алгоритма по реализующей его конкретной программе. Если понятие алгоритма, перерабатывающего реальные конструктивные объекты, можно считать однозначно определённым, то его обобщение на объекты высших типов допускает многочисленные варианты, неэквивалентные друг другу.

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

На основе теории сложности А. Н. Колмогоров, Л. А. Левин, П. Мартин-Лёф и другие развили алгоритмическую теорию вероятностей. Основой данной теории явилось содержательное определение случайной последовательности по Р. Мизесу. Двоичная последовательность случайна, если из неё нельзя выбрать никакую последовательность с другой частотой нулей и единиц. Например, последовательность 0, 1, 0, 1… неслучайна, поскольку последовательность её чётных членов состоит из одних единиц. В классической математике такое определение пусто. А. Н. Колмогоров уточнил его, предложив рассматривать лишь алгоритмические перестановки подмножеств членов данной последовательности. Оказалось, что случайность связана со сложностью определения. Сложность фрагментов случайной последовательности пропорциональна длине их записи. Итак, содержательно случайные объекты являются приближениями к случайным последовательностям. Для любой совокупности программ, имеющих ограниченную сложность, можно построить ограниченный универсальный алгоритм, исполняющий все их без ошибок, но его сложность будет неизмеримо выше, чем сложность исполняемых программ. Далее, возможно построить алгоритмический процесс, расширяющий ограниченный универсальный алгоритм с тем, чтобы включить любую предъявленную программу, не входящую в данный класс, но при этом сложность универсального метода станет ещё выше. Уже один шаг данного процесса диагонализации далеко выводит за рамки класса функций, считающихся реально вычислимыми.

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