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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

Порядковая размерность частичного порядка P это минимальный размер реализатора P , набора линейных расширений P P со свойством, что для каждых двух различных элементов x ≤ y в x и y из P — тогда и только тогда , когда x имеет более раннюю позицию, чем y, в каждом линейном расширении реализатора. Последовательно-параллельные частичные заказы имеют порядковую размерность не более двух. Если P и Q имеют реализаторы { L ₁ , L ₂ } и { L ₃ , L ₄ } соответственно, то { L ₁ L ₃ , L ₂ L ₄ } является реализатором композиции серии P ; Q , а { L ₁ L ₃ , L ₄ L ₂ } — реализатор параллельной композиции P || Вопрос . Частичный порядок является последовательно-параллельным тогда и только тогда, когда он имеет реализатор, в котором одна из двух перестановок является единицей, а другая — разделимой перестановкой .

Известно, что частичный порядок 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-полной , ее можно решить за полиномиальное время для последовательно-параллельных частичных порядков. В частности, если L ( P ) обозначает количество линейных расширений частичного порядка P , то L ( P ; Q ) = L ( P ) L ( Q ) и

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

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

Приложения

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

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

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

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

См. также

• Последовательные и параллельные цепи