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

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

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

содержание презентации «Задачи связности и реберной двусвязности на динамически меняющихся графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель кафедры системного программировния Андрей Сергеевич Лопатин Рецензент: Андрей Сергеевич.ppt»
Сл Текст Сл Текст
1Задачи связности и реберной 17за время O(N * logN). Задача о
двусвязности на динамически меняющихся двусвязности решена Thorup-ом за время O(N
графах Автор: Сергей Копелиович, студент * log3N * loglogN) в 2000-м году. До сих
545 группы Научный руководитель: старший пор это было лучшим достижением.
преподаватель кафедры системного 18Основные идеи решения. Add + Delete =
программировния Андрей Сергеевич Лопатин отрезок времени Метод разделяй и властвуй
Рецензент: Андрей Сергеевич Станкевич. Можно разбить все моменты времени на две
2Основные понятия. Неориентированный части. Рекурсивно обработать сперва первую
граф Компоненты связности Компоненты половину, затем вторую. Редукция и
реберной двусвязности – вершины в одной конденсация. Если количество запросов = k,
компоненте, если существует два реберно граф всегда можно уменьшить до размера
непересекающихся пути между ними. Мосты – O(k) вершин.
ребра, при удалении которых увеличивается 19Тестирование алгоритма. Реализованы 2
количество компонент связности. более медленных и простых решения.
3 Написаны различные генераторы 1. случайные
4 процесс (центрированный и нет) 2. волны
5 (длинные, короткие) 3. клики 4. циклы 5.
6 …. Сравнение результатов работы решений в
7Offline и online. Offline задача Все «бесконечном» цикле. Подсчет времени
запросы к структуре данных известны работы (реального + счетчики внутри
заранее. Порядок запросов также известен. программы).
Online задача Новый запрос становится 20Результат работы. Алгоритм, решающий
известен только после того, как на задачу про двусвязность за время O(KlogK)
предыдущий запрос дан ответ. и использующий O(K) памяти. На Intel
8Постановка задачи связности. Pentium U5400 1.2 GHz за 1 секунду
Неориентированный граф Запрос изменения обрабатывается более 2.105 запросов.
графа – добавить ребро или удалить ребро Подробное описание на русском языке
Нужно после каждого запроса знать offline решений задачи о связности.
количество компонент связности Входные 21Сравнение решений задачи о связности.
данные: изначально пустой граф и K Год. Время работы. Автор. 1991. O( ).
запросов изменения графа Выходные данные: Fredrickson. 1993. O( ). Eppstein. 1997.
K чисел – количество компонент связности O(log5N). Henzinger, King. 2000. O(log3N
после каждого из запросов. loglogN). Thorup. 2012. O(KlogK + M). =).
9Постановка задачи двусвязности. 22Сравнение решений задачи о
Отличие от предыдущей задачи заключается в двусвязности. Задача о связности решена в
том, что теперь нас интересует количество 1992-м году Eppstein-ом за время O(N *
компонент реберной двусвязности и logN). Мое решение работает за то же
количество мостов. время. В сравнении с решением Thorup-а,
10Усложненная задача. Между запросами мое решение проще в реализации (у Thorup-а
изменения графа нужно обрабатывать запросы поддерживается MST во взвешенном
вида «лежат ли вершины A и B в одной меняющемся графе, а задача связности
компоненте связности», «лежат ли вершины A сводится к MST).
и B в одной компоненте реберной 23Результат 2. Эффективная реализации
двусвязности, сколько между ними мостов». предложенного мной алгоритма для задачи о
11 двусвязности. ACM версия задачи о
12 двусвязности (набор тестов в формате,
13 позволяющем автоматическую проверку
14 решений) Аналогичный алгоритм для задачи о
15Цели данной работы. Обзор существующих связности. Требуемые время и память те же
решений сформулированных задач. Подробное – O(KlogK) и O(K).
описание известных мне offline решений 24Применение алгоритмов. Статистические
обеих задач. Разработка нового, более запросы к динамически меняющимся графам.
быстрого, offline решения. Пример #1: есть граф пользователей
16Наивное решение. Для каждого из K социальной сети, можно для фиксированной
моментов времени запустим процедуру поиска группы из K человек узнать “интересные
компонент связности и реберной моменты времени”, когда появлялась
двусвязности. Время работы такого связность и двусвязность в данной группе.
алгоритма = O(K2). Алгоритм использует Пример #2: Проверка надежности сетей за
O(K) дополнительной памяти. Обе оценки в счет проверки того, что сеть постоянно
худшем случае достигаются. двусвязна.
17Существующие решения. Задача о 25Вопросы? Спасибо за внимание.
связности решена в 1992-м году Eppstein-ом
Задачи связности и реберной двусвязности на динамически меняющихся графах Автор: Сергей Копелиович, студент 545 группы Научный руководитель: старший преподаватель кафедры системного программировния Андрей Сергеевич Лопатин Рецензент: Андрей Сергеевич.ppt
http://900igr.net/kartinka/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сылка на страницу

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

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

«Научные работы» - Хотя резкого уменьшения активности не произошло! Школа «Юный Медик ВолГМУ». Лидеры финансирования по хоздоговорам. Требование к вузу - ? 15 в год. Подготовка научных и научно-педагогических кадров в волгму. ЛИДЕРЫ: кафедра клинической фармакологии; кафедра фармакологии; философии, биоэтики и права; Государственные научные гранты волгоградской области.

«Научный проект» - Минобрнауки России – государственный заказчик - координатор. Цель: Цель: привлечение школьников к научной и научно-технической деятельности. Научные и научно-педагогические кадры. Структура программы. Ожидаемые результаты: Блок № 2 «Привлечение молодежи в сферу науки, образования и высоких технологий».

«Студенты» - Перспективность выбранной специальности. Куда студенты идут со своими проблемами? Однако число студентов, отдохнувших в санатории возросло в два с половиной раза. Психологический климат в университете. Материальная помощь от университета. Материальное положение. Почаще проводить различные мероприятия. 13.

«Портфолио студента» - Проекты. ПОРТФОЛИО как форма организации самостоятельной работы студентов. Домашние работы. Краткие заметки, связанные с ходом выполнения письменных работ. Что будет входить в портфолио? (продолжение). Как будет выглядеть портфолио? Каким образом будет происходить процесс оценки портфолио? Классификация портфолио по характеру и структуре материалов:

«Куратор студент» - Нормы поведения в семье. Обязанности куратора: Староста и помощник старосты. Важность куратора. Рост успеваемости. Участие в жизни колледжа: Петрозаводский медицинский колледж. «Здравствуй, племя младое, незнакомое!». Мария Лангинен победительница профессионального конкурса «Я – наследница Флоренс».

«Портфолио преподавателя» - Вопросы к аттестуемому могут касаться только представленных в портфолио материалов. Методический портфолио педагога. Требования к оформлению портфолио. Оценка методического портфолио преподавателя. Основные разделы портфолио. Введение. Резюме. С содержанием портфолио должны ознакомится заранее не менее двух членов экспертного совета.

Без темы

2329 презентаций
Урок

Педагогика

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