Теория вычислительных процессов. Лабораторные работы № 1-4. Вариант №1

Лабораторная работа № 1
Формы, свойства и виды стандартных схем программ
Цель работы: Научиться составлять и исследовать схему программы

Лабораторная работа № 2
Задание 1. Функции: F(n), G(n) определены с помощью операционной семантики равенствами:
F(0)=1, G(0)=2, F(n)=G(n-1), G(n)=F(n-1) + G(n-1)
Найти значения F(3) и G(3).

Задание 2. Формальные языки Е и Т определены над алфавитом {а, *, &, <, >} с помощью денотационной семантики равенствами

Какие из следующих строк:
a) *а&*а*&а*;
b) *а&<а&а*>;
c) *<*а*&а>&<*а*>*
принадлежат языку Е и какие не принадлежат.

Задание 3. Написать программу, используя аксиоматическую стратегию построения и проверки цикла. Дан массив B[0:n-1], n > 0. Присвоить переменной х наименьшее значение из B. Если наименьшее значение встречается в B более одного раза, выбрать любой из них.
Предусловие Q: n >0;
Постусловие R: x<= B[О: n-1] AND (j: 0<=j < n х = B[j]);
Инвариант Р: 0<=j<=n АND х<=B[0:n-l] AND (j :i<=j<n х=B[j]);
Ограничение t: i.
Задание 4. Написать программу, используя различные методы построение инвариантов циклов. Дан массив B[0:n-1], n > 0. Определить, состоит ли B[0: n-l] из одних нулей

Лабораторная работа № 3
Задание 1:
Изложите суть проблем, возникающих в модели системы, описанной притчей о пяти обедающих философах.
Задание 2:
Объясните, каким образом совокупность обычных операторов последовательного программирования может быть взята за основу структуры последовательных взаимодействующих процессов.
Задание 3:
Опишите структуру и способ построения системы, в которой ограниченное число физических ресурсов, таких, как диски и печатающие устройства, разделено между большим количеством процессов с переменной потребностью в этих ресурсах.

Лабораторная работа № 4
Задание 1: Постройте граф сети Петри для следующей структуры сети Петри:
Р = {p1, p2, p3, p4},
Т = {t1, t2, t3, t4},
I(t1) = { },
I(t2) = {p1},
I(t3) = {p2, p4},
I(t4) = { },
I(t5) = {p3},
O(t1) = {p1},
O(t2) = {p2},
О(t3) = {p1, p3},
O(t4) = {p3},
O(t5) = {p4}.
Задание 2: Изобразите граф сети Петри следующей структуры:
Р = {p1 p2},
Т = {t1 t2 t3},
I(t1) = {p1},
I(t2) = {p1},
I(t3) = {p2},
О(t1) = {p1, p2},
O(t2) = {p2},
O(t3) = { }.
Задание 3: Для структуры сети Петри:
С =(Р, Т, I, О),
Р = {p1, p2, p3, p4, p5)},
Т = {t1, t2, t3, t4},

I(p1) = { },
I(p2) = {t1, t4},
I(p3) = {t1, t4},
I(p4) = {t3},
I(p5) = {t1, t2},
O(p1) = {t1},
O(p2) = {t2),
O(p3) = {t2, t3},
O(p4) = {t4},
О(p5) = {t2},

I(t1) = {p1},
I(t2) = {p2, p3, p5)},
I(t3) = {p3},
I(t4) = {p4},
O(t1) = {p2, p3, p5)},
O(t2) = {р5},
O(t3) = {p4},
O(t4) = {p2, p3}
изобразите граф сети Петри и укажите на графе маркировку
m = <1,0,1,1,0>.
Задание 4: Промоделируйте вычислительную систему с тремя процессами и четырьмя ресурсами:
- стример (устройство ввода с магнитной ленты),
- печатающее устройство,
- диск,
- два раздела памяти.
Любой процесс может попасть в любой раздел. Использование ресурсов тремя процессами состоит в следующем:
а) процесс 1 запрашивает стример и печатающее устройство, а затем освобождает оба эти ресурса;
б) процесс 2 запрашивает стример и диск, а затем освобождает стример, запрашивает печатающее устройство и, в конце концов, освобождает и печатающее устройство, и диск;
в) процесс 3 требует все три ресурса одновременно, и затем их освобождает;

СибГУТИ 2012г., 1 вариант. Зачет.