ПРОГРА́ММЫ СХЕ́МА
-
Рубрика: Математика
-
Скопировать библиографическую ссылку:
ПРОГРА́ММЫ СХЕ́МА, математич. модель программы, отражающая её структурные свойства. При моделировании программ схемами переменные, операции, предикаты или даже целые фрагменты программ заменяются формальными символами, не имеющими внутр. свойств. В то же время структура программы, в частности информационные и управляющие связи её команд и др. составных частей, при построении П. с. обычно сохраняются. Таким образом, свойства П. с. распространяются на целый класс программ, которые могут быть получены из схемы при той или иной интерпретации, сопоставляющей формальным символам конкретные переменные, операции и предикаты.
Наиболее изученными являются классы стандартных (операторных) и рекурсивных схем. Стандартной схемой называется всякая конечная последовательность (возможно, помеченных) команд следующих трёх типов:
оператор присваивания
x:=f(x1, ..., xn) или x:=y;
условный оператор
if p(x1, ..., xn) then goto M;
оператор перехода goto N;
здесь x, y, x1, ..., xn – символы переменных, p – символ предиката, f – символ функции, M, N – метки команд.
Рекурсивной схемой называется совокупность функциональных определений, имеющих вид α(x1, ..., xn)=T, где α – символ определяемой функции, T – обычный терм, т. е. выражение формализованного языка, образованный суперпозицией определяемых функций и заданных функциональных символов, или условный терм вида
if p(x1, ..., xn) then T1 else T2,
где p – символ предиката, T1, T2 – любые термы.
Центральное понятие теории П. с. – понятие эквивалентности. Примером интерпретационной эквивалентности является функциональная эквивалентность стандартных схем: схемы S1 и S2 эквивалентны, если для любой интерпретации I программы S1(I) и S2(I) вычисляют одну и ту же функцию. Функциональная эквивалентность стандартных схем алгоритмически неразрешима. Понятие формальной эквивалентности не использует интерпретацию: со схемой связывается её детерминант – некоторое множество термов, производное от всех путей в управляющем графе (см. в ст. Программ анализ) от начала к концу; схемы с равными детерминантами объявляются эквивалентными. Введённое таким образом отношение логико-термальной эквивалентности стандартных схем оказывается разрешимым с полиномиальной сложностью.
Лит.: Котов В. Е. Введение в теорию схем программ. Новосиб., 1978.