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

  «Уточнения» понятия А. Возможны дальнейшие «уточнения» понятия А., приводящие, строго говоря, к известному сужению этого понятия. Каждое такое уточнение состоит в том, что для каждого из указанных 7 параметров А. точно описывается некоторый класс, в пределах которого этот параметр может меняться. Выбор этих классов и отличает одно уточнение от другого. Во многих уточнениях все классы, кроме двух — класса совокупностей промежуточных результатов и класса правил непосредственной переработки, — выбираются единичными, т. е. все параметры, кроме указанных двух, жестко фиксируются. Поскольку 7 параметров однозначно определяют некоторый А., то выбор 7 классов изменения этих параметров определяет некоторый класс А. Однако такой выбор может претендовать на название «уточнения», лишь если имеется убеждение, что для произвольного А., имеющего допускаемые данным выбором совокупности возможных исходных данных и возможных результатов, может быть указан равносильный ему А. из определённого данным выбором класса А. Это убеждение формулируется для каждого уточнения в виде основной гипотезы, которая — при современном уровне наших представлений — не может быть предметом математического доказательства.

  Первые уточнения описанного типа предложили в 1936 американский математик Э. Л. Пост и английский математик А. М. Тьюринг (см. Тьюринга машина ). Известны также уточнения, сформулированные советскими математиками А. А. Марковым (см. Нормальный алгоритм ) и А. Н. Колмогоровым (последний предложил трактовать конструктивные объекты как топологические комплексы определённого вида, что дало возможность уточнить свойство «локальности» преобразования). Для каждого из предложенных уточнений соответствующая основная гипотеза хорошо согласуется с практикой. В пользу этой гипотезы говорит и то, что, как можно доказать, все предложенные уточнения в некотором естественном смысле эквивалентны друг другу.

  В качестве примера приведём (в модернизированном виде) уточнение, предложенное Тьюрингом. Чтобы задать тьюрингов А., надо указать: а) попарно непересекающиеся алфавиты Б, Д, Ч с выделенной в Д буквой l и выделенными в Ч буквами a и w, б) набор пар вида < рx, hTq >, где р, qÎЧ, x, hÎБÈД, а Т есть один из знаков —, 0, +, причём предполагается, что в этом наборе (называемой программой) нет 2 пар с одинаковыми первыми членами. Параметры А. задаются так: возможными исходными данными и возможными результатами служат слова в Б, а промежуточными результатами — слова в БÈДÈЧ, содержащие не более одной буквы из Ч. Правило начала: исходное слово Р переводится в слово laРl. Правило окончания: заключительным является промежуточный результат, содержащий w. Правило извлечения результата: результатом объявляется цепочка всех тех букв заключительного промежуточного результата, которая идёт вслед за w. и предшествует первой букве, не принадлежащей Б. Правило непосредственной переработки, переводящее А в А', состоит в следующем. Приписываем к А слева и справа букву l; затем в образовавшемся слове часть вида erx, где рÎЧ, заменяем на слово Q по следующему правилу: в программе ищется пара с первым членом рx; пусть второй член этой пары есть hTq; если Т есть - , то Q = qeh, ЕСли Т есть 0, то Q =eqh; если Т есть +, то О = ehq. Возникающее после этой замены слово и есть А'.

  См. также ст. Алгоритмов теория и лит. при этой статье.

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

Алгоритмизация процессов

Алгоритмиза'ция проце'ссов, алгоритмическое описание процессов, описание процессов на языке математических символов для получения алгоритма , отображающего элементарные акты процесса, их последовательность и взаимосвязь. Алгоритмы, получающиеся путём А. п., предназначаются, как правило, для реализации на ЭВМ.

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

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

  Операции и процедуры, являющиеся элементами алгоритмического описания процесса, для программирования и реализации на ЭВМ удобно записывать на языке программирования , с которого при помощи трансляторов-программ алгоритм автоматически переводится на язык команд (операций) конкретной ЭВМ. При этом одной операции алгоритма может соответствовать в общем случае несколько операций ЭВМ.

  Лит.: Глушков В. М., Синтез цифровых автоматов, М., 1962; Бусленко Н. П., Математическое моделирование производственных процессов на цифровых вычислительных машинах, М., 1964; Алгоритмизация производственных процессов [Доклады семинара], в. 1, К., 1966.

  Н. П. Бусленко.

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

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

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