If you're seeing this message, it means we're having trouble loading external resources on our website.

Если вы используете веб-фильтр, пожалуйста, убедитесь, что домены *.kastatic.org и *.kasandbox.org разблокированы.

Основное содержание
Текущее время:0:00Общая продолжительность:6:41

Транскрипция к видео

в реальном мире мы часто сталкиваемся со случайно порядком действительно случайно числа можно получать из хаотичных процессов из так называемого шума слушая такой шум и дело и выборки из него можно получать числа например слушая телевизионный шум можно получить истина случайную последовательность эту случайную последовательность можно представить в виде пути где через каждый шаг в зависимости от числа меняется направление так называемое случайное блуждание обратите внимание на полное отсутствие закономерностей в каждой точке пути следующий шаг абсолютно непредсказуем случайные процессы являются недетерминированными их невозможно детерминировать то есть предсказать а вот автоматы наоборот ветер минирован и и их действия можно предсказать и воспроизвести в 1946 году джон фон нейман помогал проводить расчеты для военных в частности участвовал в разработке водородной бомбы при помощи компьютера eniac он аппроксимировать процессы происходящие при расщеплении ядра для этого ему требовались длинные последовательности случайных чисел которые можно было бы запомнить и повторить в компьютере eniac было слишком мало памяти и хранить готовые последовательности не получалось и фон нейман придумал алгоритм позволившая генерировать случайность при помощи автомата во-первых выберем некое действительно случайное число и назовем его сид от английского слова сид или начальное значение его можно взять из шума или из текущего времени в миллисекундах сид используется в качестве входных данных для простого действия например возведем число в квадрат и из результата возьмем средние цифры повторяем и то же действие для нового числа и так далее столько раз сколько нужно этот метод назвали серединных квадратов он был первым из огромного множества генераторов псевдослучайных чисел вся последовательность зависит только от начального значения один и тот же сид означает ту же последовательность и так в чем же разница между случайными и псевдо случайными последовательностями изобразим каждую последовательность в виде случайного блуждания разницы не видно но давайте ускорим процесс псевдослучайная последовательность когда-нибудь обязательно начнет повторяться это произойдет когда некое число встретиться и используется в качестве начального значения во второй раз и цикл пойдет заново длина такого цикла до его повторения называется периодом период строго ограничен размером сид например если сид двузначное то алгоритм выдаст максимум 100 чисел после чего какое-то начальное значение обязательно встретится повторно из трехзначного сид нельзя получить больше 1000 чисел дальше алгоритму зациклиться а из 4-значного сид нельзя получить последовательность больше чем 10000 чисел но если взять достаточно большое начальное значение то алгоритм может выдать триллионы триллионов знаков до того как возникнет повтор и важно помнить ключевое отличие при псевдо случайности генерации чисел многие последовательности не выпадут никогда например если или сгенерирует действительно случайную последовательность из 20 алфавитных сдвигов это равносильно вытаскивание случайного листа из стопки со всеми возможными комбинациями в этой стопке 26 в 20 степени листов это астрономическое число если встать у основания такой стопки и включить фонарь человек наверху стопки увидят свет только через двести миллионов лет а если б или сгенерировала псевдослучайная последовательность из 20-ти чисел при помощи 4-значного начального значения количество вариантов было бы ограничено всего десятью тысячами различных начальных сид и она может сгенерировать лишь 10 тысяч последовательностей и это ничтожно малая доля от всех возможных последовательностей используя вместо случайных чисел псевдослучайные мы уменьшаем пространство ключей до гораздо меньшего пространства начального значения и чтобы псевдослучайная последовательность была неотличима от действительно случайный нужно чтобы компьютер не смог перебрать все возможные значения и не смог найти совпадение и тут всплывает очень важное различие между тем что возможно сделать теоретически и тем что возможно сделать за разумное время такая же логика у нас появляется при покупке велосипедного замка мы знаем что угонщик может перебрать все возможные комбинации и замок когда-нибудь откроется но это может занять несколько дней для псевдослучайных генераторов защита возрастает с длиной начального значения если какой-нибудь мощный компьютер будет перебирать все возможные сид сотни лет то мы можем положиться на достаточно секретный шифр вместо совершенно секретного но компьютеры становится быстрее и размер начального значения должен увеличиваться соответственно псевдослучайный алгоритмы избавляет элис и баба от необходимости передавать друг другу длинные случайные цепочки вместо этого они могут обменяться достаточно коротким случайным начальным значением и получить одну и ту же почти случайную последовательность но что случится если они не могут встретиться и обменяться начальном значения об этом мы поговорим в следующих видео спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них