#дневниклекций
Вчера начали изучать теорему о превращении любой односторонней перестановки в генератор псевдослучайных чисел. А именно, изучили вот что:
- Общее понятие генератора случайных чисел. Отличия между генераторами истинно случайных чисел и псевдослучайных чисел
- Немного о работе ГИСЧ. Источники случайности в природе и технике и улучшение случайности при помощи экстракторов.
- Виды близости (ансамблей) случайных величин: одинаковое распределение, статистическая близость (несколько эквивалентных свойств), вычислительная неотличимость. Всё это - отношения эквивалентности.
- Определение ГПСЧ. Обсуждение, почему распределение его выходов заведомо далеко от настоящей случайности.
- Формулировка теоремы о преобразовании односторонней перестановки в ГПСЧ. План доказательства в 3 этапа: построение перестановки с трудным битом, построение генератора n->n+1, построение генератора n->p(n). Описание конструкций, неформальное обоснование их корректности.
- Доказательство корректности 3-го этапа. Сначала преобразование генератора n->n+1в генератор n->n+2, потом расширение конструкции на произвольный полином. Обсуждение, почему при растущей длине нельзя использовать соображения транзитивности для вычислительной неотличимости, а нужно явное гибридное рассуждение.