Вероятностные методы в вычислениях. Лекция 2

Независимые события и случайные величины, неравенство Чебышева, закон больших чисел для попарно независимых случайных величин, закон больших чисел для t-независимых случайных величин. Оценки Чернова-Хоефдинга. Маленькие k-независимые множества и их применение для поиска набора, выполняющего 7/8 дизъюнктов. Конструкция 2-независимого множества.

Страница лекции на сайте Computer Science клуба