Информация о документе

Цена 2000UZS
Размер 25.9KB
Покупки 0
Дата загрузки 07 Ноябрь 2026
Расширение docx
Раздел Рефераты
Предмет Информатика и ИТ

Продавец

Bohodir Jalolov

Algoritmlarni tahlil qilish asoslari. Turli xil ishlash baholari algoritmlar

Купить
Mavzu: Algoritmlarni tahlil qilish asoslari. Turli xil ishlash baholari algoritmlar. Reja: 1. Algoritm tushunchasi. 2. Algoritm xossalari. 3. Algoritmlarni tahlil qilish. Algoritm so`zi va tushunchasi IX asrda yashab ijod etgan buyuk bobokalonimiz Muxammad al-Xorazmiy nomi bilan uzviy bog`liq bo`lib, uning arifmetikaga bag`ishlangan “Al jabr va al-muqobala” nomli asarining dastlabki betidagi “Dixit Algoritmic” (“Dediki Al Xorazmiy”ning lotincha ifodasi) degan jumlalardan kelib chiqqan. Algoritm- bu aniq hisoblashlami bajaruvchi protsedura bo’lib unga kirish qismida kattalik yoki kattaliklar berilib chiqishda natijaviy kattalik yoki kattaliklar olinadi. Demak algoritm hisoblovchi qadamlardan tashkil topgan bo'lib, dastlabki qiymatlarga ko‘ra natijaviy kattaliklar qiymatini beradi. Algoritmning asosiy xossalari quyidagilardan iborat: 1. Diskretlilik. Bu xossaning mazmuni-algoritmlarni doimo chekli qadamlardan iborat qilib bo`laklash imkoniyati mavjudligidadir. Boshqacha aytganda, uni chekli sondagi oddiy ko`rsatmalar ketma-ketligi shaklida ifodalash mumkin. Algoritmning bu xossasi yuqorida keltirilgan hamma misollarda yaqqol ko`rinib turibdi. Agar kuzatilayotgan jarayonni chekli qadamlardan iborat qilib bo`laklay olmasak, u holda uni algoritm deb bo`lmaydi. 2. Tushunarlilik . Algoritmning ijrochisi hamma vaqt inson bo`lavermaydi. Choy damlashni yoki boshqa ishlarni bajarishni faqat odamga emas, balki robotga ham buyurish mumkin. Ijrochiga tavsiya etilayotgan ko`rsatmalar uning uchun tushunarli bo`lishi kerak, aks holda ijrochi oddiygina amalni ham bajara olmaydi. Bundan tashqari, ijrochi har qanday amalni bajara olmasligi ham mumkin. Har bir ijrochining bajara olishi mumkin bo`lgan ko`rsatmalar yoki buyruqlar birikmasi mavjud bo`lib, u ijrochining ko`rsatmalar tizimi (sistemasi) deyiladi. Shuning uchun ijrochi uchun berilayotgan har bir ko`rsatma ijrochining ko`rsatmalar tizimiga tegishli bo`lishi kerak. Ko`rsatmalarni ijrochining ko`rsatmalar tizimiga tegishli bo`ladigan qilib ifodalay olishimiz muhim ahamiyatga ega. Masalan, pastki sinfning a'lochi o`quvchisi “son kvadratga oshirilsin” degan ko`rsatmani tushunmasligi natijasida bajara olmaydi. Lekin “son o`zini o`ziga ko`paytirilsin” shaklidagi ko`rsatmani bemalol bajaradi. Sababi, u ko`rsatma mazmunidan ko`paytirish amalini bajarish kerakligini anglaydi. 3. Aniqlik. Ijrochiga berilayotgan ko`rsatmalar aniq mazmunda bo`lishi kerak. Chunki, ko`rsatmadagi noaniqliklar mo`ljaldagi maqsadga erishishga olib kelmaydi. Odam uchun tushunarli bo`lgan “3-4 marta silkitilsin”, “5-10 daqiqa qizdirilsin”, “1-2 qoshiq solinsin”, “tenglamalardan biri yechilsin” kabi noaniq ko`rsatmalar robot yoki kompyuterni qiyin ahvolga solib qo`yadi. Bundan tashqari, ko`rsatmalarning qaysi ketma-ketlikda bajarilishi ham muhim ahamiyatga ega. Demak, ko`rsatmalar aniq berilishi va faqat algoritmda ko`rsatilgan tartibda bajarilishi shart ekan. 4. Ommaviylik . O`ar bir algoritm mazmuniga ko`ra bir turdagi masalalarning barchasi uchun ham o`rinli bo`lishi kerak. Ya'ni, masaladagi boshlang’ich ma'lumotlar qanday bo`lishidan qat'iy nazar algoritm shu xildagi har qanday masalani yechishga yaroqlidir. 5. Natijaviylik. O`ar bir algoritm chekli sondagi qadamlardan keyin albatta natija berishi shart. Bajariladigan amallar ko`p bo`lsa ham baribir natijaga olib kelishi kerak. Chekli qadamdan keyin qo`yilgan masala yechimga ega emasligini aniqlash ham natija hisoblanadi. Agar ko`rilayotgan jarayon cheksiz davom etib natija bermasa, uni algoritm deb ayta olmaymiz. Algoritmning turlari Algoritmlarni asosan 3 turga bo`lish mumkin: 1) Chiziqli algoritmlar; 2) Tarmog`lanuvchi algoritmlar; 3) Takrorlanuvchi algoritmlar. Chiziqli algoritmlar Chiziqli algoritmlarda asosan hech qanday shart tekshirilmaydi va jarayonlar tartib bilan ketma-ket bajariladi. Demak, chiziqli algoritmlar sodda hisoblashlar yoki amallar ketma-ketligidir. Chiziqli algoritmlarga misol qilib quyidagi formulalar bo`yicha hisoblashlarni keltirish mumkin. Tarmog`lanuvchi algoritmlar. Biror shartning bajarilishi bilan bog`liq ravishda tuziladigan algoritmlarga tarmog`lanuvchi algoritmlar deyiladi. Tarmog`lanuvchi algoritmlar hisoblashlar ketma-ketligini aniqlaydigan shartlarni o`z ichiga oladi. Blok-sxema ko`rinishida bu shuni bildiradiki, blok- sxemada hech bo`lmaganda bitta romb ishtirok etadi. Masalan: ko`chaga qanday kiyimda chiqishimiz ob- havoga, avtomatdan sharbatli yoki mineral suv ichishimiz esa unga qancha so`mlik “jeton” bog`liqdir. Yuqorida keltirilgan “Svetofor” algoritmi ham tarmog`lanuvchi algoritmga misoldir. Takrorlanuvchi (siklik) algoritmlar. Ma'lum bir shart asosida algoritmda bir necha marta takrorlanish yuz beradigan jarayonlar ham ko`plab uchraydi. Masalan, yil fasllarining har yili bir xilda takrorlanib kelishi, har haftada bo`ladigan darslarning kunlar bo`yicha takrorlanishi va hokazo. Demak, takrorlanuvchi algoritmlar deb shunday algoritmlarga aytiladiki, unda bir yoki bir necha amallar ketma- ketligi bir necha marta takrorlanadi, bu ketma-ketlik tarmog`lardan iborat bo`lishi ham mumkin. Bundan chiziqli va tarmog`lanuvchi algoritmlar takrorlanuvchi algoritmlarning xususiy holi ekanligi kelib chiqadi. Algoritmni tahlil qilish tushunchasi. Algoritm tahlilini, qo’yilgan masalani ushbu algoritm bilan еchish qancha vaqt talab qilishi darajasi dеb tasavvur qilish mumkin. Har bir qaralayotgan algorimtni N o’lchovli boshlang’ich ma'lumotlar massividagi masalalarning qanchalik tеz еchilishi bilan baholaymiz. Masalan, saralash algoritmi N ta qiymatdan iborat ro’yxatni o’sish tartibida joylashtirish uchun qancha taqqoslash talab qiladi yoki N*N o’lchamli ikkita matritsani ko’paytirishda qancha arifmеtik amallar zarurligini hisoblash7. Bitta masalani turli algoritmlar bilan еchish mumkin. Algoritmlar tahlili bizga algoritmni tanlash uchun qurol bo’ladi. Algoritm tahlilining natijasi – bеlgilangan algoritmning kompyutеrdan qancha vaqt yoki takrorlash talab qilishini aniq hisoblovchi formula emas. Bunday ma'lumot muhim emas, bu holatda kompyutеr turi, u bitta yoki undan ortiq foydalanuvchi tomonidan ishlatilyaptimi, uning protsеssori va chastotasi qanaqa, protsеssor chipida komandalar to’liqmi va kompilyator bajarilayotgan kodni qay darajada amalga oshirmoqda kabi tomonlarni nazarda tutish kеrak. Bu shartlar algoritm bajarilish natijasida dasturning ishlash tеzligiga ta'sir qiladi. Yuqoridagi shartlar hisobiga dasturni boshqa tеz ishlaydigan kompyutеrga o’tkazilganda algoritm yaxshi ishlaganday bajarilishi tеzroq amalga oshadi. Aslida esa unday emas, biz shuning uchun tahlilimizda kompyutеrning imkoniyatlarini inobatga olmaymiz. Oddiy va katta bo’lmagan dasturlarda bajariladigan amallar sonini N ning funktsiyasi ko’rinishida aniq hisoblash mumkin. Aksariyat holatlarda bunga zaruriyat qolmaydi. Algoritm tomonidan bajariladigan jarayonlar borki, biz ularning hammasini hisoblab o’tirmaymiz, buning sababi shundaki, hatto uning eng kichik sozlashi ham samaradorlikning sеzilmas yaxshilanishiga olib kеladi. Algoritm murakkabligini baholash kriteriyalari Bir xil me’yorda o’lchash kriteriyasi algoritmning har bir bosqichi bir vaqt birligida, xotira yacheykasi esa hajmning bir birligida (konstanta bo’yicha aniqlikda) bajarilishini nazarda tutadi. Logarifmik o’lchash kriteriyasi ma'lum amal bilan qayta ishlanadigan operand o’lchamini va xotira yacheykasida saqlanadigan qiymatni hisobga oladi. Faktorialni hisoblashning murakkabligini baholash. #include <iostream> using namespace std; int main() { int n = 20; long long result=1; for (int i=2; i<=n; i++) result *=i; cout<<result; return 0; } Berilgan masalaning kirish kattaligi n ekanligini aniqlash oson. Qadamlar soni (n - 1). Shunday qilib, bir xil me’yorda o’lchash kriteriyasi uchun vaqt murakkabligi O(n) dir. Logarifmik o’lchash kriteriyasi bilan vaqt murakkabligi Shu nuqtada, baholanishi kerak bo'lgan amallarni ajratib ko'rsatish kerak. Birinchidan, bu taqqoslash amallari. Ikkinchidan, o'zgaruvchi qiymatiga ta’sir qiluvchi amallar (qo'shish, ko'paytirish, bo’lish, ayirish). O’zlashtirish (ta’minlash) amali hisobga olinmaydi, chunki ular bir zumda amalga oshiriladi deb taxmin qilinadi. Shunday qilib, ushbu masala uchta amal ajratilgan: 1)i≤n i-qadamda log ( n ) ni olamiz. Qadamlar soni n − 1 ta bo’lgani uchun ushbu amalning murakkabligi (n−1)∗log ⁡(n) ga tengdir. 2) i + + ; i-qadamda log ( n ) ni olamiz. Ushbu holatda, quyidagicha yig’indi hosil bo’ladi: ∑i=2 n log 2i=log 2(i!) 3) result *=i; i-qadamda log (( i − 1 ) !) ni olamiz. Ushbu holatda, quyidagi yig’indi hosil bo’ladi: ∑ i = 2n log 2 (( i − 1 ) !) = log 2 ( ∏ i = 2n ( i − 1 ) !) Agar biz barcha olingan qiymatlarni yig'sak va n ning o'sishi bilan asta sekin o'sadigan atamalarni bekor qilsak, O(log 2(∏i=2 n (i−1)!)) biz yakuniy ifodasini olamiz. Bir xil me’yorda o’lchash kriteriyasi bo’yicha sig'imning murakkabligi Bu yerda hamma narsa oddiy. O'zgaruvchilar sonini hisoblashingiz kerak. Agar topshiriq massivlardan foydalansa, massivdagi har bir yacheyka o'zgaruvchi hisoblanadi. O'zgaruvchilar soni kirish kattaligiga bog'liq bo'lmaganligi sababli, murakkablik O (1) bo'ladi. Logarifmik o’lchash kriteriyasi ega bo'lgan sig'imning murakkabligi Bunday holda, siz xotira yacheykasida bo'lishi mumkin bo'lgan maksimal qiymatni hisobga olishingiz kerak. Agar qiymat aniqlanmagan bo'lsa (masalan, i > 10 operand bo'lganda), u holda V max chegaraviy qiymati bor deb hisoblanadi. Ushbu masalada qiymati n (i) dan oshmaydigan va n (result) qiymatidan oshmaydigan o'zgaruvchi mavjud. Shunday qilib, O ( log ( n ! ) ) ga teng.

Algoritmlarni tahlil qilish asoslari. Turli xil ishlash baholari algoritmlar

Купить