Базис стандартной и рекурсивной схемы. Верификация программы

Министерство РФ по связи и информатизации

«Поволжская государственная академия телекоммуникаций и информатики»

Кафедра «программного обеспечения информационных технологий»



























КОНТРОЛЬНАЯ РАБОТА ПО КУРСУ:

«Теория вычислительных процессов»























2010

Задание 1

Построить базис стандартной схемы;

Реализовать стандартную схему в графовой и линейной формах;

Составить интерпретацию для заданной стандартной схемы;

6

Расчет суммы чисел Фибоначчи

Расчет суммы первых четырех чисел Фибоначчи

Числа Фибоначчи (F>i>) определяются по формулам F>0 >= F>1 >= 1; F>i> = F>i –1> + F>i –2> при i = 2, 3, ... (каждое очередное число равно сумме двух предыдущих).

Вычислим сумму первых четырёх чисел Фибоначчи, которые не превосходят заданного натурального числа М. Зададим число M = 4.

алгоритм Фибоначчи (аргумент целое М, результат целое S)

дано | M>0

начало цел F0, F1, F2

F0:=1; F1:=1; F2:=2

S:=4 | 4 – сумма первых трех чисел Фибоначчи

начинается пока F2<=M

F0:=F1; F1:=F2; F2:=F0+F1 | серия переприсваиваний

S:=S+F2;

кончается

S:=S–F2 | из S вычитается последнее значение F2, превосходящее M

Конец

Исполнение алгоритма

F0

F1

F2

S

F2<M

1

1

2

4

+

1

2

3

4+3

+

2

3

5

7+5

− (кц)

12-5=7

Базис класса стандартных схем программ

Полный базис класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов - слов, построенных из этих символов.

Множества символов полного базиса:

1. X = {F>0>, F>1>, F>2>, S, M} - множество символов, называемых переменными;

2. Множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c...;

3. Множество предикатных символов; нульместные символы называют логическими константами;

4. {program, uses, var, begin, end} - множество специальных символов.

Множество операторов включает пять типов:

1. начальный оператор - слово вида start(F>0>, F>1>, F>2>), где F>0>, F>1>, F>2 >- переменные, называемые результатом этого оператора;

2. заключительный оператор - слово вида stop(S), S - терм; вхождения переменных в терм S называются аргументами этого оператора;

3. оператор присваивания – F>0>:=1; F>1>:=1; F>2>:=2; S:=4; F>0>:=F>1>; F>1>:=F>2>; F>2>:=F>0>+F>1>; S:=S+F>2>; S:=S–F>2>;

4. условный оператор (тест) – логическое выражение; F>2><=M;

5. оператор петли - односимвольное слово While.

Графовая форма стандартной схемы на рис. 1.

0100090000037800000002001c00000000000400000003010800050000000b0200000000050000000c02430f3608040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d000f36080000056c0000985c110004ee8339f0d350020c020000040000002d01000004000000020101001c000000fb029cff0000000000009001000000cc0440001254696d6573204e657720526f6d616e0000000000000000000000000000000000040000002d010100050000000902000000020d000000320a960f000001000400000000003a083c0f20002d00040000002d010000030000000000

Рис. 1

Линейная форма стандартной схемы

Turbo Pascal

Program SummaFib;

Uses Crt;

Var M, {zadannoe chislo}

F0, F1, F2, {3 posledovatelnyh chisla Fibonachchi}

S : Integer; {summa chisel Fibonachi}

BEGIN

ClrScr;

Write('Vvedite naturalnoe M : ');

ReadLn(M);

F0:=1; F1:=1; F2:=2;

S:=4; {4 - summa pervih 3-h chisel Fibonachchi}

Write('Chisla Fibonachchi, ne prevoshodyaschie ', M, ' :', F0:4, F1:4);

While F2<=M do

begin

F0:=F1; F1:=F2; Write(F1 : 4);

F2:=F0+F1; S:=S+F2;

end;

S:=S-F2; {vychitanie iz summy poslednego chisla, kotoroe prevoshodit M}

WriteLn; WriteLn;

WriteLn('OTVET: Summa etih chisel ravna = ', S); ReadLn

END.

Задание 2

Построить базис рекурсивной схемы;

Составить интерпретацию для заданной рекурсивной схемы (рис. 2);

Составить протокол выполнения программы;

6

Составить рекурсивную программу-функцию подсчета количества всех положительных делителей натурального числа n.

Рассчитать количество делителей для числа 10.

0100090000037800000002001c00000000000400000003010800050000000b0200000000050000000c02430f3608040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d000f36080000056c0000985c110004ee8339f0d350020c020000040000002d01000004000000020101001c000000fb029cff0000000000009001000000cc0440001254696d6573204e657720526f6d616e0000000000000000000000000000000000040000002d010100050000000902000000020d000000320a960f000001000400000000003a083c0f20002d00040000002d010000030000000000

Рис. 2

TURBO PASCAL

program Chislo;

uses crt;

type r=array[1..10] of integer;

var

d,x:integer;

a:r;

y:integer;

begin

clrscr;

y:=1;

textcolor(6);

write('NAHOZHDENIE DELITELEJ');

gotoxy(2,2);

textcolor(9);

write('Vedite chislo, u kotorogo nado najti kolichestvo delitelej: ');

readln(x);

textcolor(6);

write ('Deliteli chisla ' ,x, ' : ');

for d:=1 to x div 2 do

begin

textcolor(9);

if x mod d=0 then begin

write(d,' ');

inc(y);end;end; {Y:= Y + 1}

writeln(x);

textcolor(5);

write('Kolichestvo delitelej: ' ,y);

readln;

end.

Результат работы PASCAL-программы (рис. 3)

Рис. 3

Задание 3

Разработать алгоритм программы, решающей поставленную задачу;

Составить стандартную схему программы и записать полученную программу в линейной форме (рис. 4);

Для каждого оператора программы, записанного в линейной форме определить слабейшие предусловия.



6

Расчет суммы чисел Фибоначчи

0100090000037800000002001c00000000000400000003010800050000000b0200000000050000000c02430f3608040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d000f36080000056c0000985c110004ee8339f0d350020c020000040000002d01000004000000020101001c000000fb029cff0000000000009001000000cc0440001254696d6573204e657720526f6d616e0000000000000000000000000000000000040000002d010100050000000902000000020d000000320a960f000001000400000000003a083c0f20002d00040000002d010000030000000000

Рис. 4

Turbo Pascal

Program SummaFib;

Uses Crt;

Var M, {Zadannoe chislo}

F0, F1, F2, {3 posledovatelnyh chisla Fibonachchi}

S : Integer; {Summa chisel Fibonachch}

BEGIN

ClrScr;

Write('Vvedite naturelnoe chislo M: ');

ReadLn(M);

F0:=1; F1:=1; F2:=2;

S:=4; {4 - summa pervyh 3-x chisel Fibonachchi}

Write('Chisla Fibonachchi, ne prevoshodyaschie ', M, ' :', F0:4, F1:4);

While F2<=M do

begin

F0:=F1; F1:=F2; Write(F1 : 4);

F2:=F0+F1; S:=S+F2;

end;

S:=S-F2; {vychitanie iz summy poslednego chisla, kotoroe prevoshodit M}

WriteLn; WriteLn;

WriteLn('O T V E T: Summa etih chisel ravna ', S); ReadLn

END.

Результаты работы Pascal-программы (рис. 5).

Рис. 5

Слабейшие предусловия операторов:

1. начальный оператор - слово вида start (F>0>, F>1>, F>2>), где F>0> = 1, F>1> = 1,

F>2 >- переменные, называемые результатом этого оператора;

2. заключительный оператор - слово вида stop (S), где S = 2 - терм; вхождения переменных в терм S называются аргументами этого оператора;

3. оператор присваивания – F>0>:=1; F>1>:=1; F>2>:=2; S:=4; F>0>:=F>1>, где F>1>=1; F>1>:=F>2>, где F>2>=2; F>2>:=F>0>+F>1>, где F>0>=1, F>1>=1; S:=S+F>2>, где S=4, F>2>=3; S:=S–F>2>, где S=4, F>2>=2;

4. условный оператор (тест) – логическое выражение; F>2><=M, где F>2>=2,

M>1;

5. оператор петли - односимвольное слово While. Слабейшее предусловие такое же, как в условном операторе.

Задание 4

Разработать алгоритм программы, решающей поставленную задачу;

Составить стандартную схему программы и записать полученную программу в линейной форме (рис. 6);

Используя метод индуктивных утверждений и правила верификации Хоара произвести верификацию программы.

6

Расчет произведения чисел Фибоначчи

0100090000037800000002001c00000000000400000003010800050000000b0200000000050000000c02430f3608040000002e0118001c000000fb021000070000000000bc02000000cc0102022253797374656d000f36080000056c0000985c110004ee8339f0d350020c020000040000002d01000004000000020101001c000000fb029cff0000000000009001000000cc0440001254696d6573204e657720526f6d616e0000000000000000000000000000000000040000002d010100050000000902000000020d000000320a960f000001000400000000003a083c0f20002d00040000002d010000030000000000

Рис. 6

Turbo Pascal

Program ProizFib;

Uses Crt;

Var M, {zadannoe chislo }

F0, F1, F2, {tri posledovatelnyh chisla Fibonachchi}

S : Integer; {summa chisel Fibonachchi}

R : Real; {proizvedenie chisel Fibonachchi}

BEGIN

ClrScr;

Write('Vvedite naturalnoe chislo M: ');

ReadLn(M);

F0:=1; F1:=1; F2:=2;

S:=4; {4 - summa pervyh 3-x chisel Fibonachchi}

R:=2; {2 - proizvedenie pervyh 3-x chisel Fibonachchi}

Write('Chisla Fibonachchi, ne prevoshodyaschie ', M, ' :', F0:4, F1:4);

While F2<=M do

begin

F0:=F1; F1:=F2; Write(F1 : 4);

F2:=F0+F1; S:=S+F2; R:=R*F2

end;

S:=S-F2; {vychitanie iz summy poslednego chisla, kotoroe prevoshodit M}

R:=R/F2; {Delenie iz proizvedeniya chisla, kotoroe prevoshodit M}

WriteLn; WriteLn;

WriteLn('O T V E T: Summa etih chisel ravna: ', S); ReadLn;

WriteLn; WriteLn;

WriteLn('O T V E T: Proizvedenie etix chisel ravno: ', R); ReadLn

END.

Результаты работы Pascal-программы (рис. 7).

Рис. 7

Задание 5

Составить алгоритм выполняемого процесса;

Определить множества условий и событий для процесса;

Построить сеть Петри для моделируемого процесса.

6

Работа банкомата в режиме выдачи наличных денежных средств

Условиями для рассматриваемой системы являются:

а) банкомат ждет;

б) запрос поступил и ждет;

в) банкомат обрабатывает запрос;

г) запрос обработан.

Событиями для этой системы являются:

1.Запрос поступил.

2. Банкомат начинает обработку запроса.

3. Банкомат заканчивает обработку запроса.

4. Результат обработки выдаются деньги клиенту.

Для перечисленных событий можно составить следующую таблицу их пред- и постусловий (рис. 8).

Событие

Предусловия

Постусловия

1

2

3

4

нет

а, б

в

г

б

в

г, а

нет


Рис. 8

Предусловие выполняется для события 2.