45. Понятие структурного программирования, этап проектирования – композиция и декомпозиция, понятие статической и динамической структуры программы, спецификация программы.

Говорят, что существует статическая и динамическая структуры программы.

Статическая структура – текст программы и ее структурная схема. Не зависит от исходных данных.

Динамическая структура определяет вычислительный процесс - состояние вычисления программы. Поэтому она(структура) зависит от исходных данных, т.к. от них зависят переходы в программе. Текущее состояние вычислений определяется значением всех входящих величин и зависит от предыдущих состояний вычислений.

Каждый оператор в программе или изменяет состояние вычисления или анализирует его, определяя тем самым переходы.

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

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

Графическое представление:

S – оператор или программа

P – условия для вход.данных

Q – условия для вых.данных

Возможна также запись нотацией: {P}S{Q} – эта запись называется спецификацией.

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

Проектирование сверху-вниз начинается с определения спецификации {P_i}S_i{Q_i} для каждой операции, с доказательством правильности каждой подзадачи и док-вом того, что композиция всех подзадач приведет к выполнению спецификации {P}S{Q}.

46. Понятие частичной и полной корректности программы, правила вывода – общий вид, правила консеквенции.

Правило вывода – рассуждение, которое говорит о том, что если соотношения, записанные над чертой верны, то справедливы и соотношения, записанные под чертой.

H1, H2, … , Hn

H

Рассмотрим правило вывода для простых операторов и как они получаются для составных с использованием композиций простых.

2 правила консеквенции:

1. P->R, {R}S{Q}

{P}S{Q}

Если из соотношения P следует соотношение R (предусловие) и постусловием является Q, то Q можно получить и из соотношения P. ( S – оператор).

2. {P}S{Q}, Q->R

{P}S{R}

Если из P получаем Q, а из Q следует R, то из P, после выполнения S, будет верно R.

Критерий корректности – соотношение является постусловием, если верно предусловие.

Частичная корректность программы – если после выполнения программы получаем результат и полная – если доказываем, что программа выполнима для любых допустимых значений.

47. Правила вывода для операторов: пустого, присваивания, составного.

Пустой оператор. Не выполняет никаких действий, не изменяет состояние вычисления => любое его предусловие будет его постусловием: {P}{P}.

Оператор присваивания: {P^x_l}x = l{P}

| x-y >= 0

\/

x = x-y

| x >= 0

\/

Составной оператор.

{P_i-1}S_i{P_i} для i = 1, 2, .. , n

{P₀} {S₁, S₂, .. , S_n} {P_n}

Для двух операторов:

{P}S1{R}, {R}S2{Q}

{P}S1, S2{Q}