См. также ст. Алгоритмов теория и лит. при этой статье.
В. А. Успенский.
Алгоритмизация процессов
Алгоритмиза'ция проце'ссов, алгоритмическое описание процессов, описание процессов на языке математических символов для получения алгоритма , отображающего элементарные акты процесса, их последовательность и взаимосвязь. Алгоритмы, получающиеся путём А. п., предназначаются, как правило, для реализации на ЭВМ.
Построение алгоритмов, описывающих реальные процессы, связывается обычно с двумя задачами: нахождением эффективных систем обработки информации и исследованием математическими методами процессов функционирования больших систем . В задачах 1-го типа для построения алгоритма управления необходимо к алгоритму, описывающему процесс функционирования системы, присоединить алгоритм определения оптимального решения или оптимальных значений параметров управления. В задачах 2-го типа А. п. функционирования большой системы позволяет провести количественное и качественное исследования, связанные с оценкой основных её свойств (эффективности, надёжности и др.).
Для проведения алгоритмизации процесс расчленяется на элементарные акты (подпроцессы), применительно к которым может быть дано математическое описание, исходя из известных математических схем алгебры логики , конечных автоматов (см. Автоматов теория ), случайных процессов , массового обслуживания теории и др. Соотношения, описывающие элементарные акты процесса, объединяются в систему, дополняются описанием взаимосвязей между актами и представляются в виде алгоритма.
Операции и процедуры, являющиеся элементами алгоритмического описания процесса, для программирования и реализации на ЭВМ удобно записывать на языке программирования , с которого при помощи трансляторов-программ алгоритм автоматически переводится на язык команд (операций) конкретной ЭВМ. При этом одной операции алгоритма может соответствовать в общем случае несколько операций ЭВМ.
Лит.: Глушков В. М., Синтез цифровых автоматов, М., 1962; Бусленко Н. П., Математическое моделирование производственных процессов на цифровых вычислительных машинах, М., 1964; Алгоритмизация производственных процессов [Доклады семинара], в. 1, К., 1966.
Н. П. Бусленко.
Алгоритмов теория
Алгори'тмов тео'рия, раздел математики, изучающий общие свойства алгоритмов . Содержательные явления, приведшие к образованию понятия «алгоритм», прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь в 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) в совокупности дают упоминаемый в ст. Алгоритм пример алгоритма Á с неразрешимой областью применимости.