City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Содержание курса, вводные примеры (в.т.ч. минимальный разрез в графе), Монте Карло, Лас Вегас, и как жить с вероятностью ошибки
Randomized Algorithms

What: Lecture
When: Wednesday, 10 February 2021, 14:10–15:45
Where: НГУ, ауд. 5210, НГУ, новый корпус

Description

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

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

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