Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Походзей, Борис Борисович
01.01.09
Кандидатская
1984
Ленинград
93 c. : ил
Стоимость:
499 руб.
ПРЕДИСЛОВИЕ
В диссертации решены принципиальные задачи, связанные с проблемой сложности (оптимальности) алгоритмов моделирования дискретных распределений. Впервые построены как общие, так и специальные оптимальные алгоритмы моделирования дискретных случайных величин. Полученные при этом новые теоретические результаты (конструктивное доказательство существования оптимальных "в самом сильном смысле" ЦЦР-алгоритмов для любого дискретного распределения, энтропийная мера сложности оптимальных ЦЦР-алгоритмов, экстремальные границы сложности оптимальных ЦЦР-алгоритмов, фундаментальность энтропии как нижней границы сложности моделирования дискретных распределений, точные меры сложности моделирования важнейших дискретных распределений и др.) практически полностью исчерпывают проблему сложности моделирования дискретных распределений.
Поскольку построенные оптимальные алгоритмы представляют больше теоретический, нежели практический интерес, диссертация дополнена рассмотрением традиционного подхода к моделированию дискретных распределений с выделением новых результатов в данном направлении.
Результаты диссертации лежат в основе метода Монте-Карло и имеют первостепенное значение при решении естественнонаучных задач методами статистического моделирования.
Цель и содержание работы.
1. ПРЕДВАРИТЕЛЬНЫЙ ПРИМЕР
Моделирование распределения Бернулли.
2. ПРЕОБРАЗОВАНИЕ СЛУЧАЙНЫХ БИТОВ В СЛУЧАЙНЫЕ ВЕЛИЧИНЫ
С КОНЕЧНЫМИ ДИСКРЕТНЫМИ РАСПРЕДЕЛЕНИЯМИ
Понятие ПДР-дерева и ПДР-алгоритма. Существование ПДР-деревьев, критерий их оптимальности и нижняя граница сложности ПДР-алгоритмов. Оптимальный алгоритм моделирования конечного дискретного распределения. Энтропийная мера сложности оптимальных ПДР-алгоритмов. Экстремальные границы сложности оптимальных алгоритмов.
3. ПРЕОБРАЗОВАНИЕ СЛУЧАЙНЫХ БИТОВ В СЛУЧАЙНЫЕ ВЕЛИЧИНЫ
С ПРОИЗВОЛЬНЫМИ ДИСКРЕТНЫМИ РАСПРЕДЕЛЕНИЯМИ
Понятие оптимальности "в самом сильном смысле" и его следствия. Оптимальные ЦДР-алгоритмы с бесконечной сложностью. Фундаментальность энтропии как нижней границы сложности моделирования любого дискретного распределения. Процедура "уточнения" БДР-деревьев. Оптимальный алгоритм моделирования произвольного дискретного распределения.
4. СЛОЖНОСТЬ ТАБЛИЧНЫХ МЕТОДОВ МОДЕЛИРОВАНИЯ КОНЕЧНЫХ
ДИСКРЕТНЫХ РАСПРЕДЕЛЕНИЙ
Простейший табличный метод. Экстремальные границы сложности табличного метода Уолкера. Оптимальность табличного метода Марсальи.
5. СПЕЦИАЛЬНЫЕ АЛГОРИТМЫ МОДЕЛИРОВАНИЯ ЦЕЛОЧИСЛЕННЫХ
СЛУЧАЙНЫХ ВЕЛИЧИН
Биномиальное распределение. Распределение Бернулли. "Урезанное" геометрическое распределение. Дискретное равномерное распределение. Сложность моделирования целочисленных случайных величин.
ДОПОЛНЕНИЕ. НОВЫЕ ИДЕИ В МОДЕЛИРОВАНИИ ДИСКРЕТНЫХ
РАСПРЕДЕЛЕНИЙ
Табличные методы моделирования конечных дискретных распределений. Альфа-, бета- и гамма-методы моделирования дискретного равномерного, биномиального и пуассоновского распределений. Моделирование отрицательного биномиального распределения методом отбора.
ЛИТЕРАТУРА
(од, >=^ а) • • • г{а-о ;л «;
где через обозначен логический оператор
^ _ [ А при ^ ~
1 V при <У- — Л
Для реализации преобразования (5.!) требуется ровно столько случайных битов и соответствующих логических операций, какова длина двоичного представления р (подчеркнем при этом существенность конечности данного представления).
Оказывается Сз] , что преобразование (5.1) может быть сведено к оптимальному алгоритму В из разд.'!, исходя из следующего обстоятельства.
Лем м а 8. Пусть случайные величины
г, г , .р
(если таких Ь нет, то ь полагается равной
считается, что (, ). Тогда случайные величины
тождественно равны. Доказательство проводится по индукции. При ^ “ А перебор всевозможных значений и
показывает, что случайная величина
'(<), А
у, 0 = И ’
<%4 рО) 1 0 ,
Название работы | Автор | Дата защиты |
---|---|---|
Решение задач маршрутизации и путевых разбиений графов методами раскрасок и весовых перераспределений | Замбалаева, Долгор Жамьяновна | 2011 |
Изопериметрические задачи на n-мерном единичном кубе | Безруков, Сергей Леонидович | 1984 |
Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти | Салищев, Сергей Игоревич | 2016 |