"Dasturiy injiniring" kafedrasi di-21-10 guruh talabasi Nasimov Shohijahon
Yüklə 1,84 Mb.
|
- Bu səhifədəki naviqasiya:
- ___2__ мustaqil ta’lim ish hisoboti
- Ikkinchi nazariy savol javobi Algoritmlarni asimptotik (O()) baholash
- 3)Algoritmlarni asimptotik (O()) baholash
|
O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI "Dasturiy injiniring" kafedrasi DI-21-10 guruh talabasi Nasimov Shohijahon № ___2__ мustaqil ta’lim ish hisoboti Fan___________“ Algoritmlarni loyihalash”___________________ Nazriy savol javoblari Birinchi nazariy savol javobi Algoritmlar sifatini baholash uchun mezonlarni ko’raylik. Mavjud mezonlar juda taxminlashgan. Masalan, algoritmni bajarishda bajaruvchining xotira uskunalari hajmi yetarli bo’lmasa, u algoritm yomon deb hisoblanadi. Boshqa mezon sifatida algoritmning bajarilishi uchun talab qilinadigan vaqtni ko’rsatish mumkin. Vaqtni baholash bajaruvchining fizik xarakteristikalari hisobga olinishi kerak. Chunki har bir operatsiya har xil o’zgaruvchilar bilan bajarilganda vaqt ham har xil bo’ladi. Bunchalik aniq ma’lumotni har bir foydalanuvchi uchun yig’ib bo’lmaganligi sababli odatda o’rtacha tezkorlik qabul qilinadi. Ketma-ket bajarilayotgan operatsiyalar sonini aniqlab, uni o’rtacha tezkorlikka ko’paytirsa, algoritm bajarilishining amalga yaqin bo’lgan vaqtini topishimiz mumkin. Demak, algoritmlarni baholash uchun ikkita asosiy kretiriya mavjud ekan. Algoritmni ishlash vaqti bo’yicha baholash Algoritmni bajarish uchun xotiradan egallagan hajmi bo’yicha baholash Ikkinchi nazariy savol javobi 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. Uch asimptotik belgilar asosan algoritmlarning vaqt murakkabligini ifodalash uchun ishlatiladi : Θ-notation ( teta ); O-notation ( O ); Ω notasi ( Omega ). Hisoblash mashinalar tezligi oshishiga qaramasdan, ular yordamida yechilayotgan masalalar kattaligini oshishini algoritm qiyinligini tahlil orqali aniqlaydi. 3)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. Uch asimptotik belgilar asosan algoritmlarning vaqt murakkabligini ifodalash uchun ishlatiladi : 4) Algebraik tenglama - P(x1 ,x2 ,…,xn )=0 ko`rinishida yoziladi. Bu erda P - x1 ,x2 ,…,xn noma’lum o'zgaruvchilardan iborat ko`phad. Algebraik tenglamaning darajasi P ko`phadning darajasiga teng bo`ladi. x1 ,x2 ,…,xn o'zgaruvchilarning algebraik tenglamaga nol qiymat beruvchi qiymatlari ushbu algebraik tenglamaning ildizlari deb ataladi. Transendent tenglama- transendent funktsiyalarni (eksponental, logarifmik, trigonometrik va teskari trigonometrik funktsiyalar) o'z ichiga olgan tenglama. Masalan, sin x + lg x = x, 2x - lg x = arccos x. 1-masala #include #include using namespace std; int main() { float a,b,x1,x0,delta,eps; int n; cout<<“Oraliq boshi a ni kiriting”< cout<<“Oraliq oxiri b ni kiriting””< cout<<“Tenglama ildizini aniqlash aniqligi eps ni kiriting”< x0=(a+b)/2; n=0; do { x1=0.5*(sin(x0*x0)-1); n=n+1; delta=fabs(x1-x0); x0=x1; } while( delta #include #include using namespace std; double fi(double x) { return cos(x)*cos(x)/3; } int main() { double a,b,c,e; cin>>a>>b; cout<<" e ning qiymatini kiriting:"; cin>>e; double x1,x2; x1=a; x2=b; while (fabs(a-x2)>=e) { x2=fi(x1); a=x1; x1=x2; } cout<<"x ning qiymati "< Dostları ilə paylaş:
|