Дискретно-детерминированный подход характерен тем, что в качестве математического аппарата на этапе формализации процесса функционирования систем используется математического аппарата математический аппарат теории автоматов. Теория автоматов — это раздел теоретической кибернетики, в котором изучаются математические модели — автоматы. На основе этой теории система представляется в виде автомата, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени.
Автомат можно представить как некоторое устройство (черный ящик), на которое подаются входные сигналы и снимаются выходные и которое может иметь некоторые внутренние состояния. Конечным автоматом называется автомат, у которого множество внутренних состояний и входных сигналов (а следовательно, и множество выходных сигналов) являются конечными множествами.
Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: конечным множеством X входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием z0, z0 Î Z; функцией переходов j (z, х)\ функцией выходов y (z, х).
Автомат, задаваемый F-схемой: ,— функционирует в дискретные моменты времени, которые называются такты, равные друг другу, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния.
Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент t = 0, 1, 2, ... дискретного времени F-автомат находится в определенном состоянии z(t) из множества Z состояний автомата, причем в начальный момент времени t = 0 он всегда находится в начальном состоянии z(0)=zo. В момент t, будучи в состоянии z(t), автомат способен воспринять на входном канале сигнал x(t)ÎX и выдать на выходном канале сигнал у(t) = y [z(t), x(t)], переходя в состояние z(t +1) = j [z(t), х(t)], z(t)ÎZ, y(t)ÎY. Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного алфавита Y. Другими словами, если на вход конечного автомата, установленного в начальное состояние z0, подавать в некоторой последовательности буквы входного алфавита х(0), х(1), х(2), ..., т. е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у(0), у(1), у(2), ..., образуя выходное слово.
Таким образом, работа конечного автомата происходит по следующей схеме: в каждом i такте на вход автомата, находящегося в состоянии z(t), подается некоторый сигнал x(t), на который он реагирует переходом в (i + 1)-такте в новое состояние z(t + l) и выдачей некоторого выходного сигнала.
По числу состояний различают конечные автоматы с памятью и без памяти.
Автоматы с памятью имеют более одного состояния, а автоматы без памяти (комбинационные или логические схемы) обладают лишь одним состоянием. При этом, работа комбинационной схемы заключается в том, что она ставит в соответствие каждому входному сигналу x(t) определенный выходной сигнал y(t), т. е. реализует логическую функцию вида
Билет 26 Вопрос 2
ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ И ПРОЦЕДУРЫ ИХ МАШИННОЙ ГЕНЕРАЦИИ
При статистическом моделировании систем одним из основных вопросов является учет стохастических воздействий. Количество случайных чисел, используемых для получения статистически устойчивой оценки характеристики процесса функционирования системы S при реализации моделирующего алгоритма на ЭВМ. Количество случайных чисел колеблется в достаточно широких пределах в зависимости от:
1 класса объекта моделирования;
2.вида оцениваемых характеристик;
3необходимой точности и достоверности результатов моделирования. Результаты статистического моделирования существенно зависят от качества исходных (базовых) последовательностей случайных чисел.
На практике используются три основных способа генерации случайных чисел:
- аппаратный (физический);
- табличный (файловый);
- алгоритмический (программный).
Аппаратный способ. Генерация случайных чисел вырабатываются специальной электронной приставкой — генератором (датчиком) случайных чисел,— служащей в качестве одного из внешних устройств ЭВМ. Реализация этого способа генерации не требует дополнительных вычислительных операций ЭВМ по выработке случайных чисел, а необходима только операция обращения к внешнему устройству (датчику). В основе лежит физический эффект, лежащего в основе таких генераторов чисел, чаще всего используются шумы в электронных и полупроводниковых приборах, явления распада радиоактивных элементов и т. д.
Достоинства:
Запас чисел не ограничен;
Расходуется мало операций;
He занимается место в памяти .
Недостатки:
Требуется периодическая проверка;
Нельзя воспроизводить последовательности;
Используется специальное устройство;
Необходимы меры по обеспечению стабильности.
Табличный способ. Случайные числа, представленные в виде таблицы, помещаются в память ЭВМ. Этот способ получения случайных чисел обычно используют при сравнительно небольшом объеме таблицы и файла чисел.
Достоинства:
Требуется однократная проверка;
Можно воспроизводить последовательности.
Недостатки:
Запас чисел ограничен;
Много места в ОЗУ;
Необходимо время для обращения к памяти.
Алгоритмический способ. Способ получения последовательности случайных чисел основанный на формировании случайных чисел в ЭВМ с помощью специальных алгоритмов и реализующих их программ. Каждое случайное число вычисляется с помощью соответствующей программы по мере возникновения потребностей при моделировании системы на ЭВМ.
Достоинства:
Требуется однократная проверка;
Многократная воспроизводимость последовательности чисел;
Мало места в памяти и нет внешних устройств.
Недостатки:
Запас чисел ограничен периодом последовательности;
Затраты машинного времени.
Программная имитация случайных воздействий сводится к генерированию некоторых стандартных процессов и их последующего функционального преобразования. В качестве базового может быть принят любой удобный для моделирования конкретной системы S процесс (например, пуассоновский поток при моделировании Q-схемы). При дискретном моделирований базовым процессом является последовательность чисел , которые представляют реализации независимых, равномерно распределенных на интервале (0, 1) случайных величин . В статистических терминах - повторная выборка из равномерно распределенной на интервале (0, 1) генеральной совокупности значений величины x.
Непрерывная случайная величина x имеет равномерное распределение в интервале (а, Ь), если ее функции плотности (а) и функция распределения (б) примет вид (Рис. 1):
Рис.1
Числовые характеристики случайной величины x, принимающей значения х— это математическое ожидание, дисперсия и среднее квадратическое отклонение соответственно:
При моделировании систем на с случайными числами интервала (0, 1), где границы интервала соответственно а=0 и б = 1. Частным случаем равномерного распределения является функция плотности и функция распределения, соответственно имеющие вид:
Такое распределение имеет математическое ожидание М [x] = 1/2
и дисперсию D[x] = 1/12.
Это распределение требуется получить на ЭВМ. Но получить его на цифровой ЭВМ невозможно, так как машина оперирует с п-разрядными числами. Поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0, 1) используют дискретную последовательность 2" случайных чисел того же интервала. Закон распределения такой дискретной последовательности называют квазиравномерным распределением.
Случайная величина x, имеющая квазиравномерное распределение в интервале (0, 1), принимает значения с вероятностями , .
Математическое ожидание и дисперсия квазиравномерной случайной величины соответственно имеют вид
