Текст книги "Большая Советская Энциклопедия (АЛ)"

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

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

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

  Детальный анализ понятия «алгоритм» обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее – областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида . (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.

  В. А. Успенский.

Алдабергенов Нурмолда

Алдаберге'нов Нурмолда [7(20).12. 1906 – 17.11.1967], деятель колхозного движения в Казахской ССР, дважды Герой Социалистического Труда (1948, 1958). Член КПСС с 1940. В 1930—34 колхозник. Председатель колхозов «Джана-Талап» (1935—42, 1945—49), имени XXII партсъезда (1950—61), им. Карла Маркса (1965—67) Талды-Курганской области Казахской ССР. Награжден 2 орденами Ленина, орденом Трудового Красного Знамени, медалями СССР и медалями ВДНХ. Делегат 20-го съезда КПСС, депутат Верховного Совета СССР 5-го созыва и Казахской ССР 3-го и 4-го созывов. Избирался членом ЦК КП Казахстана (1954, 1956, 1960).

Н. Алдабергенов.

Алдан (город в Якут. АССР)

Алда'н , город, центр Алданского района Якутской АССР, на Амуро-Якутской автомобильной магистрали, в 648 км к С. от ж.-д. ст. Большой Невер. Расположен на Алданском нагорье, в бассейне р. Алдан. 15 тыс. жителей (1966). Экономический и административный центр золотой и слюдяной промышленности Южной Якутии. Машиноремонтный завод. Политехникум, медицинское училище. Образован в 1939 из посёлка Незаметного, выросшего в связи с открытием в 20-х гг. 20 в. богатых месторождений золота.

Алдан (река в Якут. АССР)

Алда'н, река в Якутской АССР, наиболее крупный приток Лены (правый). Длина 2273 км, площадь бассейна 729 тыс. км² . Бассейн А. расположен в зоне развития многолетней мерзлоты и неглубокого залегания коренных кристаллических пород. Берёт начало с северного склона Станового хребта В пределах Алданского нагорья течёт в каменистом русле, изобилующем перекатами. Между устьями Учур и Мая протекает по широкой долине, местами сужающейся, ниже спокойно течёт по межгорной равнине; в пойме множество озёр. В низовье А. дробится на ряд рукавов. Наиболее крупные притоки: справа – Тимптон, Учур, Мая, Аллах-Юнь; слева – Амга. Питание снеговое и дождевое. Среднегодовой расход воды в устье 5060 м³ /сек. А. приносит в Лену ¹ /₃ её стока. Половодье с мая по июль (в августе– сентябре паводки), когда уровень воды А. повышается на 7—10 м, а расход достигает 30—48 тыс. м³ /сек. Зимний сток очень мал (4% годового), в феврале– апреле обычно не превышает 230—300 м³ /сек. Продолжительность ледостава около 7 месяцев, замерзание начинается с низовьев в конце октября, вскрытие – в мае. Вода по химическому составу гидрокарбонатно-кальциевая, максимальное содержание растворённых солей до 0,3 г/л (в зимнюю межень). Значительны рыбные ресурсы А. (осётр, стерлядь).

  А. судоходен до пристани Томмот. Велико значение А. для вывоза продукции горнодобывающей промышленности и привоза с Лены продовольственных и промышленных грузов. Основные пристани: Томмот, Усть-Мая, Хандыга. В бассейне – крупные месторождения золота, каменного угля, слюды.

  Подробное гидрографическое обследование А. было проведено Управлением водных внутренних путей Ленского бассейна в 1918—26.

Река Алдан в верхнем течении.

Алданский щит

Алда'нский щит, выступ докембрийского фундамента на Ю.-В. Сибирской платформы , в основном совпадающий с современным Алданским нагорьем . Наиболее древняя часть А. щ. сложена мощными (15—20 км ) толщами кристаллических сланцев архея (древнее 2,5 млрд. лет), прорванных гранитными интрузиями и содержащих пачки железистых кварцитов и карбонатных пород. Толщи смяты в складки северо-западного простирания или образуют куполовидные структуры с гранито-гнейсовыми ядрами. Северная и восточная части А. щ. полого погружаются под покров платформенных, трансгрессивно залегающих осадочных пород позднего докембрия и кембрия, на З. (хребты Удоканский и Кодар) А. щ. перекрыт мощной (свыше 10 км ) толщей нижнего протерозоя, образующей древнейший в Сибири (более 2—2,2 млрд. лет) чехол платформенного типа. Южный край щита высоко поднят по системе разломов, которые происходили в конце мезозоя – кайнозое, образуя Становой хребет; в пределах последнего распространены гранитоиды раннего протерозоя (1,6—2 млрд. лет), палеозоя и мезозоя.

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

Алданский ярус

Алда'нский я'рус (по р. Алдан в Восточной Сибири), первый снизу ярус кембрийской системы. Выделен Н. П. Суворовой и Г. Ф. Гурари в 1954. Охарактеризован комплексом трилобитов семейства Olenellidae, археоциатами, хиолитами, примитивными брахиоподами. Повсеместно выделяется в Сибири (морские карбонатные отложения), соответствующие слои известны в Европе, в зарубежной Азии (КНР), Австралии, Африке (Марокко) и Северной Америке.

Алданское нагорье

Алда'нское наго'рье, нагорье в Восточной Сибири, на Ю. Якутской АССР. Расположено севернее Станового хребта, между рр. Олёкмой и Учуром. Преобладают плоские междуречья со средней высотой 800—1000 м, над которыми поднимаются отдельные гольцовые группы и короткие горные хребты (Западные Янги, Суннагын, Кет-Кап и др.) высотой до 1400—2000 м (максимальная высота 2306 м ). Сложено главным образом архейскими и протерозойскими гнейсами и кристаллическими сланцами Алданского щита . Расчленено глубокими долинами притоков Алдана и Амги. До высоты 1100—1300 м доминируют сосново-лиственничные леса и горная лиственничная багульниковая тайга, выше – предгольцовое лиственничное редколесье и заросли кедрового стланика. На гольцовых вершинах – каменистая тундра. Месторождения железной руды, угля (поселок Чульман), слюды, золота.

  Г.С.Самойлова.

Алебарда

Алеба'рда (франц. hallebarde, заимствовано из итал. alabarda), холодное оружие, колющее и рубящее, в виде длинного копья (плоского или гранёного), поперёк которого прикреплен топорок или секира разнообразной формы; А. имела сравнительно короткое древко. Была на вооружении швейцарской пехоты, немецких ландскнехтов в 14—16 вв., применялась в войсках до 18 в. См. также Бердыш .

Различные формы алебард.

Алеви Эли

Алеви' (Halévy) Эли, французский историк, см. Галеви .

Алевиз Фрязин

Алеви'з Фря'зин, Алевиз Миланец (Aloisio da Milano) (гг. рождения и смерти неизвестны), архитектор. По происхождению итальянец. Приехал в Москву в 1494 по приглашению Ивана III. Работы: каменные палаты в Кремле (1499—1508, позднее вошли в состав Теремного дворца), ров вдоль стен Кремля со стороны Красной площади (1508—16, засыпан в 19 в.), плотина на р. Неглинной (1508). Принимал участие в постройке кремлёвской стены с башнями вдоль р. Неглинной (1495).

  Лит.: Снегирев В. Л., Московское зодчество. Очерки... XIV – XIX вв., [М.], 1948.

Алевиз Фрязин (Алевиз Новый)

Алеви'з Фря'зин, Алевиз (Aloisio) Новый, архитектор конца 15 – начала 16 вв. По происхождению итальянец. В 1503—04 работал в Бахчисарае (Крым), где строил дворец хана Менгли-Гирея (сохранился резной каменный портал). В 1504 по приглашению Ивана III прибыл в Москву, где, по свидетельству летописи, построил 11 церквей (не сохранились) и Архангельский собор в Кремле (1505—1508), в декоративной обработке которого использованы элементы архитектуры итальянского Раннего Возрождения.

  Лит.: Власюк А. И., О работе зодчего Алевиза Нового в Бахчисарае и в Московском Кремле, в сборнике: Архитектурное наследство, [в.] 10, М., 1958.

Алевиз Фрязин Новый. Портал Архангельского собора в Московском Кремле. 1505—08.

Алевриты

Алеври'ты (от греч. áleuron – мука), группа рыхлых осадочных горных пород, состоящих из мелкообломочного материала с размером зёрен от 100 до 10 мкм. Термин предложен А. Н. Заварицким в 1930 для пород, утративших характерные свойства песков, но ещё не являющихся глинами. К А. относятся пыль, ил, лёсс и лёссовидные породы.

Алевролит

Алевроли'т (от греч. áleuron – мука и líthos – камень), обломочная твёрдая порода, состоящая преимущественно из зёрен размером от 100 до 10 мкм (алеврит ), сцементированная, уплотнённая и претерпевшая некоторые диагенетические изменения (см. Диагенез ).

Алегрия Сиро

Алегри'я (Alegría) Сиро (4.11.1909, Сартибамба, – 18.2.1967, Лима), перуанский писатель. Представитель т. н. индианистского романа Латинской Америки. Его романы – «Золотая змея» (1935), «Голодные псы» (1939), «В большом и чуждом мире» (1941, рус. пер. 1944), рисующие жизнь индейского населения Перу, исполнены социального протеста. Последний из них раскрывает трагедию индейской общины, лишённой земли, и заканчивается картиной восстания.

  Соч.: Novelas completas, Madrid, 1959'

  Лит.: Кутейщикова В. Н., Роман Латинской Америки в XX в., М., 1964; Bunte H., Giro Alegría у su obra dentro de la evolucion literaria hispanoamericana, Lima, 1961.

Алезия

Але'зия (Alesia), древний галльский город-крепость (в районе современного Дижона, Франция), который в 52 до н. э. был осажден Ю. Цезарем при подавлении общего восстания галлов. Галлы во главе с Верцингеторигом упорно оборонялись, но вследствие превосходства римлян в силах, осадной технике и военном искусстве, а также недостатка продовольствия были вынуждены капитулировать. Этим закончилось завоевание Галлии. Археологическими раскопками (с 1860) здесь вскрыты осадные сооружения и рвы, воздвигнутые Цезарем. На месте, где, по его сообщению, произошло решающее сражение, найдено оружие римских и галльских типов и монеты (не моложе 52 до н. э.). Город существовал и в римское время: вскрыты римский театр, храмы и др. В средние века запустел и теперь на его месте – городище Ализ и селение Ализ-Сент-Рен.

Осада Алезии в 52 г. до н. э.

Назад к карточке книги "Большая Советская Энциклопедия (АЛ)"