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

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

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

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

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

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

Определение

Учитывать п и Q, два частично упорядоченных набора. Серийный состав п и Q, написано п; Q,[7] п * Q,[2] или же п ⧀ Q,[1]- частично упорядоченное множество, элементами которого являются несвязный союз элементов п и Q. В п; Q, два элемента Икс и у что оба принадлежат п или что оба принадлежат Q имеют такое же отношение порядка, что и в п или же Q соответственно. Однако для каждой пары Икс, у куда Икс принадлежит п и у принадлежит Q, существует дополнительное отношение порядка Икс ≤ у в составе сериала. Состав серии - это ассоциативная операция: можно писать п; Q; р как композицию серий трех порядков, без двусмысленности в том, как их попарно объединить, потому что обе скобки (п; Q); р и п; (Q; р) описать тот же частичный порядок. Однако это не коммутативная операция, потому что переключение ролей п и Q создаст другой частичный порядок, который меняет порядок отношений пар с одним элементом в п и один в Q.[1]

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

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

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

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

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

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

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

В размер заказа частичного порядка п минимальный размер реализатора п, набор линейные расширения из п со свойством, что для каждых двух различных элементов Икс и у из п, Икс ≤ у в п если и только если Икс занимает более раннюю позицию, чем у в каждом линейном продолжении реализатора. Последовательно-параллельные частичные заказы имеют размерность порядка не более двух. Если п и Q есть реализаторы {L1, L2} и {L3, L4} соответственно, то {L1L3, L2L4} - реализатор композиции серии п; Q, и {L1L3, L4L2} - реализатор параллельной композиции п || Q.[2][3] Частичный порядок является последовательно-параллельным тогда и только тогда, когда он имеет реализатор, в котором одна из двух перестановок является тождественной, а другая - отделимая перестановка.

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

  1. ^ а б c d е ж грамм час я Беше, Денис; Де Гроот, Филипп; Реторе, Кристиан (1997), "Полная аксиоматизация для включения последовательно-параллельных частичных порядков", Методы и приложения перезаписи, Конспект лекций по информатике, 1232, Springer-Verlag, стр. 230–240, Дои:10.1007/3-540-62950-5_74.
  2. ^ а б c d е ж грамм час я j k л м п о Меринг, Рольф Х. (1989), "Вычислительно поддающиеся обработке классы упорядоченных множеств", в Соперник, Иван (ред.), Алгоритмы и порядок: Труды Института перспективных исследований НАТО по алгоритмам и порядку, Оттава, Канада, 31 мая - 13 июня 1987 г., Научная серия НАТО C, 255, Springer-Verlag, стр. 105–194, ISBN  978-0-7923-0007-6.
  3. ^ а б c d е ж грамм час Вальдес, Якобо; Тарджан, Роберт Э.; Лоулер, Юджин Л. (1982), "Распознавание серий параллельных орграфов", SIAM Журнал по вычислениям, 11 (2): 298–313, Дои:10.1137/0211023.
  4. ^ а б c Юнг, Х.А. (1978), "Об одном классе множеств и соответствующих графах сопоставимости", Журнал комбинаторной теории, серия B, 24 (2): 125–133, Дои:10.1016/0095-8956(78)90013-8, МИСТЕР  0491356.
  5. ^ Лоулер, Юджин Л. (1978), «Последовательность заданий для минимизации общего взвешенного времени завершения с учетом ограничений приоритета», Анналы дискретной математики, 2: 75–90, Дои:10.1016 / S0167-5060 (08) 70323-6, ISBN  9780720410433, МИСТЕР  0495156.
  6. ^ а б Маннила, Хейкки; Мик, Кристофер (2000), «Глобальные частичные порядки из последовательных данных», Proc. 6-я Международная конференция ACM SIGKDD по открытию знаний и интеллектуальному анализу данных (KDD 2000), стр. 161–168, Дои:10.1145/347090.347122, S2CID  14735932.
  7. ^ а б c d Amer, Paul D .; Шассо, Кристоф; Коннолли, Томас Дж .; Диас, Мишель; Конрад, Филлип (1994), "Транспортные услуги частичного заказа для мультимедиа и других приложений", Транзакции IEEE / ACM в сети, 2 (5): 440–456, Дои:10.1109/90.336326, S2CID  1974607.
  8. ^ а б Choudhary, A.N .; Narahari, B .; Nicol, D.M .; Симха, Р. (1994), «Оптимальное назначение процессора для класса конвейерных вычислений», Транзакции IEEE в параллельных и распределенных системах, 5 (4): 439–445, Дои:10.1109/71.273050.
  9. ^ Фурнас, Джордж В .; Закс, Джефф (1994), «Многодеревья: обогащение и повторное использование иерархической структуры», Proc. Конференция SIGCHI по человеческому фактору в вычислительных системах (CHI '94), стр. 330–336, Дои:10.1145/191666.191778, S2CID  18710118.
  10. ^ Ма, Цзе-Хэн; Спинрад, Джереми (1991), "Транзитивное замыкание для ограниченных классов частичных порядков", Заказ, 8 (2): 175–183, Дои:10.1007 / BF00383402, S2CID  120935610.
  11. ^ Brightwell, Graham R .; Винклер, Питер (1991), "Подсчет линейных расширений", Заказ, 8 (3): 225–242, Дои:10.1007 / BF00383444, S2CID  119697949.
  12. ^ Бут, Келлог С .; Люкер, Джордж С. (1976), "Тестирование свойства последовательных единиц, интервальных графов и планарности графов с использованием алгоритмов PQ-дерева", Журнал компьютерных и системных наук, 13 (3): 335–379, Дои:10.1016 / S0022-0000 (76) 80045-1.