Что: | Лекция |
Когда: | Среда, 10 февраля 2021, 18:10–19:45 |
Где: | НГУ, ауд. 5210, НГУ, новый корпус |
В информатике методы теории вероятностей встречаются в разнейших видах. На первой лекции мы поймём, какой именно кусок большого поля методы теории вероятностей в информатике
мы будем обрабатывать в курсе и что останется за его пределами. Также мы поймём, для чего можно выгодно использовать случайность при построении алгоритмов --- посмотрим парадигмы построения рандомизированных алгоритмов.
Дальше мы увидим первые примеры, которые нам покажут общее свойство многих рандомизированных алгоритмов: они часто простые, порой даже такие простые, что до них сложно додуматься. С другой стороны мы увидим, что простота этих алгоритмов часто обусловлена их нетривиальным анализом: более сложные алгоритмы было бы слишком сложно анализировать.
В последней части лекции мы поговорим о рандомизированных алгоритмах в общем: мы ознакомимся с двумя главными видами рандомизированных алгоритмов: алгоритмы Монте-Карло, алгоритмы Лас-Вегас. Также мы поймём, как и какой ценой можно снизить вероятность ошибки и что малой вероятностью ошибки вполне можно пренебречь на фоне других рисков в жизни.