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

2. Масалани тушуниш. Ҳисоблаш қурилмасининг имкониятларини аниқлаш. 
Масалани аниқ ёки тақрибан ечиш усулларини танлаш. Алгоритмларни 
лойиҳалаш усуллари. Алгоритм корректлигини баҳолаш. Алгоритмларни 
таҳлил қилиш. Алгоритмни кодлаш.
Нима учун алгоритмларни ўрганиш керак? Ҳақиқий компьютер профессионали учун иккита 
сабаблар мавжуд: амалий ва назарий. Амалий нуқтаи назардан у турли ҳисоблаш техникаси 
соҳаларига тегишли асосий алгоритмлар стандарт тўплами ҳақида тушунчага эга бўлиш керак. 
Бундан ташқари, у янги алгоритмларни ишлаб чиқиш ва уларнинг самарадорликларини таҳлил 
қилишни билиши керак. Алгоритмика (algorithmics) дейиладиган алгоритмларни ўрганиш жараёни 
назарий нуқтаи назардан информатиканнинг (computerscience) пойдевори ҳисобланади. Дэвид 
Харел (David Harel) ўзининг эҳтиётлик билан сарлавҳа қўйилган ажойиб Algorithmics: the Spirit of 
Computing китобида қуйидагиларни ёзади:
Алгоритмика - бу нафақат информатиканинг бўлими, балки ундан кўпроқ нарса ҳисобланади. 
У информатиканинг асоси ҳисобланади ва қўлни кўксига қўйиб айтиш мумкинки, у замонавий 
фанга, техникага ва бизнесга сезиларли таъсир кўрсатди. 
Ҳатто, агар сиз компьютер фанларига ихтисослаштирилмаган ОЎЮ талабаси 
ҳисобланмасангиз, алгоритмларни ўрганиш билан шуғулланиш учун етарлича асосли сабаблар 
мавжуд. Содда қилиб айтганда, алгоритмларсиз ҳеч бир нимани яратиш мумкин эмас. Шунинг учун 
компьютер дастурлари профессионал фаолиятнинг (шахсий ҳаётда ҳам) деярли барча соҳаларида 
янада аҳамиятли бўлиб бориши билан алгоритмларни ўрганиш кенг доирадаги инсонлар учун 
янада муҳим вазифа бўлиб қолмоқда. 
Алгоритмларни ўрганиш учун яна бир сабаб шундан иборатки, бу жараён ўқувчиларда 
таҳлилий фикрлашни билишни ривожлантиради. Пировардида, алгоритмларга нафақат қанчалик 
жавобларнинг ўзи, балки уларни олиниши учун кўрсатмаларнинг шунчалик аниқлиги муҳим.
Натижада, алгоритмларни лойиҳалаштиришнинг махсус усулларини компьютер ишлатилишидан 
ёки ишлатилмасидан қатъий назар исталган ҳолда тўғри келадиган масалаларни ечилишининг 
стратегик режаси деб ҳисоблаш мумкин. Ўз-ўзидан тушунарлики, қандайдир алгоритм ёрдамида 
ечилиши мумкин бўлган масалани ечиш аслида алгоритмик фикрлашнинг аниқлигига боғлиқ 
бўлади. Масалан, бахтли ҳаёт кечириш ёки бой ва машҳур бўлишга имкон берадиган алгоритмни 
таърифлаш мумкин эмас, бошқа томондан, аниқликка илгари сурилган талаб мулоқот қилиш нуқтаи 
назаридан муҳим устунликка эга. Информатик ва алгоритмика тарихи соҳасидаги машҳур 
олимлардан бири Дональд Кнут қуйидагиларни ёзади: 
Информатика соҳасида яхши ўқиган мутахассис алгоритмлар билан қандай ишлаш 
кераклигини билиши шарт: уларни қандай яратиш, ўзгартириш, тушуниш ва таҳлил қилиш. Бу 
билимлар нафақат яхши компьютер дастурларини ёзишга, балки универсал фикрлаш аппаратининг 
асоси бўлиб қолади, у кимё, лингвистика, мусиқа ва бошқалар бўлсин бошқа фанларни тушуниб 
етишга бебаҳо ёрдам кўрасатади. Бунинг сабабини қуйига тарзда тушунтириш мумкин: кўпинча 
айтишадики, инсон буни кимгадир тушунтирмагаунча ўзи ҳеча нарса тушунмайди, мен буни 
бошқача бундай ифодалар эдим: инсон бунга компьютер ўргатмагунча, яъни ниманидир алгоритм 
кўринишида ифодалашга ўргатмагунча предметни чуқур тушунмайди. Ниманидир алгоритмлар 
тўплами кўринишида шакллантиришга уриниш нарсаларнинг маъносини анаъанавий усулда 
фикрлашга қараганда уларни чуқурроқ тушунишга олиб келади. 
Алгоритм тушунчаси 
Алгоритм нима? Бу тушунчанинг универсал таърифи йўқ, лекин у нимани билдириш 
кераклиги тўғрисида умумий фикр мавжуд: 
Алгоритм — бу қандайдир масалани ечилиши учун аниқ берилган кўрсатмалар кетма-кетлиги 
ҳисобланади. Бошқача айтганда, бу чекланган вақт оралиғида тўғри кириш маълумотларидан талаб 
қилинадиган чиқиш маълумотларини олишга имкон берадиган командалар кетма-кетлилиги 
ҳисобланади. 

---

Бу таърифни оддий схема ёрдамида кўрсатиш мумкин (1.1-расм) 
1.1-расм. Алгоритм тушунчасини кўрсатилиши 
Юқорида келтирилган таърифдаги “кўрсатмалар” сўзини ёдга олиш билан биз бу 
кўрсатмаларни таний оладиган ва уларда ёзилган ҳаракатларни бажара оладиган қандайдир 
абстракт (мавҳум) қурилма мавжудлигини кўзда тутдик. 1.1-расмда бу қурилма “ҳисоблаш 
қурилмаси” дейилган. Лекин, назарда тутиш керакки, компьютерлар пайдо бўлгунича “ҳисоблаш 
қурилмаси” атамаси деганда сонли ҳисоблашларни бажарадиган инсон тушунилган. Табиийки, гап 
замонавийлик ҳақида бораяпди, “ҳисоблаш қурилмаси” атамаси деганда компьютерлар, яъни 
бизнинг ҳаётимизга деярли ҳамма жойда кириб келган оммавий электрон қурилма тушунилади. 
Шунга қарамай, эътибор берингки, алогоритмларнинг катта қисми якунда компьютерда 
ишлатилишига мўлжалланган бўлсада, алогритм тушунчасининг ўзи бу фаразга ҳеч қандай боғлиқ 
эмас.
Бу бўлимда алгоритм тушунчасини кўрсатадиган мисоллар сифатида биз ўша бир – иккита 
бутун сонлардан ЭКУБни қидириш масаласини ечишнинг учта усулини кўриб чиқамиз. Бу мисоллар 
қуйида санаб ўтилган муҳим моментларни кўрсатиш учун бизга ёрдам беради: 
Алгоритмнинг ҳар бир қадами аниқ ва бир хил аниқланиши керак. Бу талаб мажбурий 
ҳисобланади ва ҳеч қандай ҳолларда бузилмаслиги керак. 
Алгоритм ёрдамида қайта ишланадиган кириш маълумотлари қийматларининг йўл 
қўйиладиган дипазони аниқ кўрсатилган бўлиши керак.
Ўша бир алгоритмни бир неча турли усулларда тақдим этиш мумкин. 
Ўша бир масалани ечилиши учун бир неча турли алгоритмлар бўлиши мумкин. 
Ўша бир масалани ечилиши учун алгоритмлар асосига мутлақо турли принциплар қўйилиши 
мумкин, бу мазкур масалани ечилиши тезлигига сезиларли таъсир қилиши мумкин. 
Иккита номанфий бутун m ва n сонлар учун ЭКУБни қидириш функциясини gcd(m,n) "greatest 
common divisor" билан белгилаймиз (чунончи, m ва n сонлар бир вақтда нолга тенг бўлиши мумкин). 
Аниқланиши бўйича бу функция ҳам m га, ҳам n га қолдиқсиз бўлинадиган энг катта бутун сонни 
топиши керак. Александриялик қадимги юнон математиги Евклид (эрамизгача III аср) шу билан 
шухрат қозонганки, у биринчи марта геометрия фанини тизимли тавсифлади, ўзининг ишларидан 
бири бўлган Бошланиш дейиладиган асарида бу масалани ечилишининг алгоритмини тавсифлади. 
Замонавйи тилди айтганда, Евклид алгоритми қуйидаги тенгсизликни рекуррент ҳисоблашга 
асосланган: 
gcd (m, n) = gcd (m mod n ) 
Бу ерда (m mod n ) ифода m ва n га бўлишдан қолдиқ ҳисобланади. Алгоритмнинг 
бажарилиши (m mod n ) ифода нолга тенг бўлганида тугайди. Бинобарин, ged (m, 0) = (негалиги 
тушунарли?), охирги олинган m қиймат ҳам дастлабки m ва n сонларга ЭКУБ ҳисобланади. 
Масалан, (60, 24) жуфт сонларга ЭКУБни ҳисоблаш қуйидаги тарзда бажарилиши мумкин: 
gcd (60, 24) = gcd (24, 12) = gcd (12, 0) = 12. 
(агар бу алгоритм сизда таасурот қолдирмаган бўлса, масалан, 1.1-амалиётдаги 4-масалада 
ишлатиладиган иккита катта сонларга ЭКУБни аниқлашга уриниб кўринг). 
Масала