Общая постановка задачи

Лабораторная работа №1. Исследование способов формирования случайной величины на основе датчиков.

Требования к содержанию, оформлению и порядку выполнения

 

 Работа должна быть выполнена полностью в соответствии с приведенной ниже программой работы. Результаты работы оформляются в виде отчета. Отчет оформляется на бланке установленного образца. Отчет может представляться к защите в электронном виде. Содержание отчета:

1. Листинг программы (или файл в электронном виде) генерации последовательности чисел с равномерным распределением для двух датчиков случайных чисел на основе алгоритмов сложения и умножения.

2. Гистограммы полученных распределений случайных чисел для числа испытаний n=10, 100 и 1000.

3. Выводы по работе.

Разработанные программные модули представляются либо в электронном виде в Пегасе или на электронную почту sidorenko@bsu.edu.ru (желательно), либо в распечатанном виде (листинг программы) прилагаются к отчету. Для защиты работы необходимо ответить на контрольные вопросы и пояснить полученные результаты в виде выводов.

 

Теоретическая часть

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

В настоящее время создано большое количество разнообразных программных продуктов, однако, следует знать, что задача формирования случайных величин с заданным законом распределения по-прежнему полностью не решена. Возникает вопрос: почему? Ответ состоит в том, что нельзя искусственно получить случайный поток с заданными вероятностными свойствами, так как все существующие методы получения случайных чисел используют рекуррентные формулы, реализующие детерминированные алгоритмы. То есть, на практике находят широкое применение способы получения потоков «случайных» величин, которые удовлетворяют определенным критериям на случайность, хотя на самом деле таковыми не являются.

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

Простейшие датчики случайных чисел генерируют значения случайной величины, имеющей равномерное распределение в ин­тервале (0, 1). Основная проблема разработки таких программ состоит в не­обходимости обеспечить случайные числа с помощью детерминированного процесса исполнения. Реально такие программы генерируют псевдослучайные числа. Качество последовательностей, генерируемых датчиком случайных чисел, оценивается близостью к действительно случайным с помощью мно­гих тестов. Как показал многолетний опыт разработки, наиболее эффектив­ными алгоритмами работы датчиков случайных чисел являются так называе­мые конгруэнтные генераторы. Алгоритмы их работы можно описать сле­дующими соотношениями:

алгоритм 1 

или  алгоритм 2 

.

Здесь всюду а, с, х₁, х — целые числа, а в качестве выходного псевдослучай­ного числа используется действительное Uj = хj/т. Операции вычисления по модулю mod(m) обеспечиваются работой алгоритма в компьютерах с конечной разрядностью. Приведем сначала демонстрационный пример работы такого алгоритма при следующих параметрах: .

Так как 32=2⁵, следовательно, здесь используются пятиразрядные машинные слова для представления целых чисел. Пока эти числа не превышают 31, ре­зультаты операций очевидны. При превышении этого значения будет исполь­зоваться остаток от деления на целое, кратное 32 так, как это показано на рисунке 1.

 

Рис.1 Пример результатов работы датчика случайных чисел для m=32.

 

Если продолжить вычисление, то на следующем шаге будет получена едини­ца и цикл замкнется. Далее последовательность нельзя будет считать псевдо­случайной, поскольку начнется повторение уже ранее полученных чисел. Ясно, что чем больше период, тем последовательность лучше от­ражает свойства случайного потока. Нетрудно убедиться, что период будет зависеть как от выбора т, так и от начального значения х. В системе MATLAB можно генерировать массив из п случайных чисел, равномерно распределенных на интервале (0, 1) с помощью встроенной функции X = rand(n).

На практике при­меняют несколько различных генераторов с различными параметрами. Наи­более типичными являются генераторы с именами функций URN 13 (Unified Random Number) и URN38.

Для первого из них период составляет 1 073 741 824. Алгоритм для него име­ет вид:

.

 

Для второго:

.

 

Итак, мы увидели, как программным путем реализовать генератор значений случайных интервалов.

Таким образом, получить равномерное распределение чисел в единичном интервале можно используя либо формулу суммирования (алгоритм 1), либо формулу умножения чисел (алгоритм 2) по заданному модулю m.

Для того чтобы убедиться в равномерности распределения полученных чисел можно воспользоваться методом на основе анализа гистограмм, построенных после проведения нескольких циклов работы датчика. Гистограмма – это разновидность диаграммы, столбцы которой пропорциональны числу значений случайной величины в заданных интервалах. При построении гистограммы подсчитывается число попаданий полученных значений в эквидистантные интервалы, на которые разбивается вся область возможных значений чисел. Чем больше число выполненных испытаний, тем точнее полученное распределение стремится к равномерному распределению.

Для построения гистограммы необходимо разделить весь диапазон значений случайной величины на несколько смежных поддиапазонов (интервалов), например на 10 или 100, а затем подсчитать, по сколько случайных величин из сформированного массива попало в каждый поддиапазон.

    Программу, реализующую построение гистограммы можно написать самостоятельно, или, в случае затруднений, использовать имеющуюся в системе MATLAB специальную функцию hist(Y). Здесь Y – массив случайных величин, для которого строится гистограмма для 10 интервалов. При необходимости задать другое количество интервалов (часто рекомендуется значение 100 или 1000), следует использовать функцию вида hist(Y,n), где параметр n определяет заданное число интервалов. Увеличение числа столбцов гистограммы позволяет более точно исследовать работу датчика. На практике рекомендуется выбирать число столбцов на два порядка ниже, числа сгенерированных чисел N. Например, если N=10000, то число столбцов можно принять равным n =100.

Общая постановка задачи

Для выполнения лабораторной работы необходимо:

· Изучить теоретический материал и ответить на контрольные вопросы.

· Самостоятельно в любой доступной программной среде (Matlab (лучше всего!), Excel и т.д.) разработать программные модули, реализующие рассмотренные выше датчики случайных чисел в соответствии с исходными данными в приведенной ниже таблице.

· Задать произвольные значения входных параметров a, c, m, x и сгенерировать массивы случайных чисел с использованием разработанных модулей и проанализировать полученные результаты визуально по гистограммам.

· Рассчитать для полученных массивов чисел математическое ожидание и дисперсию и сравнить их с теоретическими значениями m=0,5 и D=0,0833.

· Провести ещё несколько раз пункты 2 и 3 для различных значений входных параметров a, c, m, x, а также для различного числа сгенерированных чисел в массиве N, стараясь получить датчики с возможно близкими параметрами m и D.

· Сделать выводы о работе датчиков в зависимости от числа сгенерированных чисел в массиве N.

· Исследовать параметры встроенного в системе MATLAB датчика равномерно распределенных на интервале (0, 1) с помощью встроенной функции X = rand(n) сравнив качество его работы с разработанными самостоятельно датчиками.

· Оформить бланк отчета установленным выше образом.