Лекция 12. Задача о динамической связности в ненаправленном графе

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

Слайды с лекции

algorithms_1_lecture_151218.pdf

Описание

Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая лесов. Деревья эйлеровых обходов: слияние и разделение.