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

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

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

Последовательно-параллельные частичные порядки можно охарактеризовать как N-свободные конечные частичные порядки; они имеют размерность порядка не более двух. ^{[1] [3]} Они включают слабые порядки и отношения достижимости в ориентированных деревьях и ориентированных последовательно-параллельных графах . ^{[2] [3]} Графы сравнимости последовательно-параллельных частичных порядков являются кографами . ^{[2] [4]}

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

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

Определение

Рассмотрим P и Q , два частично упорядоченных множества . Состав серии P и Q , записанный P ; Q , ^[7] P * Q , ^[2] или P ⧀ Q , ^[1] — частично упорядоченное множество, элементы которого представляют собой непересекающееся объединение элементов 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 создаст другой частичный порядок , который меняет отношения порядка пар с одним элементом в P и одним в Q. ^[1]

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

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

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

Характеристика запрещенного подотряда

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

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

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

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

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

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

Любой частичный порядок может быть представлен (обычно несколькими способами) ориентированным ациклическим графом , в котором существует путь от x до y , если x и y являются элементами частичного порядка с x ≤ y . Графы, которые таким образом представляют последовательно-параллельные частичные порядки, называются графами, параллельными сериями вершин, а их транзитивные редукции (графы накрывающих отношений частичного порядка) называются минимальными параллельными графами серий вершин. ^[3] Ориентированные деревья и (двухтерминальные) последовательные параллельные графы являются примерами минимальных параллельных графов с последовательностями вершин; следовательно, серийно-параллельные частичные порядки можно использовать для представления отношений достижимости в ориентированных деревьях и последовательно-параллельных графах. ^{[2] [3]}

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

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

Характеристика запрещенного подпорядка последовательно-параллельных частичных порядков может использоваться в качестве основы для алгоритма, который проверяет, является ли данное бинарное отношение последовательно-параллельным частичным порядком, за промежуток времени, линейный по числу связанных пар. ^{[2] [3]} В качестве альтернативы, если частичный порядок описывается как порядок достижимости ориентированного ациклического графа , можно проверить, является ли он последовательно-параллельным частичным порядком, и если да, то вычислить его транзитивное замыкание за время, пропорциональное к числу вершин и ребер в транзитивном замыкании; остается открытым, можно ли улучшить время распознавания последовательно-параллельных порядков достижимости, чтобы оно было линейным по размеру входного графа. ^[10]

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

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

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

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

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

Приложения

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

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

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

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

Смотрите также

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

Рекомендации

1. Беше, Денис; Де Гроот, Филипп; Реторе, Кристиан (1997), «Полная аксиоматизация включения последовательно-параллельных частичных порядков», Rewriting Techniques and Applications , Lecture Notes in Computer Science, vol. 1232, Springer-Verlag, стр. 230–240, номер документа : 10.1007/3-540-62950-5_74, ISBN. 978-3-540-62950-4.
2. Мёринг, Рольф Х. (1989), «Вычислительно управляемые классы упорядоченных множеств», в Ривале, Иване (ред.), Алгоритмы и порядок: Труды Института перспективных исследований НАТО по алгоритмам и порядку, Оттава, Канада, май 31-13 июня 1987 г. , Научная серия C НАТО, том. 255, Springer-Verlag, стр. 105–194, ISBN. 978-0-7923-0007-6.
3. Вальдес, Хакобо; Тарьян, Роберт Э .; Лоулер, Юджин Л. (1982), «Распознавание серийных параллельных орграфов», SIAM Journal on Computing , 11 (2): 298–313, doi : 10.1137/0211023.
4. Юнг, HA (1978), «Об одном классе частично упорядоченных множеств и соответствующих графах сравнимости», Journal of Combinatorial Theory, Series B , 24 (2): 125–133, doi : 10.1016/0095-8956(78)90013 -8 , МР  0491356.
5. Лоулер, Юджин Л. (1978), «Упорядочение заданий для минимизации общего взвешенного времени выполнения с учетом ограничений приоритета», Annals of Discrete Mathematics , 2 : 75–90, doi : 10.1016/S0167-5060(08)70323-6, ISBN 9780720410433, МР  0495156.
6. Маннила, Хейкки ; Мик, Кристофер (2000), «Глобальные частичные порядки на основе последовательных данных», Proc. 6-я Международная конференция ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных (KDD 2000) , стр. 161–168, doi : 10.1145/347090.347122 , S2CID  14735932.
7. Амер, Пол Д.; Шассо, Кристоф; Коннолли, Томас Дж.; Диас, Мишель; Конрад, Филлип (1994), «Транспортная служба частичного порядка для мультимедиа и других приложений», IEEE/ACM Transactions on Networking , 2 (5): 440–456, doi : 10.1109/90.336326, S2CID  1974607.
8. Чоудхари, АН; Нарахари, Б.; Никол, DM; Симха, Р. (1994), «Оптимальное назначение процессора для класса конвейерных вычислений», Транзакции IEEE в параллельных и распределенных системах , 5 (4): 439–445, doi : 10.1109/71.273050, S2CID  5588390.
9. Фернас, Джордж В.; Закс, Джефф (1994), "Мультидеревья: обогащение и повторное использование иерархической структуры", Proc. Конференция SIGCHI по человеческому фактору в вычислительных системах (CHI '94) , стр. 330–336, doi : 10.1145/191666.191778 , S2CID  18710118.
10. Ма, Цзе-Хенг; Спинрад, Джереми (1991), «Транзитивное замыкание для ограниченных классов частичных порядков», Order , 8 (2): 175–183, doi : 10.1007/BF00383402, S2CID  120935610.
11. Брайтуэлл, Грэм Р.; Винклер, Питер (1991), «Подсчет линейных расширений», Order , 8 (3): 225–242, doi : 10.1007/BF00383444, S2CID  119697949.
12. Бут, Келлог С.; Люкер, Джордж С. (1976), «Проверка свойства последовательных единиц, интервальных графов и планарности графа с использованием алгоритмов PQ-дерева», Journal of Computer and System Sciences , 13 (3): 335–379, doi : 10.1016/ С0022-0000(76)80045-1.