Рубежный контроль 2 Ярматов. Я 2. Итоговый контроль по дисциплине Проектная деятельность
 Скачать 36.15 Kb.
|
Итоговый контроль по дисциплине «Проектная деятельность»
Москва 2023 Получение случайных последовательностейИстинно случайная последовательность может быть получена только с помощью истинно случайного процесса, и поэтому, в частности, не может быть выработана с помощью никакой математической формулы, так как знание формулы и достаточного числа начальных значений (т.е. знаков, уже полученных с помощью данной формулы) позволит с уверенностью предсказать следующее значение. Однако существуют формулы, дающие достаточно длинные числовые последовательности, которые удовлетворяют многим критериям случайности, пока они не начнут повторяться; такие последовательности называются "псевдослучайными". Так где же взять случайную последовательность?Возможно, у вас уже появилась мысль, что истинно случайную последовательность программным путем не получить. Это не так. Существует, по крайней мере, один способ, позволяющий получить истинно случайную последовательность байтов. Основная идея этого способа заключается в том, чтобы привлечь к процессу выработки случайной последовательности самого пользователя. Пользователь работает с компьютером. Он двигает мышь, нажимает клавиши на клавиатуре. Попробуем взять в качестве элементов случайной последовательности интервалы между последовательными нажатиями клавиш. Какая получится последовательность? Случайная? Несомненно. Равномерно распределенная? Вряд ли. Какое у нее будет распределение? Трудно сказать. Если пользователь набирает текст, получится одно распределение, если работает с Norton Commander - другое, если играет в Tetris - третье. Будут ли соседние элементы последовательности зависеть друг от друга? Скорее всего, да. Кажется, что никаких преимуществ по сравнению с предыдущим методом нет. Однако в отличие от предыдущего метода в данном случае все перечисленные проблемы можно решить. Для начала посмотрим, можно ли написать программу генерации ключа так, чтобы распределение исходной случайной величины было известно. Исходная случайная величина у нас - это продолжительность интервала между нажатиями клавиш. В разных ситуациях эта величина распределена по-разному. Выберем ситуацию, когда распределение этой случайной величины легко посчитать. Пусть, например, пользователь в процессе выработки ключа играет в Tetris. При игре в Tetris частота нажатий на клавиши мало зависит от пользователя, другими словами, все пользователи, играя в Tetris, нажимают на клавиши примерно одинаково часто (конечно, кроме пользователей, которые играют в Tetris первый раз в жизни). Распределение интервалов времени между последовательными нажатиями на клавиши несложно рассчитать. Для этого нужно прежде всего написать резидентную программу, которая перехватывала бы прерывание 16h, отвечающее за работу с клавиатурой, при каждом вызове прерывания получала бы текущее значение таймера, сравнивала его с предыдущим полученным значением, вычисляла разность и записывала полученное число в файл4). Затем нужно запустить эту программу и, пока она работает, поиграть некоторое время в Tetris. Проведите этот эксперимент в качестве упражнения. Посмотрите на рисунок. Распределение нашей случайной величины будет выглядеть примерно так:  Распределение явно неравномерное, но это и не важно. Важно то, что распределение случайной величины при разных испытаниях примерно одинаково. Преобразовать это распределение в равномерное совсем несложно. Остается решить последнюю проблему. Таймер компьютера тикает с частотой 18,2 раза в секунду, т.е. один тик занимает примерно 55 миллисекунд. Когда пользователь нажимает клавиши подряд, не думая, или просто держит клавишу нажатой, интервалы между последовательными нажатиями составляют 100-200 миллисекунд. Получается, что первый пик на приведенном графике на самом деле выглядит примерно так, как показано на рисунке.  А это нехорошо - в полученной случайной последовательности числа 2 и 3 будут встречаться гораздо чаще, чем любые другие. После преобразования к равномерному распределению значения этих часто встречающихся чисел изменятся, но сам факт наличия двух-трех значений, на которые приходится львиная доля наблюдений, останется. Получается, что нам мешает дискретность таймера персонального компьютера. Как от нее избавиться? Подумайте сами. Один из возможных ответов вы найдете в конце главы. |
