Семинар 10. Разное

Сжатие координат: простой пример задачи, идея метода. Реализация: сортировка + бин. поиск или использование std::map.

Быстрое (бинарное) возведение в степень: идея, пример кода. Применения: обратный по модулю, перемножение матриц. Количество маршрутов и маршрут минимального веса в графе среди всех маршрутов с фиксированным количеством рёбер.

Дерево Фенвика. Интерфейс. Структура: дерево отрезков без правых сыновей, единственность отрезка с заданным концом. Представление в виде массива. Алгоритмы Update и Query. Время работы. Вычисление длины отрезка при помощи битовых операций. Код Update и Query.

Интерфейс множества с ошибками. Bloom filter: одна хеш-функция и несколько. Параметры фильтра N, M, k. Вероятность ошибки (при гипотезе случайного равномерного хеширования). Выбор оптимального k. Количество бит на элемент (M/N) в зависимости от требуемой вероятности ошибки, примеры. Применение: множество опасных URL.