Теория алгоритмов: различия между версиями

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

 

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

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

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

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

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