Пример статьи на Ал
Алгоритмов теория
Алгоритмов теория, раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия "алгоритм", прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь в 20 в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя ещё в расплывчатом виде) лишь в 20-х гг. 20 в. в трудах представителей математического интуиционизма Л. Э. Я. Брауэра и Г. Вейля. Началом систематической разработки А. т. можно считать 1936, когда А. Чёрч опубликовал первое уточнение понятия вычислимой функции (предложив отождествлять понятие всюду определённой вычислимой функции, имеющей натуральные аргументы и значения, с понятием общерекурсивной функции) и привёл первый пример функции, не являющейся вычислимой, а А. М. Тьюринг и Э. Л. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, см. Тьюринга машина). В дальнейшем А. т. получила развитие в трудах С. К. Клини, Э. Л. Поста, А. А. Маркова и других. В частности, А. А. Марков предложил уточнять понятие алгоритма с помощью введённого им понятия нормального алгоритма. Наиболее общий подход к уточнению понятия алгоритма предложил А. Н. Колмогоров.
Основные понятия А. т. Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм Á говорят, что он: 1) "вычисляет функцию f", коль скоро его область применимости совпадает с областью определения f и Á перерабатывает всякий x из своей области применимости в f(x), 2) "разрешает множество А относительно множества X", коль скоро он применим ко всякому х из Х и перерабатывает всякий х из Х Ç A в слово "да", а всякий х из Х\A в слово "нет"; 3) "перечисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В. Функция называется вычислимой, если существует вычисляющий её алгоритм. Множество называется разрешимым относительно X, если существует разрешающий его относительно Х алгоритм (см. Разрешимое множество). Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм (см. Перечислимое множество).
Детальный анализ понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее — областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида <x, f(x)>. (IV) Подмножество А перечислимого множества Х тогда и только тогда разрешимо относительно X, когда А и Х \А перечислимы. (V) Если А и В перечислимы, то A' ÈB и А ÇВ также перечислимы. (VI) В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением [в силу (IV) это перечислимое подмножество будет неразрешимым относительно X]. (VII) Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают упоминаемый в ст. Алгоритм пример алгоритма Á с неразрешимой областью применимости.
Алгоритмические проблемы. Проблема построения алгоритма, обладающего теми или иными свойствами, называется алгоритмической проблемой (а. п.). Как правило, свойство искомого алгоритма формулируется в терминах свойств того соответствия, которое должно иметь место между исходными данными и результатами алгоритма. Важные примеры а. п.: проблема вычисления данной функции (требуется построить алгоритм, вычисляющий эту функцию): проблема разрешения данного множества (требуется построить алгоритм, разрешающий это множество относительно некоторого другого множества); проблема перечисления данного множества (требуется построить алгоритм, перечисляющий данное множество). Неразрешимость а. п. означает отсутствие соответствующего алгоритма; теоремы, устанавливающие неразрешимость таких проблем, относятся к числу наиболее важных теорем А. т.
Метрическая А. т. А. т. можно разделить на дескриптивную (качественную) и метрическую (количественную). Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами, к ней относятся, в частности, те алгоритмические проблемы, о которых говорилось в предыдущем разделе. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими "вычислений", т. е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что сложность алгоритмов и вычислений может определяться различными способами, причём может оказаться, что при одном способе А будет сложнее В, а при другом способе — наоборот. Чтобы говорить о сложности алгоритмов, надо сперва описать какой-либо точный язык для записи алгоритмов и затем под сложностью алгоритма понимать сложность его записи; сложность же записи можно определять различными способами (например, как число символов данного типа, участвующих в записи, или как набор таких чисел, вычисленных для разных типов символов). Чтобы говорить о сложности вычисления, надо уточнить, как именно вычисление представляется в виде цепочки сменяющих друг друга конструктивных объектов и что считается сложностью такой цепочки (только ли число членов в ней — "число шагов" вычисления или ещё учитывается "размер" этих членов и т. п.); в любом случае сложность вычисления зависит от исходного данного, с которого начинается вычисление, поэтому сложность вычисления есть функция, сопоставляющая с каждым объектом из области применимости алгоритма сложность соответствующей цепочки. Разработка методов оценки сложности алгоритмов и вычислений имеет важное теоретическое и практическое значение, однако в отличие от дескриптивной А. т., оформившейся в целостную математическую дисциплину, метрическая А. т. делает лишь первые шаги.
Приложения А. т. имеются во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают в математической логике и теории моделей; для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех её предложений (теории подразделяются на разрешимые и неразрешимые — в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Чёрч установил неразрешимость проблемы разрешения для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А. Тарскому, А. И. Мальцеву и др. Алгоритмические проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп: первые примеры полугрупп с неразрешимой проблемой тождества были найдены в 1947 независимо А. А. Марковым и Э. Л. Постом, а пример группы с неразрешимой проблемой тождества — в 1952 П. С. Новиковым); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 А. А. Марковым); в теории чисел (остающаяся до сих пор открытой проблема разрешимости диофантовых уравнений) и др. разделах математики.
А. т. тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики — понятие исчисления и потому, например, теорема К. Гёделя о неполноте формальных систем может быть получена как следствие теорем А. т. Наконец, А. т. тесно связана с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, в частности А. т. даёт аппарат, необходимый для разработки конструктивного направления в математике; в 1965 А. Н. Колмогоров предложил использовать А. т. для обоснования информации теории. А. т. образует теоретический фундамент для ряда вопросов вычислительной математики и тесно связана с кибернетикой, в которой важное место занимает изучение алгоритмов управления, в частности понятие алгоритма занимает центральное место в т. н. программированном обучении.
Лит.: Общие вопросы. Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; Марков А. А., Теория алгорифмов, М. — Л., 1954 (Тр. Матем. института АН СССР, т. 42).
Отдельные вопросы. Колмогоров А. Н., Три подхода к определению понятия "количество информации", "Проблемы передачи информации", 1965, т. 1, в. 1; Ершов Ю. Л. [и др.], Элементарные теории, "Успехи математических наук", 1965, т. 20, в. 4; Марков А. А., О нормальных алгорифмах, связанных с вычислением булевых функций, "Известия АН СССР. Серия математическая", 1967, т. 31, в. 1; Трахтенброт Б. А., Сложность алгоритмов и вычислений, Новосиб., 1967.
В. А. Успенский.
Алексеев Михаил Павлович
Алексеев Михаил Павлович [р. 24.5(5.6).1896, Киев], советский литературовед, академик АН СССР (1958; член-корреспондент 1946); профессор ЛГУ (с 1932). Почётный доктор Оксфордского, Парижского, Бордоского, Ростокского, Будапештского университетов. Руководитель сектора взаимосвязей русской и зарубежных литератур в институте русской литературы АН СССР (Пушкинский дом). С 1959 председатель Пушкинской комиссии АН СССР. Многие исследования А. посвящены изучению роли русской и др. славянских литератур в истории мировой культуры. А. также автор работ по английской, немецкой, французской, испанской и др. литературам и их взаимосвязям с русской литературой. Ответственный редактор академического издания соч. И. С. Тургенева. Награжден орденом Ленина, 2 др. орденами, а также медалями.
Соч.: Явления гуманизма в литературе и публицистике Древней Руси (XVI — XVII вв.), М., 1958; Из истории англ. литературы, М. — Л., 1960; Очерки истории испано-рус. лит. отношений XVI — XIX вв., Л., 1964: Стихотворение Пушкина "Я памятник себе воздвиг...", Л., 1967; Словари иностранных языков в русском азбуковнике XVII — в., Л., 1968.
Лит.: Берков П. Н., М. П. Алексеев — историк и теоретик литературы, в сборнике: Русско-европейские литературные связи, М. — Л., 1966; М. П. Алексеев. Список научных печатных трудов, Л., 1956.
Аллах-юнь (река в Якут. АССР)
Аллах-Юнь, река в Якутской АССР, правый приток Алдана. Длина 586 км, площадь бассейна 24 200 км2. Начинается в горах к Ю.-В. от Верхоянского хребта. Почти на всём протяжении течёт по северо-западной окраине Юдомо-Майского нагорья, в глубокой и узкой долине; в низовье выходит на равнину, где приобретает спокойный характер. Питание снеговое и дождевое. Весенний подъём воды до 3—5 м. Продолжительность ледостава около 200 дней. Среднегодовой расход 169 м3/сек. Главные притоки: Анча (левый) и Сахара (правый). В высокую воду судоходна. В бассейне А. — золотоносные россыпи.
Список статей на Ал
Аларкон-и-Мендоса Хуан Руис де
Алатырь (город в Чувашской АССР)
Алашань (горный хребет в Китае)
Албано-итальянские договоры и соглашения
Албанское телеграфное агентство
Алейкия алиментарно-токсическая
Алекперов Алескер Гаджи Ага оглы
Александер Тунисский Харолд Руперт Леофрик Джордж
Александр III (росс. император)
Александр II (росс. император)
Александравичюс Пятрас Повилас Повило
Александрова-Кочетова Александра Дормидонтовна
Александров Александр Васильевич
Александров Александр Данилович
Александров Александр Николаевич
Александров Александр Петрович
Александров Анатолий Николаевич
Александров Борис Александрович
Александров Василий Георгиевич
Александров Владимир Борисович
Александров (город во Владимирской обл.)
Александров Григорий Васильевич
Александров Диомид Александрович
Александровка (пос. гор. типа в Донецкой обл.)
Александровка (пос. гор. типа в Кировоградской обл.)
Александровская Лариса Помпеевна
Александровск (город в Луганской обл.)
Александровск (город в Пермской обл.)
Александровск (ст. назв. г. Запорожье)
Алексеев Александр Емельянович
Алексеевка (город в Белгородской обл.)
Алексеевка (город в Казах. ССР)
Алексеевка (пос. гор. типа в Кокчетавской обл.)
Алексеевка (пос. гор. типа в Куйбышевской обл.)
Алексеевка (пос. гор. типа в Саратовской обл.)
Алексеев Николай Александрович
Алексеевский Евгений Евгеньевич
Алексеевский Николай Евгеньевич
Алексенко-Сербин Тихон Михайлович
Алексидзе Димитрий Александрович
Алекси-Месхишвили Владимир Сардионович
Алекси-Месхишвили Владимир Шалвович
Алексинский Григорий Алексеевич
Алёхин Александр Александрович
Алжирская коммунистическая партия
Аллах-юнь (пос. гор. типа в Якут. АССР)
Аллергические диагностические пробы
Аллопатрическое распространение
Алма-атинский зооветеринарный институт
Алма-атинский медицинский институт
Алмазный (пос. гор. типа в Ростовской обл.)
Алмазный (пос. гор. типа в Якутской АССР)
Алмасзаде Гамэр Гаджи Ага кызы
Алмейда-Гаррет Жуан Баптишта да Силва Лейтан
Алфавитно-цифровое печатающее устройство
Альбенис Исаак Мануэль Франсиско
Альдегидокислоты и кетокислоты
Алькала Самора-и-Торрес Нисето
Альпийская геосинклинальная (складчатая) область
Альпийско-Гималайская геосинклинальная область
Альхесирасская конференция 1906
Альшванг Арнольд Александрович
Альянс социалистической демократии
Алюминийорганические соединения
Алюмосиликатные огнеупорные изделия
Алябьев Александр Александрович