2. Моделювання випадкових та квазівипадкових послідовностей: квазівипадкові бінарні послідовності.

Под моделированием случайной величины Х принято понимать процесс получения на ЭВМ её выборочных значений x₁, ..., x_n. На практике используются три основных способа генерации случайных чисел: - табличный (файловы) – ввод таблиц равномерно распределённых случайных чисел во внешнюю или оперативную память ЭВМ; - аппаратный (физический) – использование специального приспособления к ЭВМ – "датчика" случайных чисел, формирующего случайные величины путём физического моделирования некоторых случайных процессов (излучения радиоактивных источников, шумов электронных ламп и др.); - алгоритмический (программный) – использование псевдослучайных (квазислучайных) последовательностей, реализуемых программным генератором случайных чисел. Псевдослучайнымичислами называются числа, вырабатываемые ЭВМ рекуррентным способом по специальным алгоритмам, когда каждое последующее число x_i получается из предыдущих в результате применения некоторых арифметических и логических операций. Такая последовательность чисел удовлетворяет известным критериям случайности, хотя входящие в эту последовательность числа зависимы между собой. Одним из недостатков этого метода является периодичность образованных программным способом псевдослучайных чисел, но для ряда задач, не требующих большого количества случайных чисел, длина периода является достаточной.  ^ Первый способ. При решении задачи без применения ЭВМ чаще всего используют таблицы случайных чисел. Таблицы получают с помощью специальных приборов (типа рулетки) и заносят в память ЭВМ, используются по мере необходимости.  В таблицах случайных чисел случайные цифры имитируют значения дискретной случайной величины с равномерным распределением:

xi	0	1	2	3	…	9
pi	0,1	0,1	0,1	0,1	…	0,1

При составлении таких таблиц выполняется требование, чтобы каждая из этих цифр от 0; 1; ...; 9 встречалась примерно одинаково часто и независимо от других с вероятностью p_i = 0,1. Самая большая из опубликованных таблиц случайных чисел содержит 1 000 000 цифр. Таблицы случайных чисел составить не так просто. Они требуют тщательной проверки с помощью специальных статистических тестов. Основной недостаток − необходимость в памяти достаточно большой емкости, затрудняющий решение "больших" задач, тем более что преимущество "случайных" таблиц перед "псевдослучайными" числами, получаемыми алгоритмически, никем не было доказано. Во втором способе используются аппаратные датчики, основанные на некоторых физических процессах, случайных по своей природе (шумы в электронных и полупроводниковых приборах, процессы при радиоактивном распаде и т.п.). Или же при решении задач на ЭВМ для выработки случайных чисел, равномерно распределенных в интервале (0;1), могут применяться генераторы случайных чисел. Данные генераторы преобразуют результаты случайного физического процесса в двоичные числа. В качестве случайного физического процесса обычно используют собственные шумы (случайным образом меняющееся напряжение). Основные недостатки − невозможность повторного получения одной и той же последовательности случайных величин для проверочных расчетов и невозможность гарантировать постоянную надежную работу датчика. ^ Третий способ. Получение псевдослучайных чисел с равномерным законом распределения заключается в выработке псевдослучайных чисел. Псевдослучайные числа – это числа, полученные по какой-либо формуле и имитирующие значения случайной величины. Под словом "имитирующие" подразумевается, что эти числа удовлетворяют ряду тестов так, как если бы они были значениями этой случайной величины. Первый алгоритм для получения псевдослучайных чисел предложил Дж. Нейман. Это так называемый метод середины квадратов, который заключается в следующем:  _{и т.д.} Метод средин квадратов фон Неймана является сравнительно бедным источником случайных чисел, т.к. последовательность стремится войти в привычную колею, т.е. короткий цикл повторяющихся элементов. Назовем достоинства метода псевдослучайных чисел. 1. На получение каждого случайного числа затрачивается несколько простых операций, так что скорость генерирования случайных чисел имеет тот же порядок, что и скорость работы ЭВМ. 2. Малый объем памяти ЭВМ для программирования. 3. Любое из чисел легко воспроизвести. 4. Качество генерируемых случайных чисел достаточно проверить один раз. Случайные величины бывают дискретные и непрерывные, одномерные (зависящие от одной переменной) или многомерные (зависящие от двух и более переменных).  ^ Дискретной случайной величиной называется такая величина, число возможных значений которой либо конечное, либо бесконечное счетное множество (множество, элементы которого могут быть занумерованы).  ^ Непрерывной случайной величиной называется такая величина, возможные значения которой непрерывно заполняют некоторый интервал (конечный или бесконечный) числовой оси. 

Білет 9

1. Загальні вимоги до машинних експериментів.

Для моделювання об’єктів та систем керування широко застосовують електронні аналогові, цифрові та гібридні (аналогово-цифрові) обчислювальні машини /20,31/. Останнім часом на практиці все більш поширеними стають цифрові ЕОМ, тому в книзі концентрується увага на моделюванні за допомогою цифрових ЕОМ.

Моделювання ЕМС та інших систем автоматичного керування на ЦОМ є числовим рішенням відповідних рівнянь при даних початкових умовах. Тому основою моделювання є обчислювальна математика. Вона встановлює правила обчислень (алгоритмів), по яким початкові дані (вхід) ЦОМ перетворює у вихідні дані (результат, що шукається). При цьому алгоритми повинні бути машинно-орієнтованими (ЦОМ є дискретним приладом і тому працює лише з цифровими даними; тобто даними, які квантуються за часом та за рівнем).

Можна сформулювати такі основні вимоги до машино-орієнтованих даних (до машинного експеріменту).

1. Метод (математична модель) може використовуватись як алгоритм тільки тоді, коли він повністю схематизований. Це означає, що у кожен момент часу однозначно встановлено, який послідуючий крок повинен бути зроблений. Не всі аналітичні моделі (рівняння) допускають такі перетворення.

2. Алгоритми переважно повинні бути рекурсивними. Рекурсивний алгоритм складається із відносно невеликих складових частин, які багаторазово реалізуються для різноманітних наборів значень (операндів) (до них повертаються багаторазово).

3. Обчислювальний алгоритм повинен бути обмеженим, тобто вести до результату за обмежене число обчислювальних кроків. Необмежені математичні моделі (послідовності, ряди і т. ін.) необхідно трансформувати до кінцевого подання (сума ряда та ін.).

4. Обчислювальний алгоритм може мати лише ті операції, які виконуються на даній ЦОМ.

При виконанні обчислювальних експеріментів (моделюванні на ЦОМ) важливо знати характеристику похибок обчислень (нев`язок).