Послідовно-паралельний частковий порядок
Послідовно-паралельний частковий порядок — це частково впорядкована множина, побудована з менших послідовно-паралельних часткових порядків за допомогою двох простих операцій з'єднанняШаблон:SfnШаблон:Sfn.
Послідовно-паралельні часткові порядки можна описати як вільні від N-порядку скінченні часткові порядки. Вони мають Шаблон:Не перекладено максимум дваШаблон:SfnШаблон:Sfn. Ці порядки включають Шаблон:Не перекладено і відношення досяжності в орієнтованих деревах і орієнтованих паралельно-послідовних графахШаблон:SfnШаблон:Sfn. Графи порівнянності послідовно-паралельних часткових порядків — це кографиШаблон:SfnШаблон:Sfn.
Послідовно-паралельні часткові порядки застосовують у теорії розкладівШаблон:Sfn, машинному навчанні послідовностей подій у часових рядах данихШаблон:Sfn, послідовності передачі мультимедійних данихШаблон:Sfn і максимізації пропускної спроможності в потоках данихШаблон:Sfn.
Послідовно-паралельні часткові порядки називають також мультидеревамиШаблон:Sfn. Однак ця назва двозначна — Шаблон:Не перекладено також називають часткові порядки без чотириелементних підпорядків («алмазів»)Шаблон:Sfn, а також інші структури, утворені з кількох дерев.
Визначення
Нехай P і Q — дві частково впорядкованих множини. Послідовне з'єднання P і Q, що позначається Шаблон:NobrШаблон:Sfn, Шаблон:NobrШаблон:Sfn, або Шаблон:NobrШаблон:Sfn, є частково впорядкованою множиною, елементи якої є диз'юнктним об'єднанням елементів P і Q. В Шаблон:Nobr два елементи x та y, що належать одночасно P або Q, мають таке саме відношення порядку, яке вони мали в P або Q відповідно. Однак для будь-якої пари x, y, в якій x належить P, а y належить Q, є додаткове відношення порядку Шаблон:Nobr яке визначається послідовним з'єднанням. Послідовне з'єднання є асоціативною операцією — можна записати Шаблон:Nobr як послідовне з'єднання трьох порядків без внесення двозначності про те, як комбінувати їх попарно, оскільки взяття в дужки Шаблон:Nobr і Шаблон:Nobr описує один і той самий частковий порядок. Однак це з'єднання не є комутативною операцією, оскільки перестановка ролей P і Q дасть інший частковий порядок, у якому відношення порядку для пар елементів, одного з P, іншого з Q, обертаютьсяШаблон:Sfn.
Паралельне з'єднання P і Q, що позначається P || QШаблон:Sfn, Шаблон:NobrШаблон:Sfn або Шаблон:NobrШаблон:Sfn, визначається з незв'язного об'єднання елементів P і елементів Q схожим чином. Якщо пара елементів належить повністю P або Q, порядок залишається тим самим, що був у P або Q відповідно. Якщо ж елемент x належить P, а елемент y належить Q, то елементи x та y непорівнянні. Паралельне з'єднання асоціативне і комутативнеШаблон:Sfn.
Клас послідовно-паралельних часткових порядків є множиною часткових порядків, яку можна побудувати з одноелементних часткових порядків з використанням цих двох операцій. Еквівалентно, клас є найменшою множиною часткових порядків, яка включає одноелементний частковий порядок і яка замкнена за операціями послідовного і паралельного з'єднанняШаблон:SfnШаблон:Sfn.
Шаблон:Не перекладено — це послідовно-паралельний частковий порядок, отриманий внаслідок послідовності операцій з'єднання, в якому спочатку проведено всі операції паралельного з'єднання, а потім результати цих операцій комбіновано з тільки послідовними операціямиШаблон:Sfn.
Опис забороненими підпорядками
Частковий порядок N з чотирма елементами a, b, c і d і рівно трьома відношеннями порядку Шаблон:Nobr є прикладом Шаблон:Не перекладено (або зигзаг-порядку). Його діаграма Гассе нагадує велику латинську літеру «N». Цей порядок не є послідовно-паралельним, оскільки немає способу розбити його на послідовності паралельних з'єднань двох менших часткових порядків. Кажуть, що частковий порядок P є вільним від N-порядку, якщо не існує множини з чотирьох елементів у P, таких, що звуження P на ці елементи ізоморфне N у сенсі часткового порядку. Послідовно-паралельні часткові порядки є точно тими непорожніми скінченними вільними від N-порядку частковими порядкамиШаблон:SfnШаблон:SfnШаблон:Sfn.
Звідси негайно випливає (хоча це можна довести і безпосередньо), що будь-яке непорожнє звуження послідовно-паралельного часткового порядку є саме по собі послідовно-паралельним частковим порядкомШаблон:Sfn.
Порядкова розмірність
Шаблон:Не перекладено часткового порядку P є мінімальним розміром реалізатора P, множини Шаблон:Не перекладено (лінеаризацій) порядку P з властивістю, що для будь-яких двох різних елементів x і y порядку P виконується x ≤ y тоді й лише тоді, коли x передує y у будь-якому лінійному продовженні реалізації.
Існує альтернативне визначення: «Найменше число лінійних порядків, що дають у перетині дану частково впорядковану множину, називають його (порядковою розмірністю)», наприклад в лекціях Гурова С. І.Шаблон:Sfn або Кузнєцова С. О.Шаблон:Sfn.
Послідовно-паралельні часткові порядки мають розмірність, яка не перевищує двох. Якщо P і Q мають реалізатори {L1, L2} і {L3, L 4} відповідно, то {L1 L3, L2 L4} є реалізатором послідовного з'єднання Шаблон:Nobr а {L1 L3, L4 L2} є реалізатором паралельного з'єднання P || QШаблон:SfnШаблон:Sfn. Частковий порядок є послідовно-паралельним тоді й лише тоді, коли він має реалізатор, у якому одна з двох перестановок ідентична, а друга є Шаблон:Не перекладено.
Відомо, що частковий порядок P має порядкову розмірність два тоді і тільки тоді, коли існує спряжений порядок Q на тих самих елементах із властивістю, що будь-які два різних елементи x і y порівнянні рівно в одному з цих порядків. У разі серійно-паралельних часткових порядків спряжений порядок, який є сам по собі є послідовно-паралельним, можна отримати, виконавши послідовно операції з'єднання в тому ж порядку, що й для P на тих самих елементах, але замість послідовного з'єднання в P використавши паралельне з'єднання і навпаки. Строгіше, хоча частковий порядок може мати різні спряжені порядки, будь-який спряжений порядок послідовно-паралельного часткового порядку має також бути послідовно-паралельнимШаблон:Sfn.
Зв'язок з теорією графів
Будь-який частковий порядок можна подати (зазвичай не однозначно) спрямованим ациклічним графом, у якому є шлях від x до y для всіх елементів x і y часткового порядку, для яких виконується Шаблон:Nobr. Графи, які подають послідовно-паралельні часткові порядки таким чином, називають вершинними послідовно-паралельними графами і їх транзитивні скорочення (графи Шаблон:Не перекладено часткового порядку) називають мінімальними вершинними послідовно-паралельними графамиШаблон:Sfn. Орієнтовані дерева і паралельно-послідовні графи (з однією термінальною парою) є прикладами мінімальних послідовно-паралельних графів. Таким чином, послідовно-паралельні часткові порядки можна використати для подання відношення досяжності в орієнтованих деревах і паралельних графахШаблон:SfnШаблон:Sfn.
Граф порівнянності часткового порядку є неорієнтованим графом з вершинами для кожного елемента і неорієнтованим ребром для кожної пари різних елементів x, y, якщо Шаблон:Nobr або Шаблон:Nobr. Тобто він утворений з мінімального послідовно-паралельного графу усуненням орієнтації ребер. Граф порівнянності послідовно-паралельного порядку є кографом — послідовні і паралельні операції з'єднання паралельного порядку дають операції на графі порівнянності, які утворюють незв'язне об'єднання двох підграфів або з'єднують два підграфи всіма можливими ребрами. Ці дві операції є базовими операціями у визначенні кографів. Навпаки, будь-який кограф є графом порівнянності послідовно-паралельного часткового порядку. Якщо частковий порядок має кограф як граф порівнянності, то він має бути послідовно-паралельним частковим порядком, оскільки будь-який інший вид часткового порядку має N-підпорядок, який мав би відповідати породженому шляху з чотирма вершинами в його графі порівнянності, а такі шляхи заборонені в кографахШаблон:SfnШаблон:Sfn.
Обчислювальна складність
Можна використовувати опис забороненими подпорядками послідовно-паралельних часткових порядків як основу для алгоритму, який перевіряє за час, лінійно залежний від числа пар у відношенні, чи є задане бінарне відношення послідовно-паралельним частковим порядкомШаблон:SfnШаблон:Sfn. Альтернативно, якщо частковий порядок описується як порядок Шаблон:Не перекладено спрямованого ациклічного графу, можна перевірити, чи є він послідовно-паралельним частковим порядком, і якщо є, обчислити його транзитивне замикання за час, пропорційний числу вершин і ребер у транзитивному замиканні. Залишається відкритим питання, чи можна поліпшити час розпізнавання послідовно-паралельних порядків досяжності до лінійного від розміру вхідного графуШаблон:Sfn.
Якщо послідовно-паралельний частковий порядок подано як Шаблон:Не перекладено, яке описує виконання послідовних і паралельних операцій, то елементи часткового порядку можна подати листками дерева виразів. Порівняння двох будь-яких елементів можна здійснити алгоритмічно пошуком найменшого спільного предка відповідних двох листків. Якщо цей предок є паралельним з'єднанням, два елементи непорівнянні, в іншому випадку порядок послідовних з'єднань операндів визначає порядок елементів. Таким способом послідовно-паралельний частковий порядок з n елементів можна подати в просторі O (n) для визначення будь-якого порівнюваного значення з часом O(1)Шаблон:Sfn.
Задача перевірки для двох заданих послідовно-паралельних часткових порядків P і Q, що P містить звуження, ізоморфне Q, є NP-повноюШаблон:Sfn.
Хоча задача підрахунку числа лінійних продовжень довільного часткового порядку є Шаблон:НпШаблон:Sfn, можна показати, що її можна розв'язати за поліноміальний час для послідовно-паралельних часткових порядків. А саме, якщо L(P) позначає число лінійних продовжень часткового порядку P, то L(P, Q) = L(P)L(Q) і
- Шаблон:Sfn
- тому кількість лінійних розширень можна обчислити, використовуючи дерево виразів у тій самій формі, що й дерево розкладання даного послідовно-паралельного порядкуШаблон:Sfn.
Застосування
Манніла і МіїкШаблон:Sfn використали послідовно-паралельні часткові порядки як модель послідовності подій у даних часового ряду. Вони описали алгоритми машинного навчання для моделей логічного виведення для цього типу і продемонстрували ефективність алгоритмів на виробленні обов'язкових вимог курсу, виходячи з реєстраційних даних студентів, а також на моделюванні шаблонів використання браузерівШаблон:Sfn.
Амер зі співавторамиШаблон:Sfn стверджує, що послідовно-паралельні часткові порядки зручні для моделювання запитів послідовності передавання мультимедіа презентацій. Вони використовували формулу для обчислення числа лінійних продовжень послідовно-паралельного часткового порядку як основу для аналізу алгоритмів передавання мультимедіаШаблон:Sfn.
Чаудгарі зі співавторамиШаблон:Sfn використав послідовно-паралельні часткові порядки для моделювання залежностей задач у потоці даних масової обробки даних для комп'ютерного зору. Вони показали, що за використання послідовно-паралельних порядків для цієї задачі можна ефективно побудувати оптимальний розклад, який призначає різні задачі різним процесорам паралельної обчислювальної системи з метою оптимізувати її пропускну здатністьШаблон:Sfn.
Клас упорядкувань, дещо загальніший від поняття послідовно-паралельних часткових порядків, задається PQ-деревами, структурами даних, які застосовують в алгоритмах для перевірки, чи є граф планарним, і розпізнавання інтервальних графівШаблон:Sfn. Вузол P PQ-дерева допускає всі можливі впорядкування його нащадків подібно до паралельного з'єднання в часткових порядках, тоді як вузол Q вимагає, щоб нащадки слідували у фіксованому лінійному порядку подібно до послідовних часткових порядків. Однак, на відміну від послідовно-паралельних часткових порядків, PQ-дерева дозволяють обернути лінійний порядок у будь-якому вузлі Q.