Serieparallel delrækkefølge

En seriel-parallel partiel rækkefølge  er et delvist ordnet sæt konstrueret af mindre seriel-parallelle partielle ordrer ved hjælp af to simple joinoperationer [1] [2] .

Seriel-parallelle partielle ordrer kan beskrives som N-ordensfrie endelige partielle ordrer. De har ordinær dimension højst to [1] [3] . Disse ordrer inkluderer svage rækkefølger og nåbarhedsrelationen i rettede træer og rettede parallel-sekventielle grafer [2] [3] . Sammenlignelighedsgraferne for seriel-parallelle partielle ordrer er kografer [2] [4] .

Seriel-parallelle partielle ordrer anvendes i planlægningsteori [5] , maskinlæring af hændelsessekvenser i tidsseriedata [6] , multimediedataoverførselssekvens [7] og gennemstrømningsmaksimering i datastrømme [ 8] .

Seriel-parallelle partielle ordrer kaldes også multitræer [4] . Dette navn er dog tvetydigt - multitræer kaldes også partielle ordener uden fire-elements underordner ("ruder") [9] , såvel som andre strukturer dannet af flere træer.

Definition

Lad P og Q være to delvist ordnede sæt. Seriel forbindelse af P og Q , skrevet P ; Q [7] , P * Q [2] , eller P ⧀ Q [1] , er en poset, hvis elementer er den usammenhængende forening af elementerne i P og Q . I P ; Q , to elementer x og y , der samtidig hører til P eller Q , har den samme ordensrelation, som de havde i henholdsvis P eller Q. For ethvert par x , y , hvor x tilhører P og y hører til Q , er der dog en yderligere ordensrelation x ≤ y defineret af seriel forbindelse. Seriel forbindelse er en associativ operation - du kan skrive P ; Q ; R som en sammenkædning af tre ordener uden at indføre tvetydighed om, hvordan man kombinerer dem i par, da parenteser ( P ; Q ); R & P ; ( Q ; R ) beskriver den samme delrækkefølge. Denne joinforbindelse er dog ikke en kommutativ operation , da vending af rollerne for P og Q vil give en anden delrækkefølge, hvor rækkefølgerelationerne for par af elementer, den ene fra P , den anden fra Q , er omvendt [1] .

Parallelforbindelse af P og Q , skrevet P  || Q [7] , P + Q [2] eller P ⊕ Q [1] , er defineret ud fra den disjunkte forening af elementer af P og elementer af Q på en lignende måde. Hvis et elementpar udelukkende tilhører P eller Q , forbliver rækkefølgen den samme, som den var i henholdsvis P eller Q. Hvis et element x hører til P , og et element y hører til Q , er elementerne x og y uforlignelige. Parallelforbindelse er associativ og kommutativ [1] .

Klassen af ​​seriel-parallelle delordrer er det sæt af delordrer, der kan bygges ud fra singleton-delordrer ved hjælp af disse to operationer. Tilsvarende er en klasse det mindste sæt af partielle ordrer, der inkluderer en singleton partiel orden, og som er lukket under serielle og parallelle forbindelsesoperationer [1] [2] .

Svag rækkefølge er en serie-parallel partiel rækkefølge, der er et resultat af en sekvens af joinoperationer, hvor alle parallelle joinoperationer først udføres, og derefter kombineres resultaterne af disse operationer med kun sekventielle operationer [2] .

Beskrivelse af forbudte underordner

En partiel orden N med fire elementer a , b , c og d og præcis tre ordensrelationer a ≤ b ≥ c ≤ d er et eksempel på et hegn (eller zigzag-rækkefølge). Hans Hasse-diagram er i form af et stort "N". Denne rækkefølge er ikke serieparallel, da der ikke er nogen måde at opdele den i sekvenser af parallelle forbindelser af to mindre partielle ordener. En partiel orden P siges at være fri for N-orden, hvis der ikke er nogen sæt af fire elementer i P , således at begrænsningen af ​​P til disse elementer er isomorf til N i betydningen af ​​den partielle orden. Seriel-parallelle partielle ordrer er præcis de ikke-tomme endelige N-ordensfrie partielle ordrer [1] [2] [3] .

Dette indebærer umiddelbart (selvom dette kan bevises direkte), at enhver ikke-tom begrænsning af en serie-parallel partiel orden i sig selv er en serie-parallel partiel orden [1] .

Ordinal dimension

Ordinaldimensionen af en partiel orden P er minimumsstørrelsen af ​​realiseringer P , sættet af lineære udvidelser (lineariseringer) af orden P med egenskaben, at for alle to distinkte elementer x og y af orden P , x ≤ y hvis og kun hvis x går forud for y i enhver lineær fortsættelse af implementeringen.

En alternativ definition kan findes på internettet: "Det mindste antal lineære ordrer, der giver et givet delvist ordnet sæt ved skæringspunktet, kaldes dets (ordinære dimension)", for eksempel i forelæsninger af Gurov S.I. [10] eller Kuznetsova S.O. [11] .

Seriel-parallelle delordrer har en dimension, der ikke overstiger to. Hvis P og Q har implementere henholdsvis { L 1 ,  L 2 } og { L 3 ,  L 4 }, så er { L 1 L 3 ,  L 2 L 4 } implementatoren af ​​P 's serielle forbindelse ; Q , og { L 1 L 3 ,  L 4 L 2 } er implementeren af ​​parallelforbindelsen P  || Q [2] [3] . En delordre er seriel-parallel, hvis og kun hvis den har en implementer, hvor den ene af de to permutationer er identisk, og den anden kan adskilles .

Det er kendt, at en partiel orden P har ordensdimension to, hvis og kun hvis der eksisterer en konjugeret orden Q på de samme elementer med den egenskab, at alle to distinkte elementer x og y er sammenlignelige i nøjagtig en af ​​disse ordener. I tilfælde af seriel-parallelle partielle ordrer, kan den konjugerede rækkefølge, som i sig selv er seriel-parallel, opnås ved at udføre en sekvens af joinoperationer i samme rækkefølge som for P på de samme elementer, men i stedet for seriel join, P bruger parallel sammenføjning og omvendt. Mere strengt, selvom en partiel rækkefølge kan have forskellige konjugerede rækkefølger, skal enhver konjugeret rækkefølge af en seriel-parallel partiel rækkefølge også være seriel-parallel [2] .

Forholdet til grafteori

Enhver partiel orden kan repræsenteres (normalt ikke-entydig) af en rettet acyklisk graf , der har en sti fra x til y for alle elementer x og y i den partielle orden, for hvilke x ≤ y . Grafer, der repræsenterer seriel-parallelle partielle ordrer på denne måde, kaldes vertex seriel-parallelle grafer og deres transitive reduktioner (grafer af partiel orden , der dækker relationer ) kaldes minimal vertex seriel-parallelle grafer 3] . Rettede træer og (med ét terminalpar) parallel-serielle grafer er eksempler på minimale seriel-parallelle grafer. Således kan seriel-parallelle partielle ordrer bruges til at repræsentere nåbarhedsrelationen i rettede træer og parallelle grafer [2] [3] .

En partiel ordens sammenlignelighedsgraf er en urettet graf med toppunkter for hvert element og en urettet kant for hvert par af særskilte elementer x , y hvis x ≤ y eller y ≤ x . Det vil sige, at den er dannet ud fra en minimal seriel-parallel graf ved at slippe af med kantorienteringen . Seriel-parallel-ordens sammenlignelighedsgrafen er en kograf - seriel- og parallel-ordens-sammenføjningsoperationer giver operationer på sammenlignelighedsgrafen, der danner en usammenhængende forening af to undergrafer eller forbinder to undergrafer med alle mulige kanter. Disse to operationer er de grundlæggende operationer i definitionen af ​​kografer. Omvendt er enhver kograf en seriel-parallel sammenlignelighedsgraf med delvis orden. Hvis en delordre har en kograf som sin sammenlignelighedsgraf, så skal den være en seriel-parallel delrækkefølge, da enhver anden form for delordre har en N-underord, som skal svare til en genereret sti med fire hjørner i dens sammenlignelighedsgraf , og sådanne stier er forbudt i kografer [2] [4] .

Beregningsmæssig kompleksitet

Du kan bruge den forbudte underordensbeskrivelse af seriel-parallelle partielle ordrer som grundlag for en algoritme, der i tid lineært afhængigt af antallet af par i en relation kontrollerer, om en given binær relation er en seriel-parallel partiel orden [2] [3] . Alternativt, hvis en delordre beskrives som rækkefølgen for nåbarhed af en rettet acyklisk graf , er det muligt at teste, om det er en seriel-parallel delordre, og hvis det er tilfældet, beregne dens transitive lukning i tid proportionalt med antal hjørner og kanter i den transitive lukning. Det er fortsat et åbent spørgsmål, om det er muligt at forbedre genkendelsestiden for seriel-parallelle rækkevidde ordrer til lineære i størrelsen af ​​inputgrafen [12] .

Hvis en seriel-parallel partiel rækkefølge er repræsenteret som et udtrykstræ , der beskriver udførelsen af ​​serielle og parallelle operationer, så kan elementerne i den partielle rækkefølge repræsenteres af bladene i udtrykstræet. Sammenligning af alle to elementer kan udføres algoritmisk ved at finde den mindst fælles forfader af de tilsvarende to blade. Hvis denne forfader er en parallelforbindelse, er de to elementer uforlignelige, ellers bestemmer rækkefølgen af ​​operandernes serielle forbindelser rækkefølgen af ​​elementerne. På denne måde kan en serie-parallel partiel rækkefølge af n elementer repræsenteres i O( n ) rum for at bestemme enhver værdi, der skal sammenlignes i O(1) [2] tid .

Problemet med at kontrollere for to givne seriel-parallelle partielle ordrer P og Q , at P indeholder en restriktion isomorf til Q , er NP-komplet [3] .

Selvom problemet med at tælle antallet af lineære forlængelser af en vilkårlig partiel orden er #P-komplet [13] , kan det påvises, at det kan løses i polynomisk tid for seriel-parallelle partielle ordener. Nemlig, hvis L ( P ) angiver antallet af lineære forlængelser af den partielle orden P , så L ( P ; Q )= L ( P ) L ( Q ) og

[2] .

Ansøgninger

Mannila og Meek [14] brugte seriel-parallelle partielle ordrer som en model for rækkefølgen af ​​begivenheder i tidsseriedata . De beskrev maskinlæringsalgoritmer for inferensmodeller for denne type og demonstrerede effektiviteten af ​​algoritmerne til at generere krævede kursuskrav baseret på elevregistreringsdata, såvel som i modellering af browserbrugsmønstre [6] .

Amer et al . [15] hævder , at seriel-parallelle partielle ordrer er praktiske til modellering af mediepræsentationssekvenseringsanmodninger . De brugte formlen til at beregne antallet af lineære fortsættelser af en seriel-parallel partiel orden som grundlag for analysen af ​​multimedietransmissionsalgoritmer [7] .

Chaudhary et al . [16] brugte seriel-parallelle partielle ordrer til at modellere opgaveafhængigheder i en datastrøm af bulkdatabehandling til computersyn . De viste, at når man bruger seriel-parallelle ordrer til denne opgave, er det muligt effektivt at konstruere en optimal tidsplan, der tildeler forskellige opgaver til forskellige processorer i et parallelt computersystem for at optimere systemets gennemstrømning [8] .

Klassen af ​​ordener, noget mere generel end begrebet seriel-parallelle partielle ordrer, er givet af PQ-træer , datastrukturer, der bruges i algoritmer til at kontrollere, om en graf er plan og til at genkende intervalgrafer [17] . En node P i et PQ-træ tillader alle mulige rækkefølger af dets efterkommere som en parallel forbindelse i delrækkefølger, mens en node Q kræver, at efterfølgerne følger i en fast lineær rækkefølge som sekventielle delrækkefølger. I modsætning til seriel-parallelle partielle ordrer giver PQ-træer dig dog mulighed for at vende den lineære rækkefølge ved enhver node af Q .

Noter

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

Litteratur