Последовательно-параллельный частичный порядок

редактировать
Последовательно-параллельный частичный порядок, показанный как Диаграмма Хассе.

В теоретико-упорядоченной математике последовательно-параллельный частичный порядок представляет собой частично упорядоченный набор, составленный из более мелких последовательно-параллельных частичные порядки двумя простыми операциями композиции.

Последовательно-параллельные частичные порядки можно охарактеризовать как N-свободные конечные частичные порядки; они имеют размерность не более двух. Они включают слабые порядки и отношения достижимости в направленных деревьях и ориентированных последовательно-параллельных графах. Графики сопоставимости последовательно-параллельных частичных заказов - это кографы.

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

Последовательно-параллельные частичные порядки также называются многодеревьями; однако это имя неоднозначно: multitrees также относятся к частичным порядкам без четырехэлементного алмазного подотряда и к другим структурам, сформированным из нескольких деревьев.

Содержание

  • 1 Определение
  • 2 Запрещенная характеристика подотряда
  • 3 Размерность заказа
  • 4 Связь с теорией графов
  • 5 Вычислительная сложность
  • 6 Приложения
  • 7 См. Также
  • 8 Ссылки

Определение

Рассмотрим P и Q, два частично упорядоченных набора. Серийная композиция P и Q, написанная P; Q, P * Q или P ⧀ Q - это частично упорядоченное множество, элементы которого являются непересекающимся объединением элементов P и Q. В P; Q, два элемента x и y, которые оба принадлежат P или оба принадлежат Q, имеют то же отношение порядка, что и в P или Q соответственно. Однако для каждой пары x, y, где x принадлежит P, а y принадлежит Q, существует дополнительное отношение порядка x ≤ y в композиции ряда. Составление рядов - это ассоциативная операция : можно написать P; Q; R как композиция серии трех порядков, без двусмысленности в том, как их попарно объединить, потому что обе скобки (P; Q); R и P; (Q; R) описывают тот же частичный порядок. Однако это не коммутативная операция, поскольку переключение ролей P и Q приведет к другому частичному порядку, который меняет отношения порядка пар с одним элементом в P и одним в Q.

Параллельная композиция P и Q, написанная P || Q, P + Q или P ⊕ Q определяется аналогичным образом, исходя из несвязного объединения элементов в P и элементов в Q, причем пары элементов, которые оба принадлежат P или оба элемента Q, имеют тот же порядок, что и они. в P или Q соответственно. В P || Q, пара x, y несравнима, если x принадлежит P, а y принадлежит Q. Параллельная композиция одновременно коммутативна и ассоциативна.

Класс последовательно-параллельных частичных порядков - это набор частичных порядков, которые могут быть построенным из одноэлементных частичных заказов с помощью этих двух операций. Эквивалентно, это наименьший набор частичных порядков, который включает одноэлементный частичный порядок и является закрытым при последовательной и параллельной операциях композиции.

A слабый порядок - это полученный последовательный параллельный частичный порядок из последовательности операций композиции, в которой сначала выполняются все параллельные композиции, а затем результаты этих композиций объединяются с использованием только последовательных композиций.

Запрещенная характеристика подотряда

Частичный порядок N с четырьмя элементами a, b, c и d и ровно тремя отношениями порядка a ≤ b ≥ c ≤ d - это пример забор или зигзагообразного набора; его диаграмма Хассе имеет форму заглавной буквы «N». Он не является последовательно-параллельным, потому что невозможно разделить его на серию или параллельную композицию двух меньших частичных порядков. Частичный порядок P называется N-свободным, если в P не существует такого набора из четырех элементов, что ограничение P на эти элементы по порядку изоморфно N. Последовательно-параллельные частичные порядки - это в точности непустые конечные N-свободные частичные порядки.

Из этого немедленно следует (хотя это также можно доказать напрямую), что любое непустое ограничение последовательно-параллельного частичного порядка само по себе является последовательно-параллельным частичным порядком.

Размер заказа

Размер заказа частичного заказа P - это минимальный размер реализатора P, набора линейных расширений P со свойством что для любых двух различных элементов x и y из P, x ≤ y в P тогда и только тогда, когда x имеет более раннюю позицию, чем y в каждом линейном расширении реализатора. Последовательно-параллельные частичные заказы имеют размерность порядка не более двух. Если P и Q имеют реализаторы {L 1, L 2 } и {L 3, L 4 } соответственно, то { L 1L3, L 2L4} - реализатор композиции серии P; Q, а {L 1L3, L 4L2} - реализатор параллельной композиции P || Q. Частичный порядок является последовательно-параллельным тогда и только тогда, когда он имеет реализатор, в котором одна из двух перестановок является тождественной, а другая - разделимой перестановкой.

. Известно, что частичный порядок P имеет порядок размерность два, если и только если существует сопряженный порядок Q на одних и тех же элементах, со свойством, что любые два различных элемента x и y сравнимы ровно в одном из этих двух порядков. В случае последовательных параллельных частичных порядков сопряженный порядок, который сам является последовательным параллельным, может быть получен путем выполнения последовательности операций композиции в том же порядке, что и операции, определяющие P для тех же элементов, но выполняя последовательную композицию для каждой параллельной композиции. в разложении P и наоборот. Более того, хотя частичный порядок может иметь много различных конъюгатов, каждое сопряжение последовательного параллельного частичного порядка должно само быть последовательным параллельным.

Связи с теорией графов

Может быть представлен любой частичный порядок ( обычно более чем одним способом) направленным ациклическим графом, в котором существует путь от x до y, когда x и y являются элементами частичного порядка с x ≤ y. Графы, представляющие последовательно-параллельные частичные порядки таким образом, называются параллельными графами с последовательными вершинами, а их транзитивные редукции (графы , покрывающие отношения частичного порядка) называются минимальные вершинные параллельные графы. Направленные деревья и (двухконцевые) последовательные параллельные графы являются примерами параллельных графов с минимальными вершинами; следовательно, последовательные параллельные частичные порядки могут использоваться для представления отношений достижимости в ориентированных деревьях и последовательных параллельных графах.

граф сопоставимости частичного порядка - это неориентированный граф с вершиной для каждого элемента и неориентированным ребром для каждой пары различных элементов x, y с либо x ≤ y, либо y ≤ x. То есть он формируется из параллельного графа с минимальной последовательностью вершин, забывая об ориентации каждого ребра. Граф сравнимости последовательно-параллельного частичного порядка - это кограф : последовательные и параллельные операции составления частичного порядка приводят к операциям на графе сравнимости, которые образуют несвязное объединение двух подграфов или соединяют два подграфы по всем возможным ребрам; эти две операции являются основными операциями, из которых определяются кографы. И наоборот, каждый кограф является графом сравнимости последовательно-параллельного частичного порядка. Если частичный порядок имеет кограф в качестве графа сопоставимости, то он должен быть последовательно-параллельным частичным порядком, потому что любой другой вид частичного порядка имеет подпорядок N, который будет соответствовать индуцированному четырехвершинному пути в его графе сопоставимости, и такие пути запрещены в кографах.

Вычислительная сложность

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

Если последовательно-параллельный частичный порядок представлен в виде дерева выражений описывая последовательные и параллельные операции композиции, которые его сформировали, то элементы частичного порядка могут быть представлены листьями дерева выражений. Сравнение между любыми двумя элементами может выполняться алгоритмически путем поиска наименьшего общего предка соответствующих двух листьев; если этот предок является параллельной композицией, два элемента несравнимы, в противном случае порядок операндов компоновки ряда определяет порядок элементов. Таким образом, последовательно-параллельный частичный порядок на n элементах может быть представлен в пространстве O (n) с временем O (1) для определения любого значения сравнения.

Это NP-полный, чтобы проверить, для двух данных последовательно-параллельных частичных порядков P и Q, содержит ли P ограничение, изоморфное Q.

Хотя проблема подсчета количества линейных расширений произвольного частичного порядка # P-complete, может быть решена за полиномиальное время для последовательно-параллельных частичных порядков. В частности, если L (P) обозначает количество линейных расширений частичного порядка P, то L (P; Q) = L (P) L (Q) и

L (P | | Q) = (| P | + | Q |)! | P | ! | Q | ! L (P) L (Q), {\ Displaystyle L (P || Q) = {\ frac {(| P | + | Q |)!} {| P |! | Q |!}} L (P) L (Q),}L (P || Q) = \ frac {(| P | + | Q |)!} {| P |! | Q |!} L (P) L (Q),

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

Приложения

Mannila Мик (2000) использует последовательно-параллельные частичные порядки в качестве модели для последовательностей событий в данных временных рядов. Они описывают алгоритмы машинного обучения для вывода моделей этого типа и демонстрируют их эффективность при выводе предварительных условий курса из данных о зачислении студентов и при моделировании шаблонов использования веб-браузера.

Amer et al. (1994) утверждают, что последовательно-параллельные частичные порядки хорошо подходят для моделирования требований последовательности передачи мультимедийных презентаций. Они используют формулу для вычисления числа линейных расширений последовательно-параллельного частичного порядка в качестве основы для анализа алгоритмов передачи мультимедиа.

Choudhary et al. (1994) используют последовательно-параллельные частичные порядки для моделирования зависимостей задач в модели потока данных массивной обработки данных для компьютерного зрения. Они показывают, что, используя последовательно-параллельные заказы для этой проблемы, можно эффективно построить оптимизированное расписание, которое назначает различные задачи различным процессорам системы параллельных вычислений, чтобы оптимизировать пропускную способность системы..

Класс упорядочения, несколько более общий, чем последовательно-параллельные частичные порядки, обеспечивается деревьями PQ, структурами данных, которые применялись в алгоритмах для проверки того, является ли граф планарным. и распознавание интервальных графиков. Узел P дерева PQ допускает все возможные упорядочения своих дочерних элементов, как параллельная композиция частичных порядков, в то время как узел Q требует, чтобы дочерние элементы располагались в фиксированном линейном порядке, как последовательная композиция частичных порядков. Однако, в отличие от последовательно-параллельных частичных порядков, деревья PQ позволяют изменить линейный порядок любого Q-узла.

См. Также

Ссылки

Последняя правка сделана 2021-06-08 01:09:28
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте