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

 
Алгоритмни тўғрилигини баҳолаш 
Алгоритмни қандайдир бир ҳолатда тақдим этишдан сўнг, алгоритм тўғрилигини 
(cорреcтнесс) баҳолаш лозим. Танланган алгоритм чегараланган вақт ичида талаб этилган натижани 
ҳар қандай кирувчи маълумотлар белгилари учун кўрсатади. Масалан, ЭКУБ ни ҳисоблаш учун икки 
сон, м ва н Eвклид алгоритми тўғрилиги гcд (м.н)= гcд (н,ва м мод н) тенгламаси тўғрилигига тенг, 
оддий кузатиш натижасига кўра, итерациядаги ҳар икки сон ҳар вақтда кичраяди ва нолга тенг 
бўганида алгоритмни амалга ошириш тўхтатилади.
Айрим алгоритмларнинг тўғрилигини исботлаш жуда осон, айримлариникини эса - жуда 
қийин. Алгоритмни тўғрилигини исботлашнинг универсал методи - математик индуксия методи 
ҳисобланади. Гап шундаки, алгоритмлар ўз табиатига кўра итератив ва кетма-кетлик кўринишдаги 
тузилишга эга ва айнан шу индуксия исботлаш методида қўлланилади. Алгоритмни тез ишлашини 
кузатиш орқали бир қанча синчиклаб танланган кирувчи маълумотлар жуда фойдали натижаларга 
олиб келиши мумкин, бироқ бундай текширув алгоритм тўғрилигини исботлашда ишонарли деб 
ҳисоблаш мумкин эмас. Аммо, алгоритмни нотўғри ишлаётганини исботлаш учун биргина кирувчи 
маълумотлар тўпламини қайта ишлашда олинадиган нотўғри жавоб исбот бўлади. Агар алгоритмни 
нотўғри ишлаётганлиги исботланса, уни қабул қилинган тузилиш маълумотларини ўзгартирмасдан 
ёки лойиҳалаш усулларини ўзгартириш ёки муаммони кескин тарзда ҳал қилиб, аввал амалга 
оширилган ёндашув ва принсиплар ўзгартирилади. 
Яқинлаштирилган алгоритмларни тўғрилигини баҳолаш, аниқ алгоритмларни тўғрилигини 
баҳолашдан анча эскирган. Бу ҳолатда, чиқувчи маълумотлар алгоритми ёрдамида олинадиган 
натижалар камчилиги аввалдан қўйилган меъёрлардан ошмайди. Бундай баҳолаш намуналари 
кейинги бўлимларда келтирилган. 

---

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