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

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

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

Послідовно-паралельні часткові порядки можна описати як вільні від N-порядку скінченні часткові порядки. Вони мають ^[en] максимум два. Ці порядки включають ^[en] і відношення досяжності в орієнтованих деревах і орієнтованих паралельно-послідовних графах. Графи порівнянності послідовно-паралельних часткових порядків — це кографи.

Послідовно-паралельні часткові порядки застосовують у теорії розкладів, машинному навчанні послідовностей подій у часових рядах даних, послідовності передачі мультимедійних даних і максимізації пропускної спроможності в потоках даних.

Послідовно-паралельні часткові порядки називають також мультидеревами. Однак ця назва двозначна — ^[en] також називають часткові порядки без чотириелементних підпорядків («алмазів»), а також інші структури, утворені з кількох дерев.

Визначення

Нехай 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 відповідно. Якщо ж елемент x належить P, а елемент y належить Q, то елементи x та y непорівнянні. Паралельне з'єднання асоціативне і комутативне.

Клас послідовно-паралельних часткових порядків є множиною часткових порядків, яку можна побудувати з одноелементних часткових порядків з використанням цих двох операцій. Еквівалентно, клас є найменшою множиною часткових порядків, яка включає одноелементний частковий порядок і яка замкнена за операціями послідовного і паралельного з'єднання.

^[en] — це послідовно-паралельний частковий порядок, отриманий внаслідок послідовності операцій з'єднання, в якому спочатку проведено всі операції паралельного з'єднання, а потім результати цих операцій комбіновано з тільки послідовними операціями.

Опис забороненими підпорядками

Частковий порядок N з чотирма елементами a, b, c і d і рівно трьома відношеннями порядку a ≤ b ≥ c ≤ d є прикладом ^[en] (або зигзаг-порядку). Його діаграма Гассе нагадує велику латинську літеру «N». Цей порядок не є послідовно-паралельним, оскільки немає способу розбити його на послідовності паралельних з'єднань двох менших часткових порядків. Кажуть, що частковий порядок P є вільним від N-порядку, якщо не існує множини з чотирьох елементів у P, таких, що звуження P на ці елементи ізоморфне N у сенсі часткового порядку. Послідовно-паралельні часткові порядки є точно тими непорожніми скінченними вільними від N-порядку частковими порядками.

Звідси негайно випливає (хоча це можна довести і безпосередньо), що будь-яке непорожнє звуження послідовно-паралельного часткового порядку є саме по собі послідовно-паралельним частковим порядком.

Порядкова розмірність

^[en] часткового порядку P є мінімальним розміром реалізатора P, множини ^[en] (лінеаризацій) порядку P з властивістю, що для будь-яких двох різних елементів x і y порядку P виконується x ≤ y тоді й лише тоді, коли x передує y у будь-якому лінійному продовженні реалізації.

Існує альтернативне визначення: «Найменше число лінійних порядків, що дають у перетині дану частково впорядковану множину, називають його (порядковою розмірністю)», наприклад в лекціях Гурова С. І. або Кузнєцова С. О..

Послідовно-паралельні часткові порядки мають розмірність, яка не перевищує двох. Якщо P і Q мають реалізатори {L_1, L₂} і {L_3, L ₄} відповідно, то {L₁ L_3, L₂ L₄} є реалізатором послідовного з'єднання P; Q а {L₁ L_3, L₄ L₂} є реалізатором паралельного з'єднання P || Q. Частковий порядок є послідовно-паралельним тоді й лише тоді, коли він має реалізатор, у якому одна з двох перестановок ідентична, а друга є ^[en].

Відомо, що частковий порядок P має порядкову розмірність два тоді і тільки тоді, коли існує спряжений порядок Q на тих самих елементах із властивістю, що будь-які два різних елементи x і y порівнянні рівно в одному з цих порядків. У разі серійно-паралельних часткових порядків спряжений порядок, який є сам по собі є послідовно-паралельним, можна отримати, виконавши послідовно операції з'єднання в тому ж порядку, що й для P на тих самих елементах, але замість послідовного з'єднання в P використавши паралельне з'єднання і навпаки. Строгіше, хоча частковий порядок може мати різні спряжені порядки, будь-який спряжений порядок послідовно-паралельного часткового порядку має також бути послідовно-паралельним.

Зв'язок з теорією графів

Будь-який частковий порядок можна подати (зазвичай не однозначно) спрямованим ациклічним графом, у якому є шлях від x до y для всіх елементів x і y часткового порядку, для яких виконується x ≤ y. Графи, які подають послідовно-паралельні часткові порядки таким чином, називають вершинними послідовно-паралельними графами і їх транзитивні скорочення (графи ^[en] часткового порядку) називають мінімальними вершинними послідовно-паралельними графами. Орієнтовані дерева і паралельно-послідовні графи (з однією термінальною парою) є прикладами мінімальних послідовно-паралельних графів. Таким чином, послідовно-паралельні часткові порядки можна використати для подання відношення досяжності в орієнтованих деревах і паралельних графах.

Граф порівнянності часткового порядку є неорієнтованим графом з вершинами для кожного елемента і неорієнтованим ребром для кожної пари різних елементів x, y, якщо x ≤ y або y ≤ x. Тобто він утворений з мінімального послідовно-паралельного графу усуненням орієнтації ребер. Граф порівнянності послідовно-паралельного порядку є кографом — послідовні і паралельні операції з'єднання паралельного порядку дають операції на графі порівнянності, які утворюють незв'язне об'єднання двох підграфів або з'єднують два підграфи всіма можливими ребрами. Ці дві операції є базовими операціями у визначенні кографів. Навпаки, будь-який кограф є графом порівнянності послідовно-паралельного часткового порядку. Якщо частковий порядок має кограф як граф порівнянності, то він має бути послідовно-паралельним частковим порядком, оскільки будь-який інший вид часткового порядку має N-підпорядок, який мав би відповідати породженому шляху з чотирма вершинами в його графі порівнянності, а такі шляхи заборонені в кографах.

Обчислювальна складність

Можна використовувати опис забороненими подпорядками послідовно-паралельних часткових порядків як основу для алгоритму, який перевіряє за час, лінійно залежний від числа пар у відношенні, чи є задане бінарне відношення послідовно-паралельним частковим порядком. Альтернативно, якщо частковий порядок описується як порядок ^[en] спрямованого ациклічного графу, можна перевірити, чи є він послідовно-паралельним частковим порядком, і якщо є, обчислити його транзитивне замикання за час, пропорційний числу вершин і ребер у транзитивному замиканні. Залишається відкритим питання, чи можна поліпшити час розпізнавання послідовно-паралельних порядків досяжності до лінійного від розміру вхідного графу.

Якщо послідовно-паралельний частковий порядок подано як ^[en], яке описує виконання послідовних і паралельних операцій, то елементи часткового порядку можна подати листками дерева виразів. Порівняння двох будь-яких елементів можна здійснити алгоритмічно пошуком найменшого спільного предка відповідних двох листків. Якщо цей предок є паралельним з'єднанням, два елементи непорівнянні, в іншому випадку порядок послідовних з'єднань операндів визначає порядок елементів. Таким способом послідовно-паралельний частковий порядок з n елементів можна подати в просторі O (n) для визначення будь-якого порівнюваного значення з часом O(1).

Задача перевірки для двох заданих послідовно-паралельних часткових порядків P і Q, що P містить звуження, ізоморфне Q, є NP-повною.

Хоча задача підрахунку числа лінійних продовжень довільного часткового порядку є ^[en], можна показати, що її можна розв'язати за поліноміальний час для послідовно-паралельних часткових порядків. А саме, якщо L(P) позначає число лінійних продовжень часткового порядку P, то L(P, Q) = L(P)L(Q) і

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

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

Застосування

Манніла і Міїк використали послідовно-паралельні часткові порядки як модель послідовності подій у даних часового ряду. Вони описали алгоритми машинного навчання для моделей логічного виведення для цього типу і продемонстрували ефективність алгоритмів на виробленні обов'язкових вимог курсу, виходячи з реєстраційних даних студентів, а також на моделюванні шаблонів використання браузерів.

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

Чаудгарі зі співавторами використав послідовно-паралельні часткові порядки для моделювання залежностей задач у потоці даних масової обробки даних для комп'ютерного зору. Вони показали, що за використання послідовно-паралельних порядків для цієї задачі можна ефективно побудувати оптимальний розклад, який призначає різні задачі різним процесорам паралельної обчислювальної системи з метою оптимізувати її пропускну здатність.

Клас упорядкувань, дещо загальніший від поняття послідовно-паралельних часткових порядків, задається PQ-деревами, структурами даних, які застосовують в алгоритмах для перевірки, чи є граф планарним, і розпізнавання інтервальних графів. Вузол P PQ-дерева допускає всі можливі впорядкування його нащадків подібно до паралельного з'єднання в часткових порядках, тоді як вузол Q вимагає, щоб нащадки слідували у фіксованому лінійному порядку подібно до послідовних часткових порядків. Однак, на відміну від послідовно-паралельних часткових порядків, PQ-дерева дозволяють обернути лінійний порядок у будь-якому вузлі Q.

Примітки

1. Bechet, De Groote, Retoré, 1997, с. 230–240.
2. Möhring, 1989, с. 105–194.
3. Valdes, Tarjan, Lawler, 1982, с. 298–313.
4. Jung, 1978, с. 125–133.
5. Lawler, 1978, с. 75–90.
6. Mannila, Meek, 2000, с. 161–168.
7. Amer, Chassot, Connolly и др., 1994, с. 440–456.
8. Choudhary, Narahari, Nicol, Simha, 1994, с. 439–445.
9. Furnas, Zacks, 1994, с. 330–336.
10. Гуров, 2012, с. 111 Определение 3.14.
11. Кузнецов.
12. Ma, Spinrad, 1991, с. 175–183.
13. Brightwell, Winkler, 1991, с. 225–242.
14. Mannila, Meek, 2000.
15. Amer, Chassot, Connolly и др., 1994.
16. Choudhary, Narahari, Nicol, Simha, 1994.
17. Booth, Lueker, 1976, с. 335–379.

Література

• Bechet D., De Groote P., Retoré C. A complete axiomatisation for the inclusion of series-parallel partial orders // Rewriting Techniques and Applications. — Springer-Verlag, 1997. — Т. 1232. — С. 230–240. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-62950-5_74.
• Möhring R. H. Computationally tractable classes of ordered sets // Algorithms and Order: Proceedings of the NATO Advanced Study Institute on Algorithms and Order, Ottawa, Canada, May 31-June 13, 1987. — Springer-Verlag, 1989. — Т. 255. — С. 105–194. — (NATO Science Series C) — .
• Valdes J., Tarjan R. E., Lawler E. L. The recognition of series parallel digraphs // . — 1982. — Т. 11, вип. 2 (10 липня). — С. 298–313. — DOI:10.1137/0211023.
• Lawler E. L. Sequencing jobs to minimize total weighted completion time subject to precedence constraints // Annals of Discrete Mathematics. — 1978. — Т. 2 (10 липня). — С. 75–90. — DOI:10.1016/S0167-5060(08)70323-6.
• Jung H. A. On a class of posets and the corresponding comparability graphs // , Series B. — 1978. — Т. 24, вип. 2 (10 липня). — С. 125–133. — DOI:10.1016/0095-8956(78)90013-8.
• Furnas G. W., Zacks J. Multitrees: enriching and reusing hierarchical structure // Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94). — 1994. — С. 330–336. — DOI:10.1145/191666.191778.
• Ma T.-H., Spinrad J. Transitive closure for restricted classes of partial orders // Order. — 1991. — Т. 8, вип. 2 (10 липня). — С. 175–183. — DOI:10.1007/BF00383402.
• Brightwell G. R., Winkler P. Counting linear extensions // . — 1991. — Т. 8, вип. 3 (10 липня). — С. 225–242. — DOI:10.1007/BF00383444.
• Amer P. D., Chassot C., Connolly T. J., Diaz M., Conrad P. Partial-order transport service for multimedia and other applications // IEEE/ACM Transactions on Networking. — 1994. — Т. 2, вип. 5 (10 липня). — С. 440–456. — DOI:10.1109/90.336326.
• Choudhary A. N., Narahari B., Nicol D. M., Simha R. Optimal processor assignment for a class of pipelined computations // IEEE Transactions on Parallel and Distributed Systems. — 1994. — Т. 5, вип. 4 (10 липня). — С. 439–445. — DOI:10.1109/71.273050.
• Booth K. S., Lueker G. S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms // . — 1976. — Т. 13, вип. 3 (10 липня). — С. 335–379. — DOI:10.1016/S0022-0000(76)80045-1.
• Mannila H. Meek C. Global partial orders from sequential data // Proc. 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2000). — 2000. — С. 161–168. — DOI:10.1145/347090.347122.
• Кузнецов С.О. Теория решёток для интеллектуального анализа данных (PDF).^{[недоступне посилання з Ноябрь 2018]}
• Гуров С.И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры. — М. : КРАСАНД, 2012. — .