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

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

Тема: Формы, свойства и виды стандартных схем программ

1. Найдите аналитический вид функции, кодирующей слова в алфавите V = {а, b, c} числами, если функция упорядочения К:V-> {1, 2, 3} такова, что К(а) = 1, К(b) = 2, К(с) = 3.
2. Постройте машину Тьюринга, которая стирает с ленты любое начальное слово и записывает вместо него слово aabba в алфавите {а, b}.
3.На рис. 1.4. (лекции 2) даны примеры стандартных схем. Установить, какие из них тотальны, какие пусты, какие пары схем функционально эквивалентны. Укажите свободные схемы.
4. Докажите, что схемы на рисунке 1.11 (лекция 5) эквивалентны.
5. Изобразите схемы операторов: засылки произвольного числа n в счетчик с := n, умножения на число с := с х n и деления на число с := с/n с помощью трех базовых операторов. Используйте не более одного дополнительного счетчика.
6. Покажите, что предикат (с тod n = 0), где n - некоторое число, а (с mod n) - остаток от деления счетчика на n, можно представить через три базовых оператора и один дополнительный счетчик.

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

Тема: Семантическая теория программ

1. Функции: F(n), G(n) определены с помощью операционной семантики равенствами:
F(0)=I, G(0)=2, F(n)=G(n-I), G(n)=F(n-l) + G(n-I).
Найти значения F(3) и G(3).
2. Формальные языки Е и Т определены над алфавитом {а, *, &, <, >} с помощью денотационной семантики равенствами
Е = Т U * Т U Е & Т и Т= а U а* U <Е>.
Какие из следующих строк *а&*а*&а*; *а&<а&а*>; *<*а*&а>&<*а*>* принадлежат языку Е и какие не принадлежат.
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) = { }, l(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. Для структуры сети Петри: С =(Р, Т, I, О),
Р = {p1, p2, p3, p4, p5)},
Т = {t1, t2, t3, t4},
I(p1) = { }, I(p2) = {t1, t4}, l(p3) = {t1, t4}, I(p4) = {t3}, l(p5) = {t1, t2}, O(p1) = {t1}, O(p2) = {t2), O(p3) = {t2, t3}, O(p4) = {t4}, О(p5) = {t2},
I(t1) = {p1}, l(t2) = {p2, p3, p5)}, I(t3) = {p3}, I(p4) = {p4},
O(t1) = {p2, p3, p5)}, O(t2) = {р5}, O(t3) = {p4}, O(t4) = {p2, p3} изобразите граф сети Петри и укажите на графе
маркировку m = <1, 0,1,1, 0, 0>.
3. Промоделируйте вычислительную систему с тремя процессами и четырьмя ресурсами:
стример (устройство ввода с магнитной ленты),
печатающее устройство,
диск
два раздела памяти.
Любой процесс может попасть в любой раздел. Использование ресурсов тремя процессами состоит в следующем:
а) процесс 1 запрашивает стример и печатающее устройство, а затем освобождает оба эти ресурса;
б) процесс 2 запрашивает стример и диск, а затем освобождает стример, запрашивает печатающее устройство и, в конце концов, освобождает и печатающее устройство, и диск;
в) процесс 3 требует все три ресурса одновременно, и затем их освобождает.
4. Постройте деревья достижимости для маркированной сети Петри представленной заданием 3.

Работы сдавались в 2013 году.
Все работы зачтены без замечаний.