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

Построение дерева двоичного разбиения пространства, вероятностный метод, неравенство Буля
Randomized Algorithms

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

Description

В этой лекции ознакомимся с первыми ключевыми подходами к анализу рандомизированных алгоритмов: с линейностью математического ожидания и вероятностным методом доказательства.

Оба подхода проиллюстрируем на примере построения деревьев двоичного разбиения пространства (BSP-деревьев), приобретших большую известность из-за приложений при быстрой прорисовке 3D-сцен и обнаружении столкновений в компьютерных играх как Doom и Quake. Для быстрой прорисовки сцены важно, чтобы дерево было маленьким. Построение маленького дерева нетривиально. Мы посмотрим простой рандомизированный алгоритм для построения BSP-дерева почти оптимального размера.

Дальше мы перейдём к ещё одному элементарному средству для анализа рандомизированных алгоритмов --- к неравенству Буля. Оно говорит о том, что хотя бы одно из событий \(E_1,\dots,E_n\) наступит с вероятностью не больше, чем сумма вероятностей индивидуальных событий. Этот элементарное неравенство теории вероятностей встречается в анализе многих алгоритмов.