Helitaanka ku-tiirsanaanta shaqeynta ee xogta waxaa loo adeegsadaa dhinacyo kala duwan oo falanqaynta xogta ah: maareynta xogta, nadiifinta xogta, injineernimada beddelka xogta iyo sahaminta xogta. Waxaan mar hore daabacnay ku tiirsanaanta laftooda Anastasia Birillo iyo Nikita Bobrov. Markan, Anastasia, oo ka qalin jabisay Xarunta Sayniska Kombiyuutarka sanadkan, waxay la wadaagtaa horumarinta shaqadan oo qayb ka ah shaqada cilmi-baarista ee ay ku difaacday xarunta.
Doorashada hawsha
Markii aan wax ka baranayey xarunta CS, waxaan bilaabay inaan si qoto dheer u barto xogta macluumaadka, kuwaas oo ah, raadinta ku tiirsanaanta shaqeynta iyo kala duwanaanta. Mawduucan wuxuu la xiriiray mowduuca shaqada koorsada ee jaamacadda, sidaa darteed anigoo ka shaqeynaya shaqada koorsada, waxaan bilaabay inaan akhriyo maqaallo ku saabsan ku-tiirsanaanta kala duwan ee xogta macluumaadka. Waxaan qoray dib u eegis ku saabsan aaggan - mid ka mid ah kii iigu horreeyay Ingiriisi oo u gudbiyay shirka SEIM-2017. Aad ayaan ugu farxay markii aan ogaaday in la aqbalay ka dib, waxaana go'aansaday in aan si qoto dheer u galo mawduuca. Fikradda lafteedu maaha mid cusub - waxay bilowday in dib loo isticmaalo 90-meeyadii, laakiin xitaa hadda waxaa loo isticmaalaa meelo badan.
Intii lagu jiray simistarka labaad ee xarunta, waxaan bilaabay mashruuc cilmi baaris ah si aan u wanaajiyo algorithms si loo helo ku tiirsanaanta shaqeynta. Waxay si wadajir ah ula shaqeysay arday ka qalin jabisay Jaamacadda St. Petersburg Nikita Bobrov ee JetBrains Research.
Kakanaanta xisaabinta ee raadinta ku-tiirsanaanta shaqeynta
Dhibaatada ugu weyni waa kakanaanta xisaabinta. Tirada ku tiirsanaanta ugu yar ee suurtogalka ah waxay ku xaddidan tahay korka qiimaha 
halkaas oo 
- tirada sifooyinka miiska. Waqtiga hawlgalka ee algorithms waxay ku xiran tahay tirada sifooyinka, laakiin sidoo kale tirada safafka. Sannadihii 90-aadkii, algorithms-ka raadinta sharciga federaaliga ee kombuyutarka caadiga ah wuxuu farsamayn karaa xogta ka kooban ilaa 20 sifooyin iyo tobanaan kun oo saf ah ilaa dhowr saacadood gudahood. Algorithms-yada casriga ah ee ku shaqeeya soo-saareyaasha xudunta badan waxay ogaadaan ku-tiirsanaanta xogta xogta oo ka kooban boqollaal sifooyin (ilaa 200) iyo boqollaal kun oo saf ah qiyaastii isku mar. Si kastaba ha ahaatee, tani kuma filna: wakhtigan oo kale waa mid aan la aqbali karin badi codsiyada dhabta ah ee aduunka. Sidaa darteed, waxaanu samaynay habab lagu dedejinayo algorithms jira.
Nidaamyada kaydinta ee isgoysyada qaybinta
Qaybtii hore ee shaqada, waxaanu soo saarnay qorshayaal kaydineed oo loogu talagalay fasal algorithms-yada isticmaala habka isgoysyada qaybinta. Qayb ka mid ah sifada waa liisyo liis ah, halkaas oo liis kastaa ka kooban yahay lambarro xariiq oo leh qiime isku mid ah sifada la bixiyay. Liis kasta oo noocaas ah waxaa loo yaqaan koox. Algorithms-yada casriga ah oo badan ayaa isticmaala qaybo si ay u go'aamiyaan in ku-tiirsanaanta la hayo iyo in kale, kuwaas oo ah, waxay u hoggaansamaan lemma: Ku-tiirsanaanta 
la qabto hadday 
. Halkan 
qayb ayaa loo qoondeeyey iyo fikradda cabbirka qaybinta ayaa la isticmaalaa - tirada kooxaha ku jira. Algorithm-yada isticmaala qaybaha, marka ku-tiirsanaanta la jebiyo, waxay ku daraan sifooyin dheeraad ah dhinaca bidix ee ku-tiirsanaanta, ka dibna dib u xisaabiya, iyagoo fulinaya hawlgalka isgoysyada qaybaha. Hawlgalkan waxaa lagu magacaabaa takhasuska maqaallada. Laakiin waxaan ogaanay in qaybaha ku-tiirsanaanta oo kaliya lagu hayn karo ka dib dhowr wareeg oo takhasus ah ayaa si firfircoon dib loogu isticmaali karaa, taas oo si weyn u yareyn karta wakhtiga socodka algorithms, maadaama hawlgalka isgoysku uu qaali yahay.
Sidaa darteed, waxaan soo jeedinay heuristic ku salaysan Shannon Entropy iyo Ginny Uncertainty, iyo sidoo kale mitirkayaga, kaas oo aan ugu yeernay Dib-u-celinta Entropy. Waa wax ka beddel yar oo Shannon Entropy ah oo kordhiya marka ay sii korodho kala-duwanaanta xogta xogta. Heuristic-ka la soo jeediyay waa sida soo socota:
waa 
- heerka gaarka ah ee qaybta dhawaan la xisaabiyay 
iyo 
waa dhexdhexaadka darajooyinka gaarka ah ee sifooyinka gaarka ah. Dhammaan saddexda mitir ee kor lagu sharraxay waxa loo tijaabiyey mitir gaar ah. Waxa kale oo aad ogaan kartaa in ay jiraan laba wax-beddeleyaal ee heuristic. Midka kowaad wuxuu muujinayaa sida ugu dhow ee qaybta hadda ay ugu dhowdahay furaha aasaasiga ah waxayna kuu ogolaaneysaa inaad kaydiso ilaa xad weyn qaybahaas ka fog furaha suurtagalka ah. Wax ka beddelka labaad wuxuu kuu oggolaanayaa inaad la socoto joogitaanka kaydka oo markaa ku dhiirigeliso ku darista qaybo badan khasnadda haddii meel bannaan la heli karo. Xalka guusha leh ee dhibaatadan ayaa noo ogolaatay inaan ku dedejinno PYRO algorithm 10-40%, iyadoo ku xiran xogta xogta. Waxaa xusid mudan in algorithm-ka PYRO uu yahay kan ugu guulaha badan goobtan.
Jaantuska hoose waxaad ku arki kartaa natiijooyinka ku-dhaqanka heuristic-ka la soo jeediyay marka la barbar dhigo habka kaydinta qadaadiic-rogid ee aasaasiga ah. dhidibka X waa logarithmic.
Hab kale oo lagu kaydiyo qaybaha
Waxaan markaas soo jeedinay hab kale oo lagu kaydiyo qaybaha. Qaybuhu waa kooxo kooxo ah, kuwaas oo mid walba uu kaydiyo tiro tuples ah oo leh qiime isku mid ah sifooyin gaar ah. Kooxahan waxaa laga yaabaa inay ka koobnaan karaan taxane dheer oo lambarro tuple ah, tusaale ahaan haddii xogta shaxda ku jirta la dalbado. Sidaa darteed, waxaanu soo jeedinay nidaam isku-buufin ah oo lagu kaydinayo qaybaha, kuwaas oo ah kaydinta muddada u dhaxaysa qiyamka ee qaybaha qaybaha:
$$muujin$$pi(X) = {{brace hoose{1, 2, 3, 4, 5}_{barafka kowaad}, dhabarka hoose{7, 8}_{barafka labbaad}, 10}} \ hoos hoose{ cadaadis} \ pi(X) = {{sarka hoose{$, 1, 5}_{First~interval}, dhabarka hoose{7, 8}_{labaad~barafka}, 10}}$$muujin$$
Habkani wuxuu awooday inuu yareeyo isticmaalka xusuusta inta lagu jiro hawlgalka TANE algorithm laga bilaabo 1 ilaa 25%. Algorithm-ka TANE waa algorithm caadiga ah ee raadinta sharciyada federaalka; waxay isticmaashaa qaybo inta lagu jiro shaqadeeda. Iyada oo qayb ka ah dhaqanka, algorithmamka TANE ayaa la doortay, maadaama ay aad uga fududayd in la hirgeliyo kaydinta dhexda dhexdeeda marka loo eego, tusaale ahaan, PYRO si loo qiimeeyo in habka la soo jeediyay uu shaqaynayo. Natiijooyinka la helay waxaa lagu soo bandhigay sawirka hoose. dhidibka X waa logarithmic.
Shirka ADBIS-2019
Iyada oo ku saleysan natiijooyinka cilmi-baarista, Sebtembar 2019 waxaan daabacay maqaal Shirkii 23-aad ee Yurub ee Horumarka Xogta iyo Nidaamyada Macluumaadka (ADBIS-2019). Intii lagu guda jiray bandhigga, shaqada waxaa xusay Bernhard Thalheim, oo ah qof muhiim u ah goobta macluumaadka. Natiijooyinka cilmi-baaristu waxay aasaaseen qoraalkayga qalin-jabinta ee shahaadada mastarka ee xisaabta iyo makaanikada ee Jaamacadda Gobolka St. Waxaa intaa dheer, natiijadu waxay muujisay in hababka la soo jeediyay ay yihiin kuwo caalami ah, tan iyo labadaba labadaba algorithms, labada habba, hoos u dhac weyn oo isticmaalka xusuusta ayaa la arkay, iyo sidoo kale hoos u dhac weyn oo ku yimid wakhtiga hawlgalka ee algorithms.
Source: www.habr.com
