Sorozat-párhuzamos részrendelés

A soros-párhuzamos részrendelés  egy részlegesen rendezett halmaz , amely kisebb soros-párhuzamos részrendelésekből két egyszerű összekapcsolási művelettel [1] [2] épül fel .

A soros-párhuzamos részrendelések N-rendű véges részrendelésekként írhatók le. Sorozati méretük legfeljebb kettő [1] [3] . Ezek a sorrendek közé tartoznak a gyenge rendezések és az elérhetőségi reláció irányított fákban és irányított párhuzamos-szekvenciális gráfokban [2] [3] . A soros-párhuzamos részrendek összehasonlíthatósági gráfjai kográfok [2] [4] .

A soros-párhuzamos részrendeléseket alkalmazzák az ütemezési elméletben [5] , az eseménysorozatok gépi tanulásában az idősoros adatokban [6] , a multimédiás adatátviteli sorrendben [7] és az adatfolyamokban az áteresztőképesség maximalizálásában [8] .

A soros-párhuzamos részrendeléseket többfáknak is nevezik [4] . Ez az elnevezés azonban kétértelmű – a multifákat négyelemes alrendek ("gyémántok") nélküli részleges rendeknek is nevezik [9] , valamint más, több fából kialakított struktúrákat is.

Definíció

Legyen P és Q két részlegesen rendezett halmaz. P és Q soros csatlakozása, P írva ; Q [7] , P * Q [2] vagy P ⧀ Q [1] egy olyan póz, amelynek elemei P és Q elemeinek diszjunkt uniója . In P ; Q , két x és y elem , amelyek egyidejűleg tartoznak P -hez vagy Q -hoz , ugyanazzal a sorrendi összefüggéssel rendelkeznek, mint P -ben vagy Q -ban. Azonban minden olyan x , y párhoz, amelyben x P -hez , y pedig Q -hoz tartozik , létezik egy további x ≤ y rendű reláció , amelyet soros kapcsolat határoz meg. A soros kapcsolat asszociatív művelet - írhat P ; Q ; R mint három rend összefűzése anélkül, hogy kétértelművé válna, hogyan lehet őket párokban kombinálni, mivel zárójelek ( P ; Q ); R & P ; ( Q ; R ) ugyanazt a részleges sorrendet írja le. Ez az összekapcsolás azonban nem kommutatív művelet , mivel P és Q szerepének felcserélése eltérő részleges sorrendet ad, amelyben az egyik P -ből , a másik Q -ból származó elempárok sorrendisége megfordul [1] .

P és Q párhuzamos kapcsolása , P  || Q [7] , P + Q [2] vagy P ⊕ Q [1] , P elemeinek és Q elemeinek diszjunkt uniójából definiálható hasonló módon. Ha egy elempár teljes egészében P -hez vagy Q -hoz tartozik , akkor a sorrend ugyanaz marad, mint P -ben vagy Q -ban volt. Ha egy x elem P -hez, egy y elem pedig Q -hoz tartozik , akkor az x és y elemek összehasonlíthatatlanok. A párhuzamos kapcsolat asszociatív és kommutatív [1] .

A soros-párhuzamos részrendelések osztálya a részmegbízások azon halmaza, amelyek e két művelet segítségével egyszemélyes részrendelésekből építhetők fel. Ezzel egyenértékűen az osztály a részleges rendelések legkisebb halmaza, amely egyetlen részleges sorrendet tartalmaz, és amely soros és párhuzamos csatlakozási műveletek alatt zárva van [1] [2] .

Gyenge rendezés egy sor-párhuzamos részsorrend, amely összekapcsolási műveletek sorozatából adódik, amelyben először minden párhuzamos összekapcsolási műveletet végrehajtanak, majd ezen műveletek eredményeit csak egymás utáni műveletekkel kombinálják [2] .

Leírás tiltott alrendekkel

A négy a , b , c és d elemű N részleges rend és pontosan három a ≤ b ≥ c ≤ d rendű reláció egy kerítés (vagy cikcakk sorrend) példája . Hasse-diagramja nagy "N" betűvel készült. Ez a sorrend nem sorpárhuzamos, mivel nincs mód két kisebb részrend párhuzamos kapcsolódási sorozataira bontani. Egy P részleges rendet N-rendű szabadnak mondunk, ha P -ben nincs négy elemből álló halmaz úgy, hogy P ezekre az elemekre való korlátozása a részleges rend értelmében N - nel izomorf . A soros-párhuzamos részrendelések pontosan azok a nem üres véges N-rendű részrendelések [1] [2] [3] .

Ebből azonnal következik (bár ez közvetlenül bebizonyítható), hogy egy sorpárhuzamos részrend bármely nem üres megszorítása maga is sorozatpárhuzamos részrend [1] .

Sorrendi méret

A P részleges rend ordinális mérete a P megvalósítások minimális mérete, a P rendű lineáris kiterjesztések (linearizációk)halmaza,hogy bármely két különböző P rendű x és y elemre x ≤ y akkor és csak akkor, ha x megelőzi y -t a megvalósítás bármely lineáris folytatásában.

Alternatív definíció található az interneten: „Azt a legkisebb számú lineáris sorrendet, amely egy adott részben rendezett halmazt ad a metszéspontban, annak (sorrendi dimenziójának) nevezzük”, például Gurov S.I. előadásaiban. [10] vagy Kuznetsova S.O. [11] .

A soros-párhuzamos részrendelések mérete nem haladja meg a kettőt. Ha P -nek és Q - nak van { L 1 ,  L 2 } és { L 3 ,  L 4 } implementere, akkor { L 1 L 3 ,  L 2 L 4 } a P soros kapcsolatának megvalósítója ; Q , és { L 1 L 3 ,  L 4 L 2 } a P  ||  párhuzamos kapcsolat megvalósítója . Q [2] [3] . Egy részleges sorrend akkor és csak akkor soros-párhuzamos, ha olyan implementátorral rendelkezik, amelyben a két permutáció egyike azonos, a másik pedig elválasztható .

Ismeretes, hogy a P részleges rendnek akkor és csak akkor van második sorrendje, ha ugyanazon az elemeken létezik Q konjugált sorrend, amelynek tulajdonsága, hogy bármely két különálló x és y elem pontosan az egyik sorrendben összehasonlítható. Soros-párhuzamos részrendek esetén a konjugált sorrendet, amely maga is soros-párhuzamos, úgy kaphatjuk meg, hogy egy összekapcsolási műveletsort hajtunk végre ugyanabban a sorrendben, mint P esetén ugyanazokon az elemeken, de soros összekapcsolás helyett P. párhuzamos csatlakozást használ.és fordítva. Szigorúbban, bár egy részleges sorrendnek lehetnek különböző konjugált sorrendjei, a soros-párhuzamos részleges konjugált sorrendnek szintén soros-párhuzamosnak kell lennie [2] .

Kapcsolat a gráfelmélettel

Bármely részleges sorrend ábrázolható (általában nem egyedi módon) egy irányított aciklikus gráf segítségével, amelynek x és y közötti útvonala van az összes olyan részleges rendű x és y elem számára, amelyekre x ≤ y . Az ilyen módon soros-párhuzamos részrendeket ábrázoló gráfokat csúcssoros-párhuzamos gráfoknak, a tranzitív redukcióikat ( a relációkat lefedő részleges rendű gráfokat ) pedig minimális csúcsú soros-párhuzamos gráfoknak nevezzük 3] . Az irányított fák és (egy terminálpárral) párhuzamos-soros gráfok példák a minimális soros-párhuzamos gráfokra. Így a soros-párhuzamos részrendek felhasználhatók az elérhetőségi reláció reprezentálására irányított fákban és párhuzamos gráfokban [2] [3] .

A részleges sorrendű összehasonlíthatósági gráf egy irányítatlan gráf , amelynek minden elemének csúcsai vannak, és minden egyes x , y különálló elempárhoz egy irányítatlan él , ha x ≤ y vagy y ≤ x . Azaz egy minimális soros- párhuzamos gráfból alakítjuk ki az élorientációtól való megszabadulással . A soros-párhuzamos sorrendű összehasonlítási gráf egy kográf – a soros és párhuzamos párhuzamos sorrendű összekapcsolási műveletek olyan műveleteket adnak az összehasonlíthatósági gráfon, amelyek két részgráf diszjunkt unióját alkotják, vagy két részgráfot kapcsolnak össze minden lehetséges éllel. Ez a két művelet az alapműveletek a kográfok meghatározásában. Ezzel szemben bármely kográf egy soros-párhuzamos parciális sorrendű összehasonlíthatósági gráf. Ha egy részleges sorrendnek kográfja van az összehasonlíthatósági gráfban, akkor annak soros-párhuzamos részrendnek kell lennie, mivel minden más részleges rendnek van N-alrendje, amelynek meg kell felelnie egy generált útvonalnak, amelynek összehasonlíthatósági gráfjában négy csúcsa van. , és az ilyen utak tilosak a kográfokban [2] [4] .

Számítási összetettség

A soros-párhuzamos részrendelések tiltott alrendleírását használhatja egy olyan algoritmus alapjául, amely egy relációban lévő párok számától lineárisan időben ellenőrzi, hogy egy adott bináris reláció soros-párhuzamos részrend-e [2] [3] . Alternatív megoldásként, ha egy részleges sorrendet egy irányított aciklikus gráf elérhetőségi sorrendjeként írunk le , akkor tesztelhető, hogy soros-párhuzamos részleges sorrendről van-e szó, és ha igen, akkor kiszámítható a tranzitív zárása a csúcsok és élek száma a tranzitív lezárásban. Továbbra is nyitott kérdés, hogy lehetséges-e a soros-párhuzamos elérhetőségi megbízások felismerési idejét lineárisra javítani a bemeneti gráf méretében [12] .

Ha egy soros-párhuzamos parciális sorrendet a soros és párhuzamos műveletek végrehajtását leíró kifejezésfaként ábrázolunk, akkor a részleges sorrend elemei a kifejezésfa leveleivel ábrázolhatók. Bármely két elem összehasonlítása elvégezhető algoritmikusan úgy, hogy megtaláljuk a megfelelő két levél legkevésbé közös ősét . Ha ez az ős párhuzamos kapcsolat, akkor a két elem összehasonlíthatatlan, ellenkező esetben az operandusok soros kapcsolatainak sorrendje határozza meg az elemek sorrendjét. Ily módon n elemből álló sorozat-párhuzamos részrend ábrázolható O( n ) térben, hogy meghatározhassunk bármilyen összehasonlítandó értéket O(1) [2] időben .

Az a probléma, hogy két adott soros-párhuzamos P és Q parciális rend esetén ellenőrizzük, hogy P tartalmaz egy Q - ra izomorf restrikciót , NP-teljes [3] .

Bár egy tetszőleges részrend lineáris kiterjesztései számának számolásának problémája #P-teljes [13] , kimutatható, hogy soros-párhuzamos részrendek esetén polinomiális időben is megoldható. Ugyanis ha L ( P ) a P részleges rendű lineáris kiterjesztések számát jelöli , akkor L ( P ; Q )= L ( P ) L ( Q ) ill.

[2] .

Alkalmazások

Mannila és Meek [14] soros-párhuzamos részrendeket használt modellként az idősoros adatok eseménysorozatához . Leírták a gépi tanulási algoritmusokat az ilyen típusú következtetési modellekhez, és bemutatták az algoritmusok hatékonyságát a hallgatói regisztrációs adatok alapján szükséges kurzuskövetelmények generálásában, valamint a böngészőhasználati minták modellezésében [6] .

Amer és munkatársai [15] azzal érvelnek, hogy a soros-párhuzamos részrendelések kényelmesek a médiabemutatók szekvenálási kérelmeinek modellezéséhez. A multimédiás átviteli algoritmusok elemzésének alapjául a soros-párhuzamos részrend lineáris folytatásainak számítására szolgáló képletet vették alapul [7] .

Chaudhary és munkatársai [16] soros-párhuzamos részleges sorrendet alkalmaztak a feladatfüggőségek modellezésére a számítógépes látás céljára szolgáló tömeges adatfeldolgozás adatfolyamában . Megmutatták, hogy soros-párhuzamos rendelések felhasználásával erre a feladatra hatékonyan lehet olyan optimális ütemezést készíteni, amely különböző feladatokat rendel egy párhuzamos számítási rendszer különböző processzoraihoz a rendszer átviteli sebességének optimalizálása érdekében [8] .

A rendezések osztályát, amely valamivel általánosabb, mint a soros-párhuzamos részrendek fogalma, a PQ-fák adják meg , olyan adatstruktúrák, amelyeket a gráf síkbeliségének ellenőrzésére és az intervallumgráfok felismerésére használnak [17] . A PQ-fa P csomópontja lehetővé teszi leszármazottainak minden lehetséges sorrendjét, például a részleges sorrendben történő párhuzamos kapcsolatot, míg a Q csomópont megköveteli, hogy az utódok egy rögzített lineáris sorrendben kövessék, mint a szekvenciális részleges sorrendek. A soros-párhuzamos részleges sorrendekkel ellentétben azonban a PQ-fák lehetővé teszik a lineáris sorrend megfordítását a Q bármely csomópontjában .

Jegyzetek

  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 és Zacks 1994 , p. 330–336.
  10. ↑ Gurov, 2012 , p. 111 Definíció 3.14.
  11. ↑ Kuznyecov .
  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 és Lueker 1976 , p. 335–379.

Irodalom