Ordine parțială serie-paralelă

O ordine parțială serial-paralelă  este o mulțime parțial ordonată construită din ordine parțiale seriale-paralele mai mici folosind două operații simple de îmbinare [1] [2] .

Ordinele parțiale seriale-paralele pot fi descrise ca ordine parțiale finite fără ordine N. Au dimensiunea ordinală cel mult două [1] [3] . Aceste ordine includ ordonări slabe și relația de accesibilitate în arbori direcționați și grafice paralel-secvențiale direcționate [2] [3] . Graficele de comparabilitate ale ordinelor parțiale seriale-paralele sunt cografe [2] [4] .

Ordinele parțiale seriale-paralele sunt aplicate în teoria programării [5] , învățarea automată a secvențelor de evenimente în datele din seria temporală [6] , secvența de transfer de date multimedia [7] și maximizarea debitului în fluxurile de date [8] .

Ordinele parțiale seriale-paralele sunt numite și multiarbori [4] . Cu toate acestea, această denumire este ambiguă - multiarborele sunt denumite și ordine parțiale fără subordine de patru elemente ("diamante") [9] , precum și alte structuri formate din mai mulți arbori.

Definiție

Fie P și Q două mulțimi parțial ordonate. Conexiune serială a lui P și Q , scris P ; Q [7] , P * Q [2] , sau P ⧀ Q [1] , este un poset ale cărui elemente sunt uniunea disjunsă a elementelor lui P și Q . În P ; Q , două elemente x și y care aparțin simultan lui P sau Q au aceeași relație de ordine pe care o aveau în P sau , respectiv, Q. Totuși, pentru orice pereche x , y în care x aparține lui P și y aparține lui Q , există o relație de ordine suplimentară x ≤ y definită prin conexiune serială. Conectarea în serie este o operație asociativă - puteți scrie P ; Q ; R ca o concatenare a trei ordine fără a introduce ambiguitate cu privire la modul de combinare a acestora în perechi, deoarece sunt paranteze ( P ; Q ); R & P ; ( Q ; R ) descrie aceeași ordine parțială. Totuși, această îmbinare nu este o operație comutativă , deoarece inversarea rolurilor lui P și Q va da o ordine parțială diferită, în care relațiile de ordine pentru perechile de elemente, unul din P , celălalt din Q , sunt inversate [1] .

Legătura paralelă a lui P și Q , scrisă P  || Q [7] , P + Q [2] sau P ⊕ Q [1] , este definită din unirea disjunctă a elementelor lui P și elementelor lui Q într-un mod similar. Dacă o pereche de elemente aparține în întregime lui P sau Q , ordinea rămâne aceeași ca și în P sau , respectiv, Q. Dacă un element x aparține lui P și un element y aparține lui Q , elementele x și y sunt incomparabile. Conexiunea paralelă este asociativă și comutativă [1] .

Clasa ordinelor parțiale seriale-paralele este setul de ordine parțiale care pot fi construite din ordine parțiale singleton folosind aceste două operații. În mod echivalent, o clasă este cel mai mic set de ordine parțiale care include o ordine parțială singleton și care este închisă sub operațiuni de conexiune serială și paralelă [1] [2] .

Ordonarea slabă este o ordine parțială serie-paralelă care rezultă dintr-o succesiune de operații de îmbinare în care sunt efectuate mai întâi toate operațiile de îmbinare paralelă, iar apoi rezultatele acestor operații sunt combinate cu numai operații secvențiale [2] .

Descriere prin subordini interzise

Un ordin parțial N cu patru elemente a , b , c și d și exact trei relații de ordine a ≤ b ≥ c ≤ d este un exemplu de gard (sau ordin în zig-zag). Diagrama lui Hasse este sub forma unei litere mari „N”. Această ordine nu este serie-paralelă, deoarece nu există nicio modalitate de a o descompune în secvențe de conexiuni paralele a două ordine parțiale mai mici. Un ordin parțial P se spune a fi liber de ordin N dacă nu există mulțimi de patru elemente în P astfel încât restricția lui P la aceste elemente este izomorfă cu N în sensul ordinii parțiale. Ordinele parțiale seriale-paralele sunt exact acele ordine parțiale finite fără ordine N-vide [1] [2] [3] .

Acest lucru implică imediat (deși acest lucru poate fi demonstrat direct) că orice restricție nevidă a unui ordin parțial serie-paralel este ea însăși un ordin parțial serie-paralel [1] .

Dimensiunea ordinală

Dimensiunea ordinală a unui ordin parțial P este dimensiunea minimă a realizărilor P , mulțimea prelungirilor liniare (liniarizări) de ordin P cu proprietatea că pentru oricare două elemente distincte x și y de ordin P , x ≤ y dacă și numai dacă x precede y în orice continuare liniară a implementării.

O definiție alternativă poate fi găsită pe Internet: „Cel mai mic număr de ordine liniare care dau o mulțime dată parțial ordonată la intersecție se numește (dimensiunea ordinală)”, de exemplu, în prelegerile lui Gurov S.I. [10] sau Kuznetsova S.O. [11] .

Comenzile parțiale seriale-paralele au o dimensiune care nu depășește două. Dacă P și Q au implementatori { L 1 ,  L 2 } și respectiv { L 3 ,  L 4 }, atunci { L 1 L 3 ,  L 2 L 4 } este implementatorul conexiunii seriale a lui P ; Q , iar { L 1 L 3 ,  L 4 L 2 } este implementatorul conexiunii paralele P  || Q [2] [3] . O ordine parțială este serial-paralelă dacă și numai dacă are un implementator în care una dintre cele două permutări este identică și cealaltă este separabilă .

Se știe că un ordin parțial P are dimensiunea de ordin doi dacă și numai dacă există un ordin conjugat Q pe aceleași elemente cu proprietatea că oricare două elemente distincte x și y sunt comparabile în exact unul dintre aceste ordine. În cazul ordinelor parțiale seriale-paralele, ordinea conjugată, care este ea însăși serială-paralelă, poate fi obținută prin efectuarea unei succesiuni de operații de îmbinare în aceeași ordine ca și pentru P pe aceleași elemente, dar în loc de îmbinare în serie, P folosește îmbinarea paralelă și invers. Mai strict, deși o ordine parțială poate avea ordine conjugate diferite, orice ordine conjugată a unei ordine parțiale serial-paralel trebuie să fie, de asemenea, serial-paralel [2] .

Relația cu teoria grafurilor

Orice ordine parțială poate fi reprezentată (de obicei neunic) printr-un graf aciclic direcționat care are o cale de la x la y pentru toate elementele x și y de ordin parțial pentru care x ≤ y . Graficele care reprezintă ordine parțiale seriale-paralele în acest fel sunt numite grafuri seriale-paralele cu vârfuri, iar reducerile lor tranzitive (grafice de ordine parțială care acoperă relațiile ) sunt numite grafuri seriale-paralele cu vârfuri minime 3] . Arborii direcționați și (cu o pereche de terminale) graficele paralel-seriale sunt exemple de grafice minime seriale-paralele. Astfel, ordinele parțiale serial-paralel pot fi folosite pentru a reprezenta relația de accesibilitate în arbori direcționați și grafice paralele [2] [3] .

Un grafic de comparabilitate de ordin parțial este un grafic nedirecționat cu vârfuri pentru fiecare element și o muchie nedirecționată pentru fiecare pereche de elemente distincte x , y dacă x ≤ y sau y ≤ x . Adică, este format dintr-un graf serial-paralel minim prin eliminarea orientării marginii . Graficul de comparabilitate a ordinului serial-paralel este un cograf - operațiile de îmbinare în ordine în serie și paralelă oferă operații pe graficul de comparabilitate care formează o uniune disjunctă a două subgrafe sau conectează două subgrafe prin toate marginile posibile. Aceste două operații sunt operațiunile de bază în definiția cografelor. În schimb, orice cograf este un grafic de comparabilitate de ordin parțial în serie-paralel. Dacă o ordine parțială are un cograf ca grafic de comparabilitate, atunci trebuie să fie o ordine parțială serial-paralelă, deoarece orice alt tip de ordine parțială are o subordine N, care trebuie să corespundă unei căi generate cu patru vârfuri în graficul său de comparabilitate. , iar astfel de căi sunt interzise în cografe [2] [4] .

Complexitate computațională

Puteți utiliza descrierea subordinea interzisă a ordinelor parțiale serial-paralel ca bază pentru un algoritm care verifică, în timp liniar dependent de numărul de perechi dintr-o relație, dacă o anumită relație binară este o ordine parțială serial-paralelă [2] [3] . Alternativ, dacă o comandă parțială este descrisă ca ordinea de accesibilitate a unui graf aciclic direcționat , este posibil să se testeze dacă este o ordine parțială serial-paralelă și, dacă da, să se calculeze închiderea sa tranzitivă în timp proporțional cu numărul de vârfuri și muchii în închiderea tranzitivă. Rămâne o întrebare deschisă dacă este posibil să se îmbunătățească timpul de recunoaștere a comenzilor de accesibilitate serial-paralel la liniar în dimensiunea graficului de intrare [12] .

Dacă o ordine parțială serial-paralelă este reprezentată ca un arbore de expresii care descrie execuția operațiilor în serie și paralele, atunci elementele ordinii parțiale pot fi reprezentate de frunzele arborelui de expresii. Compararea oricăror două elemente se poate face algoritmic prin găsirea strămoșului cel mai puțin comun dintre cele două frunze corespunzătoare. Dacă acest strămoș este o conexiune paralelă, cele două elemente sunt incomparabile, în caz contrar ordinea conexiunilor seriale ale operanzilor determină ordinea elementelor. În acest fel, o ordine parțială serie-paralelă a n elemente poate fi reprezentată în spațiul O( n ) pentru a determina orice valoare de comparat în timp O(1) [2] .

Problema verificării pentru două ordine parțiale date serial-paralel P și Q că P conține o restricție izomorfă la Q este NP-complet [3] .

Deși problema numărării numărului de extensii liniare ale unui ordin parțial arbitrar este #P-complet [13] , se poate arăta că poate fi rezolvată în timp polinomial pentru ordinele parțiale seriale-paralele. Și anume, dacă L ( P ) denotă numărul de extensii liniare de ordin parțial P , atunci L ( P ; Q ) = L ( P ) L ( Q ) și

[2] .

Aplicații

Mannila și Meek [14] au folosit ordinele parțiale seriale-paralele ca model pentru secvența evenimentelor din datele serii de timp . Ei au descris algoritmi de învățare automată pentru modele de inferență pentru acest tip și au demonstrat eficiența algoritmilor în generarea cerințelor de curs necesare pe baza datelor de înregistrare a studenților, precum și în modelarea modelelor de utilizare a browserului [6] .

Amer și colaboratorii [15] susțin că comenzile parțiale seriale-paralele sunt convenabile pentru modelarea cererilor de secvențiere a prezentărilor media . Ei au folosit formula pentru calcularea numărului de continuări liniare ale unei ordine parțiale serial-paralel ca bază pentru analiza algoritmilor de transmisie multimedia [7] .

Chaudhary și colaboratorii [16] au folosit comenzi parțiale seriale-paralele pentru a modela dependențele sarcinilor într- un flux de date de procesare a datelor în vrac pentru viziunea computerizată . Ei au arătat că atunci când se utilizează comenzi seriale-paralele pentru această sarcină, este posibil să se construiască eficient un program optim care atribuie diferite sarcini diferitelor procesoare ale unui sistem de calcul paralel pentru a optimiza debitul sistemului [8] .

Clasa de ordonări, ceva mai generală decât conceptul de ordine parțiale seriale-paralele, este dată de PQ-trees , structuri de date utilizate în algoritmi pentru verificarea dacă un graf este plan și pentru recunoașterea graficelor de interval [17] . Un nod P al unui arbore PQ permite toate ordonările posibile ale descendenților săi ca o conexiune paralelă în ordine parțiale, în timp ce un nod Q cere succesorilor să urmeze într-o ordine liniară fixă, cum ar fi ordinele parțiale secvențiale. Cu toate acestea, spre deosebire de ordinele parțiale seriale-paralele, arborii PQ vă permit să inversați ordinea liniară la orice nod al lui Q.

Note

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

Literatură