В качестве примера приведём (в модернизированном виде) уточнение, предложенное Тьюрингом. Чтобы задать тьюрингов А., надо указать: а) попарно непересекающиеся алфавиты Б, Д, Ч с выделенной в Д буквой 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, когда А. Чёрч опубликовал первое уточнение понятия вычислимой функции (предложив отождествлять понятие всюду определённой вычислимой функции, имеющей натуральные аргументы и значения, с понятием общерекурсивной функции) и привёл первый пример функции, не являющейся вычислимой, а А. М. Тьюринг и Э. Л. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, см. Тьюринга машина ). В дальнейшем А. т. получила развитие в трудах С. К. Клини , Э. Л. Поста, А. А. Маркова и других. В частности, А. А. Марков предложил уточнять понятие алгоритма с помощью введённого им понятия нормального алгоритма . Наиболее общий подход к уточнению понятия алгоритма предложил А. Н. Колмогоров .