1-мавзу. Алгоритмик масалани ечиш асослари 4соат


Алгоритмни тўғрилигини баҳолаш



Download 0,83 Mb.
Pdf ko'rish
bet10/12
Sana21.02.2022
Hajmi0,83 Mb.
#75703
1   ...   4   5   6   7   8   9   10   11   12
 
Алгоритмни тўғрилигини баҳолаш 
Алгоритмни қандайдир бир ҳолатда тақдим этишдан сўнг, алгоритм тўғрилигини 
(cорреcтнесс) баҳолаш лозим. Танланган алгоритм чегараланган вақт ичида талаб этилган натижани 
ҳар қандай кирувчи маълумотлар белгилари учун кўрсатади. Масалан, ЭКУБ ни ҳисоблаш учун икки 
сон, м ва н Eвклид алгоритми тўғрилиги гcд (м.н)= гcд (н,ва м мод н) тенгламаси тўғрилигига тенг, 
оддий кузатиш натижасига кўра, итерациядаги ҳар икки сон ҳар вақтда кичраяди ва нолга тенг 
бўганида алгоритмни амалга ошириш тўхтатилади.
Айрим алгоритмларнинг тўғрилигини исботлаш жуда осон, айримлариникини эса - жуда 
қийин. Алгоритмни тўғрилигини исботлашнинг универсал методи - математик индуксия методи 
ҳисобланади. Гап шундаки, алгоритмлар ўз табиатига кўра итератив ва кетма-кетлик кўринишдаги 
тузилишга эга ва айнан шу индуксия исботлаш методида қўлланилади. Алгоритмни тез ишлашини 
кузатиш орқали бир қанча синчиклаб танланган кирувчи маълумотлар жуда фойдали натижаларга 
олиб келиши мумкин, бироқ бундай текширув алгоритм тўғрилигини исботлашда ишонарли деб 
ҳисоблаш мумкин эмас. Аммо, алгоритмни нотўғри ишлаётганини исботлаш учун биргина кирувчи 
маълумотлар тўпламини қайта ишлашда олинадиган нотўғри жавоб исбот бўлади. Агар алгоритмни 
нотўғри ишлаётганлиги исботланса, уни қабул қилинган тузилиш маълумотларини ўзгартирмасдан 
ёки лойиҳалаш усулларини ўзгартириш ёки муаммони кескин тарзда ҳал қилиб, аввал амалга 
оширилган ёндашув ва принсиплар ўзгартирилади. 
Яқинлаштирилган алгоритмларни тўғрилигини баҳолаш, аниқ алгоритмларни тўғрилигини 
баҳолашдан анча эскирган. Бу ҳолатда, чиқувчи маълумотлар алгоритми ёрдамида олинадиган 
натижалар камчилиги аввалдан қўйилган меъёрлардан ошмайди. Бундай баҳолаш намуналари 
кейинги бўлимларда келтирилган. 


Алгоритм таҳлили 
Одатда, алгоритм яратувчилар уларни бир қанча талабларга жавоб беришига ҳаракат 
қиладилар. Алгоритм тўғрилигини баҳолагандан сўнг, энг муҳим саволлардан бири унинг 
самарадорлигини баҳолаш бўлади. Амалиётда алгоритмни самарадорлигини баҳолаш икки усул 
бор: вақт ва ҳажм. Вақт самарадорлиги алгоритм иш тезлиги индикатори ҳисобланади. Ҳажм 
самарадорлиги - бу алгоритм ишлаши учун қўшимча оператив ҳотира қанча миқдорда керак 
эканлигини баҳолайди.
Алгоримтнинг яна муҳим жиҳатларидан бири - унинг соддалигидир (симплиcитй). Қатий 
математик қонун - қоидалар асосида самарани аниқлаш ва баҳолашдан фарқли ўлароқ,
алгоритмнинг оддийлиги нимаси биландур одам гўзаллигига ўхшайди, бу субъйектив тушунчадир, 
уни баҳолаш учун объйектив критериялар топиш осон иш эмас. Масалан, кўплаб одамлар Eвклид 
алгоритмининг икки сон НОД қидирувини, мактабда ўргатишганидан оддийроқ деб ҳисоблашади, 
лекин бу у тушунарлироқ дегани эмас. Айнан шу вақтда, Eвклид алгоритми бутун сонларни кетма-
кетликда саралаш алгоритмидан осонроқдир. Алгоритм соддалиги муҳимдир ва бунга интилиш 
зарур.
Алгоритмнинг кейинги муҳим жиҳаткаридан бири - умумийлиги ёки универсаллиги 
(генералитй). Мазмунан, бу ерда икки нарсани ажратиб кўрсатиш мумкин: масала умумийлиги, 
яъни масала ечими учун ишлаб чиқилган алгоритм ва кирувчи маълумотлар руҳсат бериши мумкин 
бўлган диапазон элементларидир. Биринчи келтириб ўтилган, баъзида алоҳида ҳолатлар ечимини 
қидиришдан кўра масаланинг умумий ечими учун алгоритм ишлаб чиқиш осонроқдир. Мисол 
тарзида қуйидаги масалани кўриб чиқамиз: икки бутун сон ўзаро содда бўла оладими шуни 
аниқлаш керак. Eслатиб ўтамиз, умумий бўлувчиси 1 дан ташқари икки сон ўзаро содда 
ҳисобланади. Бу вазифада НОД икки бутун сон ҳисоблаш учун умумий масала ечими ҳисоблаш 
алгоритмини яратиш осонроқ. Кейин, дастлабки вазифани ечиш учун, гcд функсиясига берилган 
сонларни киритиб, унинг жавоби 1 га тенг эканлигини текшириш керак. Аммо, шундай ҳолатлатлар 
бўладики, умумий алгоритмни ишлаб чиқиш керак бўлмайди, қийин ёки имконсиз бўлади. 
Масалан, м = [н/2] да м- энг кичик элементини топиш ва уларнинг медианаси қидируви учун , н 
сонлардан ташкил топган бутун жадвални қайта-қайта саралаш ортиқчадир. Яна бир мисол: 
маълумки, квадратли илдиз тенгламалари қидируви учун стандарт формулаларни, полиномларни 
юқори даражадаги илдиз қидирув билан умумлаштириш мумкин эмас.
Киритиш маълумотлари руҳсат берадиган диапозон элементлари алгоритми ҳақида 
қуйидагиларни таъкидлаб ўцак бўлади. Алгоритм яратиш жараёнида, кирувчи параметрлар 
элеметлари диапозони кенг миқёсда тебраниши мумкин ва ечилаётган масалага мос келиши керак. 
Маслан, НОД қидирув алгоритмида 1 га тенг бўлган элементларни кўриб чиқиш табиий бўлмаган 
ҳолатдир. Бошқа тарафдан, квадратли илдиз тенгламалар стандарт формуласини комплексли- 
коеффисиентларда, умумий қабул қилинганлик ҳолатларида кўриб чиқиш инкор этилади, у ҳақида 
алоҳида гапириш керакдир. 
Агар сизни алгоритм самарадорлиги, оддийлиги, умумийлиги қониқтирмаса, қўлингизга яна 
қалам олиб, алгоритмни бошқатдан лойиҳалашингиз лозим. Агар ҳаттоки анализ ижобий 
натижаларни кўрсатган бўлса, масалани ечишни бошқа алгоритмик усулларни қидиришдан фойда 
бордир. Бунинг учун ўтган бобда кўрилган уч НОД аниқловчи алгоритмини эсланг. Умуман айтганда, 
масала ечимини оптимал ечимини биринчи ҳарактдан топа олмайсиз. Алгоритм яратилганда энг 
осон қиладига ишимиз уни оптималлаштиришга уринишдир. Масалан, 1.1 бўлимда тасвирланганда 
қараганда, Eратосфен ғалвири алгоритмига бир қанча ўзгартиришлар киритилди. (уларни 
ўйламасдан айта оласизми?) Франсуз ёзувчиси ва учувчиси Антуан де Сент- Eкзюпери гапини доим 
ёдда тутинг: “Конструктор комилликка ўзи ясаган нарсасига бошқа ҳеч қандай детал қўша 
олмайдиган пайтда эмас, балки ундан бошқа ҳеҳ қандай детални олиб ташлолмайдиган пайтда 
эришади”. 

Download 0,83 Mb.

Do'stlaringiz bilan baham:
1   ...   4   5   6   7   8   9   10   11   12




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