Псевдослучайные последовательности и их тестирование (проект)

Ментор	Александр Шень
Учебный семестр	Осень 2016
Учебный курс	2-й курс
Проект можно развивать на летней практике
Максимальное количество студентов, выбравших проект: 2

Что это за проект?

Для статистических и алгоритмических целей бывают нужно как-то имитировать бросание честной монеты (получение случайных битов). Возникает естественный вопрос - что это значит, как это сделать, как проверять качество. На философском уровне можно спросить, как вообще какой-то результат бросания монеты (последовательность n нулей и единиц) может свидетельствовать о нечестности монеты, а другой - не свидетельствовать, если все результаты равновероятны. С практической точки зрения такие методы имитации делятся на "физические", когда получаемые биты зависят от результатов какого-то физического процесса, и "программнные", когда применяется какой-то алгоритм, который даёт "похожую на случайную" последовательность битов. Физические методы, как правило, состоят из двух частей - получения "сравнительно случайных битов" с помощью какого-то процесса и их преобразование для "улучшения случайности". "Программные" методы (см. Искусство программирования Кнута) минимизируют первую часть (обычно это некоторый фиксированный seed, начальное значение), всё дальнейшее получается алгоритмически. Есть традиционные тесты (Diehard Marsaglia, NIST,...) и разные их реализации, а также более современные методы и идеи (экстракторы случайности с одним и несколькими входами, псевдослучайные генераторы по Блюму-Микэли)

Чему вы научитесь?

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

Какие начальные требования?

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

Какие будут использоваться технологии?

-

Темы вводных занятий

Мог бы рассказать подробнее о ситуации и возможных направлениях деятельности

Направления развития

Изготовление физических устройств для получения достаточно быстрого потока случайных битов

Критерии оценки

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

Ориентировочное расписание занятий

В Москве с 10 октября до 8 января, далее по скайпу/e-mail