Войти на сайт

или
Регистрация

Навигация


9.4. Завершимость выполнения программы.

Одно из свойств программы, которое нас может интересовать, чтобы избежать возможных ошибок в ПС, является ее завершимость, т.е. отсутствие в ней зацикливания при тех или иных исходных данных. В рассмотренных нами структурированных программах источником зацикливания может быть только конструкция повторения. Поэтому для доказательства завершимости программы достаточно уметь доказывать завершимость оператора цикла. Для этого полезна следующая

Теорема 9.7. Пусть F - целочисленная функция, зависящая от состояния информационной среды и удовлетворяющая следующим условиям:

(1) если для данного состояния информационной среды истинен предикат Q, то ее значение положительно;

(2) она убывает при изменении состояния информационной среды в результате выполнения оператора S.

Тогда выполнение оператора цикла

ПОКА Q ДЕЛАТЬ S ВСЕ ПОКА завершается.

Доказательство. Пусть is - состояние информационной среды перед выполнением оператора цикла и пусть F(is)=k. Если предикат Q(is) ложен, то выполнение оператора цикла завершается. Если же Q(is) истинен, то по условию теоремы k>0. В этом случае будет выполняться оператор S один или более раз. После каждого выполнения оператора S по условию теоремы значение функции F уменьшается, а так как перед выполнением оператора S предикат Q должен быть истинен (по семантике оператора цикла), то значение функции F в этот момент должно быть положительно (по условию теоремы). Поэтому в силу целочисленности функции F оператор S в этом циклене может выполняться более k раз. Теорема доказана.

Например, для рассмотренного выше примера оператора циклаусловиям теоремы 9.7 удовлетворяет функция f(n, m)= n-m. Так как перед выполнением оператора цикла m=1, то тело этого цикла будет выполняться (n-1) раз, т.е. этот оператор цикла завершается.

9.5. Пример доказательства свойства программы.

На основании доказанных правил верификации программ можно доказывать свойства программ, состоящих из операторов присваивания и пустых операторов и использующих три основные композиции структурного программирования. Для этого анализируя структуру программы и используя заданные ее пред- и постусловия необходимо на каждом шаге анализа применять подходящее правило верификации. В случае применения композиции повторения потребуется подобрать подходящий инвариант цикла.

В качестве примера докажем свойство (9.4). Это доказательство будет состоять из следующих шагов.

(Шаг 1). n>0 => (n>0, p - любое, m - любое).

(Шаг 2). Имеет место

{n>0, p - любое, m - любое} p:=1 {n>0, p=1, m - любое}.

-- По теореме 9.2.

(Шаг 3). Имеет место

{n>0, p=1, m - любое} m:=1 {n>0, p=1, m=1}.

-- По теореме 9.2.

(Шаг 4). Имеет место

{n>0, p - любое, m - любое} p:=1; m:=1 {n>0, p=1, m=1}.

-- По теореме 9.3 в силу результатов шагов 2 и 3.

Докажем, что предикат p=m! является инвариантом цикла, т.е. {p=m!} m:=m+1; p:=p*m {p=m!}.

(Шаг 5). Имеет место {p=m!} m:=m+1 {p=(m-1)!}.

-- По теореме 9.2, если представить предусловие в виде {p=((m+1)-1)!}.

(Шаг 6). Имеет место {p=(m-1)!} p:=p*m {p=m!}.

-- По теореме 9.2, если представить предусловие в виде {p*m=m!}.

(Шаг 7). Имеет место инвариант цикл

{p=m!} m:=m+1; p:=p*m {p=m!}.

-- По теореме 9.3 в силу результатов шагов 5 и 6.

(Шаг 8). Имеет место

{n>0, p=1, m=1} ПОКА m /= n ДЕЛАТЬ

m:= m+1; p:= p*m

ВСЕ ПОКА {p= n!}.

-- По теореме 9.6 в силу результата шага 7 и имея в виду, что (n>0, p=1, m= 1)=>p=m!; (p=m!, m=n)=>p=n!.

(Шаг 9). Имеет место

{n>0, p - любое, m - любое} p:=1; m:=1;

ПОКА m /= n ДЕЛАТЬ

m:= m+1; p:= p*m

ВСЕ ПОКА {p= n!}.

-- По теореме 9.3 в силу результатов шагов 3 и 8.

(Шаг 10). Имеет место свойство (9.4) по теореме 9.5 в силу результатов шагов 1 и 9.


Литература к лекции 9.

9.1. С.А. Абрамов. Элементы программирования. - М.: Наука, 1982. С. 85-94.

9.2. М. Зелковец, А. Шоу, Дж. Гэннон. Принципы разработки программного обеспечения. - М.: Мир, 1982. С. 98-105.


Лекция 10. ТЕСТИРОВАНИЕ И ОТЛАДКА ПРОГРАММНОГО СРЕДСТВА

Основные понятия. Стратегия проектирования тестов. Заповеди отладки. Автономная отладка и тестирование программного модуля. Комплексная отладка и тестирование программного средства.

10.1. Основные понятия.

Отладка ПС - это деятельность, направленная на обнаружение и исправление ошибок в ПС с использованием процессов выполнения его программ. Тестирование ПС - это процесс выполнения его программ на некотором наборе данных, для которого заранее известен результат применения или известны правила поведения этих программ. Указанный набор данных называется тестовым или просто тестом. Таким образом, отладку можно представить в виде многократного повторения трех процессов: тестирования, в результате которого может быть констатировано наличие в ПС ошибки, поиска места ошибки в программах и документации ПС и редактирования программ и документации с целью устранения обнаруженной ошибки. Другими словами:

Отладка = Тестирование + Поиск ошибок + Редактирование.

В зарубежной литературе отладку часто понимают [10.1-10.3] только как процесс поиска и исправления ошибок (без тестирования), факт наличия которых устанавливается при тестировании. Иногда тестирование и отладку считают синонимами [10.4,10.5]. В нашей стране в понятие отладки обычно включают и тестирование [10.6 -10.8], поэтому мы будем следовать сложившейся традиции. Впрочем совместное рассмотрение в данной лекции этих процессов делает указанное разночтение не столь существенным. Следует однако отметить, что тестирование используется и как часть процесса аттестации ПС (см. лекцию 14).


Информация о работе «Программирование»
Раздел: Информатика, программирование
Количество знаков с пробелами: 231244
Количество таблиц: 5
Количество изображений: 6

Похожие работы

Скачать
112819
0
0

... . Объясните, для чего служат разрешения и привилегии в Windows NT. Зав. кафедрой --------------------------------------------------   Экзаменационный билет по предмету СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Билет № 22 Перечислите возможности и инструменты системы программирования Microsoft Developer Studio. Укажите для чего предназначается буфер в системах ввода-вывода, ...

Скачать
110612
10
19

... набор процедур и функций языков программирования Basic и Pascal, позволяют управлять графическим режимом работы экрана, создавать разнооборазные графические изображения и выводить на экран текстовые надписи. ГЛАВА 2. ГРАФИЧЕСКИЕ ВОЗМОЖНОСТИ ЯЗЫКА ПРОГРАММИРОВАНИЯ В КУРСЕ ИНФОРМАТИКИ БАЗОВОЙ ШКОЛЫ (НА ПРИМЕРЕ BASIC И PASCAL)   2.1 Разработка мультимедиа курса «Графические возможности языков ...

Скачать
48658
0
0

... времени на возню с файлами на дисках или ожидание ввода, не смогут продемонстрировать какое-то впечатляющее увеличение скорости. 2. КЛАССИФИКАЦИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ 2.1. Машинно – ориентированные языки  Машинно – ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и ...

Скачать
235892
25
6

... работе в графическом режиме предназ­начается для обучения студентов младших курсов Санкт-Петербургской государственной Академии аэрокосмического приборостроения навыкам программирования, а именно работе в графическом режиме языка Turbo-Pascal . Для работы с настоящей программой необходимо знание стандарта языка, интегрированной среды и элементарным навыкам работы с персональным компьютером . ...

0 комментариев


Наверх