Использование случайных битов — один из способов усиления возможностей компьютеров. Вероятностные алгоритмы позволяют решать некоторые задачи теоретической информатики, для которых не работают детерминированные алгоритмы. Самый интересный вопрос — это насколько использование случайностей сокращает время работы алгоритма? Частично на этот вопрос уже можно ответить: при некоторых предположениях истинную случайность можно подменить фальшивой и детерминированно смоделировать любой вероятностный алгоритм с незначительной потерей во времени работы. Проверка этих предположений будет, по всей видимости, одной из центральных тем теоретической информатики XXI века.
Лекцию читает старший научный сотрудник Вычислительного центра им. А.А. Дородницына РАН, доцент кафедры математических основ управления МФТИ, кандидат физико-математических наук Михаил Вялый.
Представим, что у нас есть два калькулятора. Один обычный, а у второго есть дополнительная кнопка, которая при нажатии выдает дополнительный бит. Попробуем ответить на вопрос, полезна ли будет такая функция?
Такая постановка, конечно, слишком общая. Постараемся уточнить ее с точки зрения теоретической информатики. Для этого сначала введем понятие алгоритма. Алгоритм — настолько точно определенная инструкция, что она может быть исполнена механически. Основное свойство детерминированных алгоритмов заключается в том, что каждое следующее состояние однозначно определяется текущим состоянием. Вероятностные алгоритмы отличаются тем, что в любой момент они могут определить значение случайного бита (подбросить монету), который с равной вероятностью будет равен 0 или 1. В процессе исполнения вероятностного алгоритма это может происходить неоднократно, и разные подбрасывания будут независимы.
Читать полностью »
