- •Імовірнісне моделювання
- •4.1. Метод статистичних випробувань
- •4.2. Генератори випадкових чисел
- •4.2.1. Типи генераторів
- •4.2.2. Лінійні конгруентні генератори
- •4.3. Перевірка послідовностей випадкових чисел
- •4.4. Моделювання випадкових подій та дискретних величин
- •4.4.1. Незалежні випадкові події
- •4.4.3. Умовна подія
- •4.4.4. Випадкова дискретна величина
- •4.4.2. Група несумісних подій
- •4.4.5. Геометричний розподіл
- •4.4.6. Біноміальний розподіл
- •4.4.7. Розподіл Пуассона
- •4.5. Моделювання неперервних випадкових величин
- •4.5.1. Метод оберненої функції
- •4.5.2. Рівномірний розподіл
- •4.5.3. Експоненціальний розподіл
- •4.5.4. Пуассонівський потік
- •4.5.5. Нормальний розподіл
- •4.5.6. Логарифмічно-нормальний розподіл
- •4.5.7. Розподіл і потоки Ерланга
- •4.5.8. Гамма-розподіл
- •4.5.9. Бета-розподіл
- •4.5.10. Розподіл Вейбулла
- •4.5.11. Гіпер- і гіпоекспоненціальні розподіли
- •4.6. Моделювання випадкових векторів
- •4.7. Моделювання випадкових процесів
- •4.8. Статистична обробка результатів моделювання
- •4.8.1. Оцінювання ймовірності
- •4.8.2. Оцінювання розподілу випадкової величини
- •4.8.3. Оцінювання математичного сподівання
- •4.8.4. Оцінювання дисперсії
- •4.8.5. Оцінювання кореляційного моменту
- •4.9. Визначення кількості реалізацій під час моделювання випадкових величин
- •4.9.1. Оцінювання ймовірності
- •4.9.2. Оцінювання середнього значення
- •Висновки
- •Контрольні запитання та завдання
- •Рождение метода Монте-Карло в Лос-Аламосе
- •Дальнейшее развитие и современность
- •Интегрирование методом Монте-Карло
- •Обычный алгоритм Монте-Карло интегрирования
- •Геометрический алгоритм Монте-Карло интегрирования
- •Квантовый метод Монте-Карло
- •Детерминированные гпсч
- •Гпсч с источником энтропии или гсч
- •Пример простейшего гсч с источником энтропии
- •Примеры гсч и источников энтропии
- •Гпсч в криптографии
- •Примеры криптостойких гпсч Циклическое шифрование
- •Аппаратные гпсч
- •Теоретическая основа Принципы построения
- •Графические тесты
- •Статистические тесты
- •Тесты diehard
- •Тесты д. Кнута
- •Тесты nist
- •Практические приложения
- •Конкурс aes
- •Свойства примитивных многочленов
- •Свойства
- •Линейная сложность
- •Корреляционная независимость
- •Алгоритмы генерации примитивных многочленов Готовые таблицы
- •КонфигурацияГалуа
- •Примеры генераторов Генераторы «стоп-пошёл»
- •Каскад Голлманна
- •Пороговый генератор
- •Другие виды Самопрореживающие
- •Многоскоростной генератор с внутренним произведением
- •[Править]Преимущества
- •[Править]Недостатки
- •Моменты
- •Свойства гамма-распределения
- •Связь с другими распределениями
- •Моделирование гамма-величин
- •Определение
- •Форма графика
- •Моменты
- •Связь с другими распределениями
- •Распределение Вейбулла
- •Свойства гиперэкспоненциального распределения
- •Моделирование марковских случайных процессов
- •Марковский процесс с дискретным временем
- •Марковские случайные процессы с непрерывным временем
- •Цепь Маркова
- •Цепь Маркова с дискретным временем Определение
- •Переходная матрица и однородные цепи
- •Граф переходов, связность и эргодические цепи Маркова
- •Примеры
- •Основное кинетическое уравнение
- •Функции Ляпунова для основного кинетического уравнения
- •Примеры функций Моримото
Квантовый метод Монте-Карло
Квантовый метод Монте-Карло широко применяется для исследования сложных молекул и твёрдых тел. Это название объединяет несколько разных методов. Первый из них это вариационный метод Монте-Карло, который по сути является численным интегрированием многомерных интегралов, возникающих при решении уравнения Шрёдингера. Для решения задачи, в которой участвует 1000 электронов, необходимо взятие 3000-мерных интегралов, и при решении таких задач метод Монте-Карло имеет огромное преимущество в производительности по сравнению с другими численными методами интегрирования. Другая разновидность метода Монте-Карло — это диффузионный метод Монте-Карло.
Генератор псевдослучайных чисел (ГПСЧ, Pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).
Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов.
Источники настоящих случайных чисел найти трудно. Физические шумы, такие как детекторы событий ионизирующей радиации, дробовой шум в резисторе или космическое излучение могут быть такими источниками. Однако применяются такие устройства в приложениях сетевой безопасности редко. Сложности также вызывают грубые атаки на подобные устройства.
Альтернативным решением является создание некоторого набора из большого количества случайных чисел и опубликование его в некотором словаре. Тем не менее, и такие наборы обеспечивают очень ограниченный источник чисел по сравнению с тем количеством, которое требуется приложениям сетевой безопасности. Хотя данные наборы действительно обеспечивают статистическую случайность, они не достаточно случайны, так как злоумышленник может получить копию словаря.
Генератор псевдослучайных чисел включён в состав многих современных процессоров.
Криптографические приложения используют для генерации случайных чисел особенные алгоритмы. Эти алгоритмы заранее определены и, следовательно, генерируют последовательность чисел, которая теоретически не может быть статистически случайной. В то же время, если выбрать хороший алгоритм, полученная численная последовательность будет проходить большинство тестов на случайность. Такие числа называют псевдослучайными числами.
Детерминированные гпсч
Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые их свойства. Как сказал Джон фон Нейман, «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений».
Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и составляет около 2n/2, где n — размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2n. Если порождаемая ГПСЧ последовательность сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений.
Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:
Слишком короткий период/периоды.
Последовательные значения не являются независимыми.
Некоторые биты «менее случайны», чем другие.
Неравномерное одномерное распределение.
Обратимость.
В частности, алгоритм RANDU, десятилетиями использовавшийся на мейнфреймах, оказался очень плохим[1][2], что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.
Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, регистр сдвига с линейной обратной связью, регистр сдвига с обобщённой обратной связью.
Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (219937−1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако, существуют алгоритмы, распознающие последовательность, порождаемую вихрем Мерсенна, как неслучайную.
