8. Метод заметающей прямой
Алгоритмы и структуры данных, часть 1


Что: Семинар
Когда: Суббота, 11 ноября 2017, 16:20–18:00
Где: НГУ, ауд. 2128

Описание

Задача нахождения пары пересекающихся отрезков. Тривиальное решение. Метод движущейся прямой. Состояние прямой = движущиеся точки. Хранение состояния в дереве поиска. Зависимость сравнения от времени, сохранение порядка. Схема алгоритма. Доказательство корректности, инвариант. Время работы. Случай вертикальных отрезков (кратко). Нахождение всех точек пересечения (кратко).

Пример комбинаторной динамики: количество последовательностей операций, разбивающих строку на символы.

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