|
Маърузачи: АТДТ кафедраси доценти Хидирова Чарос Муродиллоевна
1-Маъруза
Коинот икки ғояга асосланган: ҳисоблаш ва алгоритм. Математик таҳлилнинг қудратли аппаратига асосланган ҳисоблаш замонавий фаннинг асоси ҳисобланади. Бироқ, илм-фан замонавий дунё асосидаги алгоритмисиз тасаввур қилиш мумкин эмас. Нима учун алгоритмларни ўрганиш керак? Ҳақиқий компьютер профессионали учун иккита сабаб мавжуд: амалий ва назарий. Амалий нуқтаи назардан у турли ҳисоблаш техникаси соҳаларига тегишли асосий алгоритмлар стандарт тўплами ҳақида тушунчага эга бўлиш керак. Бундан ташқари, у янги алгоритмларни ишлаб чиқиш ва уларнинг самарадорликларини таҳлил қилишни билиши лозим. Алгоритмика (algorithmics) дейиладиган алгоритмларни ўрганиш жараёни назарий нуқтаи назардан компьютер билимларининг (computer science) пойдевори ҳисобланади. Алгоритмика Алгоритмика - бу нафақат информатиканинг бўлими, балки ундан кўпроқ нарса ҳисобланади. У информатиканинг асоси ҳисобланади ва шуни аниқ айтиш мумкинки, у замонавий фанга, техникага ва бизнесга сезиларли таъсир кўрсатди. Дэвид Харел Алгоритм тушунчаси Алгоритм – бу қандайдир масалани ечилиши учун аниқ берилган кўрсатмалар кетма-кетлиги ҳисобланади. Бошқача айтганда, бу чекланган вақт оралиғида тўғри кириш маълумотларидан талаб қилинадиган чиқиш маълумотларини олишга имкон берадиган командалар кетма-кетлилиги ҳисобланади.
Масала
Алгоритм
Ҳисоблаш қурилмаси
Кириш маълумотлари
Чиқиш маълумотлари
Мисол: ЭКУБни топиш (1-усул) Иккита мусбат бутун m ва n сонлар учун ЭКУБни қидириш функциясини gcd(m,n) "greatest common divisor" билан белгилаймиз. Евклид алгоритми: gcd (m, n) = gcd (m mod n) Масалан: gcd (60, 24) = gcd (24, 12) = gcd (12, 0) = 12. Евклид алгоритми бўйича m ва n сонларга ЭКУБ ҳисоблаш: 1-қадам Агар n = 0 бўлса, m ни жавоб сифатида қайтариш ва ишлашни тугатиш; акс ҳолда иккинчи қадамга ўтиш. 2-қадам m ва n сонларга бутун бўлиш ва колдиқ қийматига r ўзгарувчини бериш. 3-қадам n қийматга m ўзгарувчини бериш, r қийматга эса n ўзарувчини бериш. 1-қадамга ўтиш. Евклид алгоритми Муқобил сифатда ўша бир алгоритмни псевдокод кўринишида ёзамиз: Евклид алгоритми gcd (m, n) функциянинг қийматини ҳисоблайди Кириш маълумотлари: бир вақтда нолга тенг бўлиши мумкин иккита номанфий бутун m ва n сонлар Чиқиш маълумотлари: m ва n сонларининг энг катта умумий бўлувчиси While n≠0 do r←m m←n n←r rеturn m ЭКУБни топишнинг 2-усули Кетма-кет танлаб кўриш бўйича m ва n сонларга ЭКУБ ҳисоблаш: 1-қадам. min {m, n} функция қийматига t ўзгарувчини бериш. 2-қадам. m сонини t сонига бўлиш. Агар қолдиқ 0 га тенг бўлса, 3-қадамга ўтиш; акс ҳолда 4-қадамга ўтиш. 3-қадам. n сонинига бўлиш. Агар қолдиқ 0 га тенг бўлса, t сонини жавоб сифатида қайтариш ва ишни тугатиш; акс ҳолда 4-қадамга ўтиш. 4-қадам. t сонидан 1 сонини айириш. 2-қадамга ўтиш. ЭКУБни топишнинг 3-усули Кетма-кет танлаб кўриш бўйича иккита m ва n сонларга ЭКУБ ҳисоблаш: 1-қадам m сонини оддий кўпҳадларга ёйиш. 2-қадам n сонини оддий кўпҳадларга ёйиш. 3-қадам 1- ва 2-қадамларда аниқланган m ва n сонларининг оддий кўпҳадлари учун уларнинг умумий бўлучиларини ажратиш. Агар р сони m ва n сонларининг умумий бўлувчиси ҳисобланса ва уларнинг оддий кўпҳадларга ёйилишида мос равишда Рm ва Рn марта учраса, у ҳолда ажратишда буни mill { Рm, Рn} марта такрорлаш керак. 4-қадам барча ажратилган бўлувчиларнинг кўпайтмасини ҳисоблаш ва уни кўрсатилган иккита сонларга ЭКУБни қидириш натижаси сифатида қайтариш. Масалан: (60,24) жуфтлик сонлар учун 60 = 2·2·3·5, 24 = 2·2·2·3 gcd (60, 24) = 2·2·3 = 12 Алгоритмларни лойиҳалаштириш ва таҳлил қилиш жараёни
Масалани тушуниш
Танлаш: ҳисоблаш воситалари, аниқ ёки яқинлаштирилган ечим, маълумотлар тузилмалари, алгоритмни лойиҳалаштириш услуби
Алгоритмни ишлаб чиқиш
Тўғриликни баҳолаш
Алгоритмни таҳлил қилиш
Алгоритмнинг ишлатилиши
Кейинги муҳим саволлардан бири - масала ечишнинг аниқ ёки яқинлаштирилган усуллари орасидаги танловдир. Биринчи ҳолатда агоритм аниқ (exact algorithm), иккинчи ҳолатда - яқинлаштирилган (approcsimatsion algorithm) дейилади. Яқинлаштирилган алгоритм, масала аниқ ишланишида ёрдам берадиган бошқа қийинроқ алгоритмнинг қисми бўлиши мумкин.
Do'stlaringiz bilan baham: |
