Mavzu: Qismiy pretsedentli algoritmni texnik tashxis masalasiga qo’llash

БАҲОЛАРНИ ҲИСОБЛАШ АЛГОРИТМЛАРИДА МАНТИҚИЙ КОРРЕКЦИЯЛАШ ПРОЦЕДУРАЛАРИ

М. Х. Худайбердиев, Д. А. Хамроев

Муҳаммад ал-Хоразмий номидаги Тошкент ахборот технологиялари университети ҳузуридаги ахборот коммуникация технологиялари илмий инновацион маркази

Муҳаммад ал-Хоразмий номидаги Тошкент ахборот технологиялари университети

Тимсолларни аниқлашнинг эвристик алгоритмлари устида коррекцион процедураларни қуриш алгебраик ёндашув билан боғлиқ бўлиб, таниб олиш операторини қўшиш ва скалярга кўпайтириш амалларини бажаришдан иборат. Тимсолларни аниқлаш алгоритмлари устида амалга ошириладиган операциялар худди информацион матрицалар устида амалга ошириш каби қаралади. Бироқ, агар таниб олиш операторлари тўплами чизиқли вектор фазо шаклида бўлса, у ҳолда информацион матрицада ундан яхши операция йўқ [1]. Шунга қарамасдан, информацион матрицалар тўплами устида кўп ўринли операциялардан фойдаланилади, қайсики самарали тимсолларни аниқлаш алгоритмларини синтез қилувчи воситани яратиш имконини берувчи. Бу жараён бевосита кириш билан боғлиқ бўлиб, натижалар таниб олинаётган объект билан боғлиқ бўлмаган ҳолда чегараланган миқдордаги алгоритмларни ўрганади.

Соддалик учун синфлаштиришда инкор мавжуд бўлмаган ҳолни кўрайлик. N та 𝐴¹, 𝐴², ... , 𝐴^𝑛 алгоритмлар коллективи берилган бўлсин,

^{𝑘 𝑘} ̅̅̅̅̅

𝐴 (𝐼,𝑆 ,...,𝑆 ) = ‖𝛽 ‖ ,𝑘 = 1,𝑛. 𝑆 ,...,𝑆 мажмуа 𝑃 ,...,𝑃 придикатлар

1𝑞_{𝑖𝑗𝑞×𝑙} 1𝑞 1𝑙

^𝑘 ̅̅̅̅̅

тизимида ‖𝛼_𝑖𝑗‖ информацион матрица бўлсин. {‖𝛽_𝑖𝑗‖_𝑞×l, 𝑘 = 1, 𝑛, ‖𝛼_𝑖𝑗‖_𝑞×l} матрицалар тўпламини l маълум бир қисм (барчасини эмас)

̅̅̅̅̅

𝑓(𝑦 ,𝑦 ,...,𝑦 ),𝑗 = 1,l буль фукциялар орқали аниқлайди. Бунда

𝑗12 𝑛

- 269 -

^12𝑛̅̅̅̅̅ ^𝑛

𝑓(𝛽 ,𝛽 ,...,𝛽 )=𝛼 ,𝑖=1,𝑞,ва𝑓(𝑦,𝑦,...,𝑦)функция2 −𝑞тўпламни

𝑗 𝑖𝑗 𝑖𝑗 _𝑖𝑗 𝑖𝑗 𝑗 1 2 𝑛

қолган қисмида аниқланмайди. Асосий вазифаси 𝐸^𝑛 дискрет бирлик кубни

тўлиқ аниқловчи функцияни аниқлаб олишдан иборат бўлиб, бу функцияни

оптимал танлаш ва маълум бир қисмда бир қийматлик мосликни таъминлаб

бериши ҳамда “мазмунан изохланган” қўшимча шарт максимал амалга

оширилади. Агар унга ўхшаш функция қурилса, у ҳолда таниб олиш жараёни

_̃𝑡 ′′ ′

учун ихтиёрий равишда 𝑆 ={𝑆₁,𝑆₂,...,𝑆_𝑡} янги объектлар танланмаси

қуйидаги схемада 𝐴¹,𝐴²,...,𝐴^𝑛 алгоритмлар билан мантиқий коррекциялаш келтирилган.

Мантиқий коррекцияловчи типларни танлашни ва қидириш

усулларининг турли-туман ёндашувлари мавжуд. Мисол учун “монотон

мантиқий корректор” келтириш мумкин. Бу ерда асосий ғоя қуйидагича. 𝐾 𝑗

синфга кирувчи 𝑆 объект олдиндан маълум ва бу 𝐴_𝑡1 , 𝐴_𝑡2 , ... , 𝐴_𝑡𝑘 синф алгоритмлари натижаларида кузатилган бўлсин. У ҳолда, агар 𝐾 синфга

кирувчи янги 𝑆′ объект олиниб ва мазкур алгоритмлар ташқари 𝐴_𝑡,𝑡∉

{𝑖 , ... , 𝑖 } орқали ҳам тўғри амалга оширса, у ҳолда 𝑆′ ∈ 𝐾 эканлиги табийки 1𝑘𝑗

коллектив ҳолда қарор қабул қилинган дейилади.

Алгоритмларни монотон коррекциясини математик шакллантириш

қуйидаги масалани келитириб чиқаради.

^12𝑛 ̅̅̅̅̅

𝑓(𝛽 ,𝛽 ,...,𝛽 ) = 𝛼 ,𝑖 = 1,𝑞 бажарилиши учун қисман аниқланган

𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗

̃̃

𝑓(𝑦 ,𝑦 ,...,𝑦 ) бул функция берилган бўлсин. Мазкур буль 𝑓(𝑦 ,𝑦 ,...,𝑦 )

𝑗12 𝑛 𝑗12 𝑛

функциялар таркибидан монотонлик мавжуд қисмини топиш талаб қилинади. Шуни такидлаб ўтиш керакки, ушбу масала {𝛽¹ , 𝛽² , ... , 𝛽^𝑛 ; 𝛼 } ва

𝑖𝑗𝑖𝑗 𝑖𝑗𝑖𝑗 {𝛽_𝑡𝑗,𝛽_𝑡𝑗,...,𝛽_𝑡𝑗;𝛼_𝑡𝑗}, (𝛽_𝑖𝑗 ≤𝛽_𝑡𝑗,𝑘=1,𝑛,бироқ𝛼_𝑖𝑗 >𝛼_𝑡𝑗) жуфтлтклар

^{1 2 𝑛 𝑘 𝑘} ̅̅̅̅̅

мажмуасида ўзаро мутоносибликлар мавжуд бўлганда ечимга эга бўлмайди. Амалиётда бул функцияларни монотонлигини аниқлаш учун назорат танланмалар мажмуаси тўпламида зиддиятни келтириб чиқармайди ва эвристик ёндашувни қўллайди ёки зиддиятлик жуфтликларни “вакиллардан кам” бўлган ҳолда ўчириб юборилади. Тимсолларни аниқлаш алгоритмларини мантиқий коррекциялашни турли усуллари баёни [2,3,4] ишларда

келтирилган.
Ushbu ishda obyektlar to’plamini sinflashda ikkita hol bo’lishi mumkin. Birinchisi obyektlar to’plamini oldindan ma’lum bo’lgan sinflarga bo’lish bo’lsa, ikkinchisi obyektlar to’plamini sinflashda sinflar soni ma’lum bo’lmaydi. Maqolada ikkinchi hol qaralgan bo’lib, unda hosil qilinadigan sinflar soni ma’lum bo’maganda obyektlar qisman pretsedentli prinsip asosida sinflash algoritmi va dasturiy ta’minotini yaratish masalasi qaralgan.

Tabiyatda va jamiyatda uchraydigan hodisasalar va jarayonlarda, davlat va boshqaruv organlarida, korxona va tashkilotlarda, xalq xo’jaligining ko’plab sohalarida kiruvchi va chiquvchi ma’lumotlar to’plam shaklida beriladi. Bu sohalarda turli xil kiruvchi va chiquvchi ma’lumotlar to’plamini ma’lum bir mezon asosida sinflash masalasini yechish talab etiladi.

Obyektlarni sinflash masalasi asosan ikkita yondashuv mavjud. Birinchisi, obyektlar to’plami o’qituvchi tomonidan etalon tanlov shaklda beriladi, ya’ni obyektlar to’plami va obyektlardagi belgilar ro’yxati berilgan bo’lib, obyektlar

- 361 -to’plami oldindan sinflarga bo’lingan holda beriladi. Bu holda sinflash masalasi – etalon tanlov shaklida berilgan, ya’ni oldindan sinflarga bo’lingan obyektlar to’plamini izlab topilgan muhim belgilar yordamida o’zlari joylashgan sinflarga qaytadan sinflashdan iborat.

Ikkinchi yondashuvda obyektlar to’plami o’qituvchi tomonidan etalon tanlov shaklda berilmaydi, ya’ni obyektlar to’plami va obyektlardagi belgilar ro’yxati berilgan bo’lib, obyektlarning sinflarda joylashganligi haqidagi ma’lumotlar berilmaydi. Obyektlar to’plamini sinflarga bo’lish ma’lum bir mezon asosida amalga oshiriladi.

Maqolada ikkinchi hol qaralgan bo’lib, unda hosil qilinadigan sinflar soni ma’lum bo’maganda obyektlar qisman pretsedentli prinsip asosida sinflash algoritmi va dasturiy ta’minotini yaratish masalasi qaralgan.

Masalaning qo’yilishi: Standart shaklda, ya’ni ^S₁ ^{, S}₁ ^{,..., S} _m obyektlar to’plamidan iborat T_nm tanlov ( ⁿ – obyektlardagi belgilar soni, ^m – obyektlar soni) berilgan bo’lsin. T_nm tanlovdagi j – obyektni ^S _j ^{= a} _j1 ^{, a} _{j 2} ^{,..., a} _jm ^{( j = 1, m)} obyektlardagi belgilar alfavitini berish mumkin.