В 2022 году Computer Science Center приостановил набор и обучение
Курсы
/
Алгоритмы и структуры данных, часть 1
/
осень 2018
/

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

Суббота, 01 декабря 2018
НГУ, ауд. 2128, НГУ, новый корпус
Список тем / 24 записи
    1.
    Лекция 1. Сложность и модели вычислений
    2.
    1. Вводное занятие
    3.
    Лекция 2. Сортировки
    4.
    2. Разное
    5.
    Лекция 3. Кучи (начало)
    6.
    3. Динамическое программирование
    7.
    Лекция 4. Кучи (продолжение)
    8.
    Семинар 4. Динамическое программирование
    9.
    Лекция 5. Порядковые статистики
    10.
    Семинар 5. Тестирование
    11.
    Лекция 6. Хеширование
    12.
    Семинар 6. Быстрое преобразование Фурье
    13.
    Лекция 7. Деревья поиска
    14.
    Семинар 7. Хеширование, итераторы
    15.
    Лекция 8. Деревья поиска: продолжение
    16.
    Семинар 8. Метод заметающей прямой
    17.
    Лекция 9. Задачи RMQ и LCA
    18.
    Семинар 9. Дерево отрезков
    19.
    Лекция 10. Система непересекающихся множеств
    20.
    Семинар 10. Разное
    21.
    Лекция 11. Структуры данных для геометрического поиска
    22.
    Семинар 11. Дерево поиска с неявным ключом
    23.
    Лекция 12. Задача о динамической связности в ненаправленном графе
    24.
    Семинар 12. Параллельные алгоритмы

Описание

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

Алгоритм Евклида для поиска gcd, время работы, реализация. Приведение дробей к нормальному виду. Модифицированный алгоритм Евклида (идея).

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

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

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