В общем виде вероятностный ( стохастический ) автомат ( англ. probabilistic automat) можно определить как дискретный потактный преобразователь информации. - презентация

1

2 В общем виде вероятностный ( стохастический ) автомат ( англ. probabilistic automat) можно определить как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано статистически.

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

4 Р - автоматы могут использоваться как генераторы марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем S или воздействий внешней среды Е. Для оценки различных характеристик исследуемых систем, представляемых в виде Р - схем, кроме случая аналитических моделей можно применять и имитационные модели, реализуемые, например, методом статистического моделирования.

5 При непрерывно - стохастическом подходе в качестве типовых математических схем применяется система массового обслуживания, которые будем называть Q- схемами. Системы массового обслуживания представляют собой класс математических схем, разработанных в теории массового обслуживания и различных приложениях для формализации процессов функционирования систем, которые по своей сути являются процессами обслуживания.

6 В качестве процесса обслуживания могут быть представлены различные по своей физической природе процессы функционирования экономических, производственных, технических и других систем, например потоки поставок продукции некоторому предприятию, потоки деталей и комплектующих изделий на сборочном конвейере цеха, заявки на обработку информации ЭВМ от удаленных терминалов и т. д.

7 При этом характерным для работы таких объектов является случайное появление заявок ( требований ) на обслуживание и завершение обслуживания в случайные моменты времени, т. е. стохастический характер процесса их функционирования. Остановимся на основных понятиях массового обслуживания, необходимых для использования Q- схем.

8 В любом элементарном акте обслуживания можно выделить две основные составляющие : ожидание обслуживания заявки ; собственно обслуживание заявки. Это можно изобразить в виде некоторого i - г o прибора обслуживания П i, состоящего из накопителя заявок Н i, в котором может одновременно находиться заявок, где емкость i - го накопителя, и канала обслуживания заявок ( или просто канала ) K i

9 На каждый элемент прибора обслуживания П i, поступают потоки событий : в накопитель H i поток заявок w i на канал K i поток обслуживании u i. Потоком событий называется последовательность событий, происходящих одно за другим в какие - то случайные моменты времени. Различают потоки однородных и неоднородных событий.

10 Поток событий называется однородным, если он характеризуется только моментами поступления этих событий ( вызывающими моментами ) и задается последовательностью, где t n момент наступления n - го события неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности промежутков времени между n - м и (n1) - м событиями { n }, которая однозначно связана с последовательностью вызывающих моментов { t n }, где,, t o = 0, т. е. 1 = t 1

11 Потоком неоднородных событий называется последовательность, где t n вызывающие моменты ; f n набор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок могут быть заданы принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т. п.

12 В практике моделирования систем, имеющих более сложные структурные связи и алгоритмы поведения, для формализации используются не отдельные приборы обслуживания, а Q- схемы, образуемые композицией многих элементарных приборов обслуживания П i ( ( сети массового обслуживания ). Если каналы К i различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание ( многоканальная Q- схема ), а если приборы П i и их параллельные композиции соединены последовательно, то имеет место многофазное обслуживание ( многофазная Q- схема ). Таким образом, для задания Q- схемы необходимо использовать оператор сопряжения R, отражающий взаимосвязь элементов структуры ( каналов и накопителей ) между собой. Различают разомкнутые и замкнутые Q- схемы.

13 В разомкнутой Q- схеме выходной поток обслуженных заявок не может снова поступить на какой - либо элемент, т. е. обратная связь отсутствует. В замкнутых Q- схемах имеются обратные связи, по которым заявки двигаются в направлении, обратном движению вход - выход. Для задания Q- схемы также необходимо описать алгоритмы ее функционирования, которые определяют набор правил поведения заявок в системе в различных неоднозначных ситуациях.

14 В зависимости от динамики приоритетов в Q- схемах различают статические и динамические приоритеты. Статические приоритеты назначаются заранее и не зависят от состояний Q- схемы, т. е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают при моделировании в зависимости от возникающих ситуаций.

15 Исходя из правил выбора заявок из накопителя H i на обслуживание каналом К i можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Н i ожидает окончания обслуживания предшествующей заявки каналом К i и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Н i прерывает обслуживание каналом К i заявки с более низким приоритетом и сама занимает канал ( при этом вытесненная из К i заявка может либо покинуть систему, либо может быть снова записана на какое - то место в Н i ).

16 При рассмотрении алгоритмов функционирования приборов обслуживания П i ( каналов К i и накопителей Н i ) необходимо также задать набор правил, по которым заявки покидают Н i и К i, для Н i либо правила переполнения, по которым заявки в зависимости от заполнения Н i, покидают систему, либо правила ухода, связанные с истечением времени ожидания заявки в Н i, для К i правила выбора маршрутов или направлений ухода.

17 Кроме того, для заявок необходимо задать правила, по которым они остаются в канале К i или не допускаются до обслуживания каналом К i т. е. правила блокировок канала. При этом различают блокировки К i по выходу и по входу. Весь набор возможных алгоритмов поведения заявок в Q- схеме можно представить в виде некоторого оператора алгоритмов поведения заявок А.