В этой лекции поглубже познакомимся с вероятностным методом доказательства: доказав, что случайно выбранный объект удовлетворяет некоторому свойству с ненулевой вероятностью, можно доказать, что такой объект существует. Однако это ещё не говорит о том, как такой объект эффективно построить. Мы посмотрим, как строить такие объекты рандомизированными алгоритмами и впервые обсуждаем дерандомизацию алгоритмов --- то есть превращение рандомизированного алгоритма в детерминированного, когда это возможно и какой ценой.