ПРОГРА́ММЫ СХЕ́МА

ПРОГРА́ММЫ СХЕ́МА, ма­те­ма­тич. мо­дель про­грам­мы, от­ра­жаю­щая её струк­тур­ные свой­ст­ва. При мо­де­ли­ро­ва­нии про­грамм схе­ма­ми пе­ре­мен­ные, опе­ра­ции, пре­ди­ка­ты или да­же це­лые фраг­мен­ты про­грамм за­ме­ня­ют­ся фор­маль­ны­ми сим­во­ла­ми, не имею­щи­ми внутр. свойств. В то же вре­мя струк­ту­ра про­грам­мы, в ча­ст­но­сти ин­фор­ма­ци­он­ные и управ­ляю­щие свя­зи её ко­манд и др. со­став­ных час­тей, при по­строе­нии П. с. обыч­но со­хра­ня­ют­ся. Та­ким об­ра­зом, свой­ст­ва П. с. рас­про­стра­ня­ют­ся на це­лый класс про­грамм, ко­то­рые мо­гут быть по­лу­че­ны из схе­мы при той или иной ин­тер­пре­та­ции, со­пос­тав­ляю­щей фор­маль­ным сим­во­лам кон­крет­ные пе­ре­мен­ные, опе­ра­ции и пре­ди­ка­ты.

Наи­бо­лее изу­чен­ны­ми яв­ля­ют­ся клас­сы стан­дарт­ных (опе­ра­тор­ных) и ре­кур­сив­ных схем. Стан­дарт­ной схе­мой на­зы­ва­ет­ся вся­кая ко­неч­ная по­сле­до­ва­тель­ность (воз­мож­но, по­ме­чен­ных) ко­манд сле­дую­щих трёх ти­пов:

опе­ра­тор при­сваи­ва­ния

x:=f(x₁, ..., x_n) или x:=y;

ус­лов­ный опе­ра­тор

if p(x₁, ..., x_n) then goto M;

опе­ра­тор пе­ре­хо­да goto N;

здесь x, y, x₁, ..., x_n – сим­во­лы пе­ре­мен­ных, p – сим­вол пре­ди­ка­та, f – сим­вол функ­ции, M, N – мет­ки ко­манд.

Ре­кур­сив­ной схе­мой на­зы­ва­ет­ся со­во­куп­ность функ­цио­наль­ных оп­ре­де­ле­ний, имею­щих вид α(x₁, ..., x_n)=T, где α – сим­вол оп­ре­де­ляе­мой функ­ции, T – обыч­ный терм, т. е. вы­ра­же­ние фор­ма­ли­зо­ван­но­го язы­ка, об­ра­зо­ван­ный су­пер­по­зи­ци­ей оп­ре­де­ляе­мых функ­ций и за­дан­ных функ­цио­наль­ных сим­во­лов, или ус­лов­ный терм ви­да

if p(x₁, ..., x_n) then T₁ else T₂,

где p – сим­вол пре­ди­ка­та, T₁, T₂ – лю­бые тер­мы.

Цен­траль­ное по­ня­тие тео­рии П. с. – по­ня­тие эк­ви­ва­лент­но­сти. При­ме­ром ин­тер­пре­та­ци­он­ной эк­ви­ва­лент­но­сти яв­ля­ет­ся функ­цио­наль­ная эк­ви­ва­лент­ность стан­дарт­ных схем: схе­мы S₁ и S₂ эк­ви­ва­лент­ны, ес­ли для лю­бой ин­тер­пре­та­ции I про­грам­мы S₁(I) и S₂(I) вы­чис­ля­ют од­ну и ту же функ­цию. Функ­цио­наль­ная эк­ви­ва­лент­но­сть стан­дарт­ных схем ал­го­рит­ми­че­ски не­раз­ре­ши­ма. По­ня­тие фор­маль­ной эк­ви­ва­лент­но­сти не ис­поль­зу­ет ин­тер­пре­та­цию: со схе­мой свя­зы­ва­ет­ся её де­тер­ми­нант – не­ко­то­рое мно­же­ст­во тер­мов, про­из­вод­ное от всех пу­тей в управ­ляю­щем гра­фе (см. в ст. Про­грамм ана­лиз) от на­ча­ла к кон­цу; схе­мы с рав­ны­ми де­тер­ми­нан­та­ми объ­яв­ля­ют­ся эк­ви­ва­лент­ны­ми. Вве­дён­ное та­ким об­ра­зом от­но­ше­ние ло­ги­ко-тер­маль­ной эк­ви­ва­лент­но­сти стан­дарт­ных схем ока­зы­ва­ет­ся раз­ре­ши­мым с по­ли­но­ми­аль­ной слож­но­стью.

Лит.: Ко­тов В. Е. Вве­де­ние в тео­рию схем про­грамм. Но­во­сиб., 1978.