Математическая энциклопедия

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

раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия "алгоритм", прослеживаются в математике в течение всего времени ее существования. Однако само это понятие сформировалось лишь в 20 в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя еще в расплывчатом виде) в 20-х гг. 20 в. в трудах представителей интушионизма Л. Э. Я. Брауэра (L. Е. J. Brouwer) и Г. Вейля (Н. Weyl, см. [1]). Началом сиотематич. разработки А. т. можно считать 1936, когда А. Чёрч (A. Church, [2]) опубликовал первое уточнение понятия вычислимой функции (предложив отождествлять понятие всюду определенной вычислимой функции, имеющей натуральные аргументы и значения, с понятием общерекурсивной функции) и привел первый пример функции, не являющейся вычислимой, а А. М. Тьюринг (А. М. Turing, [3], [4]) и Э. Л. Пост (Е. L. Post, [5]) дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, см. Тьюринга машина). В дальнейшем А. т. получила развитие в трудах С. К. Клини (S. С. Kleene), Э.
Метрическая теория алгоритмов. А. т. можно разделить на дескриптивную (качественную) и метрическую (количественную). Первая - исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами; к ней относятся, в частности, те алгоритмич. проблемы, о к-рых говорилось в предыдущем разделе. Вторая - исследует алгоритмы с точки зрения сложности как самих алгоритмов (см. Алгоритма сложность), так и задаваемых ими "вычислений", то есть процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что как сложность алгоритмов, так и сложность вычислений могут определяться различными способами, причем может оказаться, что при одном способе Абудет сложнее В, а при другом способе - наоборот. Чтобы говорить о сложности алгоритмов, надо сначала описать к.-л. точный язык для записи алгоритмов и затем под сложностью алгоритма понимать сложность его записи; сложность же записи можно определять различными способами (напр., как число символов данного типа, участвующих в записи, или как набор таких чисел, вычисленных для разных типов символов). Чтобы говорить о сложности вычисления, надо уточнить, как именно вычисление представляется в виде цепочки сменяющих друг друга конструктивных объектов и что считается сложностью такой цепочки (только ли число членов в ней - "число шагов" вычисления, или еще учитывается "размер" этих членов и т. п.); в любом случае сложность вычисления зависит от исходного данного, с к-рого начинается вычисление, поэтому сложность вычисления есть функция, сопоставляющая с каждым объектом пз области применимости алгоритма сложность соответствующей цепочки. Разработка методов оценки сложности алгоритмов и вычислений имеет важное теоретич. ы практпч. значение, однако в отличие от дескриптивной А. т., оформившейся в целостную математич. дисциплину (см. [11], [15], [16]), метрич. А. т. находится в процессе становления (см. [17] - [20]). Приложения теории алгоритмов имеются во всех областях математики, в к-рых встречаются алгоритмпч. проблемы. Такие проблемы возникают в математической логике и моделей теории;для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех ее предложений (теории подразделяются на разрешимые и неразрешимые - в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Чёрч (см. [21] , [22]) установил неразрешимость проблемы разрешения -для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А. Тарскому (A. Tarski), А. И. Мальцеву и др. (см. [23]). Неразрешимые алгоритмич. проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп); первые примеры полугрупп с неразрешимой проблемой тождества были найдены в 1947 независимо А. А. Марковым (см. [9]) и Э. Л. Постом (см. [8]), а пример группы с неразрешимой проблемой тождества - в 1952 П. С. Новиковым (см. [24], [25]); в топологии (проблема гомеоморфии, неразрешимость к-рой для важного класса случаев была доказана в 1958 А. А. Марковым, (см. [26]); в теории чисел (проблема разрешимости диофантовых уравнений, неразрешимость к-рой была установлена в 1970 Ю. В. Матия-севичем, (см. [27], [28]) и др. разделах математики. А. т. тесно связана с математич. логикой, поскольку на понятие алгоритма опирается одно из центральных понятии математич. логики - понятие исчисления, и потому, напр., Гёделя теорема о неполноте формальных систем может быть получена как следствие теорем А. т. (см. [29]). Наконец, А. т. тесно связана с основаниями математики, в к-рых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного; в частности, А. т. дает аппарат, необходимый для разработки конструктивного направления в математике; в 1965 А. Н. Колмогоров предложил использовать А. т. для обоснования теории информации (см. [30], Алгоритмическая теория информации). А. т. образует теоретич. фундамент для ряда вопросов вычислительной математики и тесно связана с кибернетикой, в которой важное место занимает изучение алгоритмов управления. Лит.:[1] Вейль Г., О философии математики, пер. с нем., М.- Л., 1934; [2] Church A., "Amer. J. Math.", 1936, v. 58, № 2, p. 345-63; [3] Turing A. M., "Proc. London Math. Soc.", ser. 2, 1936, v. 42, №№ 3-4, p. 230-65; [4] его же, там же, 1937, v. 43, № 7, p. 544-46; [5] Pоst E. L., "J. Symbol. Log.", 1936, v. 1, № 3, p. 103-05; [6] его же, "Amer. J. Math.", 1943, v. 65, № 2, p. 197-215; [7] его же, "Bull. Amer. Math. Soc.", 1944, v. 50, № 5, p. 284-316; [8] его же, "J. Symbol. Log.", 1947, v. 12, № 1, p. 1-11; [9]Mapков А. А., "Докл. АН СССР", 1947, т. 55, № 7, с. 587-90; [10] его же, "Тр. Матем. ин-та АН СССР", 1951, т. 38, с. 176-89; [11] его же, Теория алгорифмов, М.- Л., 1954; [12] Колмогорова. Н., "Успехи матем. наук", 1953, т. 8, № 4, с. 175-76; [13] Колмогоров А. Н., Успенский В. А., там же, 1958, т. 13, К" 4, с. 3-28; [14] Ершов Ю. Л., Теория нумераций, ч. 1-2, Новосибирск, 1969-73; [15] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [16] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [17] Марков А. А., "Изв. АН СССР. Сер. матем.", 1967, т. 31, № 1, с. 161-208; [18] Трахтенброт Б. А., Сложность алгоритмов и вычислений, Новосибирск, 1967; [19] Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций, сб. переводов, М., 1970; [20] Сложность вычислений и алгоритмов, сб. переводов, М., 1974; [21] Church A., "J. Symbol. Log.", 1936, v. 1, Т 1, p. 40-41; [22] его же, там же, № 3, р. 101-02; [23] Ершов Ю. Л., Лавров И. А., Тайманов А. Д., Тайцлин М. А., "Успехи матем. наук", 1965, т. 20, № 4, с. 37-108; [24] Новиков П. С., "Докл. АН СССР", 1952, т. 85, с. 709-12; [25] его ж е, Об алгоритмической неразрешимости проблемы тождества слов в теории групп, М., 1955; [26] Марков А. А., "Докл. АН СССР", 1958, т. 121, № 2, с. 218-20; [27] Матиясевич Ю. В., там же, 1970, т. 191, №2, с. 279-82; [28] его же, "Успехи матем. наук", 1972, т. 27, №5, с. 185-222; [29] Успенский В. А., там же, 1974, т. 29, № 1, с. 3-47; [30] Колмогоров А. Н., "Проблемы передачи информации", 1965, т. 1, № 1, с. 3 -Н. В.


Смотреть значение Алгоритмов Теория в других словарях

Теория — ж. греч. умозренье, умозаключенье; заключенье, вывод из чего-либо, не по явленью на деле, а по выводам своим; противоположное дело, на деле, опыт, практика. не всегда верна;........
Толковый словарь Даля

Теория — теории, ж. (греч. theoria - исследование). 1. учение, являющееся ражением действительности, обобщением практики, человеческого опыта. ..., если она является действительной теорией,........
Толковый словарь Ушакова

Теория Ж. — 1. Обобщение фактов, опыта, знаний, основывающееся на глубоком проникновении в сущность изучаемого явления, вскрывающее его закономерности. 2. Учение о какой-л. области........
Толковый словарь Ефремовой

Исторического Пессимизма Теория — - направление в футурологии международных отношений, которое, в противовес теории технократического оптимизма, исходит из перспективы долгого существования классического........
Политический словарь

Конвергенции Теория — (от лат. convergere - сближаться, сходиться) основана на идее преобладания тенденций объединения элементов в систему над процессами дифференциации, различения и индивидуализации.........
Политический словарь

Мобильности Теория — (от фр. mobile, лат. mobilis - подвижный, способный к быстрому действию) - система идей в социологии и политологии, в которой осмысливаются процессы изменения положения людей........
Политический словарь

Олигархизации Политических Партий Теория — - (от греч. oliarchia - власть немногих) - обоснование характерной тенденции в развитии партии: переход от организации демократического типа к жесткому бюрократическому аппарату........
Политический словарь

Политическая Система Индустриально Развитых Стран (теория) — Политическая система представляет собой совокупность лиц, институтов, участвующих в политическом процессе, неформальных и неправительственных факторов, влияющих........
Политический словарь

Политическая Теория — (POLITICAL THEORY) - массив научной мысли, нацеленной на оценку, объяснение и прогнозирование политических феноменов. Одновременно политическая теория представляет собой раздел........
Политический словарь

Постиндустриального Общества Теория — - широко применяется в западной политологии и социологии для обозначения современного общества. Концепция индустриального общества разрабатывалась в трудах Р.Дарендорфа........
Политический словарь

Теория — - интегрированная совокупность принципов, которые объясняют и предсказывают наблюдаемые явления. (Д. Майерс, с.50)
Политический словарь

Теория Конвергенции — (лат. convergere приближаться, сходиться) - одна из концепций политологии, социологии и политэкономии, усматривающая в общественном развитии современной эпохи преобладающую........
Политический словарь

Теория Нового Институционализма — - направление в американской политологии, возникшее в 1970-е гг. Классики неоинституционализма американские политологи Д.Марч и Д.Олсен в работе "Вновь открывая институты:........
Политический словарь

Теория Партисипаторной Демократии — - теоретики партисипаторной демократии (Дж.Вольф, Ф.Грин, Б.Барбер)остаются верными центральной идее классической теории демократии о способности простых людей управлять........
Политический словарь

Теория Плебисцитарной Демократии — - ее основателем считается М.Вебер. По его мнению, с развитием партий меняется характер политического представительства и политическая организация власти. Политическое........
Политический словарь

Теория Плюралистической Демократии — - концепция, согласно которой политический процесс предоставляет собой борьбу множества социальных, профессиональных, религиозных, местных, национальных или др. группировок,........
Политический словарь

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

Теория Социально-когнитивного Научения — (SOCIAL COGNITIVE LEARNING THEORY). Направление персонологии, представленное Бандурой и Роттером, в котором подчеркивается, что поведение является результатом сложного взаимодействия........
Политический словарь

Теория Статусной Перестановки — - концепция, объясняющая политизацию социальных групп в условиях, когда их объективные социально- 285 экономические характеристики не снижаются, но происходит рост статуса........
Политический словарь

Теория Элитарной (элитистской) Демократии — - концепция, согласно которой власть при демократии осуществляется элитами. Отличие демократии от диктатуры состоит в наличии нескольких элит, конкурирующих друг с........
Политический словарь

Амортизационная Теория Страхового Фонда — См. Теория амортизационная страхового фонда
Экономический словарь

Арбитражная Теория Оценки — (arbitrage pricing theory) – теория равновесия на рынке капиталов, основанная на предположении об отсутствии арбитражных возможностей. В соответствии с арбитражной теорией оценки,........
Экономический словарь

Арбитражная Теория Ценообразования — Альтернативная модель определения стоимости основных фондов, разработанная Стивеном Россом и построенная исключительно на арбитражных аргументах.
Экономический словарь

Государственная Теория Денег — См.
Теория денег государственная
Экономический словарь

Густав Кассель: Экономическая Теория Как Чистая Теория Цен — Густаву Касселю (1866-1944) всемирную известность принесли его многочисленные произведения и общественная деятельность. Вначале Кассель изучал технические науки, в 1895........
Экономический словарь

Декларативная Теория Признания — - правовая
концепция, отрицающая, что
субъект международного
права возникает лишь в силу акта его признания другими государствами. Согласно этой концепции........
Экономический словарь

Кардиналистская Теория Полезности — (от англ. cardinal - количественный) - исходит из того, что любой
потребитель способен количественно измерить
уровень полезности всякого данного
товара и уровень........
Экономический словарь

Классическая Теория — - теория, объединяющая представителей экономической науки, развивавших экономические концепции, начало которым положили английские
экономисты А. Смит и Д, Рикардо.........
Экономический словарь

Количественная Теория Денег — теория денежного обращения, основанная на уравнении
обмена (уравнении Фишера), связывающем денежную массу в обращении,
скорость обращения денег, среднюю цену........
Экономический словарь

Мальтузианская Теория Народонаселения — MALTHUSIAN THEORY OF POPULATIONПреподобный Томас Мальтус в своем
труде `Опыт
закона о народонаселении` (1798г.) отстаивал точку зрения, что
численность населения при его........
Экономический словарь

Посмотреть еще слова :