|
Турли структурали алгоритмлар.Барча турдаги алгоритмлар ткрларидан фойдаланган ҳолда алгоритмлар тузиш.
Ишнинг мақсади
1.Турли кўринишдаги алгоритмлар билан танишиш
2. Турли структурали алгоритмларни тузишни урганинг. (чизикли, тармоқланувчи ва такрорланувчи(цикли)).
3.Масалаларнинг математик изохлаб беришни билиш.
4. Топшириқни таърифлаб беришни ўрганиш
Топширик
9, 10 жадвалдан(жадвалнинг ракамини укитувчидан билиб оласиз), ўз вариантингизга мос топшириқни кўчириб олинг,маълумотларга асосланиб берилган топшириклар учун, тузинг:
1) масаланинг математи қўйилиши;
чизиқли структурали алгоритм:
а) блок – схема;
б) псевдокод
в) Насси диаграммасини.
11, 12. жадвалдан(жадвалнинг ракамини укитувчидан билиб оласиз), ўз вариантингизга мос топшириқни кўчириб олинг,маълумотларга асосланиб берилган топшириклар учун, тузинг:
Тармоқланувчи структурали алгоритм:
а) блок – схема;
б) псевдокод
в) Насси диаграммасини.
13-18. жадвалдан(жадвалнинг ракамини укитувчидан билиб оласиз), ўз вариантингизга мос топшириқни кўчириб олинг,маълумотларга асосланиб берилган топшириклар учун, тузинг:
Такрорланувчи структурали алгоритм:
а) блок – схема;
б) псевдокод
в) Насси диаграммасини.
Алгоритмни аниқлаш
Алгоритм – масалани ечимини топишда аниқ натижага эришишда ҳаракатларнинг тартибланган кетма-кетлигини белгиловчи кўрсатмалар тўпламидир.Илгари «тартибланган»сўзининг ўрнига «кетма-кетлик» сўзи ишлатиларди, лекин компьютерларнинг ривожланиши натижасида «кетма-кетлик» сўзининг ўрнига «тартибланган» сўзи ишлатила бошланди.Бу алгоритмнинг кўрсатмалари бошқа кўрсатмалар ёки уларнинг натижалари билан боғлиқлигини кўрсатади.Шунинг учун, баъзи бир кўрсатмалар бошқа кўрсатмалар ишига боғлиқ бўлганлиги туфайли, уларнинг иши тугаллангандан сўнггина бажарилиши керак.Мустақил кўрсатмалар ёки кўрсатмалар иши тугалланганлиги сабабли мустақил бўлган кўрсатмалар иши , ўз ишларини мустақил, параллел ёки бир хил вақтда бажаришлари мумкин, агарда буни процессор ва операцион система фойдалануви йўл берса.
Алгоритмларнинг формал хусусиятлари
Алгоритмни ҳар хил аниқлашда аниқ ва ноаниқ формасида қуйидаги умумий талабларни ўз ичига олади.
Дискретлилик – алгоритм масалани ечилиш жараёнини оддий қадамма қадам бажарилиш кетма-кетлигини ўз ичига олиши керак. Бунда алгоритмнинг ҳар бир қадамини бажарилишига маълум бир вақт талаб қилинади, яъни чиқаётган маълумотларнинг қайта ишлови натижада вақт бўйича дискрет бўлади.
Аниқлилик (детерминированность). Ҳар доим системанинг ҳолатига қараб ишнинг кейинги қадами аниқланади. Шунда, алгоритм чиқаётган бир хил маълумот учун бир хил жавобни беради. Замонавий трактовкада хар хил реализацияда худди шу алгоритмни ўзида изоморф графи бўлиши керак. Бошқа тарафдан эса, эҳтимоллик алгоритмлари мавжуд бўлиб, уларнинг ҳар бир кейинги қадами системанинг ҳолатидан ва ихтиёрий сон генерациясидан келиб чиқади. Бироқ, “Чиқарилаётган маълумотлар” рўйхатида эҳтимоллик алгоритми ихтиёрий сонларни генерация усулини тадбиқида оддий ҳолат бўлиб қолади.
Тушунарлилик – фақат бажарувчи учун бўлиб, унинг буйруқлар системасига кирадиган алгоритмларини буйруқларини ўз ичига олади.
Тамомийлик – топширилган маълумотни чиқиши алгоритм ишини тамомлаши керак ва охирги қадам учун натижани бериши керак.Бошқа тарафдан эса эҳтимоллик алгоритми ҳеч қачон натижа бермаслиги мумкин, бу эҳтимоллик 0 га тенг бўлади.
Оммавийлик (универсаллилик). Алгоритм чиқаётган маълумотларни хар хил тўпламига қўлланилиши керак.
Натижавийлик – аниқ натижаларда алгоритмнинг тамомланиши.
Алгоритм хатоликларни ташкил этади, агар у нотўғри натижа берса ёки умуман натижа бермаса.
Алгоритм хатоликларни ташкил этмайди, агар у чиқадиган маълумотлар учун тўғри натижа берса.
Алгоритм турлари
Аниқ амалий масалалар ечими учун мўлжалланган амалий алгоритмлар алоҳида ўрин эгаллайди. Алгоритм тўғри саналади, қачонки у масаланинг талабларига жавоб берса(масалан, ҳақиқатга яқин натижани берса).Алгоритм (дастур) хатоликларга эга, агар у баъзи бир чиқувчи маълумотларга нотўғри натижани берса, узилса, жавоб бермаса ва умуман ҳеч қандай натижа бермаса. Алгоритм турлари худди мантиқий-математик масалалар каби инсон фаолияти компоненталари ва тенденцияларини акслантиради, алгоритмларни ўзи эса қўйилган мақсадга, бошланғич масала шартига, унинг ечимларига, ижро этувчининг ҳаракатларини аниқлашга боғлиқ равишда қуйидагиларга бўлинади:
Механик алгоритмлар, ёки бошқача қилиб айтганда детерминлашган, қаттиқ(масалан, машина, двигатель ишининг алгоритми ва ҳ.к.);
Эгилувчан алгоритмлар, масалан стохастик, яъни эҳтимоллашган ва эвристик. Механик алгоритм, ягона ва ишонарли кўрсаткичларни белгилаб,шу билан бирга талаб қилинган ва қидирилган натижани ягона қийматини таъминлаб, аниқ ҳаракатларни беради, агарда шу алгоритм ишлаб чиқариш учун масалани ечиш жараёнидаги шартлари бажарилса.
Эҳтимоллилик (стохастик) алгоритми дастурга масаланинг аниқ бир натижага олиб келадиган бир неча хил йўллар ва усуллар билан ечишни беради.
Эвристик алгоритми(грекча “эврика” сўзидан) – бу шундай алгоритмки, бунда дастур ишини охирги натижасига эришиш аниқланмаган, шунингдек ишнинг кетма-кетлиги кўрсатилмаган, бажарувчининг ҳаракатлари очиб берилмаган. Эвристик алгоритмларга, мисол учун инструкция ва аввалдан ёзилган рўйхат киради. Бу алгоритмларда универсал мантиқий процедуралар ва уларнинг аналогияларга, ассоцияцияларга ва аввалги ўхшаш масалаларни ечишга асосланган ҳал этиш усуллари ишлатилади.
Чизиқли алгоритм – бир-бирининг кетидан кетма-кет бажариладиган буйруқлар(кўрсаткичлар) тўплами.
Тармоқланувчи алгоритм – ҳеч бўлмаганда битта шарти бор алгоритм, яъни текшириш натижасида алгоритмни параллел тармоқларга ажралиши.
Циклик алгоритми - янги маълумотлар устида бир ҳаракатнтнг бир неча бор такрорланишини кўзда тутадиган алгоритм.Циклик алгоритмларга кўпинча ҳисоблаш усуллари, варианларни танлаш киради.Цикл дастурлар – бу шундай дастурларки бунда буйруқлар кетма-кетлиги бир неча бор бажарилиши мумкин(янги чиқаётган маълумотлар учун), то маълум бир шартни бажаргунгача.
Ёрдам берувчи (бўйсинувчи) алгоритм (процедура) – Аввалдан ва бутунлигича фойдаланиладиган, аниқ масалани алгоритмлаш учун ишлаб чиқилган алгоритм. Баъзи бир ҳолатларда хар хил маълумотлар учун бир хил буйруқлар ткетма-кетлиги учраганда, ёзувни қисқартириш мақсадида ёрдамчи алгоритмлар ажратилади. Алгоритмлашга тайёрлашни хамма этапларида алгоритмнинг структурали кўриниши ишлатилади.
Алгоритмнинг структурали блок-схема, граф-схемаси – алгоритмнинг бири-бири билан стрелка ёрдамида боғланган блокларининг- график символларининг график кўриниши, яъни уларнинг ҳар бири алгоритмнинг бир қадамига тўғри келади. Блок ичида ҳаракатнинг кўриниши берилади. Алгоритмнинг график кўриниши масалани дастурлашдан олдин уни ечимини кенг кўриниши учун фойдаланилади, бунда кўз хотираси дастур ёзилиш жараёнини осонлаштиради, юзага келиши мумкин бўлган хатоликларни олдини олади, ахборотни қайта ишлаш жараёнини тўла тушунишга олиб келади.
Ҳатто шундай дейиш мумкин:” Ташқи алгоритм ўзида шундай схемани мужассам этганки – у ўзини ичида шу масалани ечишда, ҳисоблашда, келаётган ахборотни машинага киритишда ва босмага чиқаришда шаклларни ичига киритиладиган масалани ечимини ўзида мужассам этади.
Алгоритмларга мисоллар киритамиз:
Энг катта умумий бўлувчи ва энг кичик умумий каррали
а ва b нинг энг катта умумий бўлувчиси(ЭУБ(НОД))ни топишни биз ҳаммамиз мактабда ўрганганмиз. Яъни бу, а ва b қолдиқсиз бўлинадиган энг катта бутун сон d. Ҳеч қандай қийинчиликсиз ҳар бир ўқувчи айтиши мумкин ЭУБ(12,18)=6 га. Агар бу икки сондан бири 0 га тенг бўлсачи? Агар
а ва b манфий бўлсачи? Бу ҳақда мактаб дарсларида хар биримиз ўйлаб кўрганмиз.Бу саволларга жавоб бериши учун умумий бўлувчини нима эканлигини аниқлаштириб оламиз.
1-аниқлаштириш. а ва b қолдиқсиз бўлинадиган 0га тенг бўлмаган энг катта бутун сон d. Бу қуйидагича бўлади: d= ЭУБ (a,b). Агар иккита сон ҳам нолга тенг бўлса ЭУБ(0,0)=0. Булардан келиб чикиб қуйидаги тенгликка эга бўламиз:
ЭУБ(a,b)= ЭУБ(b,a),
ЭУБ(a,b)= ЭУБ(-a,b)
ЭУБ(a,0)=|a|
Айтиш мумкин нима учун ЭУБ (-12,18) тенг 6га, нега -6га эмас? -12 ва 18 , 6га ва -6га бўлинади. Буни жавоби осон: ЭУБ – бу энг катта умумий бўлувчи, 6 сони эса -6 дан катта .
Энг катта умумий бўлувчи ва энг кичик каррали бир-бири билан чамбарчас боғлиқдир.
2-аниқлаштириш. а ва b сонларининг Энг кичик умумий каррали(ЭУК(НОК))си а ва b сонларининг энг кичик умумий бўлинувчисидир.
Арифметиканинг асосий теоремаси шуни кўрсатадики, ҳар қандай натурал сон n ни оддий сонлар кўпайтмаси сифатида тасвирлаш мумкин:
Натурал сонларнинг бундай кенгайтмаси каноник дейилади.Бундан қуйидаги келиб чиқади, агар
 бўлса, қуйидагича бўлади
Do'stlaringiz bilan baham: |
