Тема курсовой работы: Алгоритмы получения последовательности псевдослучайных чисел

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

В ходе выполнения курсовой работы будут выполнены следующие задачи: изучение и анализ основных методов и подходов к генерации последовательностей псевдослучайных чисел: генерирование равномерно распределённых случайных чисел, получение псевдослучайных чисел на основе полиномиального счетчика (сдвигового регистра), линейный и нелинейный конгруэнтные методы, системно-теоретический подход на примере каскада Голлманна и альтернирующего (перемежающегося) Stop‐and‐Go генератора и сложно-теоретический подход на примере генераторов Blum‐Micali, RSA и Blum Blum Shub (BBS); составление программы на языке программирования C# для реализации алгоритмов генерации последовательностей псевдослучайных чисел.

Глава 1.   Генератор псевдослучайных чисел: понятие, области применения

1.1.  Понятие и основные области применения ГПСЧ

Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

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

Числа, которые выбираются случайным образом, находят множество полезных применений [5].

• Моделирование. При использовании компьютера для моделирования естественных явлений случайные числа нужны для того, чтобы сделать эти модели похожими на реальные явления. Моделирование применяется во многих областях, начиная от исследований в ядерной физике (где частицы испытывают случайные столкновения) и заканчивая исследованием операций (где люди прибывают, например, в аэропорт через случайные промежутки времени).
• Выборочный метод. Часто бывает невозможно исследовать все варианты, но случайная выборка обеспечивает понимание того, что можно назвать «типичным» поведением.
• Численный анализ. Для решения сложных задач численного анализа была разработана остроумная техника, использующая случайные числа. Об этом написано несколько книг.
• Компьютерное программирование. Случайные величины являются хорошим источником данных для тестирования эффективности компьютерных алгоритмов.
• Более важно то, что они играют решающую роль при использовании рандомизированных алгоритмов, которые часто намного превосходят своих детерминированных двойников.
• Принятие решений. Говорят, что многие администраторы принимают решения, бросая монету, игральную кость либо каким-нибудь другим подобным способом. Сплетничают, что некоторые профессора в колледжах ставят оценки, используя тот же метод. Иногда важно принять полностью «беспристрастное» решение.
• Случайность является также важной частью оптимальных стратегий в теории матричных игр.
• Эстетика. Небольшая добавка случайности оживляет музыку и компьютерную графику.
• Развлечения. Многие считают, что они замечательно проводят время, бросая игральные кости, тасуя колоду карт, вращая колесо рулетки и т. п. Такие традиционные способы использования случайных чисел получили название метод Монте-Карло. Это общее название всех алгоритмов, использующих случайные числа.