Семинар 10. Разное (Алгоритмы и структуры данных, часть 1)

Сжатие координат: простой пример задачи, идея метода. Реализация: сортировка + бин. поиск или использование std::map. Алгоритм Евклида для поиска gcd, время работы, реализация. Приведение дробей к нормальному виду. Модифицированный алгоритм Евклида (идея). Быстрое (бинарное) возведение в степень: идея, пример кода. Применения: обратный по модулю, перемножение матриц. Количество маршрутов и маршрут минимального веса в графе среди всех маршрутов с фиксированным количеством рёбер. Дерево Фенвика. Интерфейс. Структура: дерево отрезков без правых сыновей, единственность отрезка с заданным концом. Представление в виде массива. Алгоритмы Update и Query. Время работы. Вычисление длины отрезка при помощи битовых операций. Код Update и Query. Интерфейс множества с ошибками. Bloom filter: одна хеш-функция и несколько. Параметры фильтра N, M, k. Вероятность ошибки (при гипотезе случайного равномерного хеширования). Выбор оптимального k. Количество бит на элемент (M/N) в зависимости от требуемой вероятности ошибки, примеры. Применение: множество опасных URL. Семинар №10 в курсе "Алгоритмы и структуры данных, часть 1", осень 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница семинара на сайте CS центра:
Все видео курса по порядку:    • Алгоритмы и структуры данных, часть 1...