Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

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

Что: Лекция
Когда: Среда, 10 февраля 2021, 14:10–15:45
Где: НГУ, ауд. 5210, НГУ, новый корпус

Описание

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

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

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