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

Презентация:



Advertisements
Похожие презентации
Двусвязность Лекция 14. Связность компонент Граф G называется k-связным (k 1), если не существует набора из k-1 или меньшего числа узлов V` V, такого,
Advertisements

Применение генетических алгоритмов для генерации тестов к олимпиадным задачам по программированию Буздалов М.В., СПбГУ ИТМО.
Декларативное объявление сервисов в динамических компонентных системах Автор: Маврин П.Ю. Научный руководитель: Корнеев Г.А.
Проверка эквивалентности срединной и линейной осей многоугольника Дипломная работа студента 545 группы Подколзина Максима Валериевича Санкт-Петербургский.
1 Сложность, сортировка, поиск Работа по дисциплине «Алгоритмы и структуры данных» Выполнена Садукевич А.В., 271ПИ.
Вычислительная сложность Классы сложности P и NP. Сергей Казаков, аспирант каф. КТ, НИУ ИТМО.
Задача слияния карт памяти (Mind Maps) в Web-системе Comapping Евгений Ларчик, 545 группа Научный руководитель: к. ф.-м. н., доцент Кознов Д.В.
Построение наукометрического индекса, устойчивого к спаму Докладчик : Александр Пироженко.
Алгоритмы сканирования и обхода Лекция 3. Алгоритм сканирования графа Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s,
Зимняя Школа Параллельного Программирования 2011 Проект «Фрагментированное Программирование» : генератор графа фрагментированной программы для алгоритма.
Создание системы хранения и выдачи данных Константинов Александр Сергеевич Научный руководитель: ст.пр.А.С.Лопатин.
Visual Graph: универсальная интерактивная среда визуализации атрибутированных иерархических графовых моделей Золотухин Тимур Александрович НГУ, ФИТ Участник.
Разработка модели родительской селективности для оптимизации запросов в XML базах данных Чернышев Г.А. 545 гр. Научный руководитель Барашев Д. В.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ МОСКОВСКИЙ ФИЗИКО - ТЕХНИЧЕСКИЙ ИНСТИТУТ (государственный университет) Решение задачи восстановления профильной.
1 Генерация контекстных ограничений для баз данных Выполнил: Жолудев В. Научный руководитель: Терехов А.Н. Рецензент: Иванов А.Н.
Алгоритмы на графах Топологическая сортировка поиском в глубину Югов Иван Олегович МОУ Гимназия 10, г. Тверь.
Разбор задачи 2013D «Cave». Презентацию подготовили Белых Евгений и Проскурин Александр.
Алгоритм приближённого joinа на потоках данных Выполнил : Юра Землянский, 445 группа Научный руководитель : Б.А. Новиков СПб, 2011 Санкт-Петербургский.
Национальный исследовательский университет « МЭИ » Кафедра прикладной математики Выпускная работа студента гр. А Бочарова Ивана на тему : « Исследование.
Санкт-Петербургский Государственный Университет Математико-Механический факультет Кафедра системного программирования Применение диаграмм двоичных решений.
Транксрипт:

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

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

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

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

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

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

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

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

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

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

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

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

Сравнение решений задачи о связности ГодВремя работыАвтор 1991O( )Fredrickson 1993O( )Eppstein 1997O(log 5 N)Henzinger, King 2000O(log 3 N loglogN)Thorup 2012O(KlogK + M)=)

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

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

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

Спасибо за внимание Вопросы?