Sériově paralelní dílčí objednávka

Sérioparalelní dílčí objednávka  je částečně uspořádaná sada sestavená z menších sérioparalelních dílčích objednávek pomocí dvou jednoduchých operací spojení [1] [2] .

Sériově paralelní dílčí řády lze popsat jako konečné dílčí řády bez N řádů. Mají ordinální rozměr nejvýše dva [1] [3] . Tyto řády zahrnují slabé uspořádání a vztah dosažitelnosti v orientovaných stromech a orientovaných paralelně sekvenčních grafech [2] [3] . Grafy srovnatelnosti sérioparalelních dílčích řádů jsou kografy [2] [4] .

Sériově-paralelní dílčí objednávky se uplatňují v teorii plánování [5] , strojovém učení sekvencí událostí v datech časových řad [6] , sekvenci přenosu multimediálních dat [7] a maximalizaci propustnosti v datových tocích [8] .

Sériově paralelní dílčí objednávky se také nazývají multistromy [4] . Tento název je však nejednoznačný – multistromy se také nazývají dílčí řády bez čtyřprvkových podřádů („diamanty“) [9] , stejně jako další struktury tvořené z několika stromů.

Definice

Nechť P a Q jsou dvě částečně uspořádané množiny. Sériové zapojení P a Q , psané P ; Q [7] , P * Q [2] , nebo P ⧀ Q [1] , je poset, jehož prvky jsou disjunktním spojením prvků P a Q . V P ; Q , dva prvky x a y , které patří současně k P nebo Q , mají stejný vztah uspořádání, jaký měly v P nebo Q. Avšak pro každou dvojici x , y , ve které x patří do P a y patří do Q , existuje další relace pořadí x ≤ y definovaná sériovým spojením. Sériové připojení je asociativní operace - můžete psát P ; Q ; R jako zřetězení tří řádů bez zavedení nejednoznačnosti, jak je kombinovat ve dvojicích, protože závorky ( P ; Q ); R & P ; ( Q ; R ) popisuje stejné dílčí uspořádání. Toto spojení však není komutativní operace , protože obrácení rolí P a Q dá různé částečné pořadí, ve kterém jsou vztahy pořadí pro dvojice prvků, jeden z P , druhý z Q , obrácené [1] .

Paralelní spojení P a Q , psané P  || Q [7] , P + Q [2] nebo P ⊕ Q [1] , je definováno z disjunktního spojení prvků P a prvků Q podobným způsobem. Pokud pár prvků patří zcela k P nebo Q , pořadí zůstává stejné jako v P nebo Q. Jestliže prvek x patří do P a prvek y patří do Q , prvky x a y jsou nesrovnatelné. Paralelní spojení je asociativní a komutativní [1] .

Třída sériově-paralelních dílčích objednávek je sada dílčích objednávek, které lze sestavit z jednotlivých dílčích objednávek pomocí těchto dvou operací. Ekvivalentně je třída nejmenší množinou dílčích objednávek, která zahrnuje jednonásobnou dílčí objednávku a která je uzavřena při operacích sériového a paralelního připojení [1] [2] .

Slabé řazení je sériově-paralelní částečné pořadí vyplývající ze sledu operací spojení, ve kterém jsou nejprve provedeny všechny operace paralelního spojení a poté jsou výsledky těchto operací kombinovány pouze se sekvenčními operacemi [2] .

Popis podle zakázaných podřádů

Dílčí řád N se čtyřmi prvky a , b , c a da přesně třemi řádovými vztahy a ≤ b ≥ c ≤ d je příkladem plotu (nebo klikatého řádu). Jeho Hasseův diagram je ve formě velkého písmene „N“. Toto uspořádání není sériově paralelní, protože neexistuje způsob, jak jej rozdělit na sekvence paralelních spojení dvou menších dílčích řádů. O částečném řádu P se říká, že je bez řádu N, pokud v P nejsou žádné množiny čtyř prvků , takže omezení P na tyto prvky je izomorfní k N ve smyslu částečného řádu. Sériově-paralelní dílčí řády jsou přesně ty neprázdné konečné dílčí řády bez N-řádů [1] [2] [3] .

To okamžitě implikuje (ačkoli to lze přímo dokázat), že každé neprázdné omezení sérioparalelního dílčího řádu je samo sérioparalelním dílčím řádem [1] .

Řadový rozměr

Pořadový rozměr dílčího řádu P je minimální velikost realizací P , množina lineárních rozšíření (linearizací) řádu P s vlastností, že pro libovolné dva odlišné prvky x a y řádu P , x ≤ y právě tehdy, když x předchází y v jakémkoli lineárním pokračování implementace.

Alternativní definici lze nalézt na internetu: „Nejmenší počet lineárních řádů, které dávají danou částečně uspořádanou množinu v průsečíku, se nazývá její (ordinální dimenze)“, například v přednáškách Gurova S.I. [10] nebo Kuzněcova S.O. [11] .

Sériově paralelní dílčí objednávky mají rozměr nepřesahující dva. Jestliže P a Q mají implementátory { L 1 ,  L 2 } a { L 3 ,  L 4 } v tomto pořadí, pak { L 1 L 3 ,  L 2 L 4 } je implementátorem sériového připojení P ; Q , a { L 1 L 3 ,  L 4 L 2 } je implementátorem paralelního zapojení P  || Q [2] [3] . Částečná objednávka je sériově paralelní tehdy a pouze tehdy, pokud má implementátor, ve kterém je jedna ze dvou permutací identická a druhá je oddělitelná .

Je známo, že dílčí řád P má rozměr řádu dva právě tehdy, když existuje sdružený řád Q na stejných prvcích s tou vlastností, že jakékoli dva odlišné prvky x a y jsou srovnatelné přesně v jednom z těchto řádů. V případě sérioparalelních dílčích objednávek lze sdružené pořadí, které je samo o sobě sérioparalelní, získat provedením sekvence operací spojení ve stejném pořadí jako pro P na stejných prvcích, ale místo sériového spojení P používá paralelní spojení.a naopak. Přesněji řečeno, ačkoli částečné pořadí může mít různá sdružená uspořádání, jakékoli sdružené pořadí sérioparalelního částečného uspořádání musí být také sérioparalelní [2] .

Vztah k teorii grafů

Libovolný dílčí řád může být reprezentován (obvykle nejednoznačně) orientovaným acyklickým grafem , který má cestu od x do y pro všechny prvky x a y dílčího řádu, pro které x ≤ y . Grafy, které tímto způsobem reprezentují sérioparalelní dílčí řády, se nazývají vrcholové sérioparalelní grafy a jejich tranzitivní redukce (grafy vztahů pokrývajících dílčí řády ) se nazývají minimální vrcholové sérioparalelní grafy 3] . Řízené stromy a (s jedním párem terminálů) paralelně-sériové grafy jsou příklady minimálních sérioparalelních grafů. Sérioparalelní dílčí řády lze tedy použít k reprezentaci vztahu dosažitelnosti v orientovaných stromech a paralelních grafech [2] [3] .

Graf srovnatelnosti částečného řádu je neorientovaný graf s vrcholy pro každý prvek a neorientovanou hranou pro každou dvojici odlišných prvků x , y , pokud x ≤ y nebo y ≤ x . To znamená, že je vytvořen z minimálního sérioparalelního grafu odstraněním okrajové orientace . Sériově -paralelní graf srovnatelnosti pořadí je kograf — sériové a paralelní paralelní operace spojení poskytují operace na grafu srovnatelnosti, které tvoří disjunktní spojení dvou podgrafů nebo spojují dva podgrafy všemi možnými hranami. Tyto dvě operace jsou základní operace v definici kografů. Naopak, každý cograph je sérioparalelní graf srovnatelnosti částečného řádu. Pokud má částečný řád jako graf srovnatelnosti kograf, pak to musí být sérioparalelní dílčí řád, protože jakýkoli jiný druh dílčího řádu má N-podřád, který musí odpovídat vygenerované cestě se čtyřmi vrcholy v jeho grafu srovnatelnosti. a takové cesty jsou v cographech zakázány [2] [4] .

Výpočetní složitost

Zakázaný popis podřádů sérioparalelních dílčích řádů můžete použít jako základ pro algoritmus, který v čase lineárně v závislosti na počtu párů v relaci kontroluje, zda daná binární relace je sérioparalelním dílčím řádem [2] [3] . Alternativně, pokud je částečné pořadí popsáno jako pořadí dosažitelnosti orientovaného acyklického grafu , je možné otestovat, zda se jedná o sérioparalelní dílčí řád, a pokud ano, vypočítat jeho tranzitivní uzavření v čase úměrném počet vrcholů a hran v tranzitivním uzávěru. Otevřenou otázkou zůstává, zda je možné zlepšit dobu rozpoznávání sérioparalelních řádů dosažitelnosti na lineární ve velikosti vstupního grafu [12] .

Pokud je sérioparalelní částečná objednávka reprezentována jako strom výrazů popisující provádění sériových a paralelních operací, pak mohou být prvky částečné objednávky reprezentovány listy stromu výrazů. Porovnání libovolných dvou prvků lze provést algoritmicky nalezením nejmenšího společného předka odpovídajících dvou listů. Pokud je tímto předkem paralelní spojení, jsou tyto dva prvky neporovnatelné, jinak pořadí sériových spojení operandů určuje pořadí prvků. Tímto způsobem lze sérioparalelní částečné pořadí n prvků reprezentovat v prostoru O( n ) pro určení jakékoli hodnoty, která má být porovnána v čase O(1) [2] .

Problém kontroly dvou daných sérioparalelních dílčích řádů P a Q , že P obsahuje omezení izomorfní k Q , je NP-úplný [3] .

Ačkoli je problém počítání počtu lineárních rozšíření libovolného dílčího řádu #P-úplný [13] , lze ukázat, že jej lze vyřešit v polynomiálním čase pro sérioparalelní dílčí řády. Totiž, jestliže L ( P ) značí počet lineárních rozšíření dílčího řádu P , pak L ( P ; Q )= L ( P ) L ( Q ) a

[2] .

Aplikace

Mannila a Meek [14] použili sérioparalelní dílčí řády jako model pro posloupnost událostí v datech časových řad . Popsali algoritmy strojového učení pro inferenční modely pro tento typ a prokázali účinnost algoritmů při generování požadovaných požadavků na kurzy na základě registračních údajů studentů a také při modelování vzorců používání prohlížeče [6] .

Amer et al [15] tvrdí, že sériové paralelní dílčí objednávky jsou vhodné pro modelování požadavků na sekvenování mediální prezentace . Jako základ pro analýzu algoritmů přenosu multimédií použili vzorec pro výpočet počtu lineárních pokračování sérioparalelního dílčího řádu [7] .

Chaudhary et al [16] použili sérioparalelní dílčí objednávky k modelování závislostí úloh v datovém toku hromadného zpracování dat pro počítačové vidění . Ukázali, že při použití sérioparalelních zakázek pro tuto úlohu je možné efektivně sestavit optimální rozvrh, který přiděluje různé úlohy různým procesorům paralelního výpočetního systému za účelem optimalizace propustnosti systému [8] .

Třída uspořádání, poněkud obecnější než koncept sérioparalelních dílčích uspořádání, je dána PQ-trees , datovými strukturami používanými v algoritmech pro kontrolu, zda je graf rovinný , a pro rozpoznávání intervalových grafů [17] . Uzel P stromu PQ umožňuje všechna možná uspořádání jeho potomků jako paralelní spojení v dílčích řádech, zatímco uzel Q vyžaduje, aby následníci následovali v pevném lineárním pořadí jako sekvenční dílčí řády. Na rozdíl od sériově-paralelních částečných objednávek vám však PQ-stromy umožňují obrátit lineární pořadí v libovolném uzlu Q .

Poznámky

  1. ↑ 1 2 3 4 5 6 7 8 9 Bechet, De Groote, Retoré, 1997 , str. 230–240.
  2. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Möhring, 1989 , str. 105–194.
  3. ↑ 1 2 3 4 5 6 7 8 Valdes, Tarjan, Lawler, 1982 , str. 298–313.
  4. ↑ 1 2 3 Jung, 1978 , str. 125–133.
  5. ↑ Lawler, 1978 , str. 75–90.
  6. ↑ 1 2 Mannila, Meek, 2000 , str. 161–168.
  7. ↑ 1 2 3 4 Amer, Chassot, Connolly a kol., 1994 , str. 440–456.
  8. ↑ 1 2 Choudhary, Narahari, Nicol, Simha, 1994 , str. 439–445.
  9. ↑ Furnas a Zacks 1994 , str. 330–336.
  10. ↑ Gurov, 2012 , str. 111 Definice 3.14.
  11. ↑ Kuzněcov .
  12. ↑ Ma, Spinrad, 1991 , str. 175–183.
  13. ↑ Brightwell, Winkler, 1991 , s. 225–242.
  14. ↑ Mannila, Meek, 2000 .
  15. ↑ Amer, Chassot, Connolly a kol., 1994 .
  16. ↑ Choudhary, Narahari, Nicol, Simha, 1994 .
  17. ↑ Booth a Lueker 1976 , str. 335–379.

Literatura