Algoritmlarni loyihalash Ass. Bobonazarov A. A

Algoritmlarni loyihalash

Ass. Bobonazarov A.A.

Dasturiy injiniring kafedrasi

1-MAVZU: ALGORITMNI LOYIHALASH FANIGA KIRISH. ALGORITMLARNI VAQT VA HAJM BO’YICHA BAHOLASH. KO’PHADLAR QIYMATLARINI HISOBLASHDA GORNER SXEMASI

2-kurslar uchun, 2021-2022 o’quv yili 3-semester
30 soat ma’ruza + 60 soat laboratoriya
90 soat mustaqil ish
Jami 6 kredit
Kursning asosiy o’quv materiallari va mustaqil ish topshiriqlari uchun elektron manbalar:

Dars rejasi

• 1. Algoritmning ta’rifi
• 2. Algoritmlarni baholash kriteriyalari
• Algoritmlarni tahlil qilishga doir misollar

“Алгоритм” тушунчасининг пайдо бўлиш

• «Algoritm» atamasi xorazmlik buyuk olim Muhammad al-Xorazmiy (825 y.) nomi bilan bog’liq.
• Algoritm tushunchasi XX asrning boshlarida yashab ijod qilgan D.Gilbert, K.Gyodel, S.Klini, A.Chyorch, E.Post, A.Tyuring, N.Viner, A.A.Markov kabi olimlarning ishlari orqali fanga kirib kelgan.
• Algoritmlarning turli ta’riflari mavjud. Rasmiy ta’riflardan biri bo’yicha algoritm bu qo’yilgan masalani yechilishiga olib keluvchi aniq harakatlarning chekli ketma-ketligidir.

Algoritmning ta’rifi

• Algoritm – bu qat’iy belgilangan qoidalarga muvofiq amalga oshiriladigan muayyan sondagi qadamlardan keyin masalaning yechimiga olib keluvchi hisoblash tizimidir. (A.Kolmogorov).
• Algoritm – bu ma’lum kiruvchi ma’lumotlardan izlanayotgan yechimga olib keluvchi hisoblash jarayoni to’g’risidagi ko’rsatma (A.Markov).
• Algoritm — bu bir turdagi masalalarni yechishga olib keladigan aniq operatsiya (amal)lar tizimini muayyan tartibda bajarish to’g’risidagi ko’rsatma (M.M.Rozental tahriri ostida chop etilgan falsafa lug’ati)
• Algoritm – bu aniq masalalar to’plamini yechish uchun amallar ketma-ketligini aniqlovchi tugallangan qoidalar majmuasi bo’lib, u 5 ta muhim xossalarga ega bo’ladi: tugallanganlik, aniqlik, kirish, chiqish, samaradorlik. (D.E.Knut).

Algoritmning xossalari

Bu tushunchadan algoritmning quyidagi xossalari kelib chiqadi:

• Diskretlilik – hal qilinayotgan jarayonni qadamma-qadam ko’rinish tasvirlanishi.
• Ommaviylik – o’xshash masalalarga qo’llash mumkinligi.
• Tushunarlilik –berilgan ko’rsatmalar ijrochiga tushunarli bo’lishi va uning talablariga to’liq javob berishi kerak.
• Aniqlilik – aniq sondagi amallarni bajarish nazarda tutilib, ijrochiga joriy qadam tugatilishi bilan keyin bajariladigan qadam aniq ko’rsatilishi kerak.
• Natijaviylik. Har bir algoritm chekli sondagi qadamlardan so‘ng albatta natija berishi shart. Bajariladigan amallar ko‘p bo‘lsa ham bari-bir natijaga olib kelishi kerak.

Algoritmni to’liq qurish bosqichlari

• Masalaning qo’yilishi
• Modelni qurish
• Algoritmni ishlab chiqish
• Algoritm to’g’riligini tekshirish
• Kodlashtirish
• Dasturni tekshirish
• Hujjatlashtirish

Demak, algoritmlarni baholash uchun ikkita asosiy kretiriya mavjud ekan. - Algoritmni ishlash vaqti bo’yicha baholash - Algoritmni bajarish uchun xotiradan egallagan hajmi bo’yicha baholash

• Algoritmlarni asimptotik (O()) baholash – algoritmda kiruvchi ma’lumotlarning bajariladigan amallar soniga ma’lum bir qonuniyatlar asosida mos qo’yilishidir. Bu qonuniyatlar kvadratik, factorial, logarifmik bo’lishi mumkin.
• Agar kiruvchi ma'lumotlarning o'lchamlari oshsa, algoritmning bajarilish vaqti f(N) funksiyasi bilan bir xil tezlikda oshsa, algoritmda O(f(n)) murakkablik bor.
• Agar kiruvchi ma'lumotlarning o'lchamlari oshsa, algoritmning bajarilish vaqti f(N) funksiyasi kvadratik tezlikda oshsa, algoritmda O(f(n^2)) murakkablik bor.

Keyingi jadval 1 sekundda, 1 minutda, 1 soatda 5 ta algoritmlarni har birining yordamida yechiladigan masalaning kattaligi keltirilgan.

Samaradorlikni baholashga misollar Masala, Qalam va qog’oz yordamida, quyidagi 16 ta kvadratdan iborat shaklni yasash kerak.

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Algoritm bahosi O(n)

Bu jarayon 4 ta qadamda bajarildi. Demak algoritm bahosi O(logN)