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

Семинар 7. Хеширование, итераторы

Суббота, 27 октября 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. Параллельные алгоритмы

Описание

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

Концепция итератора и ручки(handle) для элементов в контейнере. Инвалидация ручек. Ручка = указатель в связном списке и дереве. Сложность задания хороших ручек в массиве.

Решение задачи о максимуме в скользящем окне при помощи бинарной кучи. Номер во входном массиве как ручка. Инкапсулированный вариант бинарной кучи: нумерация добавляемых элементов (выдача ID) и использование ID в качестве ручек. Поддержка двустороннего соответствия между ID и номерами в куче.