Cтраница 2
Книга посвящена изложению основ теории вероятностных автоматов - важного раздела дискретной математики, имеющего широкие приложения. В ее основу положен курс лекций, читаемый в Казанском государственном университете им. Она представляет собой достаточно полное руководство, написанное на едином языке и отражающее современное состояние теории на уровне важнейших результатов. [16]
Указанный отрицательный результат означает, что определение вероятностного автомата не подчиняется общей категорной схеме и можно лишь действовать по аналогия. [17]
При имитационном моделировании применяется много математических схем: конечные и вероятностные автоматы, системы массового обслуживания ( СМО), агрегативные системы, системы, описываемые дифференциальными уравнениями и марковскими процессами, методы общей теории систем, а также специально сконструированные эвристические подходы для конкретных типов объектов моделирования. Применительно к экономическим объектам и процессам наиболее часто используются, на наш взгляд, математические схемы СМО, агрегативные системы, а также эвристические подходы. Кроме этого, отдельные элементы метода статистических испытаний или метода Монте-Карло, которые лежат в основе имитационного моделирования, применяются достаточно часто при расчете различных параметров для других типов моделей - эконометрических, моделей кривых роста и т.п. В данной главе будут рассмотрены имитационные модели СМО и агрегативные имитационные модели. Естественно, приведенные ниже математические схемы ни в коей мере не исчерпывают их перечень. Кроме того, часто при имитационном моделировании применяется сочетание различных математических подходов, поэтому дать весь перечень применяемых математических схем затруднительно, да и вряд ли целесообразно. Главное - наличие имитационного мышления при выборе тех или иных математических подходов. [18]
Легко видеть, что операции умножения и суммирования вероятностных автоматов можно обобщить на случай п автоматов. [19]
Четкие различия, которые я всегда проводил между детерминированными и вероятностными автоматами, в прошлом не раз подвергались публичной критике, основанной на том, что преобразование детерминированного автомата в эквифинальную кибернетическую машину представляет собой простую и непротиворечивую задачу. Первая часть настоящей главы была написана прежде всего с целью дать ответ на эту критику. Я согласен с тем, что можно смоделировать строго автономную вероятностную систему на детерминированной вычислительной машине, решить на ней операционные задачи, связанные с методом Монте-Карло, и даже эффективно имитировать кибернетический механизм. Но, по моему мнению, утверждать, что такая вычислительная машина может быть преобразована в кибернетическую при помощи искусного программирования по применяемым до сих пор методам, - значит извращать природу кибернетической системы. Не только эта глава, но и вся книга опровергают такую точку зрения. [20]
Рабин ввел вероятность в теорию вычислений, начиная со статьи о вероятностных автоматах. [21]
Легко видеть, что детерминированный конечный автомат можно рассматривать как частный случай вероятностного автомата, у которого для каждого х Х при любом данном ie / точно одна из вероятностей pih ( x) равна единице, а все остальные вероятности равны нулю. [22]
В заключение главы отметим, что с содержательной точки зрения операции над вероятностными автоматами означают то же, что и в случае детерминированных автоматов, а свойства, которыми они обладают, повторяют свойства операций над детерминированными автоматами. [23]
Используя такой способ задания вероятностных автоматов, можно ввести теоретико-множественные операции объединения и пересечения вероятностных автоматов по аналогии с операциями над детерминированными автоматами, накладывая, правда, некоторые ограничения на множество стохастических матриц, которые делают довольно узким класс вероятностных автоматов, к которым применимы данные операции. При этом выводы, полученные для теоретико-множественных операций над детерминированными автоматами, справедливы для операций над вероятностными автоматами, разумеется, при сохранении накладываемых органичений на стохастические матрицы. Поэтому, не останавливаясь на этих операциях, перейдем сразу к алгебраическим операциям умножения, суммирования и суперпозиции, которые применимы к произвольным вероятностным автоматам. [24]
Естественно предположить, что дискретная последовательность, подающаяся на управление перемешивающего автомата, вырабатывается конечным вероятностным автоматом ( детерминированным конечным автоматом, на вход которого поступает последовательность независимых одинаково распределенных случайных величин, реализуемая некоторым датчиком случайных чисел [12]) и является, в частности, случайной последовательностью с независимыми значениями, цепью Маркова или функцией цепи Маркова. В более общем случае при исследовании установившегося режима работы можно считать, что эта последовательность является стационарной дискретной случайной последовательностью. [25]
Проведенные в последнее время исследования [1,2] подтверждают гипотезу о том, что человек относится к группе вероятностных автоматов. Исключительную роль в описании статистической динамики вероятностных автоматов играет теория случайных функций и, в частности, тот ее раздел, который занимается исследованием нестационарных случайных процессов. [26]
Большая часть понятий и задач, характерных для конечных автоматов, может быть, перенесена в различных вариантах и на вероятностные автоматы. При этом часто сохраняются свойства, присущие конечным автоматам. Например, можно так ввести по - нятие неотличимости состояний вероятностного автомата, что сохранятся некоторые теоремы об отличимости состояний простыми экспериментами. Вместе с тем в отличие от конечных автоматов, для которых минимальная форма автомата определена с точностью до изоморфизма однозначно, для данного вероятностного автомата может существовать континуум эквивалентных минимальных форм. Следующей модификацией понятия абстрактного конечного автомата является так называемый недетерминированный автомат, представляющий собой объект ( A, Q, В, х), где A, Q, В - алфавиты, имеющие прежний смысл, а х - QxAxQxB - отношение переходов-выходов. QxA в QXB, недетерминированный автомат называется детерминированным и фактически совпадает с абстрактным конечным автоматом, поскольку в этом случае функцию х можно рассматривать как пару функций ф -, if, отображающих QX в Q и В соответственно. [27]
С точки зрения кибернетических принципов анализа условий функциональной надежности структурных элементов системы человек - автомат последние могут быть разбиты на группы детерминированных и вероятностных автоматов. [28]
ТАБЛИЦА ПЕРЕХОДОВ ( transition table, flow table; tableau destransferls; Obergangstabelle) - таблица, задающая зависимость состояния релейного устройства ( конечного автомата или вероятностного автомата) в настоящий момент от состояния устройства в нредыдущи и момент и входа в настоящий момент. [29]
В том случае, когда вероятностные автоматы рассматриваются с точки зрения представления событий подобно тому, как это имеет место в случае детерминированных автоматов, при задании вероятностного автомата А указывается множество Q Q отмеченных состояний. [30]