Генерирование псевдослучайных чисел Метод середины квадрата

Федеральное агентство по образованию

Бийский технологический институт (филиал)

государственного образовательного учреждения

высшего профессионального образования

«Алтайский государственный технический университет им. И.И. Ползунова»

(БТИ АлтГТУ)

КАФЕДРА

Информационных и управляющих систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОМУ ПРОЕКТУ (РАБОТЕ)

«Генерирование псевдослучайных чисел. Метод середины квадрата»

2009

Введение

Курсовая работа состоит из двух основных частей: теоретической и практической. В теоретической будет рассмотрено понятие вероятностного алгоритма, понятие «генератор случайных чисел», применение, методы генерирования случайных чисел, псевдослучайные числа, немного истории о генерировании случайных чисел и методе середины квадрата. В практической – рассмотрение и реализация метода середины квадрата, для этого работа разбита на несколько частей:

1. формулировка задачи.

2. построение модели

3. разработка алгоритма

4. кодирование (реализация) алгоритма

5. анализ сложности

6. проверка правильности

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

Алгоритм называется вероятностным (randomized), если он использует генератор случайных чисел (random – numbergenerator). Это классическое определение, дается в большинстве литературных источников (в нашем случае Т. Кормен, Ч. Лейзерсон, Р. Ривест). Примерная работа генератора выглядит так: Random[a, b] возвращает с равной вероятностью любое целое число в интервале от а до b. Например Random[0,1] возвращает 0 или 1с вероятностью 1/2 чаще на практике используют генератор псевдослучайных чисел (pseudorandom – numbergenerator) – детерминированный алгоритм, который выдает числа, похожие на случайные.

Кроме того, генераторы случайных чисел называют датчиками случайных чисел – это могут быть разнообразные технические устройства, которые способны вырабатывать случайные величины. Используем пример, приведенный в опорном литературном источнике (А.В. Налимов, Основы алгоритмизации) – использование шумящих радиоэлектронных приборов (диоды, транзисторы). При работе такого прибора будем считать, сколько раз v за фиксированное время Δt напряжение превысило заданный уровень E0. двоичное случайное число получаем при помощи соотношения µ=vmod 2. если частоты появления 0 и 1 равны, то можно считать, что устройство вырабатывает случайную последовательность двоичных цифр. Если же частоты не равны то вводим какую-нибудь схему стабилизации: группировать цифры парами, тройками, и т.д., а значение 0 и 1 приписывать некоторым комбинациям.

Обычно датчики содержат несколько генераторов описанного типа, работающих независимо друг от друга. Так что датчиком выдается число 0, а₁ …а_m , записанное в форме m-разрядной двоичной дроби.

Что касается псевдослучайных чисел, возьмем любую случайную величину z , значения z₁ ,…, z_n , которые вычисляются по какой-либо заданной формуле и могут быть использованы вместо случайных чисел при решении некоторых задач, называются псевдослучайными. Одним из преимуществ псевдослучайных чисел является их быстрая генерация, к тому же они не требуют запоминающих устройств. Запас псевдослучайных чисел ограничен. В качестве стандартных обычно равномерно распределенные на интервале [0,1] псевдослучайные числа.

Рассмотрим так же понятие равномерного распределения. Равномерным распределением на конечном множестве чисел называется такое распределение, при котором любое из возможных чисел имеет одинаковую вероятность появления. Если не задано определенное распределение на конечном множестве чисел, то принято считать его равномерным.

Большинство алгоритмов вычисления случайных (псевдослучайных) чисел, используемых при практических расчетах, основаны на рекуррентных формулах первого порядка: γ_n+1 =Φ(γ_n ),где γ_o задано. Гладкая функция y =Φ(x) не может породить хорошую последовательность псевдослучайных чисел, т. к. если при

помощи действительно случайных чисел нанести точки с координатами (γ₁ , γ₂ ) ; (γ₂ , γ₃ ) ;…; (γ_n , γ_{n +1} ) ; на квадрат [(0,1)*(0,1)], то точки ( γ₁ , Φ(γ₁ )) ; ( γ₂ , Φ(γ₂ ));…; ( γ_n , Φ(γ_n )) ;… На основе этогоположения можно сформулировать условие относительно функции Φ(x). Что бы функция y =Φ(x) порождала псевдослучайные числа, ее график должен плотно заполнять квадрат [(0,1)*(0,1)] т.е. она должна быть разрывной в каждой точке. Поскольку равномерно распределенные случайные числа должны довлетворять статистическим требованиям (например, математическое ожидание равно 0,5, дисперсия равна 1/12и т.д.), то условие плотного заполнения всего квадрата является только необходимым. Еще одна особенность алгоритмов типа γ _{n +1}

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать