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

[[Файл:Series-parallel partial order.svg|thumb|upright=1.35|Последовательно-параллельный частичный порядок, показанный в виде [[Диаграмма Хассе|диаграммы Хассе]].]]
'''Последовательно-параллельный частичный порядок''' — это [[частично упорядоченное множество]], построенное из меньших последовательно-параллельных частичных порядков с помощью двух простых операций соединения{{sfn|Bechet, De Groote, Retoré|1997|с=230–240}}{{sfn|Möhring|1989|с=105–194}}.

Последовательно-параллельные частичные порядки можно описать как свободные от N-порядка конечные частичные порядки. Они имеют {{не переведено 5|Порядковая размерность|порядковую размерность||order dimension}} максимум два{{sfn|Bechet, De Groote, Retoré|1997|с=230–240}}{{sfn|Valdes, Tarjan, Lawler|1982|с=298–313}}. Эти порядки включают {{не переведено 5|Слабое упорядочение|слабые упорядочения||weak order}} и отношение [[Достижимость|достижимости]] в [[Дерево (теория графов)|ориентированных деревьях]] и ориентированных [[Параллельно-последовательный граф|параллельно-последовательных графах]]{{sfn|Möhring|1989|с=105–194}}{{sfn|Valdes, Tarjan, Lawler|1982|с=298–313}}. [[Граф сравнимости|Графы сравнимости]] последовательно-параллельных частичных порядков — это [[кограф]]ы{{sfn|Möhring|1989|с=105–194}}{{sfn|Jung|1978|с=125–133}}.

Последовательно-параллельные частичные порядки применяются в [[Теория расписаний|теории расписаний]]{{sfn|Lawler|1978|с=75–90}}, [[Машинное обучение|машинном обучении]] последовательностей событий во [[Временной ряд|временны́х рядах]] данных{{sfn|Mannila, Meek|2000|с=161–168}}, последовательности передачи [[Мультимедиа|мультимедийных]] данных{{sfn|Amer, Chassot, Connolly и др.|1994|с=440–456}} и максимизации пропускной способности в [[Программирование потоков данных|потоках данных]]{{sfn|Choudhary, Narahari, Nicol, Simha|1994|с=439–445}}.

Последовательно-параллельные частичные порядки называются также мультидеревьями{{sfn|Jung|1978|с=125–133}}. Однако это название двусмысленно — {{не переведено 5|Мультидерево|мультидеревьями||multitree}} также называют частичные порядки без четырёхэлементых подпорядков («алмазов») {{sfn|Furnas, Zacks|1994|с=330–336}}, а также другие структуры, образованные из нескольких деревьев.

==Определение==
Пусть ''P'' и ''Q'' — два частично упорядоченных множеств.  Последовательное соединение ''P'' и ''Q'', записывется {{nowrap|''P''; ''Q''}}{{sfn|Amer, Chassot, Connolly и др.|1994|с=440–456}}, {{nowrap|''P'' * ''Q''}}{{sfn|Möhring|1989|с=105–194}}, или  {{nowrap|''P'' ⧀ ''Q''}}{{sfn|Bechet, De Groote, Retoré|1997|с=230–240}}, является частично упорядоченным множеством, элементы которого являются  [[Дизъюнктное объединение|дизъюнктным объединением]] элементов ''P'' и ''Q''.  В {{nowrap|''P''; ''Q''}}, два элемента ''x'' и ''y'', принадлежащих одновременно ''P'' или ''Q'', имеют то же самое отношение порядка, которое они имели в ''P'' или ''Q'' соответственно. Однако для любой пары ''x'', ''y'', в которой ''x'' принадлежит ''P'', а ''y'' принадлежит ''Q'', имеется дополнительное отношение порядка {{nowrap|''x'' ≤ ''y''}}, определяемое последовательным соединением.  Последовательное соединение является [[Ассоциативная операция|ассоциативной оерацией]] — можно записать {{nowrap|''P''; ''Q''; ''R''}} как последовательное соединение трёх порядков без внесения двусмысленности о том, как комбинировать их попарно, поскольку взятие в скобки {{nowrap|(''P''; ''Q''); ''R''}} и {{nowrap|''P''; (''Q''; ''R'')}} описывает один и тот же частичный порядок. Однако это соединение не является [[Коммутативная операция|коммутативной операцией]], поскольку перестановка ролей ''P'' и ''Q'' даст другой частичный порядок, в котором отношения порядка для пар элементов, одного из ''P'', другого из ''Q'', обращаются{{sfn|Bechet, De Groote, Retoré|1997|с=230–240}}.

Параллельное соединение ''P'' и ''Q'', записывается ''P''&nbsp;||&nbsp;''Q''{{sfn|Amer, Chassot, Connolly и др.|1994|с=440–456}}, {{nowrap|''P'' + ''Q''}}{{sfn|Möhring|1989|с=105–194}} или {{nowrap|''P'' ⊕ ''Q''}}{{sfn|Bechet, De Groote, Retoré|1997|с=230–240}}, определяется из несвязного объединения элементов ''P'' и элементов ''Q'' похожим образом. Если пара элементов принадлежит полностью ''P'' или ''Q'', порядок остаётся тем же самым, что и был в ''P'' или ''Q'' соответственно. Если элемент ''x''  принадлежит ''P'', а элемент ''y'' принадлежит ''Q'', элементы ''x'' и ''y'' несравнимы. Параллельное соединение ассоциативно и коммутативно{{sfn|Bechet, De Groote, Retoré|1997|с=230–240}}.

Класс последовательно-параллельных частичных порядков является множеством частичных порядков, которое может быть построено из одноэлементных частичных порядков с использованием этих двух операций. Эквивалентно, класс является наименьшим множеством частичных порядков, который включает одноэлементный частичный порядок и который [[Замыкание (алгебра)|замкнут]] по операциям последовательного и параллельного соединения{{sfn|Bechet, De Groote, Retoré|1997|с=230–240}}{{sfn|Möhring|1989|с=105–194}}.

{{не переведено 5|Слабое упорядочение|||weak order}} —  это последовательно-параллельный частичный порядок, полученный в результате последовательности операций соединения, в котором сначала проведены все операции параллельного соединения, а затем результаты этих операций комбинированы с только последовательными  операциями{{sfn|Möhring|1989|с=105–194}}.

==Описание запрещёнными подпорядками ==
Частичный порядок ''N'' с четырьмя элементами ''a'', ''b'', ''c'' и ''d'' и в точности тремя отношениями порядка {{nowrap|''a'' ≤ ''b'' ≥ ''c'' ≤ ''d''}} является примером {{не переведено 5|Забор (математика)|забора||Fence (mathematics)}} (или зигзаг-порядка). Его [[диаграмма Хассе]] имеет вид заглавной латинской буквы "N". Этот порядок не является последовательно-параллельным, поскольку нет способа разбить его на последовательности параллельных соединений двух меньших частичных порядков. Говорят, что частичный порядок ''P'' является свободным от N-порядка, если не существует множества из четырёх элементов в ''P'', таких, что сужение ''P'' на эти элементы изоморфно ''N'' в смысле частичного порядка. Последовательно-параллельные частичные порядки являются в точности теми непустыми конечными свободными от N-порядка частичными порядками{{sfn|Bechet, De Groote, Retoré|1997|с=230–240}}{{sfn|Möhring|1989|с=105–194}}{{sfn|Valdes, Tarjan, Lawler|1982|с=298–313}}.

Отсюда немедленно следует (хотя это можно доказать и непосредственно), что любое непустое сужение  последовательно-параллельного частичного порядка является само по себе последовательно-параллельным частичным порядком{{sfn|Bechet, De Groote, Retoré|1997|с=230–240}}.

== Порядковая размерность ==
{{не переведено 5|Порядковая размерность|||order dimension}} частичного порядка ''P'' является минимальным размером реализаций ''P'', множестве {{не переведено 5|Линейное продолжение|линейных продолжений||Linear extension}} (линеаризаций) порядка ''P'' со свойством, что для любых двух различных элементов ''x'' и ''y'' порядка ''P'' выполняется {{nowrap|''x'' ≤ ''y''}} тогда и только тогда, когда ''x'' предшествует ''y'' в любом линейном продолжении реализации. 

В интернете можно найти альтернативное определение: «Наименьшее число линейных порядков, дающих в пересечении данное частично упорядоченное множество, называется его (порядковой размерностью)», например в лекциях Гурова С.И.{{sfn|Гуров|2012|с=111 Определение 3.14}} или Кузнецова С.О.{{sfn|Кузнецов}}.

Последовательно-параллельные частичные порядки имеют размерность, не превосходящую двух. Если ''P'' и ''Q'' имеют реализаторы {''L''<sub>1</sub>,&nbsp;''L''<sub>2</sub>} и {''L''<sub>3</sub>,&nbsp;''L''<sub>4</sub>} соответственно, то {''L''<sub>1</sub>''L''<sub>3</sub>,&nbsp;''L''<sub>2</sub>''L''<sub>4</sub>} является реализатором последовательного соединения {{nowrap|''P''; ''Q''}}, а {''L''<sub>1</sub>''L''<sub>3</sub>,&nbsp;''L''<sub>4</sub>''L''<sub>2</sub>} является реализатором параллельного соединения ''P''&nbsp;||&nbsp;''Q''{{sfn|Möhring|1989|с=105–194}}{{sfn|Valdes, Tarjan, Lawler|1982|с=298–313}}. Частичный порядок является последовательно-параллельным тогда и только тогда, когда он имеет реализатор, в котором одна из двух перестановок идентична, а вторая является {{не переведено 5|Отделимая перестановка|отделимой||separable permutation}}.

Известно, что частичный порядок ''P'' имеет порядковую размерность два тогда и только тогда, когда существует сопряжённый порядок ''Q'' на тех же элементах со свойством, что любые два различных элементах ''x'' и ''y'' сравнимы в точности в одном из этих порядков. В случае серийно-параллельных частичных порядков сопряжённый порядок, являющийся сам по себе является последовательно-параллельным, может быть получен путём осуществления последовательности операций соединения в том же порядке, как и для ''P'' на тех же элементах, но вместо последовательного соединения в ''P'' используется параллельное соединение и наоборот. Более строго, хотя частичный порядок может иметь различные сопряжённые порядки, любой сопряжённый порядок последовательно-параллельного частичного порядка должен также быть последовательно-параллельным{{sfn|Möhring|1989|с=105–194}}.

==Связь с теорией графов ==
Любой частичный порядок может быть представлен (обычно не однозначно) [[Направленный ациклический граф|направленным ациклическим графом]], в котором имеется путь от  ''x'' к ''y'' для всех элементов ''x'' и ''y'' частичного порядка, для которых выполняется{{nowrap|''x'' ≤ ''y''}}. Графы, которые представляют последовательно-параллельные частичные порядки описанным образом, называются вершинными последовательно-параллельными графами и их [[Транзитивное сокращение|транзитивные сокращения]] (графы {{не переведено 5|Отношение покрытия|отношений покрытия||covering relation}} частичного порядка) называются минимальными вершинными последовательно-параллельными графами{{sfn|Valdes, Tarjan, Lawler|1982|с=298–313}}. Ориентированные деревья и (с одной терминальной парой) [[Параллельно-последовательный граф|параллельно-последовательные графы]] являются примерами минимальных последовательно-параллельных графов. Таким образом, последовательно-параллельные частичные порядки могут быть использованы для представления отношения достижимости в ориентированных деревьях и параллельных графах{{sfn|Möhring|1989|с=105–194}}{{sfn|Valdes, Tarjan, Lawler|1982|с=298–313}}.

[[Граф сравнимости]] частичного порядка является [[Неориентированный граф|неориентированным графом]] с вершинами для каждого элемента и неориентированным ребром для каждой пары различных элементов ''x'', ''y'', если {{nowrap|''x'' ≤ ''y''}} или {{nowrap|''y'' ≤ ''x''}}. То есть он образован из минимального последовательно-параллельного графа путём избавления от [[Ориентация (теория графов)|ориентации]] рёбер. Граф сравнимости последовательно-параллельного порядка является [[кограф]]ом — последовательные и параллельные операции соединения параллельного порядка дают операции на графе сравнимости, которые образуют несвязное объединение двух подграфов или соединяют два подграфа всеми возможными рёбрами.  Эти две операции являются базовыми операциями в определении кографов. Обратно, любой кограф является графом сравнимости последовательно-параллельного частичного порядка. Если частичный порядок имеет кограф в качестве графа сравнимости, то он должен быть последовательно-параллельным частичным порядком, поскольку любой другой вид частичного порядка имеет N-подпорядок, который должен соответствовать порождённым путём с четырьмя вершинами в его графе сравнимости, а такие пути запрещены в кографах{{sfn|Möhring|1989|с=105–194}}{{sfn|Jung|1978|с=125–133}}.

==Вычислительная сложность ==
Можно использовать описание запрещёнными подпорядками последовательно-параллельных частичных порядков как базис для алгоритма, который проверяет за время, линейно зависящее от числа пар в соотношении, является ли заданное бинарное отношение последовательно-параллельным частичным порядком{{sfn|Möhring|1989|с=105–194}}{{sfn|Valdes, Tarjan, Lawler|1982|с=298–313}}. Альтернативно, если частичный порядок описывается как порядок {{не переведено 5|Достижимость|достижимости||reachability}} [[Направленный ациклический граф|направленного ациклического графа]], возможно проверить, является ли он последовательно-параллельным частичным порядком, и если является, вычислить его транзитивное замыкание за время, пропорциональное числу вершин и рёбер в транзитивном замыкании. Остаётся открытым вопрос, можно ли улучшить время распознавания последовательно-параллельных порядков достижимости до линейного от размера входного графа{{sfn|Ma, Spinrad|1991|с=175–183}}.

Если последовательно-параллельный частичный порядок представлен как {{не переведено 5|Бинарное дерево выражений|дерево выражений||expression tree}}, описывающее выполнение последовательных и параллельных операций, то элементы частичного порядка могут быть представлены листьями дерева выражений. Сравнение двух любых элементов может быть осуществлено алгоритмически путём поиска [[Наименьший общий предок|наименьшего общего предка]] соответствующих двух листьев. Если этот предок является параллельным соединением, два элемента несравнимы, в противном случае порядок последовательных соединений операндов определяет порядок элементов. Таким способом последовательно-параллельный частичный порядок из ''n'' элементов может быть представлен в пространстве O(''n'') для определения любого сравниваемого значения с временем O(1){{sfn|Möhring|1989|с=105–194}}.

Задача проверки для двух заданных последовательно-параллельных частичных порядков ''P'' и ''Q'', что ''P'' содержит сужение, изоморфное ''Q'', является [[NP-полная задача|NP-полной]]{{sfn|Valdes, Tarjan, Lawler|1982|с=298–313}}.

Хотя задача подсчёта числа линейных продолжений произвольного частичного порядка является [[Класс Sharp-P-complete|#P-полной]]{{sfn|Brightwell, Winkler|1991|с=225–242}}, можно показать, что она может быть решена за полиномиальное время для последовательно-параллельных частичных порядков. А именно, если ''L''(''P'') обозначает число линейных продолжений частичного порядка ''P'', то ''L''(''P''; ''Q'')=''L''(''P'')''L''(''Q'') и
:<math>L(P||Q)=\frac{(|P|+|Q|)!}{|P|!|Q|!} L(P)L(Q),</math>{{sfn|Möhring|1989|с=105–194}}.

==Приложения==
Маннила и Миик{{sfn|Mannila, Meek|2000}} использовали последовательно-параллельные частичные порядки в качестве модели последовательности событий в данных [[Временной ряд|временного ряда]]. Они описали алгоритмы [[Машинное обучение|машинного обучения]]  для моделей логического вывода для этого типа и продемонстрировали эффективность алгоритмов на выработке обязательных требований курса, исходя из регистрационных данных студентов, а также на моделировании шаблонов использования браузеров{{sfn|Mannila, Meek|2000|с=161–168}}.
 
Амер с соавторами{{sfn|Amer, Chassot, Connolly и др.|1994}} утверждает, что последовательно-параллельные частичные порядки удобны для моделирования запросов последовательности передачи [[мультимедиа]] презентаций. Они использовали формулу для вычисления числа линейных продолжений последовательно-параллельного частичного порядка в качестве базиса анализа алгоритмов передачи мультимедиа{{sfn|Amer, Chassot, Connolly и др.|1994|с=440–456}}.

Чаудхари с соавторами{{sfn|Choudhary, Narahari, Nicol, Simha|1994}} использовал последовательно-параллельные частичные порядки для моделирования зависимостей задач в [[Поток данных|потоке данных]] массовой обработки данных для [[Компьютерное зрение|компьютерного зрения]]. Они показали, что при использовании последовательно-параллельных порядков для этой задачи можно эффективно построить оптимальное расписание, назначающее различные задачи различным процессорам [[Параллельные вычислительные системы|параллельной вычислительной системы]] с целью оптимизировать пропускную способность системы{{sfn|Choudhary, Narahari, Nicol, Simha|1994|с=439–445}}.

Класс упорядочений, несколько более общий понятию последовательно-параллельных частичных порядков, задаётся [[PQ-дерево|PQ-деревьями]], структурами данных, применяемых в алгоритмах для проверки, является ли граф [[Планарный граф|планарным]], и распознавания [[Интервальный граф|интервальных графов]]{{sfn|Booth, Lueker|1976|с=335–379}}. Узел ''P'' PQ-дерева допускает все возможные упорядочения его наследников подобно параллельному соединению в частичных порядках, в то время как узел ''Q'' требует следования наследников в фиксированном линейном порядке подобно последовательным частичным порядкам. Однако, в отличие от последовательно-параллельных частичных порядков, PQ-деревья позволяют обратить [[Линейно упорядоченное множество|линейный порядок]] в любом узле ''Q''.

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

[[Категория:Теория порядков]]
[[Категория:Бинарные отношения]]
{{rq|checktranslate|style}}