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

Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Теоретическая часть

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

1.2 Генерирование псевдослучайных чисел с помощью класса Random в С++

Глава 2. Практическая часть

2.1 Метод середины квадрата. Формулировка задачи

2.2 Разработка алгоритма

2.3 Кодирование алгоритма

2.4 Проверка правильности программы

Заключение

Список литературы

Введение

С момента своего создания компьютеры всё больше и больше проникают в нашу жизнь. Они находят своё применение, как в быту, так и на производстве. В автоматизированных цехах и заводах широко применяется оборудование с использованием микропроцессоров и микро ЭВМ. Их использование в составе промышленного оборудования обеспечивает снижение его стоимости по сравнению с системами на элементах малой и средней степени интеграции, что и является актуальностью курсовой работы.

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

Цель курсовой работы - охарактеризовать псевдослучайные числа.

Исходя из цели курсовой работы, ставим перед собой ряд задач:

- Изучить генерирование псевдослучайных чисел;

- Охарактеризовать генерирование псевдослучайных чисел с помощью класса Random в С++;

- Рассмотреть метод середины квадрата. Формулировка задачи, Разработка алгоритма, Кодирование алгоритма.

Структура курсовой работы - данная работа состоит из двух основных частей: теоретической и практической.

В теоретической будет рассмотрено понятие вероятностного алгоритма, понятие «генератор псевдослучайных чисел», применение, методы генерирования псевдослучайных чисел, псевдослучайные числа, немного истории о генерировании и методе середины квадрата.

В практической - рассмотрение и реализация метода середины квадрата, для этого работа разбита на несколько частей:

- формулировка задачи;- построение модели;- разработка алгоритма.

Глава 1. Теоретическая часть

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

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

В языке программирования C получить случайное число можно с помощью функции rand(), которая входит в стандартную библиотеку языка. Эта функция не принимает никакие параметры.

Для расстановки мин на игровом поле в игре «Сапер» необходимо случайным образом задать координаты клетки с миной. Для этого в программе используются различные методы генерирования таких координат.

Генератор псевдослучайных чисел (ГПСЧ) -- алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению [1].

Современная информатика широко использует псевдослучайные числа в самых разных приложениях -- от метода Монте-Карло до криптографии. Генераторы псевдослучайных чисел широко используются в имитационном моделировании.

Термин ГПСЧ часто используется для описания ГПСБ (PRBG) -- генераторов псевдослучайных бит, а так же различных поточных шифров. Предназначение ГПСЧ -- генерация последовательностей чисел, которые невозможно отличить от случайных. Никакой детерминированный алгоритм не может генерировать полностью случайные числа, а только лишь аппроксимировать некоторые свойства случайных чисел.

Самые простые аппаратные ГСЧ (АГСЧ) основаны на тех свойствах элементов электронных схем, с которыми так долго и упорно боролись инженеры - схемотехники. Это свойство - собственные шумы электронного прибора.

В отдельный подкласс АГСЧ стоит вынести разработки, в которых вместо дискретного электронного компонента применяется куда более сложный источник естественной случайности. Например, помещенная в специальный футляр при полном отсутствии света ПЗС-матрица камеры приводится управляющей программой в наихудший режим, при котором шумовые характеристики максимальны и картина чистого, природного хаоса пригодна к дальнейшей обработке.

Второму обширному классу АГСЧ лучше всего подойдет название "функциональный". Здесь в качестве "источника энтропии" используются фундаментальные функциональные свойства электронных приборов, например счетчиков Гейгера-Мюллера. Неприятной особенностью подобных устройств является необходимость применения радиоизотопных источников.

Третий класс АГСЧ - это "фундаментальный" класс. Наиболее яркий представитель "фундаментальных" АГСЧ - оптический квантовый генератор случайных чисел". Также существует устройство, в котором фундаментальные физические принципы, наносекундная синхронизация и самая современная электроника подчинены решению самой утилитарной задачи - получению случайных чисел, обновляющихся 100 тыс. раз в секунду.

Четвертый класс АГСЧ можно условно назвать "паразитным персонально-компьютерным". К их свойствам относятся прежде всего тепловые шумы и флуктуации в подсистеме аналогового ввода/вывода звукового адаптера.

В отдельный класс "курьезных" АГСЧ можно выделить специализированных роботов, методично бросающих... обычные игральные кости и оснащенных системой технического зрения для считывания выпавших очков [3].

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

· Слишком короткий период/периоды

· Последовательные значения не являются независимыми

· Некоторые биты «менее случайны», чем другие

· Неравномерное одномерное распределение

· Обратимость

Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, алгоритм Блюма, Блюма и Шуба, Вихрь Мерсенна [5].

Линейный конгруэнтный метод

Данный алгоритм был предложен Д. Х. Лемером в 1948 году. Применяется в простых случаях и не обладает криптографической стойкостью. Используется в качестве стандартного генератора многими компиляторами.

Этот алгоритм заключается в итеративном применении формулы (1):

(1)

где a > 0, c > 0, M > 0 -- некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X₀ и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности X_j определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда:

1. НОД (c, m) = 1 (то есть c и m взаимно просты);

2. a - 1 кратно p для всех простых p -- делителей m;

3. a - 1 кратно 4, если m кратно 4.

При реализации выгодно выбирать m = 2^e, где e -- число бит в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.

Формула (2) для вычисления n-й члена последовательности, зная только 0-й [7].

(2)

Метод Фибоначчи с запаздываниями

Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делает невозможным их использование в статистических алгоритмах, требующих высокого разрешения.[2]

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

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

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле (3):

X(k) = (3)

где X(k) -- вещественные числа из диапазона [0, 1),

a, b -- целые положительные числа, называемые лагами.

Для работы фибоначчиеву датчику требуется знать max(a, b) предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется max (a, b) случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.

Рекомендуются следующие значения: a = 55, b = 24; a = 17, b = 5; a = 97, b = 33 [9].

Алгоритм Блюма, Блюма и Шуба (Blum Blum Shub, BBS)

Предложен в 1986 году Ленор и Мануэлем Блюм и Майклом Шубом.

BBS заключается в применении формулы (4):

x_n+1 = (x_n)² mod M (4)

где

M=p*q

является произведением двух больших простых p и q.

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

Два простых числа, p и q, должны быть оба сравнимы с 3 по модулю 4 и НОД(ц(p-1), ц(q-1)) должен быть мал.

Интересной особенностью этого алгоритма является то, что для получения x_n необязательно вычислять все n - 1 предыдущих чисел, если известно начальное состояние генератора x₀ и числа p и q. n-ное значение может быть вычислено "напрямую" используя формулу (5):

x_n = x₀ ^{(2 ^ n) mod ((p-1)(q-1))} mod M (5)

Вихрь Мерсенна (Mersenne twister)

Разработан в 1997 японскими учёными Макото Мацумото и Такудзи Нисимура. Он обеспечивает быструю генерацию высококачественных псевдослучайных чисел, так как изначально был разработан с учётом ошибок, найденных в других алгоритмах.

Существуют по меньшей мере два общих варианта алгоритма, различающихся только размером использующегося простого числа Мерсенна. Новейший и наиболее распространённый называется Mersenne Twister MT 19937.

MT 19937 имеет следующие ожидаемые свойства:

1. Он был разработан с целью иметь огромный период, размером 2¹⁹⁹³⁷ ? 1

2. Он имеет высокий порядок пространственного эквираспространения.

3. Он значительно быстрее, чем все остальные генераторы, за исключением статистически-дефектных генераторов.

4. Он статистически случаен во всех выходных битах [10].

1.2 Генерирование псевдослучайных чисел с помощью класса Random в С++

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

В классе Random определены следующие два конструктора:

public Random()

public Random(int seed)

С помощью первой версии конструктора создается объект класса Random, который для вычисления начального числа последовательности случайных чисел использует системное время. При использовании второй версии конструктора начальное число задается в параметре seed.

Класс Random (сокращено)

//Конструкторы

Random ()

Random(int а);

//Методы экземпляра

int Next () ;

int Next(int макс_значение) ;

int Next(int мин_значение, int макс_значение) ;

double NextDouble() ;

Конструкторы возвращают случайные объекты, которые образуют последовательность псевдослучайных чисел. Методы Next возвращают следующее число в последовательности, возможно, между заданными значениями. NextDouble возвращает число в диапазоне от 0.0 до 1.0.

Сравнив методы получения псевдослучайных чисел для реализации в программе, я выбрала, помимо метода, основанного на использовании системного класса Random, линейный конгруэнтный метод и алгоритм Блюма, Блюма и Шуба, исходя из преимуществ этих методов перед другими:

1) более простое математическое представление, а следовательно и программная реализация;

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

Алгоритм называется вероятностным (randomized), если он использует генератор случайных чисел (random - number generator). Это классическое определение, дается в большинстве литературных источников (в нашем случае Т. Кормен, Ч. Лейзерсон, Р. Ривест).

Примерная работа генератора выглядит так: Random [a, b] возвращает с равной вероятностью любое целое число в интервале от а до b. Например Random [0,1] возвращает 0 или 1с вероятностью 1/2 чаще на практике используют генератор псевдослучайных чисел (pseudorandom - number generator) - детерминированный алгоритм, который выдает числа, похожие на случайные [4].

Кроме того, генераторы случайных чисел называют датчиками случайных чисел - это могут быть разнообразные технические устройства, которые способны вырабатывать случайные величины. Используем пример, приведенный в опорном литературном источнике (А.В. Налимов, Основы алгоритмизации) - использование шумящих радиоэлектронных приборов (диоды, транзисторы).

При работе такого прибора будем считать, сколько раз v за фиксированное время Дt напряжение превысило заданный уровень E0. двоичное случайное число получаем при помощи соотношения µ=v mod 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=Ц(г_n)

заключается в том, что они всегда порождают периодические последовательности. Следовательно, существуют такие L и l, что

г_L+i=г_l+i, (i=1,2…).

Пусть теперь L - наименьшее число, удовлетворяющее последнему равенству и такое, что l<L.

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

Поэтому готовые генераторы псевдослучайных чисел перед использованием необходимо тщательно проверить и настроить их на конкретные условия [6].

Каждая из 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, однако избавиться от длинных циклов довольно трудно [8].

Глава 2. Практическая часть

2.1 Метод середины квадрата. Формулировка задачи

Этот алгоритм является одним из первых и предложен Дж. Нейманом. Пусть числа г_n 2k значимые, т.е. г_n =0, а1, а2,… а2k. Тогда функцию Ц(г_n) определим

следующим образом:

г_n+1=Ц(г_n)=Franc{10^-2k *Int(10^3k*г²_n)}

т.е. возведем г_n в квадрат и получим. г_n²=0, b₁, b₂,… b_4k. Затем отберем средние 2k цифр и получим г_n+1=0, b_k+1b₂…b_3k. Теперь перейдем к более детальному рассмотрению алгоритма.

В результате работы программы должны получить математическое ожидание и дисперсию, определенные для последовательности из 50 000 элементов. Дана последовательность из 50 000 элементов. По ходу решения генерируем 2k - разрядные псевдослучайные числа. На входе должно быть задано х₀-2k разрядное начальное число. М - последовательность случайных чисел. Есть вероятность, что числа, генерируемые при помощи алгоритма обнулятся, при условии х₀ < 10⁴. чтобы избежать этого нужно длину отрезка апериодичности L увеличить, что подробно будет рассмотрено ниже.

Построение модели

Случайная величина г равномерно распределена на интервале [0,1], если определяются соотношениями:

Р_г(г)=1, г[0,1]; F_г(г)=

Математическое ожидание и дисперсия (среднеквадратическое отклонение) для непрерывных и дискретных случайных величин:

=

=

=

=

Теперь об упомянутом увеличении длины отрезка апериодичности. Есть вероятность, что числа, генерируемые при помощи алгоритма обнулятся, при условии х₀ < 10⁴. чтобы избежать этого нужно длину отрезка апериодичности L увеличить. Практические расчеты показали, что L (длина отрезка апериодичности) достаточно мала, и это может явиться причиной отказа от алгоритма середины квадрата. Длину отрезка апериодичности можно несколько увеличить, если при выполнении условия

в качестве следующего случайного числа взять [10]

Теперь функция г_n примет следующий вид:

Ц(г_n)= if ,

Для реализации алгоритма нужно определить наибольшее возможное значение k (чем больше это число, тем больше число значащих разрядов, а, следовательно, и длина отрезка апериодичности).

Таким образом, для обеспечения максимальной длины отрезка апериодичности нужно, используя простейшие типы данных, выбрать такие, которые обеспечивают наибольшее значение для k.

Например, можно принять, что г_n есть величина типа Single, а типа Double. При длине слова в 32 бита (1 разряд для знака; 7 бит для характеристики СС и 24 разряда под мантиссу ffffff ) мантисса может принимать

2¹⁰ *2 ¹⁰ *2 ⁴=1024*1024*32

различных значения, что соответствует 7…8 значащим цифрам.

При длине слова в 64 бита под мантиссу отводится 24+32 разряда. При помощи 56 разрядов можно закодировать

2⁵⁶=(1024)⁵*64,

что соответствует 15..16 значащим цифрам. Таким образом, при величинах такого типа максимально возможное значение k равно 3 (т. к. 2k<7; 4k<15) [9].

2.2 Разработка алгоритма

псевдослучайный число алгоритм

Приступим к разработке алгоритма.

Алгоритм seredina [середина квадрата]

Шаг0 [инициализация] х:=х₀;

Шаг1 [цикл, вычисление последовательности M случайных чисел х [1..M].]

For j:=1 to M do [окончание шаг2 и stop]

Шаг2 [генерация нового случайного числа]

Y:=X² [Y имеет 4k разрядов]

Число Х получаем удалением по k разрядов с каждого конца Y

X[j]:=X;

При k=2 и х₀=0.2134 в соответствии с первым оператором Шаг2 получим Y==0.04 5539 56. после применения второго оператора х₁=0.5539. если х₀<10⁴, то все числа, генерируемые при помощи данного алгоритма, будут тождественно равны нулю. Здесь нужно осуществлять описанное выше увеличение отрезка апериодичности.

Для реализации алгоритма потребуется написать процедуру, реализующую метод середины квадрата, которую назовем Rand, в которой при первом обращении задается целое число IX из [0.999999] и между вызовами оно не должно меняться. На выходе имеем числа: Rand числа типа Single из (0,1), IX числа типа LongInt из (0,999999), K числа типа LongInt из (0, К+1). Далее зададим переменные. Обнулим 7 и далее разряды числа Х, вычислим квадрат Х. Выберем 4…9 разряды числа Y. Определим новое целое случайное число IX из [0.999999] и случайную величину из [0.1]. Вычислим число К из [0.K+1].



Рисунок 1. блок-схем программы



Рисунок 2. блок-схема процедуры Rand

2.3 Кодирование алгоритма

Program seredina {метод середины квадрата}

Uses crt;

Var

Urand: Single;

Dm, Dd: Double;

n, i, j, k, l, ll: LongInt;

F: Text;

Procedure Rand (var Ix, k: LongInt; Urand: Single);

Var

x, z: Single;

y, z1: Double; i: LongInt;

Begin

z:=Ix; x:=z {*1.e-6}; {обнулим 7 и далее разряды числа Х.}

z1:=x+1.e-6; y:=z1*z1*1.e-12; {вычислим квадрат Х.}

z1:=y*1.e+3; y:=z1-Trunc(z1); {выберем 4…9 разряды числа Y.}

if y<1.e-6 then

Begin

z1:=y*1.e+6;

y:=z1-Trunc(z1);

End;

z1:=y*1.e+6;

y:=Trunc(z1);

Ix:=Trunc(y); y:=y*1.e-6; Urand:=y;

{определили новое целое случайное число IX из [0.999999] и случайную величину из [0.1]}

k:=Round((k+1)*y); {вычисляем число К из [0, К+1]}

End; {Rand}

Begin

Clrscr;

Assign (F, 'd:/F/Rand.dat');

Rewrite(F);

n:=3-23; Dm:=0; Dd:=0; ll:=50000;

for l:=1 to ll do

begin

k:=100;

Rand (n, k, Urand);

Dm:=Dm+Urand/ll;

Dd:=Dd+(Urand-0.5)*(Urand-0.5)/ll;

End;

Writeln (F, 'M=', Dm, 'Sig^2=', Dd);

Close(F);

End.

В результате работы алгоритма, после создания текстового файла по указанному адресу, получаем файл Rand, содержащий результат - математическое ожидание и дисперсию.

Анализ сложности алгоритма

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

Пусть G(n) - алгоритм для решения некоторого класса задач, а n - размерность отдельной задачи из этого класса. Определим (n) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций, которые должен выполнить алгоритм G(n) для решения любой задачи размерности n.

Алгоритм G(n) полиномиальный, если (n) растет не быстрее, чем полином от n, в противном случае алгоритм экспоненциальный.

Функцию f(n) определяют как О и говорят, что она порядка g(n) для больших n, если

Функция h(n) является О для больших n, если

Если f(n) есть О, то эти две функции возрастают с одинаковой скоростью при n>?. Если f(n) есть О, то g(n) возрастает гораздо быстрее, чем f(n).

Алгоритм G(n) называется полиномиальным, если

(n)= О,

в противном случае алгоритм является экспоненциальным.

Рассмотрим процедуру Rand. В ней всего 4 шага, одно сравнение. Для процедуры G(n) рабочая функция имеет вид

(n)= О(n)

и она является полиномиальной [6].

2.4 Проверка правильности программы

Анализ структуры программы

Для этого воспользуемся управляющим графом (ориентированный граф, вершины которого - операторы, а дуги соединяют операторы, между которыми возможна передача управления).

Рисунок 3. Схема Мартынюка

На приведенной выше схеме Мартынюка путь является простым, так как он не содержит ни одной вершины или дуги более одного раза. Схема правильная, так как выполняется условие, что каждая вершина принадлежит хотя бы одному пути по графу.

Таблица 1. Матрица Путей. Матрица путей С - путей длины 1.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
4	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
5	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
6	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
7	0	0	0	0	0	0	0	1	0	1	0	0	0	0	0
8	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
9	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
10	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
11	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
12	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
13	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Таблица 2. Матрица Путей. Матрица Р - матрица всех путей

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1
2	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1
3	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1
4	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1
5	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1
6	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1
7	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
8	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1
9	0	0	0	0	0	0	0		0	1	1	1	1	1	1
10	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1
11	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1
12	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1
13	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Все элементы 1 столбца равны 1, значит в 1 вершину управление не передается ни из какой другой. Все элементы 1 строки равны 1, значит из 1 вершины управление не передается ни в какую другую, отсюда следует, что схема программы является правильной.

Проверка диапазона значений переменных

Dm - математическое ожидание,

Dm: Dm+Urand/ll;

Dd - дисперсия,

Dd: Dd+Urand;

k: Round((k+1)*y);

L: array [1..50 000];

ll: 50 000;

Ix: Trunc(y);

Urand: y;

X: z;

Z: Ix;

Y: z1*z1z*1.e-12, z1-Trunc(z1), Trunc(z1);

Z1: x+1.e-6, y*1.e+3, y*1.e+6.

Тестирование программы

Проверка входных данных. N:=3-23, Dm:=0, Dd:=0, ll:=50000, l:=[1..ll], k:=10. все входные данные обрабатываются верно [8].

Заключение

В ходе выполнения курсовой работы были рассмотрены и проанализированы основные методы генерирования псевдослучайных чисел: линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, алгоритм Блюма, Блюма и Шуба, Вихрь Мерсенна.

Для реализации в курсовой работе были выбраны: метод, основанный на использовании системного класса Random, линейный конгруэнтный метод и алгоритм Блюма, Блюма и Шуба в связи с их достаточно простым математическим представлением и возможностью получения любого числа, располагая только значением стартового.

В конструкторской части были использованы новые визуальные компоненты. На основе имеющихся и полученных знаний об основных структурах языка С++ реализованы алгоритм игры и графический интерфейс.

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

Список литературы

1. А.В. Налимов. Анализ и разработка алгоритмов, методические рекомендации. Барнаул 2001 г.

2. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы построение и анализ, Москва 2007 г.

3. Л.Е. Захарова. Алгоритмы дискретной математики, Москва 2007 г.

4. Ватсон К. С++. - М.: Издательство "Лори", 2005

5. Зубинский А. В поисках случайности. - Компьютерное Обозрение, 29, 2003

6. Д.Э. Кнут. Искусство программирования. Том 2.

7. Кнут Д. Искусство программирования, т. 2. Получисленные методы -М.: «Вильямс», 2007. -- С. 832.

8. А.В. Налимов. Основы алгоритмизации, учебное пособие. Барнаул 2000 г.

9. Рихтер Дж. Программирование на платформе Microsoft .NET Framework. - М.: Издательско-торговый дом “Русская Редакция”, 2003.-464 с.

10. Шилдг Г. Полный справочник по С++/Пер. с англ. -- М. : Издательский дом "Вильямc", 2004. -- 752 с.

Размещено на Allbest.ru

...