ПОНЯТИЕ АЛГЕБРАИЧЕСКОЙ СИСТЕМЫ. Общие замечания.

Одной из особенностей абстрактной теории алгоритмов является неизменность набора допустимых средств, используемых для построения записи алгоритма или при его выполнении. Например, все частично рекурсивные функции получаются из некоторого фиксированного набора базисных функций с помощью трех операторов — оператора подстановки, оператора примитивной рекурсии, оператора наименьшего корня.

Элементарные акты при вычислениях на машине Тьюринга ограничиваются фиксированным набором операций, которые выполняет описываемый класс машин и т. д.

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

Поэтому одним из требований, которое предъявляется к определению алгоритма при его практическом использовании, является то, чтобы как вид перерабатываемой информации, так и средства ее переработки выбирались в зависимости от класса рассматриваемых алгоритмов.

В каждой классической алгоритмической системе тем или иным способом вводится понятие выполнения алгоритма, то есть осуществления последовательности актов, производящих постепенный переход от исходных данных к конечному результату. При этом характерно, что в каждом алгоритме список предписаний о выполнении элементарных актов — » команд » алгоритма фиксируется заранее и явно указывается в записи алгоритма.

В то же время допущение формирование команд алгоритма в процессе ее реализации приводит к существенному сокращению и упрощению записи алгоритма. В связи с этим следующим требованием, предъявляемым к понятию алгоритма, является допущение формирования команд алгоритма в процессе его выполнения.

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

Однако, как правило, логические операции в классических алгоритмических системах носят тирвиальный характер. Во многих случаях такая тривиальность логических опрераций сильно усложняет построени конкретных алгоритмов.

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

В той или иной мере этим требованиям отвечают так называемые операторные алгоритмические системы.

 

Логика - доступно для всех