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

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

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