Порядок разработки программного модуля
Пошаговая детализация и понятие о псевдокоде
Контроль программного модуля
Свойства основных конструкций структурного программирования
Завершимость выполнения программы
Принципы и виды отладки
Автономная отладка модуля
Комплексная отладка программного средства
Функциональность и надежность как обязательные критерии качества программного средства
Обеспечение автономности программного средства
Обеспечение легкости применения программного средства
Пользовательская документация программных средств
Назначение аттестации программного средства
Навигация
Свойства основных конструкций структурного программирования
Программирование
231244
знака
5
таблиц
6
изображений
9.3. Свойства основных конструкций структурного программирования.
Рассмотрим теперь свойства основных конструкций структурного программирования: следования, разветвления и повторения.
Свойства следования выражает следующая
Теорема 9.3. Пусть P, Q и R - предикаты над информационной средой, а S1 и S2 - обобщенные операторы, обладающие соответственно свойствами
{P}S{Q} и {Q}S2{R}.
Тогда для составного оператора
S1; S2<.blockquote>
имеет место свойство
{P} S1; S2 {R} .
Доказательство. Пусть для некоторого состояния информационной среды перед выполнением оператора S1 истинен предикат P. Тогда в силу свойства оператора S1 после его выполнения будет истинен предикат Q. Так как по семантике составного оператора после выполнения оператора S1 будет выполняться оператор S2, то предикат Q будет истинен и перед выполнением оператора S2. Следовательно, после выполнения оператора S2 в силу его свойства будет истинен предикат R, а так как оператор S2 завершает выполнение составного оператора (в соответствии с его семантикой), то предикат R будет истинен и после выполнения данного составного оператора, что и требовалось доказать.
Например, если имеют место свойства (9.2) и (9.3), то имеет
место и свойство
{n<m} n:=n+k; n:=3*n {n<3*(m+k)}.
Свойство разветвления выражает следующая
Теорема 9.4. Пусть P, Q и R - предикаты над информационной средой, а S1 и S2 - обобщенные операторы, обладающие соответственно свойствами
{P,Q} S1{R} и {`P,Q} S2 {R}.
Тогда для условного оператора
ЕСЛИ P ТО S1 ИНАЧЕ S2 ВСЕ ЕСЛИ
имеет место свойство
{Q} ЕСЛИ P ТО S1 ИНАЧЕ S2 ВСЕ ЕСЛИ {R} .
Доказательство. Пусть для некоторого состояния информационной среды перед выполнением условного оператора истинен предикат Q. Если при этом будет истинен также и предикат P, то выполнение условного оператора в соответствии с его семантикой сводится к выполнению оператора S1. В силу же свойства оператора S1 после его выполнения (а в этом случае - и после выполнения условного оператора) будет истинен предикат R. Если же перед выполнением условного оператора предикат P будет ложен (а Q, по-прежнему, истинен), то выполнение условного оператора в соответствии с его семантикой сводится к выполнению оператора S2. В силу же свойства оператора S2 после его выполнения (а в этом случае - и после выполнения условного оператора) будет истинен предикат R. Тем самым теорема полностью доказана.
Прежде чем переходить к свойству конструкции повторения следует отметить полезную для дальнейшего
Теорему 9.5. Пусть P, Q, P1 и Q1 - предикаты над информационной средой, для которых справедливы импликации
P1=>P и Q=>Q1,
и пусть для оператора S имеет место свойство {P}S{Q}.Тогда имеет место свойство {P1}S{Q1} .
Эту теорему называют еще теоремой об ослаблении свойств.
Доказательство. Пусть для некоторого состояния информационной среды перед выполнением оператора S истинен предикат P1. Тогда будет истинен и предикат P (в силу импликации P1=>P). Следовательно, в силу свойства оператора S после его выполнения будет истинен предикат Q, а значит и предикат Q1 (в силу импликации Q=>Q1). Тем самым теорема доказана.
Свойство повторения выражает следующая
Теорема 9.6. Пусть I, P, Q и R - предикаты над информационной средой, для которых справедливы импликации
P=>I и (I,`Q)=>R ,
и пусть S - обобщенный оператор, обладающий свойством {I}S{I}.
Тогда для оператора цикла
ПОКА Q ДЕЛАТЬ S ВСЕ ПОКА
имеет место свойство
{P} ПОКА Q ДЕЛАТЬ S ВСЕ ПОКА {R} .
Предикат I называют инвариантом оператора цикла.
Доказательство. Для доказательства этой теоремы достаточно доказать свойство
{I} ПОКА Q ДЕЛАТЬ S ВСЕ ПОКА {I,`Q}
(по теореме 9.5 на основании имеющихся в условиях данной теоремы импликаций). Пусть для некоторого состояния информационной среды перед выполнением оператора цикла истинен предикат I. Если при этом предикат Q будет ложен, то оператора цикла будет эквивалентен пустому оператору (в соответствии с его семантикой) и в силу теоремы 9.1 после выполнения оператора цикла будет справедливо утверждение (I,`Q). Если же перед выполнением оператора цикла предикат Q будет истинен, то оператор цикла в соответствии со своей семантикой может быть представлен в виде составного оператора S; ПОКА Q ДЕЛАТЬ S ВСЕ ПОКА
В силу свойства оператора S после его выполнения будет истинен предикат I, и возникает исходная ситуация для доказательства свойства оператора цикла: предикат I истинен перед выполнением оператора цикла, но уже для другого (измененного) состояния информационной среды (для которого предикат Q может быть либо истинен либо ложен). Если выполнение оператора цикла завершается, то применяя метод математической индукции мы за конечное число шагов, придем к ситуации, когда перед его выполнением будет справедливо утверждение (I,`Q). А в этом случае, как было доказано выше, это утверждение будет справедливо и после выполнения оператора цикла. Теорема доказана.
Например, для оператора цикла из примера (9.4) имеет место свойство
{n>0, p=1, m=1} ПОКА m /= n ДЕЛАТЬ
m:= m+1; p:= p*m
ВСЕ ПОКА {p= n!}.
Это следует из теоремы 9.6, так как инвариантом этого оператора цикла является предикат p=m! и справедливы импликации(n>0, p=1, m=1) => p=m! и (p=m!, m=n) => p=n!
Похожие работы
... . Объясните, для чего служат разрешения и привилегии в Windows NT. Зав. кафедрой -------------------------------------------------- Экзаменационный билет по предмету СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Билет № 22 Перечислите возможности и инструменты системы программирования Microsoft Developer Studio. Укажите для чего предназначается буфер в системах ввода-вывода, ...
... набор процедур и функций языков программирования Basic и Pascal, позволяют управлять графическим режимом работы экрана, создавать разнооборазные графические изображения и выводить на экран текстовые надписи. ГЛАВА 2. ГРАФИЧЕСКИЕ ВОЗМОЖНОСТИ ЯЗЫКА ПРОГРАММИРОВАНИЯ В КУРСЕ ИНФОРМАТИКИ БАЗОВОЙ ШКОЛЫ (НА ПРИМЕРЕ BASIC И PASCAL) 2.1 Разработка мультимедиа курса «Графические возможности языков ...
... времени на возню с файлами на дисках или ожидание ввода, не смогут продемонстрировать какое-то впечатляющее увеличение скорости. 2. КЛАССИФИКАЦИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ 2.1. Машинно – ориентированные языки Машинно – ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и ...
... работе в графическом режиме предназначается для обучения студентов младших курсов Санкт-Петербургской государственной Академии аэрокосмического приборостроения навыкам программирования, а именно работе в графическом режиме языка Turbo-Pascal . Для работы с настоящей программой необходимо знание стандарта языка, интегрированной среды и элементарным навыкам работы с персональным компьютером . ...
0 комментариев