Лекция 1. Рандомизированные алгоритмы. Как жить с вероятностью ошибки?

Описание: https://compscicenter.ru/

Лекция №1 курса «Рандомизированные алгоритмы», весна 2021 (Новосибирск).

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

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

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

Преподаватель курса: Рене Андреасович ван Беверн, заведующий лабораторией алгоритмики ММФ НГУ, старший преподаватель ММФ НГУ.

Подробное описание занятия: https://nsk.compsciclub.ru/courses/ra...