В информатике методы теории вероятностей встречаются в разнейших видах. На первой лекции мы поймём, какой именно кусок большого поля методы теории вероятностей в информатике мы будем обрабатывать в курсе и что останется за его пределами. Также мы поймём, для чего можно выгодно использовать случайность при построении алгоритмов --- посмотрим парадигмы построения рандомизированных алгоритмов.

Дальше мы увидим первые примеры, которые нам покажут общее свойство многих рандомизированных алгоритмов: они часто простые, порой даже такие простые, что до них сложно додуматься. С другой стороны мы увидим, что простота этих алгоритмов часто обусловлена их нетривиальным анализом: более сложные алгоритмы было бы слишком сложно анализировать.

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