У вас вопросы?
У нас ответы:) SamZan.net

Лабораторная работа 6 ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ ПРОГРАММ МЕТОДОМ ПРОГРАММНЫХ ФУНКЦИЙ Цель работы- ов

Работа добавлена на сайт samzan.net: 2016-03-13

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 28.2.2025

Лабораторная работа 6

ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ ПРОГРАММ МЕТОДОМ ПРОГРАММНЫХ ФУНКЦИЙ

Цель работы: овладение техникой доказательства правильности линейных, ветвящихся и циклических структурированных программ.

Контрольные вопросы

1. Какова стратегия доказательства правильности не элементарных структурированных программ?

2. Назначение аксиомы замещения?

3. Как формулируется лемма о сведении циклических программ к рекурсивным?

4. Методика доказательства правильности циклических программ?

5. Назначение и структура трассировочных таблиц?

Методические указания

Если программа Р не является элементарной программой, то при доказательстве правильности пароизводится разложение Р на элементарные составляющие программы. Пусть, например, имеется функция f и соответствующая программа F = IF p THEN G ELSE H FI, где G и H являются также программами. Вместо прямой верификации равенства

f = [IF p THEN G ELSE H FI] доказательство правильности проводится

в два этапа:

- в первую очередь доказывается правильность составляющих программ G и H на основе предположения об их программных функциях g и h, т.е. доказывается, что g=[G] и h=[H];

- если первый этап доказательства завершился успешно, то проводится доказательство равенства f=[IF p THEN g ELSE h FI].

Правомочность подстановки в программу F вместо программ G и H их программных функций g и h базируется на аксиоме замещения [ ].

Если верифицируемая программа Р является ациклической, то доказательство правильности может быть проведено непосредственным построением [P] по схеме выполнения программы и сравнением [P] с заданной функцией f.

Верификацию циклических программ типа WHILE-DO, DO-UNTIL, DOWHILE-DO можно свести к доказательству их окончания и к доказательству правильности ациклических рекурсивных программ. Сведение циклических программ к рекурсивным основано на следующей лемме [ ].

Лемма. Пусть даны функции f, g, h и предикат p. Тогда:

а) (f=[WHILE p DO g OD]) <--> (fin(f, WHILE p DO g OD) & f=[IF p THEN g; f FI]);

б) (f=[DO g UNTIL p OD]) <--> (fin(f, DO g UNTIL p OD) & f=[g; IF - p THEN f FI]);

в) (f=[DO1 g WHILE p DO2 h OD]) <--> (fin(f, DO1 g WHILE p DO2 h OD) & f=[g; IF p THEN h; f FI]).

где fin(f,P) - предикат, принимающий значение "истина" когда программа Р заканчивается для любого Х из области определения функции f.

Для вывода программных функций можно использовать трассировочные таблицы [ ].

Пример 1.  Необходимо построить программную функцию для программы

x := x + a;

y := y + x;

x := x - y;

Трассировочная таблица для этой программы будет иметь вид:

Шаг

Оператор программы

Д а н н ы е

X

Y

1

2

3

x := x+a

y := y+x

x := x-y

x1:= x2:=

x3:=

x0 + a

x1

x2 – y2

y1:=

y2:=

y3:=

y0

y1 + x1

y2

Все данные в таблице имеют индексы, соответствующие шагам вычислений, индекс начальных значений данных равен нулю.  Из трассировочной таблицы легко вывести функцию программы:

x3 : = x2 – y2 := x1 – y1 – x1  :=  -y1  =  -y0

y3 : = y2  := y1 + x1 := y0 + x0 + a

Следовательно, приведенная программа имеет функцию

x , y  :=  -y , y+x+a.

Задание к лабораторной работе

Методом программных функций доказать правильность программы, выполняющей заданную обработку массива (см. табл.). Составить структурированную программу (блок-схему) и выполнить ее верификацию с использованием программных функций.

Порядок выполнения работы

При верификации структурированной программы на основе программных функций следует придерживаться следующей методики:

- составить структурированную программу обработки массива;

- с помощью декомпозиции разбить исходную программу на ряд более простых программ и доказать правильность каждой из них в отдельности;

- используя аксиому замещения, доказать правильность исходной программы.

Если какая-нибудь подпрограмма является ациклической, то доказательство правильности проводится на основе построения её Е-схемы.

В случае циклической программы методика верификации состоит в следующем:

- формулируется гипотеза о программной функции (она может быть и задана);

- путем анализа программы устанавливается истинность условия окончания fin(f,p);

- с использованием леммы о рекурсивном представлении циклическая подпрограмма приводится к рекурсивной форме;

- с помощью трассировочных таблиц строится программная функция рекурсивной подпрограммы;

- проводится сравнение полученной функции с гипотезой и делается вывод о правильности программы.

Содержание отчета

1. Название и цель работы.

2. Блок-схема верифицируемой программы.

3. Доказательство правильности программы методом программных функций.

Таблица 1

N

варианта

Задание по обработке массива чисел

1

2

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

Упорядочение элементов по возрастанию

Определение минимума

Нахождение суммы элементов

Замещение отрицательных элементов массива нулями

Упорядочение элементов по убыванию

Определение максимального элемента

Определение места заданного элемента в массиве

Определение суммы отрицательных элементов

Упорядочение по возрастанию абсолютных величин

Определение суммы квадратов

Подсчет количества положительных элементов

Подсчет количества отрицательных элементов

Упорядочение по убыванию абсолютных величин

Определение произведения элементов

Подсчет количества одинаковых элементов заданной величины

Определение среднего арифметического

Определение минимального положительного элемента

Определение максимального отрицательного элемента

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

Определение максимального положительного элемента

Определение минимального отрицательного элемента

Определение суммы положительных элементов

Определение произведения положительных элементов

Нахождение суммы модулей

Определение суммы четных элементов

Определение произведения отрицательных элементов

Выделение первых K положительных элементов

Пересылка положительных элементов в начало

Нахождение среднего геометрического




1. А Сегодня раздается много похвал по поводу состояния экономики США
2.  Общее понятие о темпераментеТемперамент это индивидуальные особенности человека определяющие динамику
3. Тема 9- Антикризисные стратегии корпорации Содержание- 1
4. Песня года 1 2 3 4 5 18 голосов Муниципальное образовательное учреждение средняя общеобразователь.
5. Этикет ~ это совокупность правил поведения регулирующих внешнее проявления человеческих взаимоотношени
6. европейская идея приобрела после окончания Первой мировой войны
7. довании страхового случая
8. ВВЕДЕНИЕ Актуальность работы обусловлена тем что вендинг активно входит в обиход предпринимателе1
9. I ПОЛИТИЧЕСКИЕ ПРИНЦИПЫ И ЦЕННОСТИ
10. это государь сплачивающий общество и использующий любые средства для поддержания общественного порядка и