WWW.KONFERENCIYA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Конференции, лекции

 

с/к “Эффективные алгоритмы”

Лекция 9: Линейный вероятностный алгоритм

построения минимального покрывающего дерева

А. Куликов

Computer Science клуб при ПОМИ

http://logic.pdmi.ras.ru/infclub/

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 1 / 27

План лекции

Введение

1

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 2 / 27 План лекции Введение 1 Алгоритм 2 А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 2 / 27 План лекции Введение 1 Алгоритм 2 Время работы в худшем случае 3 А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 2 / План лекции Введение Алгоритм Время работы в худшем случае Время работы в среднем А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 2 / План лекции Введение Алгоритм Время работы в худшем случае Время работы в среднем А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 3 / Минимальное покрывающее деревро Определение А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 4 / Минимальное покрывающее деревро Определение Покрывающим деревом (связного) графа (spanning tree) называется его поддерево на всех вершинах графа.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 4 / Минимальное покрывающее деревро Определение Покрывающим деревом (связного) графа (spanning tree) называется его поддерево на всех вершинах графа.

Задача о минимальном покрывающем дереве (minimum spanning tree problem, MST) заключается в нахождении по данному взвешенному (с вещественными весами на рёбрах) графу покрывающего дерева минимального веса.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 4 / Минимальное покрывающее деревро Определение Покрывающим деревом (связного) графа (spanning tree) называется его поддерево на всех вершинах графа.

Задача о минимальном покрывающем дереве (minimum spanning tree problem, MST) заключается в нахождении по данному взвешенному (с вещественными весами на рёбрах) графу покрывающего дерева минимального веса.

Замечания А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 4 / Минимальное покрывающее деревро Определение Покрывающим деревом (связного) графа (spanning tree) называется его поддерево на всех вершинах графа.

Задача о минимальном покрывающем дереве (minimum spanning tree problem, MST) заключается в нахождении по данному взвешенному (с вещественными весами на рёбрах) графу покрывающего дерева минимального веса.

Замечания Будем считать, что веса всех рёбер различны. При таком предположении у графа есть ровно одно минимальное покрывающее дерево.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 4 / Минимальное покрывающее деревро Определение Покрывающим деревом (связного) графа (spanning tree) называется его поддерево на всех вершинах графа.

Задача о минимальном покрывающем дереве (minimum spanning tree problem, MST) заключается в нахождении по данному взвешенному (с вещественными весами на рёбрах) графу покрывающего дерева минимального веса.

Замечания Будем считать, что веса всех рёбер различны. При таком предположении у графа есть ровно одно минимальное покрывающее дерево.

Для несвязного графа имеет смысл искать минимальный покрывающий лес.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 4 / Общая схема детерминированных алгоритмов Общая схема детерминированных алгоритмов А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 5 / Общая схема детерминированных алгоритмов Общая схема детерминированных алгоритмов На кажом шаге поддерживаем ациклический подграф F графа G, который будем называть промежуточным остовным лесом (intermediate spanning forest).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 5 / Общая схема детерминированных алгоритмов Общая схема детерминированных алгоритмов На кажом шаге поддерживаем ациклический подграф F графа G, который будем называть промежуточным остовным лесом (intermediate spanning forest).

F является подграфом минимального покрывающего дерева, а каждая компонента F является минимальным покрывающим деревом подграфа на вершинах этой компоненты.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 5 / Общая схема детерминированных алгоритмов Общая схема детерминированных алгоритмов На кажом шаге поддерживаем ациклический подграф F графа G, который будем называть промежуточным остовным лесом (intermediate spanning forest).

F является подграфом минимального покрывающего дерева, а каждая компонента F является минимальным покрывающим деревом подграфа на вершинах этой компоненты.

На каждом шаге алгоритм соединяет различные компоненты, добавляя рёбра графа G в F.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 5 / Общая схема детерминированных алгоритмов Общая схема детерминированных алгоритмов На кажом шаге поддерживаем ациклический подграф F графа G, который будем называть промежуточным остовным лесом (intermediate spanning forest).

F является подграфом минимального покрывающего дерева, а каждая компонента F является минимальным покрывающим деревом подграфа на вершинах этой компоненты.

На каждом шаге алгоритм соединяет различные компоненты, добавляя рёбра графа G в F.

Изначально, F содержит |V | деревьев, состоящих из одной А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 5 / Общая схема детерминированных алгоритмов Общая схема детерминированных алгоритмов На кажом шаге поддерживаем ациклический подграф F графа G, который будем называть промежуточным остовным лесом (intermediate spanning forest).



F является подграфом минимального покрывающего дерева, а каждая компонента F является минимальным покрывающим деревом подграфа на вершинах этой компоненты.

На каждом шаге алгоритм соединяет различные компоненты, добавляя рёбра графа G в F.

Изначально, F содержит |V | деревьев, состоящих из одной В конце работы алгоритма F состоит из одного дерева на |V | вершинах, которое и является минимальным покрывающим А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 5 / Безопасные и бесполезные рёбра Определение Рассмотрим граф G и его промежуточный подлес F.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 6 / Безопасные и бесполезные рёбра Определение Рассмотрим граф G и его промежуточный подлес F.

Ребро G называется бесполезным (useless), если оно не является ребром F, в то время как оба его конца принадлежат одной А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 6 / Безопасные и бесполезные рёбра Определение Рассмотрим граф G и его промежуточный подлес F.

Ребро G называется бесполезным (useless), если оно не является ребром F, в то время как оба его конца принадлежат одной Ребро G называется безопасным (safe), если для некоторой компоненты F это ребро является самым лёгким из всех рёбер, соединяющих вершины этой компоненты с оставшимися вершинами.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 6 / Два важных свойства минимального покрывающего дерева Свойство цикла Для любого цикла C самое тяжёлое ребро C не содержится в минимальном покрывающем дереве.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 7 / Два важных свойства минимального покрывающего дерева Свойство цикла Для любого цикла C самое тяжёлое ребро C не содержится в минимальном покрывающем дереве.

Свойство разреза Для любого подмножества вершин X V самое лёгкое ребро между X и V X содержится в минимальном покрывающем дереве.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 7 / Два важных свойства минимального покрывающего дерева Свойство цикла Для любого цикла C самое тяжёлое ребро C не содержится в минимальном покрывающем дереве.

Свойство разреза Для любого подмножества вершин X V самое лёгкое ребро между X и V X содержится в минимальном покрывающем дереве.

Следствие Минимальное покрывающее дерево содержит все безопасные рёбра и не содержит бесполезных рёбер.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 7 / Известные алгоритмы Известные алгоритмы А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 8 / Известные алгоритмы Известные алгоритмы Алгоритм Борувки Добавляем все безопасные рёбра и производим А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 8 / Известные алгоритмы Известные алгоритмы Алгоритм Борувки Добавляем все безопасные рёбра и производим Алгоритм Прима В каждый момент есть ровно одна нетривиальная компонента связности. На каждом шаге добавляем в неё А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 8 / Известные алгоритмы Известные алгоритмы Алгоритм Борувки Добавляем все безопасные рёбра и производим Алгоритм Прима В каждый момент есть ровно одна нетривиальная компонента связности. На каждом шаге добавляем в неё Алгоритм Крускала Перебираем рёбра в порядке возрастания их веса.

Если ребро является безопасным, добавляем его.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 8 / Общая схема алгоритма Борувки Общая схема А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 9 / Общая схема алгоритма Борувки Общая схема Для каждой вершины выберем ребро минимального веса, инцидентное ей.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 9 / Общая схема алгоритма Борувки Общая схема Для каждой вершины выберем ребро минимального веса, инцидентное ей.

Каждую компоненту связности, образованную выбранными рёбрами, стянем в вершину, после чего удалим висячие вершины, петли, а при появлении кратных рёбер оставим только самое А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 9 / Общая схема алгоритма Борувки Общая схема Для каждой вершины выберем ребро минимального веса, инцидентное ей.

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

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 9 / Общая схема алгоритма Борувки Общая схема Для каждой вершины выберем ребро минимального веса, инцидентное ей.

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

Время работы На каждом шаге количество вершин уменьшается хотя бы вдвое, а количество рёбер не увеличивается. Значит, время работы есть O(|E | log |V |).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 9 / F -тяжёлые рёбра Определение Пусть лес F является подграфом графа G.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 10 / F -тяжёлые рёбра Определение Пусть лес F является подграфом графа G.

Через F (x, y ) обозначим путь (если такой есть вообще) из А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 10 / F -тяжёлые рёбра Определение Пусть лес F является подграфом графа G.





Через F (x, y ) обозначим путь (если такой есть вообще) из Через wF (x, y ) обозначим вес тяжелейшего ребра пути F (x, y ) (если такого пути нет, положим wF (x, y ) равным ).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 10 / F -тяжёлые рёбра Определение Пусть лес F является подграфом графа G.

Через F (x, y ) обозначим путь (если такой есть вообще) из Через wF (x, y ) обозначим вес тяжелейшего ребра пути F (x, y ) (если такого пути нет, положим wF (x, y ) равным ).

Ребро (x, y ) называется F -тяжёлым (F -heavy), если w (x, y ) > wF (x, y ), и F -лёгким (F -light) в противном случае.

F -тяжёлые рёбра Определение Пусть лес F является подграфом графа G.

Через F (x, y ) обозначим путь (если такой есть вообще) из Через wF (x, y ) обозначим вес тяжелейшего ребра пути F (x, y ) (если такого пути нет, положим wF (x, y ) равным ).

Ребро (x, y ) называется F -тяжёлым (F -heavy), если w (x, y ) > wF (x, y ), и F -лёгким (F -light) в противном случае.

Замечания F -тяжёлые рёбра Определение Пусть лес F является подграфом графа G.

Через F (x, y ) обозначим путь (если такой есть вообще) из Через wF (x, y ) обозначим вес тяжелейшего ребра пути F (x, y ) (если такого пути нет, положим wF (x, y ) равным ).

Ребро (x, y ) называется F -тяжёлым (F -heavy), если w (x, y ) > wF (x, y ), и F -лёгким (F -light) в противном случае.

Замечания Все рёбра леса F являются F -лёгкими.

F -тяжёлые рёбра Определение Пусть лес F является подграфом графа G.

Через F (x, y ) обозначим путь (если такой есть вообще) из Через wF (x, y ) обозначим вес тяжелейшего ребра пути F (x, y ) (если такого пути нет, положим wF (x, y ) равным ).

Ребро (x, y ) называется F -тяжёлым (F -heavy), если w (x, y ) > wF (x, y ), и F -лёгким (F -light) в противном случае.

Замечания Все рёбра леса F являются F -лёгкими.

Для любого леса F ни одно F -тяжёлое ребро не входит в минимальный остовный лес.

Лёгкие и тяжёлые рёбра Лёгкие и тяжёлые рёбра А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 11 / Лёгкие и тяжёлые рёбра Лёгкие и тяжёлые рёбра Ребро улучшает лес, если либо добавление этого ребра уменьшает количество деревьев в лесу, либо добавление этого ребра с последующим удалением самого тяжёлого ребра единственного образованного цикла ведёт к лесу меньшего веса.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 11 / Лёгкие и тяжёлые рёбра Лёгкие и тяжёлые рёбра Ребро улучшает лес, если либо добавление этого ребра уменьшает количество деревьев в лесу, либо добавление этого ребра с последующим удалением самого тяжёлого ребра единственного образованного цикла ведёт к лесу меньшего веса.

Лёгкие рёбра могут улучшить лес, в то время как тяжёлые — нет.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 11 / Важный факт Факт Существует алгоритм, проверяющий, является ли данный лес минимальным остовным лесом, за линейное время. Модификация данного алгоритма также по лесу F находит за линейное время все F -тяжёлые ребра.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 12 / Важная лемма Лемма Пусть H – подграф G, полученный случайным выбором каждого ребра G с вероятностью p, а F — минимальный остовный лес H. Тогда мат.

ожидание количества F -лёгких рёбер в G не превосходит n/p (где n = |V (G )|).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 13 / Важная лемма Лемма Пусть H – подграф G, полученный случайным выбором каждого ребра G с вероятностью p, а F — минимальный остовный лес H. Тогда мат.

ожидание количества F -лёгких рёбер в G не превосходит n/p (где n = |V (G )|).

Доказательство А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 13 / Важная лемма Лемма Пусть H – подграф G, полученный случайным выбором каждого ребра G с вероятностью p, а F — минимальный остовный лес H. Тогда мат.

ожидание количества F -лёгких рёбер в G не превосходит n/p (где n = |V (G )|).

Доказательство Будем строить граф H и его минимальный остовный лес F одновременно.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 13 / Важная лемма Лемма Пусть H – подграф G, полученный случайным выбором каждого ребра G с вероятностью p, а F — минимальный остовный лес H. Тогда мат.

ожидание количества F -лёгких рёбер в G не превосходит n/p (где n = |V (G )|).

Доказательство Будем строить граф H и его минимальный остовный лес F одновременно.

Изначально H и F пусты.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 13 / Важная лемма Лемма Пусть H – подграф G, полученный случайным выбором каждого ребра G с вероятностью p, а F — минимальный остовный лес H. Тогда мат.

ожидание количества F -лёгких рёбер в G не превосходит n/p (где n = |V (G )|).

Доказательство Будем строить граф H и его минимальный остовный лес F одновременно.

Изначально H и F пусты.

Обрабатываем рёбра в порядке увеличения веса.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 13 / Важная лемма Лемма Пусть H – подграф G, полученный случайным выбором каждого ребра G с вероятностью p, а F — минимальный остовный лес H. Тогда мат.

ожидание количества F -лёгких рёбер в G не превосходит n/p (где n = |V (G )|).

Доказательство Будем строить граф H и его минимальный остовный лес F одновременно.

Изначально H и F пусты.

Обрабатываем рёбра в порядке увеличения веса.

Для ребра e сперва проверим, не лежат ли оба конца e в одной А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 13 / Доказательство (продолжение) Доказательство А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 14 / Доказательство (продолжение) Доказательство Если лежат, то e является F -тяжёлым, поскольку все текущие рёбра F имеют меньший вес.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 14 / Доказательство (продолжение) Доказательство Если лежат, то e является F -тяжёлым, поскольку все текущие рёбра F имеют меньший вес.

С вероятностью p добавим e в H. Если e добавлено в H и является F -лёгким, добавим его в F.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 14 / Доказательство (продолжение) Доказательство Если лежат, то e является F -тяжёлым, поскольку все текущие рёбра F имеют меньший вес.

С вероятностью p добавим e в H. Если e добавлено в H и является F -лёгким, добавим его в F.

Построенный таким образом лес F является минимальным остовным лесом H (в точности такой лес строит алгоритм Крускала).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 14 / Доказательство (продолжение) Доказательство Если лежат, то e является F -тяжёлым, поскольку все текущие рёбра F имеют меньший вес.

С вероятностью p добавим e в H. Если e добавлено в H и является F -лёгким, добавим его в F.

Построенный таким образом лес F является минимальным остовным лесом H (в точности такой лес строит алгоритм Крускала).

Ясно, что любое ребро e, которое было F -тяжёлым на момент добавления, будет F -тяжёлым и дальше, поскольку из F рёбра не удаляются.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 14 / Доказательство (продолжение) Доказательство Если лежат, то e является F -тяжёлым, поскольку все текущие рёбра F имеют меньший вес.

С вероятностью p добавим e в H. Если e добавлено в H и является F -лёгким, добавим его в F.

Построенный таким образом лес F является минимальным остовным лесом H (в точности такой лес строит алгоритм Крускала).

Ясно, что любое ребро e, которое было F -тяжёлым на момент добавления, будет F -тяжёлым и дальше, поскольку из F рёбра не удаляются.

Аналогично каждое F -лёгкое ребро остаётся таковым, поскольку после добавления e добавляются только F -тяжёлые рёбра.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 14 / Доказательство (продолжение) Доказательство Если лежат, то e является F -тяжёлым, поскольку все текущие рёбра F имеют меньший вес.

С вероятностью p добавим e в H. Если e добавлено в H и является F -лёгким, добавим его в F.

Построенный таким образом лес F является минимальным остовным лесом H (в точности такой лес строит алгоритм Крускала).

Ясно, что любое ребро e, которое было F -тяжёлым на момент добавления, будет F -тяжёлым и дальше, поскольку из F рёбра не удаляются.

Аналогично каждое F -лёгкое ребро остаётся таковым, поскольку после добавления e добавляются только F -тяжёлые рёбра.

При обработке ребра мы заранее знаем, является ли оно А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 14 / Доказательство (продолжение) Доказательство А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 15 / Доказательство (продолжение) Доказательство Рассмотрим подбрасывания монетки, соответствующие F -лёгким А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 15 / Доказательство (продолжение) Доказательство Рассмотрим подбрасывания монетки, соответствующие F -лёгким Каждый такой эксперимент с вероятностью p (при выпадении решки) добавляет ребро в F.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 15 / Доказательство (продолжение) Доказательство Рассмотрим подбрасывания монетки, соответствующие F -лёгким Каждый такой эксперимент с вероятностью p (при выпадении решки) добавляет ребро в F.

Размер F в конце не превосходит n 1, поэтому подбрасывания заканчиваются после выпадения не более чем n 1 решек.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 15 / Доказательство (продолжение) Доказательство Рассмотрим подбрасывания монетки, соответствующие F -лёгким Каждый такой эксперимент с вероятностью p (при выпадении решки) добавляет ребро в F.

Размер F в конце не превосходит n 1, поэтому подбрасывания заканчиваются после выпадения не более чем n 1 решек.

Представим, что мы подкидываем монетку до выпадения ровно n решек. Пусть Y есть общее число подбрасываний.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 15 / Доказательство (продолжение) Доказательство Рассмотрим подбрасывания монетки, соответствующие F -лёгким Каждый такой эксперимент с вероятностью p (при выпадении решки) добавляет ребро в F.

Размер F в конце не превосходит n 1, поэтому подбрасывания заканчиваются после выпадения не более чем n 1 решек.

Представим, что мы подкидываем монетку до выпадения ровно n решек. Пусть Y есть общее число подбрасываний.

Ясно, что количество F -лёгких ребер не превосходит Y.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 15 / Доказательство (продолжение) Доказательство Рассмотрим подбрасывания монетки, соответствующие F -лёгким Каждый такой эксперимент с вероятностью p (при выпадении решки) добавляет ребро в F.

Размер F в конце не превосходит n 1, поэтому подбрасывания заканчиваются после выпадения не более чем n 1 решек.

Представим, что мы подкидываем монетку до выпадения ровно n решек. Пусть Y есть общее число подбрасываний.

Ясно, что количество F -лёгких ребер не превосходит Y.

Распределение случайной величины Y — отрицательное биномиальное распределение с параметрами n и p (количество независимых подбрасываний монетки до n выпадений решки, где решка выпадает с вероятностью p).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 15 / Доказательство (продолжение) Доказательство Рассмотрим подбрасывания монетки, соответствующие F -лёгким Каждый такой эксперимент с вероятностью p (при выпадении решки) добавляет ребро в F.

Размер F в конце не превосходит n 1, поэтому подбрасывания заканчиваются после выпадения не более чем n 1 решек.

Представим, что мы подкидываем монетку до выпадения ровно n решек. Пусть Y есть общее число подбрасываний.

Ясно, что количество F -лёгких ребер не превосходит Y.

Распределение случайной величины Y — отрицательное биномиальное распределение с параметрами n и p (количество независимых подбрасываний монетки до n выпадений решки, где решка выпадает с вероятностью p).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 15 / План лекции Введение Алгоритм Время работы в худшем случае Время работы в среднем А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 16 / Алгоритм Randomized-MST(G ) 1 Выход: минимальный остовный лес для G 2 применить три шага алгоритма Борувки к G (количество вершин в полученном графе будет хотя бы в восемь раз меньше);

полученный граф назовем G * 3 в G * выбрать подграф H, включая в H каждое ребро с вероятностью 1/ 4 F = Randomized-MST(H) 5 найти все F -тяжёлые рёбра графа G * и удалить их из G * ;

полученный граф назовём G 6 F = Randomized-MST(G ) 7 return рёбра F и рёбра, стянутые на первом шаге А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 17 / Схема работы А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 18 / Схема работы А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 18 / Схема работы А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 18 / Схема работы А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 18 / Схема работы А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 18 / Схема работы Анализ алгоритма Анализ алгоритма А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 19 / Анализ алгоритма Анализ алгоритма Применение двух шагов Борувки занимает линейное от количества рёбер время.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 19 / Анализ алгоритма Анализ алгоритма Применение двух шагов Борувки занимает линейное от количества рёбер время.

Нахождение всех F -тяжёлых ребер также требует линейного от количества рёбер времени.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 19 / Анализ алгоритма Анализ алгоритма Применение двух шагов Борувки занимает линейное от количества рёбер время.

Нахождение всех F -тяжёлых ребер также требует линейного от количества рёбер времени.

Для оценки времени работы, таким образом, достаточно оценить общее количество рёбер в исходной задаче и всех рекурсивных А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 19 / Анализ алгоритма Анализ алгоритма Применение двух шагов Борувки занимает линейное от количества рёбер время.

Нахождение всех F -тяжёлых ребер также требует линейного от количества рёбер времени.

Для оценки времени работы, таким образом, достаточно оценить общее количество рёбер в исходной задаче и всех рекурсивных Допустим, что у исходного графа n вершин и m рёбер. НУО, А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 19 / Анализ алгоритма Анализ алгоритма Применение двух шагов Борувки занимает линейное от количества рёбер время.

Нахождение всех F -тяжёлых ребер также требует линейного от количества рёбер времени.

Для оценки времени работы, таким образом, достаточно оценить общее количество рёбер в исходной задаче и всех рекурсивных Допустим, что у исходного графа n вершин и m рёбер. НУО, На уровне d дерева работы алгоритма находится не более 2d графов, в каждом из которых не более n/8d вершин.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 19 / Анализ алгоритма Анализ алгоритма Применение двух шагов Борувки занимает линейное от количества рёбер время.

Нахождение всех F -тяжёлых ребер также требует линейного от количества рёбер времени.

Для оценки времени работы, таким образом, достаточно оценить общее количество рёбер в исходной задаче и всех рекурсивных Допустим, что у исходного графа n вершин и m рёбер. НУО, На уровне d дерева работы алгоритма находится не более 2d графов, в каждом из которых не более n/8d вершин.

Значит, общее количество вершин не превосходит А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 19 / План лекции Введение Алгоритм Время работы в худшем случае Время работы в среднем А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 20 / Время работы в худшем случае Теорема Время работы алгоритма Randomized-MST в худшем случае есть А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 21 / Время работы в худшем случае Теорема Время работы алгоритма Randomized-MST в худшем случае есть Доказательство Оценим количество рёбер двумя способами.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 21 / Время работы в худшем случае Теорема Время работы алгоритма Randomized-MST в худшем случае есть Доказательство Оценим количество рёбер двумя способами.

Поскольку кратных рёбер нет, любой граф на уровне d содержит не более (n/8d )2 /2 рёбер. Просуммировав по всем уровням, получим верхнюю оценку O(n2 ).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 21 / Время работы в худшем случае Теорема Время работы алгоритма Randomized-MST в худшем случае есть Доказательство Оценим количество рёбер двумя способами.

Поскольку кратных рёбер нет, любой граф на уровне d содержит не более (n/8d )2 /2 рёбер. Просуммировав по всем уровням, получим верхнюю оценку O(n2 ).

Покажем, что общее количество рёбер двух графов, на которых производятся рекурсивные вызовы, не превосходит количества рёбер исходного графа. Из этого будет следовать, что на каждом уровне не более m рёбер.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 21 / Доказательство (продолжение) Доказательство А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 22 / Доказательство (продолжение) Доказательство Количество рёбер в левой ветке есть |E (H)|.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 22 / Доказательство (продолжение) Доказательство Количество рёбер в левой ветке есть |E (H)|.

Количество рёбер в правой ветке есть А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 22 / План лекции Введение Алгоритм Время работы в худшем случае Время работы в среднем А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 23 / Время работы в среднем Теорема Мат. ожидание времени работы алгоритма Randomized-MST есть O(m).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 24 / Время работы в среднем Теорема Мат. ожидание времени работы алгоритма Randomized-MST есть O(m).

Доказательство А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 24 / Время работы в среднем Теорема Мат. ожидание времени работы алгоритма Randomized-MST есть O(m).

Доказательство Обозначим через T (n, m) мат. ожидание времени работы алгоритма на графе из n вершин и m рёбер.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 24 / Время работы в среднем Теорема Мат. ожидание времени работы алгоритма Randomized-MST есть O(m).

Доказательство Обозначим через T (n, m) мат. ожидание времени работы алгоритма на графе из n вершин и m рёбер.

Применение трёх шагов алгоритма Борувки требует O(n + m) шагов и производит граф G * с не более чем n/8 вершинами.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 24 / Время работы в среднем Теорема Мат. ожидание времени работы алгоритма Randomized-MST есть O(m).

Доказательство Обозначим через T (n, m) мат. ожидание времени работы алгоритма на графе из n вершин и m рёбер.

Применение трёх шагов алгоритма Борувки требует O(n + m) шагов и производит граф G * с не более чем n/8 вершинами.

На следующем шаге за время O(n + m) производится граф H с мат. ожиданием количества рёбер не более m/2.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 24 / Доказательство (продолжение) Доказательство А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 25 / Доказательство (продолжение) Доказательство Нахождение минимального остовного леса F для H требует T (n/8, m/2) шагов в среднем.

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 25 / Доказательство (продолжение) Доказательство Нахождение минимального остовного леса F для H требует T (n/8, m/2) шагов в среднем.

Нахождение всех F -тяжёлых рёбер делается за время O(n + m) и производит граф G с не более чем n/8 вершинами и мат.

ожиданием количества рёбер не более n/4 (по доказанной лемме).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 25 / Доказательство (продолжение) Доказательство Нахождение минимального остовного леса F для H требует T (n/8, m/2) шагов в среднем.

Нахождение всех F -тяжёлых рёбер делается за время O(n + m) и производит граф G с не более чем n/8 вершинами и мат.

ожиданием количества рёбер не более n/4 (по доказанной лемме).

Наождение минимального остовного леса для G требует времени А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 25 / Доказательство (продолжение) Доказательство Нахождение минимального остовного леса F для H требует T (n/8, m/2) шагов в среднем.

Нахождение всех F -тяжёлых рёбер делается за время O(n + m) и производит граф G с не более чем n/8 вершинами и мат.

ожиданием количества рёбер не более n/4 (по доказанной лемме).

Наождение минимального остовного леса для G требует времени откуда следует, что T (n, m) 2c(n + m).

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 25 / Что мы узнали за сегодня?

Что мы узнали за сегодня?

А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 26 / Что мы узнали за сегодня?

Что мы узнали за сегодня?

Существует детерминированный линейный алгоритм проверки, является ли данный лес минимальным остовным лесом данного А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 26 / Что мы узнали за сегодня?

Что мы узнали за сегодня?

Существует детерминированный линейный алгоритм проверки, является ли данный лес минимальным остовным лесом данного Используя этот алгоритм, можно построить вероятностный алгоритм для нахождения минимального остовного леса, который в худшем случае имеет время работы O(min{n2, m log n}), а в А. Куликов (CS клуб при ПОМИ) 9. Мин. покрывающее дерево 26 / А. Куликов (CS клуб при ПОМИ) 9.

Мин. покрывающее дерево 27 /

Похожие работы:

«2 Цель и задачи дисциплины, ее место в учебном процессе Ветеринарное акушерство, гинекология и биотехника размножения сельскохозяйственных животных – это профилирующая клиническая дисциплина, которая освещает вопросы физиологии и патологии размножения животных с учетом целостности организма и его неразрывной связи с условиями окружающей среды. Цель курса - студент-заочник должен получить теоретические знания и практические навыки по акушерству, гинекологии и биотехнике размножения...»

«Е.Н.Романова Г.В.Ксенофонтов: миф о странствующем герое Писать о Гаврииле Васильевиче Ксенофонтове (1888—1938) — ярком ученом, крупном общественном деятеле, в чьей судьбе как в зеркале отразились трагические страницы становления национальной якутской интеллигенции, зарождения якутской этнографической школы, — трудно и ответственно. Ученый-энциклопедист, юрист, крупнейший сибиревед, он прекрасно разбирался в вопросах ориенталистики, разрабатывал собственные курсы по истории религии, занимался...»

«2 Определения, сокращения и аббревиатуры В данной рабочей программе приняты следующие сокращения: ДЗi – домашнее задание i-го порядкового номера; ЗЕ – зачетная единица; ЗФ – заочная форма обучения; ПЗ – практические занятия; ЛК – лекции; ОФ – очная форма обучения; ПК – профессиональная компетенция; Тi – письменный опрос i-го порядкового номера; ТК – текущий контроль. 3 1 Цель освоения дисциплины Целью освоения дисциплины Инженерная гидрология является изучение гидросферы и протекающих в ней...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ ДЕПАРТАМЕНТ НАУЧНО-ТЕХНИЧЕСКОЙ ПОЛИТИКИ И ОБРАЗОВАНИЯ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ АЗОВО-ЧЕРНОМОРСКАЯ ГОСУДАРСТВЕННАЯ АГРОИНЖЕНЕРНАЯ АКАДЕМИЯ Кафедра энергетики С.М.ВОРОНИН НЕТРАДИЦИОННЫЕ И ВОЗОБНОВЛЯЕМЫЕ ИСТОЧНИКИ ЭНЕРГИИ (курс лекций) Зерноград, 2008 УДК 631.371 Воронин С.М. Нетрадиционные и возобновляемые источники энергии: Курс лекций. – Зерноград: ФГОУ ВПО АЧГАА, 2008. -...»

«Федеральное агентство по образованию Федеральное государственное образовательное учреждение высшего профессионального образования Сибирский федеральный университет ТЕОРИЯ И ПРАКТИКА СОЦИОКУЛЬТУРНОГО МЕНЕДЖМЕНТА Курс лекций Укрупненная группа 07000 Культура и искусство Направление 071200.62 Социально-культурная деятельность и народное художественное творчество Факультет искусствоведения и культурологии Кафедра рекламы и социально-культурной деятельности Красноярск 2007 Модуль 1....»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ А.Г. СТОВПОВОЙ УГОЛОВНЫЙ ПРОЦЕСС КУРС ЛЕКЦИЙ Часть 1 2 издание, исправленное и дополненное ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЭКОНОМИКИ И ФИНАНСОВ 2010 ББК 67. С Стовповой А.Г. Уголовный процесс: Курс лекций. Часть 1. 2 изд., испр. и доп.– СПб.: Изд-во СПбГУЭФ, 2010.– 258 с. Второе...»

«Министерство образования и науки РФ ФГАОУ ВПО Казанский (Приволжский) федеральный университет Институт физики В.М. Безменов Картографо-геодезическое обеспечение кадастра Конспект лекций Казань 2014 Безменов В.М Картографо-геодезическое обеспечение кадастра.Конспект лекций / Безменов В.М.; Казанский (Приволжский) федеральный университет. – Казань. – 39 с Аннотация Предлагаемые лекции предназначены для студентов, обучающихся по направлению Геодезия и дистанционное зондирование, Землеустройство и...»

«Русский Гуманитарный Интернет Университет БИБЛИОТЕКА УЧЕБНОЙ И НАУЧНОЙ ЛИТЕРАТУРЫ WWW.I-U.RU Г.С. БАТЫГИН ЛЕКЦИИ ПО МЕТОДОЛОГИИ СОЦИОЛОГИЧЕСКИХ ИССЛЕДОВАНИЙ УЧЕБНИК ДЛЯ СТУДЕНТОВ ГУМАНИТАРНЫХ ВУЗОВ И АСПИРАНТОВ Оглавление Предисловие Глава 1.Три типа социологического дискурса: исторический очерк Глава 2.Язык социологического исследования Глава 3.Концепты и измерения Глава 4.Теория Глава 5.Проектирование выборки Глава 6.Экспериментальный метод в социологии Глава 7.Подготовка научной публикации...»

«НЕЙТРОНЫ ДЛЯ БОЛЬШОЙ НАУКИ К.А. Коноплёв Наконец-то в нашем расписании появилась строчка – лекции профессора Б.П. Константинова. Специальность наша была определена еще на втором курсе физмеха. Мы распределены на кафедру Б.П. Константинова, но прошло уже несколько лет, а своего заведующего кафедрой реально встречаем впервые. Самое первое впечатление совершенно определенное – профессор доволен жизнью, а жизнь его в это время крутая – на лекции он приходит зачастую прямо с вокзала. Главная работа...»

«И.А.Ильиных Экология человека Курс лекций Министерство образования и науки Российской Федерации Федеральное агентство по образованию Горно-Алтайский государственный университет И.А.Ильиных Экология человека Курс лекций Горно-Алтайск 2005 2 Рекомендовано учебно-методическим управлением ГАГУ ББК 20.1 И46 Ильиных И.А. Экология человека: Курс лекций Горно-Алтайск: РИО ГАГУ, 2005. - 136 с. Автор-составитель Ильиных И. А., к.б.н., старший преподаватель кафедры геоэкологии и природопользования...»

«В.И.Назаров ОТСТАВНОЙ ДАРВИНИСТ Жизнь многих советских биологов, оставшихся верными своим научным взглядам после 1948 г., отмечена трагическим единообразием, во всяком случае поначалу. Отстранение от работы, увольнение, если не более суровые кары, поиск заработка, смена профессии и места жительства, долгое и мучительное ожидание перемен к лучшему. Через подобные испытания прошли почти все. Одни не выдержали ожидания и ушли из жизни; другие, которых можно считать счастливчиками, дожили до более...»

«Константин Семёнович Мелихан Рассказы http://fictionbook.ru Содержание Русалка 9 Сравнительная анатомия человека 12 Слово джентльмена (Избранное) 15 Джентльмен ли вы? Тест 15 Записная книжка джентльмена 22 Эпизоды из жизни дам и джентльменов 27 Словарь джентльмена 49 Правдивые истории сивой кобылы 63 Квартирка 63 Тоннель 66 Сила искусства 69 Аппарат профессора Коро 74 Случай с литературоведом 77 Двойной блок 81 Окно 85 Вещий сон Химик Баня Смех сквозь слезы Начинание 01 Вмешательство Ворон и...»

«ИНФОРМАТИКА (семестр 1) Лекция 1. Информатика как наука 1. Понятие информатики как науки и учебной дисциплины. 2. Основные направления информатики. 1. Понятие информатики как науки и учебной дисциплины Предметом курса Информатика и математика являются информационные отношения, складывающиеся в процессе деятельности по сбору, переработке, передаче, хранению и выдаче информации. Изучение данного курса обеспечивает базовую подготовку в сфере информатики, вычислительной техники, математики и...»

«1. Цель дисциплины Особое место в системе профессиональной подготовки кадров сельского хозяйства принадлежит курсу Психология и педагогика, которая вооружает студентов академии системой профессиональных педагогических и психологических знаний, умений и навыков, учит творчески применять их во взаимодействии с коллективом и отдельными сотрудниками. Преподавание курса Психология и педагогика в сельскохозяйственной академии имеет целью обеспечить необходимую психолого-педагогическую подготовку...»

«2 Определения, сокращения и аббревиатуры В данной рабочей программе приняты следующие сокращения: ДЗi – домашнее задание i-го порядкового номера; ЗЕ – зачетная единица; ЛК – лекции; ПЗ – практические занятия; ЛЗ – лабораторные занятия; ПК – профессиональная компетенция; Тi – письменный опрос i-го порядкового номера; ТК – текущий контроль. 3 1 Цель освоения дисциплины Целью освоения дисциплины Пути сообщения, технологические сооружения является ознакомление студентов с принципами технико-...»

«ОСНОВЫ РИТОРИКИ Автор программы А.А. Волков Курс предназначен для студентов филологического факультета, занимающихся по специальности Риторика. В курсе выделяются три раздела: теория риторики, в который входит отчасти история риторики; общая риторика; частная риторика. Первые два разделе преподаются в виде лекций, материал третьего раздела – частная риторика изучается в спец. семинаре, так как предполагает в основном семинарские и практические занятия. Курс Основы риторики со спец. семинаром...»

«Посвящается великому кардиохирургу современности Владимиру Ивановичу Бураковскому учителю, наставнику и другу нашему. с ЛЕКЦИИ ПО СЕРДЕЧНО­ СОСУДИСТОЙ ХИРУРГИИ ПОД РЕДАКЦИЕЙ Л. А. Б О К Е Р И Я ТОМ ПЕРВЫЙ Научно-медицинская БИБЛИ(/.ЕКА г. Тюмень г. инв т Издательство НЦССХ и м. А. Н. Бакулева РАМН Москва УДК 616.12-089 Л е к ц и и по с е р д е ч н о - с о с у д и с т о й хирургии. Под ред. Л. А. Б о к е р и я. В 2-х т. Т. - М. : Издательство Н Ц С С Х и м. А. Н. Бакулева РАМН, 1999. - 3 4 8...»

«Лекция № 8-9. Накопители на жестких дисках Лекция № 8-9. Накопители на жестких дисках Содержание: Что такое жесткий диск Новейшие достижения Принципы работы накопителей на жестких дисках Несколько слов о наглядных сравнениях Форматирование дисков Форматирование низкого уровня Организация разделов на диске Форматирование высокого уровня Основные компоненты накопителей на жестких дисках Рабочий слой диска Оксидный слой Тонкопленочный слой Двойной антиферромагнитный слой Головки чтения/записи...»

«©Хоменко Н.Н. Обзорная лекция по основам ОТСМ-ТРИЗ / http://otsm-triz.org http://jlproj.org Обзорная лекция по основам ОТСМ-ТРИЗ © Николай Николаевич Хоменко (НН) 27 марта 1999г Ингрида Мурашковска (ИМ) Светлана Гин (СГ) Анна Корзун (АК) Распечатка записи и первичное редактирование – С.Соколов От редактора сайта Бывают такие совпадения: эта лекция прочитана Николаем для коллегпедагогов ровно за 12 лет до его ухода, 27 марта. Многие годы этот материал хранился не только в архиве Николая, но и в...»

«Общество с ограниченной ответственностью Химфарммаркет Автономная некоммерческая организация Центр социальных исследований и инноваций Учебно-методический комплекс материалов для проведения семинаров по выработке форм ЧГП в сфере дошкольного, общего и дополнительного образования Москва 2008 1 Учебно-методический комплекс был разработан для участников семинаров по выработке форм частно-государственного партнерства в сфере деминары проводились в Центральном, Северо-западном и Приволжском...»









 
2014 www.konferenciya.seluk.ru - «Бесплатная электронная библиотека - Конференции, лекции»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.