Федеральное агентство по образованию
Бийский технологический институт (филиал)
государственного образовательного учреждения
высшего профессионального образования
«Алтайский государственный технический университет им. И.И. Ползунова»
(БТИ АлтГТУ)
КАФЕДРА
Информационных и управляющих систем
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОМУ ПРОЕКТУ (РАБОТЕ)
«Генерирование псевдослучайных чисел. Метод середины квадрата»
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, а1…аm, записанное в форме m-разрядной двоичной дроби.
Что касается псевдослучайных чисел, возьмем любую случайную величину z, значения z1,…, zn, которые вычисляются по какой-либо заданной формуле и могут быть использованы вместо случайных чисел при решении некоторых задач, называются псевдослучайными. Одним из преимуществ псевдослучайных чисел является их быстрая генерация, к тому же они не требуют запоминающих устройств. Запас псевдослучайных чисел ограничен. В качестве стандартных обычно равномерно распределенные на интервале [0,1] псевдослучайные числа.
Рассмотрим так же понятие равномерного распределения. Равномерным распределением на конечном множестве чисел называется такое распределение, при котором любое из возможных чисел имеет одинаковую вероятность появления. Если не задано определенное распределение на конечном множестве чисел, то принято считать его равномерным.
Большинство алгоритмов вычисления случайных (псевдослучайных) чисел, используемых при практических расчетах, основаны на рекуррентных формулах первого порядка: γn+1 =Φ(γn),где γoзадано. Гладкая функция y =Φ(x) не может породить хорошую последовательность псевдослучайных чисел, т. к. если при
помощи действительно случайных чисел нанести точки с координатами (γ1,γ2); (γ2,γ3);…; (γn,γn+1); на квадрат [(0,1)*(0,1)], то точки (γ1,Φ(γ1)); (γ2,Φ(γ2));…; (γn,Φ(γn));… На основе этогоположения можно сформулировать условие относительно функции Φ(x). Что бы функция y =Φ(x) порождала псевдослучайные числа, ее график должен плотно заполнять квадрат [(0,1)*(0,1)] т.е. она должна быть разрывной в каждой точке. Поскольку равномерно распределенные случайные числа должны довлетворять статистическим требованиям (например, математическое ожидание равно 0,5, дисперсия равна 1/12и т.д.), то условие плотного заполнения всего квадрата является только необходимым. Еще одна особенность алгоритмов типа γn+1=Φ(γn) заключается в том, что они всегда порождают периодические последовательности. Следовательно существуют такие L и l, что γL+i=γl+i, (i=1,2…). Пусть теперь L – наименьшее число, удовлетворяющее последнему равенству и такое, что l<L. Существует множество генераторов псевдослучайных чисел. Практически все алгоритмы генерирования псевдослучайных чисел ориентированы на конкретные машины (учитывают особенности работы процессора и способы хранения информации) и компиляторы (учитываются особенности арифметики, реализованной в конкретном языке программирования для конкретной машины). Поэтому готовые генераторы псевдослучайных чисел перед использованием необходимо тщательно проверить и настроить их на конкретные условия.
Каждая из 10 цифр от 0 до 9 будет появляться примерно один раз из 10 в равномерной последовательности случайных цифр. Каждой паре двух последовательных цифр следует появиться 1 раз из 100 и т.д. однако если взять конкретную случайную последовательность длиной в миллион цифр, то она не всегда будет содержать 100 000 нулей, 100 000 единиц и т.д. Действительно, возможность появления такой последовательности незначительна; на самом деле, если рассматривать достаточно большую совокупность таких последовательностей, то в среднем будет появляться 100 000 нулей, 100 000 единиц и т.д.
Любая конкретная последовательность, содержащая миллион цифр, так же вероятна, как и любая другая. Если мы выберем миллион цифр наудачу и если окажется, что первые 999 999 из них – нули, то вероятность того, что последняя цифра в этой последовательности – также нуль, все еще останется точно равной одной десятой в истинно случайной ситуации. Это утверждение, хоть и кажется парадоксальным, не противоречит реальности.
Несовершенство первых механических методов в вначале пробудило интерес к получению случайных чисел с помощью обычных арифметических операций, заложенных в компьютер. Джон фон Нейман первым предложил такой подход около 1946 года; его идея заключалась в том, чтобы возвести в квадрат предыдущее случайное число и выделить средние цифры. Например, мы хотим получить 10-значное число и предыдущее равнялось 5772156649. возводим его в квадрат и получаем 33317792380594909201, значит следующим числом будет 7923805949.
Метод середин квадратов фон Неймана, как было показано, фактически является сравнительно бедным источником случайных чисел. Опасность состоит в том, что последовательность стремиться войти в привычную колею, т.е. короткий цикл повторяющихся элементов. Например, каждое появление нуля как числа последовательности приведет к тому, что все последующие числа также будут нулями.
Некоторые ученые экспериментировали с методом середин квадратов в начале 50-х годов. Работая с четырехзначными числами вместо десятизначных, Дж.Э. Форсайт испытал 16 различных начальных значений и обнаружил, что 12 из них приводят к циклическим последовательностям, заканчивающимся циклом 6100, 2100, 4100, 8100, 6100,…, в то время как две из них приводят к последовательностям, вырождающимся в 0. более интенсивные исследования, главным образом в двоичной системе счисления, провел Н.К. Метрополис. Он показал, что если использовать 20-разрядное число, то последовательность случайных чисел, полученная методом середин квадратов, вырождается в 13 различных циклов, причем длина самого большого периода равна 142.
Достаточно легко запустить метод середин квадратов с новым исходным значением, если обнаружить число 0, однако избавиться от длинных циклов довольно трудно.
Практическая часть
Метод середины квадрата
Формулировка задачи
Этот алгоритм является одним из первых и предложен Дж. Нейманом. Пусть числа γn 2kзначимые, т.е. γn =0, а1, а2,… а2k. Тогда функцию Φ(γn) определим
следующимобразом:γn+1=Φ(γn)=Franc{10-2k *Int(103k*γ2n)} т.е. возведемγn вквадратиполучим.γn2=0, b1, b2,… b4k. Затем отберем средние 2k цифр и получим γn+1=0, bk+1b2…b3k. Теперь перейдем к более детальному рассмотрению алгоритма.
В результате работы программы должны получить математическое ожидание и дисперсию, определенные для последовательности из 50 000 элементов. Дана последовательность из 50 000 элементов. По ходу решения генерируем 2k – разрядные псевдослучайные числа. На входе должно быть задано х0-2k разрядное начальное число. М – последовательность случайных чисел. Есть вероятность, что числа, генерируемые при помощи алгоритма обнулятся, при условии х0 < 104. чтобы избежать этого нужно длину отрезка апериодичности L увеличить, что подробно будет рассмотрено ниже.