Mavzu: ichma-ich joylashgan takrorlanuvchi jarayonlar, iteratsion jarayonlar

URGANCH DAVLAT UNIVERSITETI FIZIKA-MATEMATIKA FAKULTETI AMALIY MATEMATIKA VA INFORMATIKA YO’NALISHI 182-GURUH TALABASI OLLABERGANOVA AZIZANING ALGORITMLAR NAZARIYASI FANIDAN


KURS ISHI


MAVZU: ICHMA-ICH JOYLASHGAN TAKRORLANUVCHI JARAYONLAR, ITERATSION JARAYONLAR.

Topshirdi: Ollaberganova Aziza

Qabul qildi: Boltayeva Iroda

Urganch 2019-2020

Mavzu: Ichma-ich joylashgan takrorlanuvchi jarayonlar, iteratsion jarayonlar.

Reja:

1. 
   Kirish.
   
2. 
   Asosiy Qism:
   

2.1. Algoritm va uning turlari.

2.2. Ketma-ket yaqinlashuvchi algoritmlar.

2.3. Ichma-ich joylashgan takrorlanuvchi jarayonlar va ularga doir misollar.

3. 
   Xulosa..
   
4. 
   Ilova.
   
5. 
   Foydalanilgan Adabiyotlar.
   

1. 
   Kirish.
   

Bizgаchа еtib kеlgаn intuitiv mа’nоdаgi аlgоritm erаmizdаn аvvаlgi III- аsrdа Еvklid tоmоnidаn tаklif qilingаn. Ushbu аlgоritm judа mаshhur bo’lib, XX-аsr bоshlаrigаchа «аlgоritm» so’zining o’zi «Еvklid аlgоritmi» mа’nоsidа ishlаtilib kеlindi. Bоshqа mаtеmаtikа mаsаlаlаrni bоsqichli еchishni tаsvirlаsh uchun esа «usul» so’zidаn fоydаlаnilgаn.

Zаmоnаviy аlgоritmlаr nаzаriyasi rivоjidаgi bоshlаng’ich nuqtа dеb, nеmis mаtеmаtigi Kurt Gyodеlning ilmiy ishini ko’rsаtib o’tish mumkin (1931 y. Simvоlik mаntiqlаrning to’lаmаsligi to’g’risidаgi tеоrеmа). Ushbu ishdа bа’zi mаtеmаtik muаmmоlаrni qаysidir sinfgа tааlluqli аlgоritmlаr yordаmidа hаl etib bo’lmаsligi ko’rsаtib bеrilgаn. …

1936 yildа Аlgоritmlаr nаzаriyasi bo’yichа birinchi fundаmеntаl ilmiy ishlаr bir-biridаn аlоhidа tаrzdа Аlаn Tyuring, Аlоiz CHyorch vа Emil Pоstlаr e’lоn qildilаr. Ulаr tоmоnidаn tаklif etilgаn Tyuring mаshinаsi, Pоst mаshinаsi vа CHyorchning lyamdа-hisоblаnuvchаnlik usuli аlgоritm fоrmаlizmining ekvivаlеnt shаkllаridir. Ulаr tоmоnidаn tаklif etilgаn tеzislаr аlgоritm intuitiv tushаnchаsi vа fоrmаl tizimlаrning ekvivаlеntligini tа’kidlаb bеrdi. Аlgоritmik еchimsiz muаmmоlаrning fоrmulirоvkаsi vа isbоti ushbu ishlаrning muhim nаtijаsi bo’ldi.

1950- yillаrdа Аlgоritmlаr nаzаriyasi rivоjlаnishigа rus mаtеmаtiklаri Kоlmоgоrоv vа Mаrkоvlаri z hissаlаrini qo’shdilаr . 60-70-yillаrgа kеlib Аlgоritmlаr nаzаriyasi fаnidа quyidаgi mustаqil yo’nаlishlаr аjrаlib chiqdi:

- Klаssik аlgоritmlаr nаzаriyasi(fоrmаl tillаr tеrminlаridа mаsаlаlаrni ifоdаlаsh, еchimli mаsаlа tushunchаsi, 1965 yildа Edmоnds tоmоnidаn tа’riflаngаn PqNP muаmmоsi, NP to’liq mаsаlаlаr sinfining оchilishi vа tеkshirilishi);

- Аlgоritmlаrning аsimptоtik аnаlizi nаzаriyasi(аsimptоtik bаhоlаsh usullаri, аlgоritmlаrning murаkkаbligi, аlgоritmlаrni bаhоlаsh kritеriylаri vа hokazo). Ushbu yo’nаlish rivоjigа Knut, Ахо, Хоpkrоft, Ulmаn, Kаrp kаbi оlimlаr o’z hissаlаrini qo’shdilаr;

- hisоblаsh аlgоritmlаrining prаktik аnаlizi nаzаriyasi(аlgоritmlаrning mеhnаttаlаbligi оshkоr funksiyasini tоpish, funksiyalаrning chеgаrаviy аnаlizi, rаsiоnаl аlgоritmlаrni tаnlаsh mеtоdikаsi).Ushbu yo’nаlish rivоjlаnishigа sаbаb bo’lgаn ilmiy ish D.Knutning “Isskustvо prоgrаmmirоvаniya dlya EVM” kitоbidаn ibоrаt.

Algoritm – berilgan natijaga erishish uchun qilinishi kerak boʻlgan aniq koʻrsatmalar ketma-ketligi. Algoritm keng maʼnoda faqat kompyuterga oid atama boʻlmay, balki unda berilgan koʻrsatmalarni bajara oluvchi har qanday narsaga oiddir.

Algoritm, algorifm – maʼlum bir turga oid masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi aniq qoida (dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri. O‘rta asrlarda sanoqning o‘nli tizimi bo‘yicha to‘rt arifmetik amal bajariladigan qoidani Algoritm deb atashgan. "Bu qoidalarni matematikaga 9-asrda al-Xorazmiy kiritgan. Yevro-pada bunday qoidalar uning tugilgan yurtiga nisbatan lotinchalashtirilgan (Algoritmus yoki Algorithmus shaklida "algorizm" deyilgan), keyinchalik "algoritm"ga aylangan" (akad. A. N. Kol-mogorov). Fanda "Yevklid algoritmi", "G‘iyosiddin Koshiy algoritmi", "Laure algoritmi", "Markov algoritmi" deb ataluvchi A.lar maʼlum. A. tushunchasi tobora kengayib borib, kibernetikaning nazariy va mantiqiy asosi hisoblangan A.lar nazariyasi paydo bo‘ldi. Oʻzbekiston Respublikasi da bir necha ilmiy tadqiqot muassasalari va hisoblash mar-kazlarida A.dan foydalanish sohasida samarali ishlar olib borilmoqda. Mas, O‘zbekiston Fanlar Akademiyasi "Kibernetika" ilmiy ishlab chiqarish birlashmasida, O‘zbekistondagi bar-cha universitetlarda, Toshkent davlat texnika untida, Oʻzbekiston Respublikasi Makroiqgisod va statistika vazirligi qoshidagi Hisoblash markazi va boshqa muassasalarda olib borilayotgan ishlar bunga misol bo‘la oladi.

2. 
   Asosiy qism.
   
   1. 
      Algoritm va ularning turlari.
      

Inson hayoti davomida katta-kichik vazifalar yoki masalalarni hal etishni o‘z oldiga maqsad qilib qo‘yadi. Odatda, u o‘z maqsadiga erishishi uchun bajarishi lozim bo'lgan amal yoki ishlarini hayotiy tajribasi yoki o'zlashtirgan bilimiga asos- lanib ma'lum bir tartibga keltiradi. Bunga hayotimizdan xilma- xil misollar keltirish mumkin. Demak, algoritm deganda, biror maqsadga erishishga qaratilgan ijrochi bajarishi uchun mo'ljallangan ko‘rsatma (buyruq)laming aniq, tushunarli va chekli ketma-ketligi tushuniladi. Bu algoritm tushunchasining matematik ta'rifi bo’lmasa ham intuitiv ma'noda algoritmning mazmunini ochib beruvchi tavsifidir.

Algoritmni tasvirlashni turlicha usullari mavjud. Odatda biz masalani yechish algoritmini so‘zlar va matematik formulalar orqali ifodaladik. Lekin algoritm boshqa ko‘rinishlarda ham berilishi mumkin. Biz endi algoritmlarning eng ko‘p uchraydigan turlari bilan tanishamiz. Algoritmning so‘zlar orqali ifodalanishi. Bu usulda ijrochi uchun beriladigan har bir ko‘rsatma jumlalar, so‘zlar orqali buyruq shaklida beriladi. Algoritmning formulalar bilan berilish usulidan matematika, fizika, kimyo kabi aniq fanlardagi formulalarni o‘rganishda foydalaniladi. Bu usulni ba’zan analitik ifodalash deyiladi. 3. Algoritmlarning grafik shaklida tasvirlanishida algoritmlar maxsus geometrik figuralar yordamida tasvirlanadi va bu grafik ko‘rinishi blok-sxema deyiladi. 4. Algoritmning jadval ko‘rinishda berilishi. Algoritmning bu tarzda tasvirlanishdan ham ko‘p foydalanamiz. Masalan, maktabda qo‘llanib kelinayotgan to‘rt xonali matematik jadvallar yoki turli xil lotereyalar jadvallari. Funksiyalarning grafiklarini chizishda ham algoritmlarning qiymatlari jadvali ko‘rinishlaridan foydalanamiz. Bu kabi jadvallardan foydalanish algoritmlari sodda bo‘lgan tufayli ularni o‘zlashtirib olish oson. Men ushbu kurs ishimda algortimni asosan blok-sxemalar orqali ifodalaganman.

Algoritmlarni shartli ravishda quyidagi turlarga ajratish mumkin:

- chiziqli algoritmlar;

- tarmoqlanuvchi algoritmlar;

- takrorlanuvchi yoki siklik algoritmlar;

- ichma-ich joylashgan siklik algoritmlar;

- rekurrent algoritmlar;

- takrorlanishlar soni oldindan no’malum algoritmlar;

- ketma-ket yaqinlashuvchi algoritmlar.

Faqat ketma-ket bajariladigan amallardan tashkil topgan algoritmlarga - chiziqli algoritmlar deyiladi. Bunday algoritmni ifodalash uchun ketma-ketlik strukturasi ishlatiladi. Strukturada bajariladigan amal mos keluvchi shakl bilan ko‘rsatiladi. Chiziqli algoritmlar blok-sxemasining umumiy strukturasini quyidagi ko‘rinishda ifodalash mumkin:


Bosh.

Kiritiladigan qiymat

1-amal

2-amal



n-amal


Chop qilish




Tamom

Agar hisoblash jarayoni biror bir berilgan shartning bajarilishiga qarab turli tarmoqlar bo‘yicha davom ettirilsa va hisoblash jarayonida har bir tarmoq faqat bir marta bajarilsa, bunday hisoblash jarayonlariga tarmoqlanuvchi algoritmlar deyiladi. Tarmoqlanuvchi algoritmlar uchun ayri strukturasi ishlatiladi. Tarmoqlanuvchi struktura berilgan shartning bajarilishiga qarab ko‘rsatilgan tarmoqdan faqat bittasining bajarilishini ta’minlaydi.


P - shart
+ -


A-amal

B-amal

Berilgan shart romb orqali ifodalanadi, P - berilgan shart. Agar shart bajarilsa, "ha" tarmoq bo‘yicha A - amal, shart bajarilmasa "yo‘q" tarmoq bo‘yicha B - amal bajariladi.

Ko‘pgina masalalarni yechishda, shart asosida tarmoqlanuvchi algoritmlarning ikkita tarmog‘idan bittasining, ya’ni yoki «ha» yoki «yo‘q» ning bajarilishi yetarli bo‘ladi. Bu holat tarmoqlanuvchi algoritmning xususiy holi sifatida aylanish strukturasi deb atash mumkin. Aylanish strukturasi quyidagi ko‘rinishga ega:

P - shart

amal

Takrorlanuvchi algoritmlar. Agar biror masalani yechish uchun tuzilgan zarur bo‘lgan amallar ketma-ketligining ma’lum bir qismi biror parametrga bog‘liq ko‘p marta qayta bajarilsa, bunday algoritm takrorlanuvchi algoritm yoki siklik algoritmlar deyiladi. Takrorlanuvchi algoritmlarga tipik misol sifatida odatda qatorlarning yig‘indisi yoki ko‘patmasini hisoblash jarayonlarini qarash mumkin.


Bosh.




N



S=0;



i = 1,. N



S=S+i;



S



Tamom


Ichma-ich joylashgan siklik algoritmlar .   Ba’zan, takrorlanuvchi algoritmlar  bir nechta parametrlarga bog‘liq bo‘ladi. Odatda bunday algoritmlarni ichma-ich joylashgan algortmlar deb ataladi.

Ichma-ich joylashgan takrorlanuvchi jarayonlar asosan ikki va undan yuqori bo’lgan o’lchovli massivlarda kuzatiladi. Misol tariqasi soddaroqi ikki o’lchovli massivni ko’rib chiqamiz.

Bosh.




N, M



i = 1,. N



k = 1,. M



A[i, k]



i = 1,. N



k = 1,. M



A[i, k]



Tamom

Ushbu blok sxemada ikki o’lchovli massivning satri N va ustuni M ga teng bo’lgan massiv kiritlgan va u chop qilingan. Quyida shu blok sxemaning Visual Studio muhiti C# dasturlash tilidagi kodi keltirilgan:

Undan quyidagicha natija oldim: