Задачи для экзамена по ИИ и ПП

A)  Написать асинхронную программу для примера :

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

Решение

Integer x, y, z .

Input(x,y,z)

Arynehronous_do

%   tr(ak)          ak  %

x<y     ->   x:=x+1;

y<z     ->   y:=y+1;

z<x     ->   z:=z+1.

End_do

Tr(ak) – спусковая функция.

Б)  Написать  асинхронную программу, реализующую конвейер (используя спусковые функции и управляющ. операторы)  Показать  конструир. управления.

Решение

Integer x,y,z .

Arynehronous_do

x:=1;  y:=z:=0;

%  tr(ak)      ak         c(ak)  %                           

x=1    ->  f1         [ y:=1; x:=0 ]

y=1    ->  f2         [ z:=1; y:=0 ]

p&z=1-> f3         [ x:=1; z:=0 ]

end_do

c(ak) – управляющ. оператор

tr(ak) – спусковая функция

Асинхронная программа реализует этот конвейер и имеет вид : x:=1; y:=z:=0 – присваивание значений разрешают управляющим переменным инициировать операцию f1, а запрещают – f2 и f3. потому в начальный момент может инициирован быть блок А-f1.

После выполнения  f1 оператор с.в.[ y:=1; x:=0 ] запретит исполнение f1 и разрешит f2 и т.д. Цикл конвейера завершиться когда предикат Р станет ложным и не позволит инициировать f3

В) Сконструировать сеть Петри  для управления конвейером из 3хфункциональных устройств L₀,L₁,L₂ , с огранич. Емкостью мест: P₁ < -2и P₂ < -3

Решение

t₀ t₁ t₂ –обрабат. устройства.

Р1, Р2 – ограничивающие емкости места.

Р1 - 2-ое ограничение , а Р2 – 3 –го .

n – наличие фишек в Р0

В Р1 не может быть более 2-х фишек, а в Р2 – более 3-х .

Две фишки в Р4 говорят о срабатывании перехода t₀ два раза .

Р1 и Р2 – асинхронные каналы.

Г) Сконструировать сеть Петри для управления двумя протекающими процессами: «производитель-потребитель». Производитель производит детали и отправляет на склад. Потребитель берет детали со склада. Склад ограничен: PБ<=10.

Д) Сконструировать сеть Петри из фрагментов:

По формуле ((((a, b), (a, c)) || d), e).

(a,b) =

(a,c) =

 

(a,b),(a,c) =

 

((((a, b), (a, c)) || d) =

 

((((a, b), (a, c)) || d), e) =

E) Сконструировать сеть Петри для управления тремя обедающими философами. Такую, чтобы каждый философ был бы в состоянии гарантировать пообедать за конечное время.

Ж) Программа разделения 2-х множеств (2 Дейкстра). Даны 2 множества натуральных чисел S и T. Сохраняя мощность  необходимо собрать в S наименьшие эл-ты множества S u T, а в Т – наибольшие эл-ты. 

Small:

Mx := max(S);  a ! mx;  S := S – {mx};                                       small

b ? x;  S := S u {x};  mx := max(S);

[ mx > x   ®    a ! mx;  S := S – {mx};  b ? x;

S := S u {x};  mx := max(S) ] stop

Large:                                                                                                large

A ? y;  T :=T u {y};  mn := min(T);

B ! min; T := T – {mn}; mn := min(T);

[ mn < y  ®   a ? y;  T := T u {y};

mn := min(T);   b ! mn;  T := T – {mn}; ] stop

Написать неравенства, при кот. эта программа работает некорректно.

Проверить программу на  наборах множеств:

S = {5, 10, 15, 20},  T = {17, 18, 30, 40}

На  этих множествах программа работает правильно.

Сортирует множества и завершается после однократного прохождения

циклов в обоих процессах. 

S = {5, 10, 15, 20},  T = {14, 17, 18, 30, 40}

В этом случае программа работает некорректно, т.к. при i =1 первое

вхождение процесса Large в цикл приводит к дедлоку, потому что Small

завершится, не войдя в цикл.

З) Читатели – писатели. Писатели только модифицируют разделенный объект. Читатели – только считывают значение. Написать фрагмент программы работы этих процессов с помощью семафоров.

Begin

Semaphore mem_work := 1;

Reader_work :=1’

Int nOfReaders := 0;

         Parbegin

Reader:

begin

A1: P(reader_work);

If (nOfReaders = 0 Then

P(mem_work);   

nOfReaders := nOfReaders + 1;

V(reader_work);

Reading;

P(reader_work);

If (nOfReaders = 0) Then

V(mem_work);

V(reader_work);

Data processing

Goto A1;

End

Writer:

Begin

A2: data processing

P(mem_work);

Data writting

V(mem_work);

Goto A2

End

Parend

End

И) Производитель производит продукцию и отсылает в ограниченный буфер. Потребитель берет из этого буфера продукцию. Оба процесса циклические и конфликтуют при доступе к общему буферу. Написать фрагменты программ работы этих процессов с помощью семафоров.

Begin

Semaphore free := 1;

Parbegin

P_iL_i: begin

P(free)

(do something  critical);

V(free);

(do some);

goto L_i;

end

parend

end.

К) Имеется несколько циклических процессов. Каж. процесс на каж. своем цикле имеет доступ к некоторому общему для всех процессов ресурсу и конфликтует с другими процессами при доступе к нему. Написать фрагмент программы для i-го процесса этой задачи. 

Begin

Semaphore  nEmpty := n

nProduced := 0;

buff_work = 1;

Parbegin

Procedure

Begin

A1: p(nEmpty);

p(buff_work);

add a portion;

goto A1

end

consumer:

begin

A2: p(produced);

p(buff_work);

comsums a portion

V(nEmpty);

V(buff_work);

Goto A2;

End

Parend

End