60.Элементы теории асинхронных процессов: концепция процесса, основные определения, глобальные свойства - параллельность, синхронность, недетерминизм; физическое и событийное время, понятие алгебры над процессами; модели вычислительных процессов - автоматная модель, способы задания и построения.

Алфавит - конечное множество имен событий, выбранных для описания объекта. Алфавит считается заранее определенным свойством объекта и постоянным. При выборе алфавита абстрагируются от:

1)Не рассматривается множество несуществующих событий; 2)Событие происходи мгновенно (элементарное действие); 3)Отсутствует точная привязка событий ко времени.

Процесс – поведение объекта, описанное в терминах определенного набора событий, выбранного в качестве его алфавита. Малые прописные – имена событий; Заглавные – имена процессов; алфавит некоторого процесса – α.

Способы описания:

1) Префиксы (предваренные описания объектов): х—>P (P за x) – описывает объект, который в начале участвует в событии x, a затем ведет себя в точности как P. α (х—>Р)= αР, при условии х €αР – описание процесса с использованием префикса. Используется для описания процесса который рано или поздно останавливается.

2)Рекурсия: Префиксную запись можно использовать для полного описания поведения процесса, который рано или поздно останавливается. Рекурсия позволяет описать поведение процесса компактно и не требую знать заранее срок жизни объекта. Часы=(тик—>Часы). Будет правильно работать, если в правой части уравнения рекурсивному вхождению процесса предшествует хотя бы одно событие;

3)Выбор: x—>P|y—>Q – описывает объект, который в начале участвует в одном из событий x или y. Дальнейшее поведение объекта описывается процессом P, если первым произошло событие x, и Q – если первым произошло событие y.

Св-ва процессов: 1) Параллелизм. αP=αQ – если алфавит Р совпадает с алфавитом Q, то P||Q – процесс ведущий себя как система составленная из процессов Р и Q, взаимодействие между которыми пошагово синхронизировано. Законы: 1)Симметричность P||Q = Q||P (симметрия процессов); 2)Ассоциативность P||(Q||R) = (P||Q)||R (при совместной работе 3 процессов неважно, в каком порядке они объединены); 3)Процесс, находящийся в тупиковой ситуации, приводит к дедлоку всей системы P||СТОП _P = СТОП _p; 4)Пара процессов либо одновременно выполняют одно и тоже действие, либо попадает в состояние дедлока, если начальные состояния процессов не совпадают: (c—>P||c—>Q)—>(c—>(P||Q)) и (c—>P||d—>Q)—>СТОП (c d)

2)Синхронность. αP≠αQ – Когда такие процессы объединяются для совместного исполнения, события, содержащиеся в обоих алфавитах, требуют одновременного участия Р и Q. События же из алфавита Р, не содержащиеся в алфавите Q, не имеют никакого отношения к Q, который физически неспособен ни контролировать, ни замечать такие события. Такие события процесса P могут происходить независимо от Q. Аналогично Q может самостоятельно участвовать в событиях, содержащихся в его алфавите, но отсутствующих в алфавите Р. Таким образом, множество всех событий, логически возможных для данной системы, есть просто объединение алфавитов составляющих ее процессов: Α(P||Q)=αP U αQ

3)Недетерминизм. Когда процесс обладает некоторым спектром поведения, а его окружение не имеет возможности влиять на выбор, то выбор осуществляется произвольным (недетерминированным) образом. Одна из главных причин введения недетерминизма – абсрагироваться от некоторых деталей реализации. – недетерминированные процессы P и Q. Законы: 1)Идемпотентность 2)Симметричность = ; 3)Ассоциативность = ; 4)Дистрибутивность x—> =(x—>P) (x—>Q)

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

Свойства протоколов и операции над ними:

1)Конкатенация – строит новый протокол из пары операндов, соединяя их в указанном порядке. <n1>^<n2>=<n1,n2>

2)Сужение –протокол t суженный на множество символов A. Он строится из t отбрасыванием всех символов, не принадлежащих A (операция строго дистрибутивна).

3)S₀ – голова; S^| – хвост; <x,y,x>₀ = x; < x,y,x >^| = <y,x>

4)Итерация А* – набор всех конечных протоколов, включая <>, составленных из элементов множества А.

5)Длина протокола #S (примеры: #<>=0, #<x,y,x>=3)

6)Число вхождений символа x в протокол S S x

Автомат – математическая модель процесса. – конечное множество входных символов (входной алфавит); – выходной алфавит; – состояния автомата. При рассмотрении автомата рассматривается отображение множества входных сигналов на множество выходных. Если Q конечно, то автомат называется конечным (с конечной памятью). Автомат с 1м состоянием – тривиальный. – функция перехода; – функция выхода. Автоматы: - синхронные и асинхронные - конечные и бесконечные - детерминированные и недетерминированные

По способу формирования функций выходов выделяют автоматы Мили и Мура.

Автомат Мили: – определение входного сигнала с привязкой по времени. Поведение автомата в любой момент времени зависит от q и v. Можно устранить время и выразить выходную формулу так: Общая запись авт. Мили: , где V, W ,Q – алфавит входных и выходных символов состояний; – функции переходов и выходов; q₀ – начальное состояние. Можно вычислить реакцию автомата в виде последовательности выходных символов.

Автомат Мура: Частный случай авт. Миле, но выходной символ зависит только от q (внутр. состояния). Для каждого авт Миле можно построить экв-ый ему автомат Мура

– Функция выхода – Функция переходов

По учебнику Хоар Ч. Взаимодействующие последовательные процессы. Если что-то не понятно, там можно посмотреть.

61.Основы специальной теории сетей: синтаксис и семантика сетей Петри, модельная и предметная интерпретация, определение, способы задания сетей Петри, понятие выполнения сети, основные соглашения выполнения сети, пространство состояний, множество и граф достижимости, динамические свойства сетей, анализ сетей; сетевая объектная модель процессов, ее особенности и отличие от автоматной модели.

Синтаксис и семантика сетей Петри, модельная и предметная интерпретация, определение, способы задания сетей Петри: Сети Петри – инструмент исследования систем. В настоящее время сети Петри применяются в основном в моделировании. Во многих областях исследований явление изучается не непосредственно, а косвенно, через модель. Модель – это представление, как правило, в математических терминах того, что считается наиболее характерным в изучаемом объекте или системе. Манипулируя моделью системы, можно получить новые знания о ней, избегая опасности, дороговизну или неудобства анализа самой реальной системы. Обычно модели имеют математическую основу.

Развитие теории сетей Петри проводилось по двум направлениям. Формальная теория сетей Петри занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри. Прикладная теория сетей Петри связана главным образом с применением сетей Петри к моделированию систем, их анализу и получающимся в результате этого глубоким проникновением в моделируемые системы.

Определение: Сеть Петри N является четверкой N=(P,Т,I,O), где P = {p₁, p₂,..., p_n} — конечное множество позиций, n  0; T = {t₁, t₂,..., t_m} — конечное множество переходов, m  0; I: T  P* — входная функция, сопоставляющая переходу мультимножество его входных позиций; О: T  P* - выходная функция, сопоставляющая переходу мультимножество его выходных позиций.

Позиция pP называется входом для перехода tT, если pI(t). Позиция pP называется выходом для перехода tT, если pO(t). Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.