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

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

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

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

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

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

[[Категория:Теория автоматов]]