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

АЛГОРИТМОВ ТЕОРИЯ, раздел математики, изучающий общие свойства алгоритмов. Часть алгоритмов теории, в которой изучаются свойства вычислимых функций, не зависящие от сложности их задания и вычисления, называется общей или дескриптивной алгоритмов теорией. К основным понятиям алгоритмов теории относятся понятия вычислимой функции, перечислимого множества, т. е. множества значений вычислимой функции, и разрешимого множества (такого, для которого существует алгоритм проверки принадлежности к нему).

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

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

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

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

Алгоритмов теория используется при построении конструктивной логики, конструктивной математики, находит применение в математической лингвистике, при проектировании и построении устройств информационных технологий, разработке языков программирования, построении конкретных алгоритмов и доказательстве правильности их работы.

Лит.: Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., 1979; Успенский В. А., Семенов А. Л. Теория алгоритмов: основные открытия и приложения. М., 1987; Марков А. А., На горный Н. М. Теория алгорифмов. М., 1996; Гончаров С. С., Ершов Ю.Л. Конструктивные модели. Новосиб.,1999; Кормен Т., Лей зерсон Ч., РивестР. Алгоритмы: построение и анализ. М., 2002; Верещагин Н. К., Шень А. Вычислимые функции. М., 2002.