Алгоритм тушунчаси

Алгоритм тушунчаси.

Алгоритм — информатика ва математиканинг асосий тушунчаларидан ҳисобланади.

Алгоритм сўзи  ва тушинчаси алгоритҳми сўзидан олинган бўлиб, у ИХ (783 йилда тўғилган) асрда яшаб ижод этган буюк бобоколонимиз Мухаммад ал-Хоразмий номи билан узвий боғлиқ бўлиб, унинг арифметикага бағишланган «Ал жабр ва ал муқабала» номли асарининг дастлабки сахифасидаги «Дихит Алгоритмиc» («Дедики Ад-Хоразмий» нинг лотинча ифодаси) деган сўзлардан келиб чиққан.

Ал-Хоразмий биринчи бўлиб унлик саноқ тизимининг принципларини ва унда турли амаллар бажариш қоидаларини асослаб берди. Бу эса ҳисоблаш ишларини ихчамлаштириш ва осонлаштириш имконини яратди. Чунки бу билан уша даврда қулланиб келинган Рим рақамлари ва сонларни сўз оркали ёзиб бажаришдаги ноқулайликлар бартараф этилди.

Алгоритм нима? Дастлаб алгоритм дейилганда унлик саноқ тизимидаги сонлар устида турли арифметик амаллар бажариш қоидалари тушиниб келинган. Умуман олганда, уни аниқ таърифлаш мушкул. Алгоритм деганда бирор мақсадга эришишга ёки қандайдир масалани ечишга қаратилган буйруқларнинг аниқ, тушинарли, чекли ҳамда тўлиқ тизими, аниқ натижага олиб келадиган амалларнинг чекланган кетма-кетлиги тушинилади.

Алгоритимнинг хизмати нимадан иборат? Айтайлик, кимдир қандайдир масалани ечишни ўйлаб топиб ва уни бошқаларга айтмоқчи бўлса, у ҳолда у ўйлаб топган ечимни шундай тасвирлаши керакки, натижада бошқалар ҳам масалани тўғри ечишсин. Шунинг учун тасвир бир неча талабларга бўйсуниши керак. Агар ечимнинг тасвири аниқ бўлмаса, яъни мужмал бўлса, у ҳолда шу тасвирга асосан бошқа жавобни олиш мумкин. Чунки ҳар ким масала ечимнинг тасвирини ноаниқ жойини ўзича аниқлаштириши мумкин. Бундай тасвирни алгоритим деб бўлмайди.

Ҳар куни неча марталаб бажарадиган ишимиз алгоритмга мисол бўла олади. Алгоритмни ишлаб чиқиш учун аввало масаланинг ечиш йўлини яхши тасаввур қилиб олиш, кейин эса уни формаллаштириш, яъни аниқ қоидалар кетма-кетлиги кўринишида ёзиш керак.

Бу мисоллардан битта умумий томонни кузатишимиз мумкин. Бу алгоритмдан қандай мақсад кўзланганлигини билмасдан туриб ҳам уни муваффақият билан бажариш мумкин. Демак, ҳаётда учрайдиган мураккаб жараёнларни бошқаришни ёки амалга оширишни роботлар, компьютерлар ва бошқа машиналар зиммасига юклашимиз мумкин экан. Бу алгоритмнинг жуда муҳим афзаллигидир. Шунга кура, ҳар бир инсон ўз олдига қуйилган масаланинг ечиш алгоритимини тўғри тузиб бера олса, у ўз ақлий ва жисмоний меҳнатини енгилаштирибгина қолмай, бу ишларни автоматик тарзда бажаришни машиналарга топшириши мумкин.

Светофордан фойдаланиш алгоритими.

1)    светофор чироғига қаралсин;

2)    қизил чироқ ёнган бўлса тўхталсин;

3)    сариқ чироқ ёнган бўлса, юришга ёки тўхташга тайёрлансин;

4)    яшил чироқ ёнган бўлса юрилсин.

2. Алгоритм ижрочиси.

Алгоритмларга хос хусусиятлар:

оддий харакатлар;

буйруқлар тизими.

Буйруқлар тизими. Ҳар бир ижрочи фақатгина ушбу ижрочи тушунадиган буйруқларни (яъни, ижрочи бажарадиган буйруқлар рўйхатига мансубларни) бажара олади.

Ижрочи буйрукларни бажариш жараёнида оддий ҳаракатларни бажаради.

Информатикада алгоритмларнинг универсал ижрочиси, компьютерлар ҳисобланади.

3. Алгоритмнинг хоссалари.

Алгоритмларнинг асосий ҳоссалари қуйидагилардан иборат:

Тушунарлилик. Алгоритм ижрочиси буйруклар кетма-кетлигини қандай бажаришни аниқ билиши керак. Алгоритмнинг ижрочиси ҳамма вақт ҳам инсон бўлавермайди. Ижрочига тавсия этилаётган кўрсатмалар унинг учун тушинарли бўлиши керак, акс ҳолда ижрочи ҳар қандай амални ҳам бажара олмайди.

Дискпетлик. Алгопитм ижрочиси масалани ечиш жараёнини алоҳида ва содда қадамлар кетма-кетлигини бажариш деб тушуниши керак. Бу хоссанинг мазмуни – алгоритмларни доимо чекли қадамлардан иборат қилиб булаклаш имконияти мавжудлигидадир. Бошқача айтганда, уни чекли сондаги оддий кўрсатмалар кетма-кетлиги шаклида ифодалаш мумкин. Алгоритмнинг бу ҳоссаси юқорида келтирилган мисолларда яққол кўриниб турибди. Агар кўзатилаётган жараёнларни чекли қадамлардан иборат қилиб булаклай олмасак, у ҳолда уни алгоритм деб булмайди.

Аниқлик. Алгоритмнинг хар бир қоидаси, ундаги амаллар ва буйруқлар бир маъноли бўлиши керак. Шу ҳоссага асосан алгоритм ижрочиси буйруқлар кетма-кетлигини механик бажариш имкониятига эга бўлади. Ижрочига берилаётган кўрсатмалар аниқ мазмунда булиши керак. Чунки, кўрсатмадаги ноаниқликлар мулжалдаги мақсадга эришишга олиб келмайди.

Натижавийлик. Бу ҳоссанинг мазмуни шундан иборатки, ҳар қандай алгоритмнинг ижроси охир-оқибат маълум бир ечимга келиши керак. Ҳар бир алгоритм чекли сондаги қадамлардан кейин, албатта, натижа бериши шарт. Бажариладиган амаллар кўп бўлса ҳам, барибир натижага олиб келиши керак. Чекли қадамдан кейин қўйилган масала ечимга эга эмаслигини аниқлаш ҳам натижа ҳисобланади. Агар кўрилаётган жараён чексиз давом этиб, натижа бермаса, уни алгоритм деб айта олмаймиз.

Оммавийлик. Масалани ечиш алгоритми умумий ҳоллар учун яратилади, яъни фақатгина бошланғич қийматлари билан фарқланувчи бир турдаги масалалар синфи учун тузилади. Бунда бошланғич қийматлар алгоритмнинг қийматлар қабул қилиши мумкин бўлган соҳадан олинади. Ҳар бир алгоритм мазмунига кўра бир турдаги масалаларнинг барчаси учун ҳам уринли бўлиши керак, яъни масаланинг бошланғич маълумотлари қандай бўлишидан қатъий назар алгоритм шу хилдаги ҳар қандай масалани ечишга яроқлидир.

4. Алгоритмни тасвирлаш усуллари.

Амалиётда алгоритмларни тасвирлашнинг кенг тарқалган усуллари қуйидагилар:

1.             Сўзлар ёрдамида (оғзаки нутқда ишлатиладиган сўзлар) Алгоритмнинг сўз орқали берилиши. Бунда ижрочи учун бериладиган ҳар бир кўрсатма сўзлар орқали буйруқ мазмунида берилади;

2.             Алгоритмларнинг формулалар ёрдамида берилиши. Алгоритмнинг формулалар билан берилиш усулидан математика, физика, кимё ва бошқа аниқ фанларни урганишда купроқ фойдаланилади. Масалан, учбурчакнинг юзини унинг асоси ва баландлиги бўйича ҳисоблаш формуласи:   С=(ҳ*а)/2

 Алгоритмларнинг жадвал кўринишида берилиши. Алгоритмни бу кўринишида тасвирланишидан ҳам куп фойдаланилади.

3.             График усулда (график символлар ёрдамида) Алгоритмнинг график (блок-схема) шаклида тасвирланиши. Алгоритмнинг блок-схема кўринишдаги тасвирида геометрик фигуралар шаклидаги оддий элементлардан фойдаланилади.

4.             Дастур кўринишида (дастурлаш тилларига оид хизматчи сўзлар, оператор ва функциялар ёрдамида). Алгоритмларнинг дастур шаклида ифодаланиши. Миллионлаб компьютерларнинг кенг тарқалиб кетиши алгоритмларнинг дастур тарзида тасвирнинг кенг оммалашиб кетишига катта туртки берди. Сабаби шундаки, компьютерлар доимо дастур орқали бошқарилади.  

Алгоритмларни сўзлар ёрдамида тасвирлаш.

Масалан, икки соннинг энг катта умумий булувчисини (ЭКУБ) топиш алгоритми қуйидагича ёзилиши мумкин:

Иккита сонни киритинг;

Агарда бу сонлар тенг бўлса, у ҳолда улардан бирини жавоб сифатида олинг ва ишни тухтатинг, акс ҳолда эса давом эттиринг;

Иккитасини ичида каттасини аниқланг;

Катта ва кичик сонларнинг айирмасини катта сон билан алмаштиринг;

Алгоритмни 2-қадамдан бошлаб қайтаринг.

Келтирилган алгоритмни ҳар қандай натурал сонларнинг ЭКУБини топиш учун ишлатиш мумкин.

Алгоритмларни сўзлар ёрдамида тасвирлашнинг бир қанча камчилиги мавжуд бўлиб, аксарият ҳолларда алгоритмларни тасвирлашда бу усулдан фойдаланилмайди.

Алгоритмларни график усулда тасвирлаш.

Алгоритмнинг бундай тасвирлаш усули алгоритм схемаси ёки блок-схема деб аталади.

Блок-схемада ҳар бир харакат турини (бошланғич қийматларни  киритиш, ифодалар қийматларини ҳисоблаш, шартларни текшириш, амалларни такрорлашни бошқариш, қайта ишлашни тугатиш ва х.к.) маълум бир геометрик фигура орқали ифодаланади.

Блокли белгилар (геометрик фигуралар) чизиқлар орқали боғланади (бунда қайси амал олдин, қайсиниси кейин бажарилиши курсатилади). Нисбатан мураккаб масалаларни ечишда алгоритмдан муаян ЭҲМ тилидаги дастурга утиш жуда қийин. Бундай бевосита утишда алгоритмнинг алоҳида қисмлари орасидаги боғланиш йўқолади, алгоритм таркибининг асосий ва муҳим бўлмаган қисмларини фарқлаш қийин бўлиб қолади. Бундай шароитда кейинчалик аниклаш ва тўғрилаш анча вақт талаб қиладиган хатоларга осонгина йўл қўйиш мумкин. Одатда, алгоритм бир неча марта ишлаб чиқилади, баъзан хатоларни тўғрилаш, алгоритм таркибини аниқлаштириш ва текшириш учун бир неча марта орқага қайтишга тўғри келади. Алгоритм ишлаб чиқишнинг биринчи босқичида алгоритмни ёзишнинг энг қулай усули алгоритмни блок-схема кўринишда ифодалашдир.

”Оддий харакат” белгиси орқали формулалар, ҳисоб-китоб, ўзлаштириш амаллари ифодаланилади. Бир нечта амалларни алоҳида ёки битта белги орқали ифодалаш мумкин.

"Шарт текшириш" блоки орқали амаллар бажарилиш йўналиши шарт бажарилиши асосида кўрсатилади. Бундай блокнинг ҳар бирида савол, шарт ёки муносабат кўрсатилади.

"Цикл" блоки амалларни такрорлаш учун ишлатилади. Блок ичида циклнинг боши ва охирини кўрсатувчи параметр (и), параметрнинг ўзгариш қадами кўрсатилади.

"Ёрдамчи алгоритмга мурожаат" блоки алоҳида ва мустақил ишловчи қисм дастур ва ёрдамчи алгоритмларга мурожаатни билдиради.

5. Алгоритм таркиби.

Алгоритм тузилиши

ЭХМларнинг тараққиёти учун алгоритм ва дастурлашнинг тутган урни.

ЭХМларнинг ривожланиши билан дастурларни автоматлаштириш, уларни дастурларни ёзишда қулай қилиб ишлаб чиқиш асосий мутахассисларнинг асосий масалаларидан бири бўлиб қолди.

Бу йўналишлардан биринчи қадамлардан бири машинага-мулжалланган тиллардан бири булган Ассемблерни ишлаб чиқди.

Дастурлар устида кейинги ишлаб чиқишлар машинага боғлиқ бўлмаган тиллар ҳисобланиб, булар орқали ихтиёрий ЭҲМларда дастур тузиш имконини яратди. Бу эса муҳандислик, илмий техник, иқтисодий ахборотларни қайта ишловчи, рўйхатларни қайта ишловчи моделлаштиришда ишлатилувчи ва хокозо процедурали – йўналтирилган тилларни яратилишига сабаб бўлди. Бу тиллар қаторига Паскал, Фортран, Алгол, Кобол ва шу каби тиллар киради.

Хозирги кунда ҳисоблаш, муҳандис – техник, иқтисодий, матнли ва сонли ахборотларни таҳлил қилиш ва бошқа масалаларни ечиш учун юқори даражадаги дастурлаш тиллари мавжуд. Булар жумласига Бейсик, Фортран, СИ, С++ ва бошқалар киради.

Хозирда дастурлаш тилларини қуйидаги турларга ажратишимиз мумкин:

-       машинага –мулжалланган Ассемблер ва бошқ.

-       процедурага мулжалланган Фортран, Кобол ва бошқ.

-       муаммога мулжалланган ПЛ/1 ва бошқалар.

-       диалогли Бейсик ва бошқ.

-       структурали дастурловчи Паскал ва бошқ.

-       мантиқий дастурловчи Пролог ва бошқ.

6.Чизиқли ҳисоблаш жараёнлари

1. Чизиқли (кетма-кет) буйруқлар структураси кетма-кет бажариладиган буйруқлар тизимидан иборат бўлади:

Чизиқли алгоритмларда асосан ҳеч қандай шарт текширилмайди ва жараёнлар тартиб билан кетма-кет бажарилади. Демак, чизиқли алгоритмларга мисол қилиб қуйидаги формулалар бўйича ҳисоблашларни келтириш мумкин:

С= (аҳ)/2; ҳ=сн .

1-расм.Чизиқли блок-схема.

7. Тармоқланувчи ҳисоблаш жараёнлари

Тармоқланиш алгоритми. Масалаларни ечиш учун алгоритмларини тузиш даврида кўпинча масаланинг ечиш босқичларида ҳисоблаш жараёнларини олдинги олинган натижаларга қараб керакли йўлга юналтирииш зарурияти туғилади.  Бунинг учун ЭҲМларнинг буйруқлар тизимида амалларни керакли томонга йўналтирувчи буйруқлар мавжуд. Бунинг ёрдамида автоматик равишда ҳисоблаш жараёнини зарур йўлга буриш мумкин. Бундай шартларни текшириш алгоритмларнинг асосий қисми ҳисобланади. Ҳисоблаш жараёнининг бундай тури тармоқланувчи ҳисоблаш жараёни дейилади. Бу структура шарт бажарилиши натижасига қараб (ҳа ёки йўқ) алгоритмни бажариш йўналишини белгилайди.

Тармоқланиш структураси туртта кўринишда бўлиши мумкин:

агар-у ҳолда;

агар-у ҳолда-акс ҳолда;

шартлар кетма-кетлиги агар-у ҳолда;

шартлар кетма-кетлиги агар-у ҳолда-акс ҳолда.

Агар буйруғига мисоллар

8.Такрорланувчи ҳисоблаш жараёнлари.

Такрорланувчи жараёнларни ифодалаш учун

дан фойдаланилади, бу ерда и - ихтиёрий ўзгарувчи и₁ – бошланғич қиймат, и₂ - охирги қиймат, и₃ - қадам. Шуни таъкидлаш лозимки, ҳар доим ҳам охирги қиймат бўлиши шарт эмас. Агар и₃ нинг қиймати 1 га тенг бўлса, уни ёзмаса ҳам бўлади.

Циклли алгоритм цикл танаси танаси деб аталиши блокдан ва такрорлашни амалга оширувчи шартдан иборат.

         Такрорлаш алгоритми ҳам икки турга бўлинади. Биринчи тур алгоритм “токи” цикли деб аталиб, бунда берилган шарт текширилади, шу шарт қаноатлангунга қадар цикл танаси такрорланаверади. Шарт бажарилмаса, циклдан чиқиб кетилади. Иккинчи тур цикл алгоритми “гача” циклидир. “Гача” циклида дастлаб цикл танаси бажарилиб, сунгра шарт текширилади. Шарт қаноатлангунга қадар цикл танаси такрорланаверади. Шарт бажарилиши биланоқ циклдан чиқилади.

Скачано с www.znanio.ru