Семинар 10. Разное
Суббота, 23 ноября 2019
НГУ, ауд. 2128, НГУ, новый корпус
Сжатие координат: простой пример задачи, идея метода. Реализация: сортировка + бин. поиск или использование std::map.
Алгоритм Евклида для поиска gcd, время работы, реализация. Приведение дробей к нормальному виду. Модифицированный алгоритм Евклида (идея).
Быстрое (бинарное) возведение в степень: идея, пример кода. Применения: обратный по модулю, перемножение матриц. Количество маршрутов и маршрут минимального веса в графе среди всех маршрутов с фиксированным количеством рёбер.
Дерево Фенвика. Интерфейс. Структура: дерево отрезков без правых сыновей, единственность отрезка с заданным концом. Представление в виде массива. Алгоритмы Update и Query. Время работы. Вычисление длины отрезка при помощи битовых операций. Код Update и Query.
Интерфейс множества с ошибками. Bloom filter: одна хеш-функция и несколько. Параметры фильтра N, M, k. Вероятность ошибки (при гипотезе случайного равномерного хеширования). Выбор оптимального k. Количество бит на элемент (M/N) в зависимости от требуемой вероятности ошибки, примеры. Применение: множество опасных URL.
Видео для студентов заочного отделения: https://my.compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4392/