Служба підтримки:

Київ +38 (050) 653-07-96

Навигация
 
акус-алейж
<< В начало < Предыдущая Следующая > В конец >>

АЛГОРИТМОВ ТЕОРИЯ

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

Основные понятия А. т.

Областью применимости алгоритма наз. совокупность тех объектов, к которым он применим. Про алгоритм Я говорят, что он: 1) "вычисляет функцию f", коль скоро его область применимости совпадает с областью определения f и Я перерабатывает всякий х из своей области применимости в f(x); 2) "разрешает множество А относительно множества X", коль скоро он применим ко всякому x из X и перерабатывает всякий x из  з слово "да", а всякий x из Х\Л в слово "нет"; 3)"пе-речисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В. Функция наз. вычислимой, если существует вычисляющий её алгоритм. Множество наз. разрешимым относительно X, если существует разрешающий его относительно X алгоритм (см. Разрешимое множество). Множество наз. перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм (см. Перечислимое множество).

Детальный анализ понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у к-рого больщее множество служит множеством исходных данных, а меньшее - областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида <x,f(x)>. (IV) Подмножество А перечислимого множества X тогда и только тогда разрешимо относительно X, когда А и Х\А перечислимы. (V) Если Л и В перечислимы, то также перечислимы.

(VI) В каждом бесконечном перечислимом множестве X существует перечислимое подмножество с неперечислимым дополнением [ в силу (IV) это перечислимое подмножество будет неразрешимым относительно X].

(VII) Для каждого бесконечного перечислимого множества X существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают упоминаемый в ст. Алгоритм пример алгоритма  с неразрешимой областью применимости.

Алгоритмические проблемы.

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

Метрическая А. т.

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

Приложения А.

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

А. т. тесно связана с матем. логикой, поскольку на понятие алгоритма опирается одно из центральных понятий матем. логики - понятие исчисления и потому, напр., теорема К. Гёделя о неполноте формальных систем может быть получена как следствие теорем А. т. Наконец, А. т. тесно связана с основаниями математики, в к-рых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, в частности А. т. даёт аппарат, необходимый для разработки конструктивного направления в математикев; 1965 А. Н. Колмогоров предложил использовать А. т. для обоснования информации теории. А. т. образует теоретич. фундамент для ряда вопросов вычислит, математики и тесно связана с кибернетикой, в к-рой важное место занимает изучение алгоритмов управления, в частности понятие алгоритма занимает центральное место в т. н. программированном обучении.

Лит.: Общие вопросы. Мальцев . А. И., Алгоритмы и рекурсивные функции, М., 1965; Марков А. А., Теория алгорифмов, М.- Л., 1954 (Тр. Матем. института АН СССР, т. 42).

Отдельные вопросы.

Колмогоров А. Н., Три подхода к определению понятия "количество информации". "Проблемы передачи информации", 1965. т. 1, в. 1; Ершов Ю. Л. [и др.], Элементарные теории, "Успехи математических наук", 1965, т. 20, в. 4; Марков А. А., О нормальных алгорифмах, связанных с вычислением булевых функций, "Известия АН СССР. Серия математическая", 1967, т. 31, в. 1; Трахтенброт Б. А., Сложность алгоритмов н вычислений, Ново-сиб., 1967. В. А. Успенский.



 
Большая советская энциклопедия
  [ АННОТАЦИЯ]   [а-абон]   [аборд-авар]   [авач-австрич]   [австрия - автомот]   [автомут-аграм]   [агран-аджз]   [аджи-азер]   [азеф-айя]   [ака-акоп]   [акост-акур]   акус-алейж   [алейк-ален]   [алеп-алле]   [алли-альбен]   [альбер-альп]   [альт-амап]   [амар-амим]   [амин-амуд]   [амул-анан]   [анап-андез]   [андер-анип]   [анис-антен]   [антер-антон]   [антоф-апел]   [апен-апшер]   [ар-аргум]   [аргун-аркт]   [арл-арсен]   [арсин-арха]   [архе-аса]   [асб-ассиз]   [ассим-астроп]   [астрос-атол]   [атом-афил]   [афин-ацет]   [ацид-аяч]