АЛГОРИТМОВ ГРАФ-СХЕМЫ, ГРАФ-СХЕМЫ АЛГОРИТМОВ

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

Первые понятия и проблемы, относящиеся К А. г.-с., связанные с их формальными преобразованиями для целей программирования, ввели в 1956 сов. математики А. А. Ляпунов и Ю. И. Янов и в 1959 Л. A. Калужнин. Первым классом, подвергнутым систематическому изучению, был подкласс А. г.-с., в которых распознавателями являются булевы функции переменных , а для каждого преобразователя указывается, какие из он может Изменять. В качестве инварианта рассматривалось мн-во путей в графе переходов, в которых учитываются только преобразователи и значения переменных . При этом определении эквивалентности была построена полная система преобразований в условиях линейной записи. А. г.-с., предложенные Ю. И. Яновым, легли в основу многих исследований. Они касались усовершенствования системы преобразований, доказательства независимости отдельных преобразований и распространения теории на случаи, когда между операторами схемы и их композициями допускаются отношения тождества, описываемые некоторой полугруппой над мн-вом операторов. Понятие А. г.-с. явилось источником различных обобщений и модификаций, приспособленных для целей теоретического программирования, привело к формулировке таких важных понятий, как операторные схемы и алгоритмов схемы.

Лит.: Калужнин Л. А. Об алгоритмизации математических задач. «Проблемы кибернетики», 1959, в. 2; Ершов А. П., Ляпунов А. А. О формализации понятия программы. «Кибернетика», 1967, Ns 5. А. П. Ершов.