Методнинг асосий босқичлари ва объектлари



Download 120,46 Kb.
bet1/6
Sana08.07.2022
Hajmi120,46 Kb.
#757891
  1   2   3   4   5   6
Bog'liq
Avvalgi qismda


Комбинаториал тўпламларни яратиш алгоритмлари турли хил дастурий таъминот ва аппарат тизимларини қуриш ва тадқиқ қилишда кенг қўлланилади. Масалан, турли хил синов тизимларида. "Дастур генератори" атамаси жуда умумий талқинга ега, масалан, "ҳисобот генератори", "дастур коди генератори", "тасодифий сонлар генератори". Бу ерда generator амалга оширадиган дастур сифатида тушунилади комбинаториал тўпламни яратиш учун бошқа алгоритм. Комбинаториал тўплам елементлари чекланган тўплам баъзи умумий тузилишга ега. Масалан, пермутациялар, бўлимлар, иккилик дарахтлар, махсус турдаги жадваллар ва бошқалар.
Комбинаторикада генерация алгоритимларини 4 та синфга ажратамиз:
барча тўпламнинг навбатдаги авлоди берилган синфнинг комбинаториал объектлари (listing);
ушбу синфнинг барча комбинаториал объектларини рақамлаш (ranking);
рақамлаш жараёнига мувофиқ комбинаториал объектларни яратиш (unranking);
комбинаториал объектни амалга оширишнинг тасодифий авлоди (random selection).

Кетма-кет авлод алгоритмлари енг кўп ўрганилган. Бироқ, генераторлар асосланган объектларни рақамлаш ва ҳосил қилиш алгоритмлари унинг сони бўйича объект тобора оммалашиб бормоқда.


Авлодни қуриш учун кўплаб усуллар мавжуд рақамлаш алгоритмлари ва уларнинг барчаси аниқ кўриб чиқилаётган комбинаториал объект. Нисбатан яқинда, комбинаториал ҳосил қилиш ва рақамлаш алгоритмларини тузишнинг универсал методи обиекти пайдо бўлди, бир дарахт шаклида бир комбинаторел мажмуи вакиллик асосланган И /ИЛИ.
Бунда асосан таклиф яратиш учун алгоритмларни қуриш ва тадқиқ қилиш комбинаториал тўпламлар, қуриш ва тадқиқи қилиш учун universal дастурий восита комбинаторик тўпламлар елементларининг генераторлари.

Методнинг асосий босқичлари ва объектлари
Ҳосил қилиш алгоритмларини тузиш усули ва комбинаториал объектларни рақамлаш асосида комбинаториал тўпламнинг шаклда ифодаланиши дарахтни қуриш учун рекурсив композиция схемаси И /ИЛИ қуйидагича:
Рекурсив композицияни қуриш учун комбинаториал объектлар тўплами текширилади дарахт И /ИЛИ. Рекурсив композиция қуйидаги схема билан тасвирлаш мумкин
R(0)=D1,
R(n+1)=Si(2),i(2)…….i(k)(D, D1, D2,……,Dk),
Dj=R(n), j=1,k.


бу ерда D0 ва D -рухсат етилган дарахтлар, {im}km=1 -дарахтнинг барглар тўплами D, улар алмаштирилади дарахт томонидан R(n) – n-қадамда олинган.
Рекурсив композициянинг ишлаши кўрсатилган.
Агар комбинаториал кардиналлик бўлса, бу кўрсатилган тўплам функсия f(n) функсияси сифатида берилган {N, +, x, R, S}, бу ерда R- рекурсия оператори, S-суперпозиция оператори, у ҳолда тўплам рекурсив схемани қуриш мумкин дарахтларнинг таркиби И / ИЛИ.
2,Агар рекурсив композиция олинадиган бўлса, унда комбинаториал тўплам объектларини яратиш алгоритмини тузинг, алгоритм дарахтнинг бир variant яратиш учун ишлатилади И/ИЛИ янада, ўрганилаётган тўплам объектлари олинган дарахт вариантларига мувофиқ қурилади. Дарахтнинг бир варианти И/ИЛИ subtree чиқишни кесиш орқали берилган нарсадан олинади умуман ИЛИ тугунлардан ташқарилар.
Объектни рақамлаш алгоритмлари учун, дарахт варианти қурилади И /ИЛИ ундан кейин дарахт вариантларини рақамлаш алгоритмидан фойдаланиб, биз ўрганилаётган тўпламда объект рақамини оламиз.
Шундай қилиб, генераторларни қуриш жараёни комбинаторик объектларни 3 қисмга ажратиш мумкин:
1. Умумлаштирилган дарахт алгоритмларини амалга ошириш И/ИЛИ (рақамлаш ва вариантларни яратиш).
2. Дарахт И /ИЛИ қуриш алгоритмини амалга ошириш.
3. И/ИЛИ Дарахтнинг объект бўйича вариантини олиш алгоритмларни рақамлаш ва объектнинг ўзи учун вариянт рақамини олинг
Биринчи қисми сифатида амалга оширилиши мумкин C++ да синф шаблонлари кутубхонаси. Бу кутубхонадан ҳар хил турдаги комбинаториал объектлар учун фойдаланишга имкон беради. Иккинчисини ҳал қилиш қисман, дарахтлар ва/ёки билан ишлашга йўналтирилган ихтисослашган тилдан фойдаланиш таклиф етилади. Бу генераторларни амалга ошириш учун зарур бўлган код миқдорини камайтиради ва, шунга кўра, ривожланиш вақтини камайтиринг. Агар вазифанинг дастлабки икки қисми автоматлаштирилиши мумкин, кейин учинчиси объектнинг ўзига хос турига боғлиқ ва бутунлай дастурчининг елкасига тушади.

Download 120,46 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish