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

Детальный анализ понятия «алгоритм» обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее — областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида <x, f(x)>. (IV) Подмножество А перечислимого множества Х тогда и только тогда разрешимо относительно X, когда А и Х \А перечислимы. (V) Если А и В перечислимы, то A' `EB и А CВ также перечислимы. (VI) В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением [в силу (IV) это перечислимое подмножество будет неразрешимым относительно X]. (VII) Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают упоминаемый в ст. Алгоритм пример алгоритма 'A с неразрешимой областью применимости.

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

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

Приложения А. т. имеются во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают в математической логике и теории моделей; для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех её предложений (теории подразделяются на разрешимые и неразрешимые — в зависимости от разрешимости или неразрешимости указанной проблемы); в 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 млрд. лет), палеозоя и мезозоя.