imported>GalinaKaleeva: Migrated current public revision from wiki.cs.hse.ru

2017-10-18T16:17:35Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

{{Карточка_проекта
|name=Псевдослучайные последовательности и их тестирование
|mentor=Александр Шень
|mentor_login={{URLENCODE:Alexander.shen|WIKI}}
|semester=Осень 2016
|course=2
|summer=on
|number_of_students=2
|categorize=yes
|is_archived=yes
}}

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

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

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

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

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

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

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

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

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

imported>GalinaKaleeva: Migrated current public revision from wiki.cs.hse.ru