Построить базис стандартной схемы - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Построить базис стандартной схемы - страница №1/1

Вариант 6.

1 Задание:Расчет суммы чисел Фибоначчи

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

Базис {a[i], y, s, i}, {q, q1, q2, f(2), h(2)}, {p(2)}, {start, stop, if, then, (, ), :=, ,} и множество операторов { start(y); s:=q; a[q]:=q; a[q1]:=q1; i:=q2; p(i,y); a[i]:=f(a[h(i,q1)], a[h(i,q2)]) ; s:=f (s,a[i]); i:=f(i,q1); stop(s)}


Стандартная схема в линейной форме
0: Start(y)

1: s:=q;


2: a[q]:=q;

3: a[q1]:=q1;

4: i:=q2;

5: if p(i,y) then goto 8;

6: a[i] :=f(a[h(i,q1)], a[h(i,q2)]) ;

7: s:=f (s,a[i]);

8: i:=f(i,q1);goto 5;

9: Stop(s);



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

Программа

Begin integer y,s,i,a[i];

Ввод (y);

s:=0;

a[0]:=0;


a[1]:=1;

i:=2;


Lb1: if i>=y then goto Lb2;

a[i] :=a[i-1] + a[i-2];

s:=s + a[i];

i:=i+1;goto Lb1;

Lb2: Вывод(s);

End.
Графовая форма.



0

Start(y)



1

s:=q



2

a[q]:=q



3

a[q1]:=q1




i:= q2



4




1

5

p(i,y)



0



9

6

a[i] :=f(a[h(i,q1)], a[h(i,q2)])

Stop(s)



7

s:=f (s,a[i])



8

i:=f(i,q1)



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

Интерпретация (S1, I1) задана так:

  • область интерпретации D1 Nat – подмножества Nat целых неотрицательных чисел.

  • I1(q)=0; I1(q1)=1; I1(q2)=2; I1(y)=4; I1(i)=0; I1(s)=0;

  • I1(h)=H, где H – функция вычитания чисел, т.е. H(d1,d2)=d1-d2;

  • I1(f)=F, где F – функция сложения чисел, т.е F(d1,d2)=d1+d2;

  • I1(p)=P, где P – предикат «равно 0», т.е P(d1,d2)=0, если d1<=d2;




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

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

Ряд из первых 4 чисел Фибоначчи: 1 1 2 3



Сумма равна 6.

Конфигурация

U0

U1

U2

U3

U4

U5

U6

U7

U8

U9

U10

U11

U12

U13

U14

U15

U16

U17

Метка

0

1

2

3

4

5

6

7

8

5

6

7

8

5

6

7

8

9

Значения

y

4

4

4

4

4

4

4

4

4

4

4

4

4

4

4

4

4

4

a [0]

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

a [1]

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

i

0

0

0

0

2

2

2

2

3

3

3

3

4

4

4

4

5

5

a [i]

0

0

0

0

0

0

1

1

1

1

2

2

2

2

3

3

3

3

s

0

0

0

0

0

0

0

1

1

1

1

3

3

3

3

6

6

6



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




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

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

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

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

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

Базис {n, i, k},{q1,m(1),g(2),p1(2),p2(1),F(1)} ,{start,stop,if,then,else,(,),:=, ,}
Start (n);

if p1(n,i) then goto Lb1;

F(i): if p2(m(g(n,i))) then k:=z(k,q1);F(z(i,q1));

else F(z(i,q1));

Lb1:Stop(k).

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

Интерпретация (S1,I1) задана так:


  • область интерпретации D1  Nat - подмножество множества Nat целых неотрицательных чисел;

  • I1(n)=10, I1(q1)=1, I1(i)=1

  • I1(g)=G,где G- функция деления 2 чисел,т.е G(d1,d2)=d1/d2;

  • I1(m)=M, где M – функция нахождения остатка от деления, т.е. M(d1)=mod(d1);

  • I1(z)=Z,где Z – функция сложения 2 чисел,т.е Z(d1,d2)=d1+d2;

  • I1(F)=F(x) – вызов функции подсчета количества всех положительных делителей натурального числа n



2.3 Протокол выполнения программы

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

В результате выполнения программа выдаст следующие числа: 1, 2, 5, 10



  1. Задание: Расчет суммы чисел Фибоначчи

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

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

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

Решение:

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

Ряд чисел Фибоначчи – это последовательность чисел в которой, каждый следующий член ряда равен сумме 2 предыдущих. Такой ряд начинается с двух единиц.

Запрашиваем у пользователя, сколько первых членов суммировать(у).Присваиваем нулевому элементу массива значение 0,а первому элементу массива значение 1. Со второго элемента мы начинаем в цикле искать значения следующих элементов последовательности и суммировать их.

Блок-схема алгоритма:


Начало



y



s:=0;

a[0]:=0;


a[1]:=1;

i:=2;





i>y



s




a[i] :=a[i-1] + a[i-2];

s:=s + a[i];

i:=i+1;




Конец

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




Стандартная схема в линейной форме
0: Start(y)

1: s:=q;{

2: a[q]:=q;

3: a[q1]:=q1;

4: i:=q2;

5: if p(i,y) then goto 8;

6: a[i] :=f(a[h(i,q1)], a[h(i,q2)]) ;

7: s:=f (s,a[i]);

8: i:=f(i,q1);goto 5;

9: Stop(s);


Программа

Begin integer y,s,i,a[i];

Ввод (y);

s:=0;

a[0]:=0;


a[1]:=1;

i:=2;


Lb1: if i>y then goto Lb2;

a[i] :=a[i-1] + a[i-2];

s:=s + a[i];

i:=i+1;goto Lb1;

Lb2: Вывод(s);

End.


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

0: Start(y)

1: s:=q;{s>0}

2: a[q]:=q;{a[i]>0,a[i]- натуральные числа}

3: a[q1]:=q1; ;{a[i]>0,a[i]- натуральные числа}

4: i:=q2;{i>=2}

5: if p(i,y) then goto 8;{y>i>=2,y>0}

6: a[i] :=f(a[h(i,q1)], a[h(i,q2)]) ; {a[i]>0,a[i]- натуральные числа}

7: s:=f (s,a[i]); {s>0}

8: i:=f(i,q1);goto 5;{i>=2}

9: Stop(s);


  1. В соответствии с вариантом задания необходимо:

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

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

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

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



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

Ряд чисел Фибоначчи – это последовательность чисел в которой, каждый следующий член ряда равен сумме 2 предыдущих. Такой ряд начинается с двух единиц.

Запрашиваем у пользователя, сколько первых членов суммировать(у).Присваиваем нулевому элементу массива значение 0,а первому элементу массива значение 1. Со второго элемента мы начинаем в цикле искать значения следующих элементов последовательности и перемножать их.

Блок-схема алгоритма:


Начало



y



pr:=1;

a[0]:=0;


a[1]:=1;

i:=2;





i>y



pr




a[i] :=a[i-1] + a[i-2];

pr:=pr* a[i];

i:=i+1;




Конец



Стандартная схема в линейной форме
0: Start(y)

1: pr:=q1;{

2: a[q]:=q;

3: a[q1]:=q1;

4: i:=q2;

5: if p(i,y) then goto 8;

6: a[i] :=f(a[h(i,q1)], a[h(i,q2)]) ;

7: pr:=g (pr,a[i]);

8: i:=f(i,q1);goto 5;

9: Stop(pr);


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

Программа

Begin integer y,pr,i,a[i];

Ввод (y);

pr:=1;

a[0]:=0;


a[1]:=1;

i:=2;


Lb1: if i>y then goto Lb2;

a[i] :=a[i-1] + a[i-2];

pr:=pr*a[i];

i:=i+1;goto Lb1;

Lb2: Вывод(pr);

End.



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

Входные данные y и выходные данн pr, y>0.

Ввести(y);

pr:=1;


a[0]:=0;

a[1]:=1;


i:=2;

while i<=y do

begin

a[i] :=a[i-1] + a[i-2];



pr:=pr*a[i];

i:=i+1;


end;

Вывести(pr);


Сформулируем постусловие:

R: (i=y) AND (pr = pr*a[i-1]*a[i-2])


Доказательство:

1)Очевидно, что произведение первых 2 чисел Фибоначчи равно 1.

Q=>1*(1+0)=1;

2) Применим аксиому A1 к оператору pr:=1,тогда получим {1*(1+0)=1} pr:=1 {pr*(1+0)=pr}

3) Применим аксиому A1 к оператору a[0]:=0,тогда получим { pr*(1+0)=pr} a[0]:=0 { pr*(1+a[0])=pr}

4) Применим аксиому А1 к оператору a[1]:=1, тогда получим { pr*(1+a[0])=pr} a[1]:=1 { pr*(a[1]+a[0])=pr}

5) Применяя правило А3 к результатам пунктов 1 и 2,получим {Q} pr:=1 {pr*(1+0)=pr}

6) Применяя правило A4 к результ1атам пунктов 5 и 3-4, получим {Q} }pr:=1; a[0]:=0; a[1]:=1; { pr*(a[1]+a[0])=pr}

7)i:=2.Выполним равносильное преобразование pr=pr*(a[1]+a[0]) AND i<=y => pr=pr*(a[i-1]+a[i-2])

8) Применяя правило А1 к оператору a[i] :=a[i-1] + a[i-2],по получим { pr=pr*(a[i-1]+a[i-2])} a[i] :=a[i-1] + a[i-2] { pr=pr*a[i]}

9)Применяя правило A4,получим { pr*(a[1]+a[0])=pr} a[i] :=a[i-1] + a[i-2];pr:=pr*a[i]; i:=i+1; { pr=pr*a[i]}

10) Применяя правило A2 , получим { pr=pr*(a[i-1]+a[i-2]) AND i<=y} a[i] :=a[i-1] + a[i-2];pr:=pr*a[i]; i:=i+1; { pr=pr*a[i]}

11) Применяя правило A8 к результату пункта 10, получим { pr=pr*a[i]} while i<=y do begin a[i] :=a[i-1] + a[i-2];pr:=pr*a[i]; i:=i+1; end;{NOT (i<=y) AND (pr=pr*a[i])}

Утверждение pr=pr*a[i]) является инвариантом цикла, так как значение его остается истинным до цикла и после выполнения каждого шага цикла.

12) Применяя правило A4 , получаем то, что требовалось доказать,

{ Q } S { NOT (i  y) AND (pr=pr*a[i])) }

Осталось доказать, что выполнение программы заканчивается.

Доказывать будем от противного, т.е. предположим, что программа не заканчивается. Тогда должна существовать бесконечная последовательность значений a[i] удовлетворяющая условиям,что



  1. i  y,где y= const;

  2. y>0;

  3. pr,a[i]  Nat

Но значение i на каждом шаге цикла увеличивается на положительную величину: i:=i+1 (i<=y). Значит, последовательность значений y является конечной.


  1. В соответствии с вариантом задания необходимо:

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

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

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

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

5.1 Для случая работы банкомата в режиме выдачи наличных денежных средств , существуют события:

З – запрос нужной суммы

О – обработка запроса, отсчет нужной суммы

В – выдача денег

αВД={З,О,В}

ВД = (З -> О -> П->ВД}

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

а) Ожидание запроса

б) Запрос поступил

в) Деньги выданы

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



  1. Пользователь запросил необходимую сумму

  2. Отсчет денег

  3. Пользователь получил нужную ему сумму денег

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

События

Предусловия

Постусловия

1

Нет,а

б

2

б

в

3

в

а




3

в

2

б

1

а
Сеть Петри для процесса работы автоматической справки о поездах дальнего следования.


izumzum.ru