Что: | Лекция |
Когда: | Среда, 17 февраля 2021, 18:10–19:45 |
Где: | НГУ, ауд. 5210, НГУ, новый корпус |
В этой лекции ознакомимся с первыми ключевыми подходами к анализу рандомизированных алгоритмов: с линейностью математического ожидания и вероятностным методом доказательства.
Оба подхода проиллюстрируем на примере построения деревьев двоичного разбиения пространства (BSP-деревьев), приобретших большую известность из-за приложений при быстрой прорисовке 3D-сцен и обнаружении столкновений в компьютерных играх как Doom и Quake. Для быстрой прорисовки сцены важно, чтобы дерево было маленьким. Построение маленького дерева нетривиально. Мы посмотрим простой рандомизированный алгоритм для построения BSP-дерева почти оптимального размера.
Дальше мы перейдём к ещё одному элементарному средству для анализа рандомизированных алгоритмов --- к неравенству Буля. Оно говорит о том, что хотя бы одно из событий \(E_1,\dots,E_n\)
наступит с вероятностью не больше, чем сумма вероятностей индивидуальных событий. Этот элементарное неравенство теории вероятностей встречается в анализе многих алгоритмов.