Без темы
<<  Задачи практического содержания при обучении математике Задачи: 1. Освоение общеобразовательных программ учебного плана на уровне, достаточном для продолжения обучения на ступени основного общего образования  >>
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Основные понятия
Основные понятия
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Offline и online
Offline и online
Постановка задачи связности
Постановка задачи связности
Постановка задачи двусвязности
Постановка задачи двусвязности
Усложненная задача
Усложненная задача
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Задачи связности и реберной двусвязности на динамически меняющихся
Цели данной работы
Цели данной работы
Наивное решение
Наивное решение
Существующие решения
Существующие решения
Основные идеи решения
Основные идеи решения
Тестирование алгоритма
Тестирование алгоритма
Результат работы
Результат работы
Сравнение решений задачи о связности
Сравнение решений задачи о связности
Сравнение решений задачи о двусвязности
Сравнение решений задачи о двусвязности
Результат 2
Результат 2
Применение алгоритмов
Применение алгоритмов
Вопросы
Вопросы

Презентация на тему: «Задачи связности и реберной двусвязности на динамически меняющихся графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель кафедры системного программировния Андрей Сергеевич Лопатин Рецензент: Андрей Сергеевич». Автор: Burunduk1. Файл: «Задачи связности и реберной двусвязности на динамически меняющихся графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель кафедры системного программировния Андрей Сергеевич Лопатин Рецензент: Андрей Сергеевич.ppt». Размер zip-архива: 194 КБ.

Задачи связности и реберной двусвязности на динамически меняющихся графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель кафедры системного программировния Андрей Сергеевич Лопатин Рецензент: Андрей Сергеевич

содержание презентации «Задачи связности и реберной двусвязности на динамически меняющихся графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель кафедры системного программировния Андрей Сергеевич Лопатин Рецензент: Андрей Сергеевич.ppt»
СлайдТекст
1 Задачи связности и реберной двусвязности на динамически меняющихся

Задачи связности и реберной двусвязности на динамически меняющихся

графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель кафедры системного программировния Андрей Сергеевич Лопатин Рецензент: Андрей Сергеевич Станкевич

2 Основные понятия

Основные понятия

Неориентированный граф Компоненты связности Компоненты реберной двусвязности – вершины в одной компоненте, если существует два реберно непересекающихся пути между ними. Мосты – ребра, при удалении которых увеличивается количество компонент связности.

3 Задачи связности и реберной двусвязности на динамически меняющихся
4 Задачи связности и реберной двусвязности на динамически меняющихся
5 Задачи связности и реберной двусвязности на динамически меняющихся
6 Задачи связности и реберной двусвязности на динамически меняющихся
7 Offline и online

Offline и online

Offline задача Все запросы к структуре данных известны заранее. Порядок запросов также известен. Online задача Новый запрос становится известен только после того, как на предыдущий запрос дан ответ.

8 Постановка задачи связности

Постановка задачи связности

Неориентированный граф Запрос изменения графа – добавить ребро или удалить ребро Нужно после каждого запроса знать количество компонент связности Входные данные: изначально пустой граф и K запросов изменения графа Выходные данные: K чисел – количество компонент связности после каждого из запросов

9 Постановка задачи двусвязности

Постановка задачи двусвязности

Отличие от предыдущей задачи заключается в том, что теперь нас интересует количество компонент реберной двусвязности и количество мостов

10 Усложненная задача

Усложненная задача

Между запросами изменения графа нужно обрабатывать запросы вида «лежат ли вершины A и B в одной компоненте связности», «лежат ли вершины A и B в одной компоненте реберной двусвязности, сколько между ними мостов»

11 Задачи связности и реберной двусвязности на динамически меняющихся
12 Задачи связности и реберной двусвязности на динамически меняющихся
13 Задачи связности и реберной двусвязности на динамически меняющихся
14 Задачи связности и реберной двусвязности на динамически меняющихся
15 Цели данной работы

Цели данной работы

Обзор существующих решений сформулированных задач. Подробное описание известных мне offline решений обеих задач. Разработка нового, более быстрого, offline решения.

16 Наивное решение

Наивное решение

Для каждого из K моментов времени запустим процедуру поиска компонент связности и реберной двусвязности. Время работы такого алгоритма = O(K2). Алгоритм использует O(K) дополнительной памяти. Обе оценки в худшем случае достигаются.

17 Существующие решения

Существующие решения

Задача о связности решена в 1992-м году Eppstein-ом за время O(N * logN). Задача о двусвязности решена Thorup-ом за время O(N * log3N * loglogN) в 2000-м году. До сих пор это было лучшим достижением.

18 Основные идеи решения

Основные идеи решения

Add + Delete = отрезок времени Метод разделяй и властвуй Можно разбить все моменты времени на две части. Рекурсивно обработать сперва первую половину, затем вторую. Редукция и конденсация. Если количество запросов = k, граф всегда можно уменьшить до размера O(k) вершин

19 Тестирование алгоритма

Тестирование алгоритма

Реализованы 2 более медленных и простых решения. Написаны различные генераторы 1. случайные процесс (центрированный и нет) 2. волны (длинные, короткие) 3. клики 4. циклы 5. …. Сравнение результатов работы решений в «бесконечном» цикле. Подсчет времени работы (реального + счетчики внутри программы).

20 Результат работы

Результат работы

Алгоритм, решающий задачу про двусвязность за время O(KlogK) и использующий O(K) памяти. На Intel Pentium U5400 1.2 GHz за 1 секунду обрабатывается более 2.105 запросов. Подробное описание на русском языке offline решений задачи о связности

21 Сравнение решений задачи о связности

Сравнение решений задачи о связности

Год

Время работы

Автор

1991

O( )

Fredrickson

1993

O( )

Eppstein

1997

O(log5N)

Henzinger, King

2000

O(log3N loglogN)

Thorup

2012

O(KlogK + M)

=)

22 Сравнение решений задачи о двусвязности

Сравнение решений задачи о двусвязности

Задача о связности решена в 1992-м году Eppstein-ом за время O(N * logN). Мое решение работает за то же время. В сравнении с решением Thorup-а, мое решение проще в реализации (у Thorup-а поддерживается MST во взвешенном меняющемся графе, а задача связности сводится к MST).

23 Результат 2

Результат 2

Эффективная реализации предложенного мной алгоритма для задачи о двусвязности. ACM версия задачи о двусвязности (набор тестов в формате, позволяющем автоматическую проверку решений) Аналогичный алгоритм для задачи о связности. Требуемые время и память те же – O(KlogK) и O(K)

24 Применение алгоритмов

Применение алгоритмов

Статистические запросы к динамически меняющимся графам. Пример #1: есть граф пользователей социальной сети, можно для фиксированной группы из K человек узнать “интересные моменты времени”, когда появлялась связность и двусвязность в данной группе. Пример #2: Проверка надежности сетей за счет проверки того, что сеть постоянно двусвязна.

25 Вопросы

Вопросы

Спасибо за внимание

«Задачи связности и реберной двусвязности на динамически меняющихся графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель кафедры системного программировния Андрей Сергеевич Лопатин Рецензент: Андрей Сергеевич»
http://900igr.net/prezentacija/pedagogika/zadachi-svjaznosti-i-rebernoj-dvusvjaznosti-na-dinamicheski-menjajuschikhsja-grafakh-avtor-sergej-kopeliovich-student-545-gruppy-nauchnyj-rukovoditel-starshij-prepodavatel-kafedry-sistemnogo-programmirovnija-andrej-sergeevich-lopatin-retsen-225389.html
cсылка на страницу
Урок

Педагогика

135 тем
Слайды
900igr.net > Презентации по педагогике > Без темы > Задачи связности и реберной двусвязности на динамически меняющихся графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель кафедры системного программировния Андрей Сергеевич Лопатин Рецензент: Андрей Сергеевич