1-mustaqil ish topshiriqlari nazariy topshiriqlar: Quyidagi nazariy savollarga javob bering

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
"Dasturiy injiniring" kafedrasi
TT-21_03 guruh talabasi
RAVSHANOVA DURDONANING

№ 1- мustaqil ta’lim ish hisoboti

Fan_“ Algoritmlarni loyihalash”
1-MUSTAQIL ISH TOPSHIRIQLARI

1. 
   Nazariy topshiriqlar: Quyidagi nazariy savollarga javob bering:
   

1.Algoritm murakkabligini ststic va dynamic o’lchovlari.Vaqt va hajm bo’yicha qiyinchiliklar
Javob :
Algoritmlar murakkabligi haqida ma'lumot berish uchun, ularni static va dynamic murakkabliklari bilan baholash mumkin.

Statik murakkablik: Algoritmda foydalaniladigan ma'lumotlar soni va o'lchamlari bilan aniq qaydalanishi mumkin. Misol uchun, qidiruv algoritmi uchun bajarilishi kerak bo'lgan operatsiyalar soni, ishlatiladigan ma'lumotlar soni, algoritmda ishlatiladigan xotiralar hajmi va boshqa ko'rsatkichlar aniqlanishi mumkin.

Dinamik murakkablik: Algoritmda foydalaniladigan ma'lumotlar va xotiralar hajmi dastlab aniq emas, amalda o'zgarishi mumkin. Misol uchun, bir bitta sonlardan iborat ro'yxatdagi biror elementni qidiruv qilish algoritmi. Ro'yxat uzunligi muayyan emas, shuningdek, qidiruv natijasiga qarab, algoritm qancha xotira ishlatadi aniqlanishi mumkin.

Vaqt bo'yicha qiyinchiliklar: Murakkablik darajasi, amalga oshirilayotgan harakatlar soni va amalga oshirilayotgan harakatlar uchun sarflangan vaqt algoritmda qiyinchilikni belgilaydi. Algoritm murakkabligi kattaroq bo'lsa, algoritm amalga oshirilishida ko'p vaqt sarflanishi kerak bo'ladi.

Hajm bo'yicha qiyinchiliklar: Algoritmda ishlatiladigan xotiralar soni, o'lchami va turlari murakkablik darajasini belgilashda muhim rol o'ynaydi. Xotira sarflanishi ko'p bo'lsa, algoritmda ishlatiladigan xotiralar hajmi kattaroq bo'ladi.

Statik va dinamik murakkabliklar, vaqt va hajm bo'yicha qiyinchiliklar algoritmlarning effektivligi va samaradorligi haqida ma'lumot beradi. Buning ko'rsatilishi kerakki, murakkab algoritmlarni yaratishda har qanday optimallashtirish, kodni kamchilash, modullarni birlashtirish va boshqa texnologiyalarni qo'llash ko'rsatiladi.

2.Algoritmlarni eng yomon va o’rtacha holatlarda baholash

Javob :
Algoritmlar yomon yoki o'rtacha holatlarda baholash uchun bir necha usullar mavjud.

Vakolatli insonlar guruhi yordamida baholash: Bu usulda, bir yoki bir nechta vakolatli insonlar to'plami, ushbu algoritmni o'qing va uning yomon yoki o'rtacha holatlardagi samaradorligini baholash uchun tahlil qiladi. Bu usul algoritmni imtihon qilish uchun keng tarqalgan usullardan biridir.

Inputlar va outputlar orqali baholash: Bu usulda, algoritmning har qanday kiritish va chiquvchilariga e'tibor beriladi. Algoritmning iste'mol qilish davomida kiritishlarga qanday javob berilishi yoki chiquvchilarga qanday natijalar chiqishi hisobga olingan holda, o'rtacha va yomon holatda biror ma'lumotlarni kiritish, chiquvchilarga javob berish va o'zgarishlar kiritish mumkin.

Imtihon qilish: Algoritmlarni yomon yoki o'rtacha holatlarda baholashning eng oddiy yondashuvlari imtihon qilishni o'z ichiga oladi. Bu usulda, algoritmlarni alohida test senariylari yordamida imtihon qilish uchun biror program yoziladi. Shuningdek, algoritmni bir nechta xususiyatlarni o'rgangan holda o'zingizning test senariylaringizni yozish uchun ochiq kod qismlari yozishingiz mumkin.

Bu usullar yomon yoki o'rtacha algoritmlarni baholashda ishlatiladigan oddiy yondashuvlardir. Algoritmlarning to'liq baholash uchun esa rivojlangan tahlil usullarini va matematik modellari ishlatiladi.

3.Algoritmlarni vaqt va hajmiy murakkablik bo’yicha baholashda tekis va logarifmik solishtirma mezonlar.

Javob :
Algoritmning effektivligi, ularning murakkablik darajasini hisoblash orqali baholash mumkin. Ular murakkablikning ikki turi, ya'ni vaqt murakkabligi va hajmiy murakkabligi bo'yicha baholash mumkin.

Vaqt murakkabligi: Bu murakkablik turi algoritmda amalga oshirilayotgan harakatlar soni va amalga oshirilayotgan harakatlar uchun sarflangan vaqt bilan belgilanadi. Vaqt murakkabligi, algoritmni amalga oshirishda qancha vaqt sarflanishi kerakligini belgilaydi. Algoritmlarni vaqt murakkabligi quyidagi mezonlarda belgilanadi:

Tekis solishtirma (Linear Search): Bu algoritm, bir ro'yxatda bitta elementni qidirish uchun ishlatiladi. Vaqt murakkabligi O(n) (n - elementlar soni) ga tengdir.

Logarifmik solishtirma (Binary Search): Bu algoritm, ro'yxatning saralanayotgan holatida qidirishni amalga oshiradi. Vaqt murakkabligi O(log n) ga tengdir.

Hajmiy murakkablik: Bu murakkablik turi algoritmda ishlatiladigan xotiralar soni, o'lchami va turlari bilan belgilanadi. Hajmiy murakkablik, algoritmni ishga tushirish uchun qancha xotira sarflanishi kerakligini belgilaydi. Algoritmlarni hajmiy murakkabligi quyidagi mezonlarda belgilanadi:

Tekis solishtirma (Linear Search): Bu algoritm ro'yxatning uzunligi bo'yicha O(1) xotira ishlatadi.

Logarifmik solishtirma (Binary Search): Bu algoritm ro'yxatning saralanayotgan holatida ishlatiladi, shuning uchun O(1) xotira ishlatadi.

Tekis solishtirma va logarifmik solishtirma murakkabliklarini taqqoslashda, logarifmik solishtirmaning murakkabligi tezlik va hajmiy murakkablikni kamaytirishi sababli yuqoriroq.

Shunday qilib, algoritmlarni murakkablikning ikki turini baholash, ularni optimallashtirish uchun vaqt va hajmni to'g'ri ishlatish uchun muhimdir.

4.Taqribiy integrallash usuli va aniqligi bo’yicha hisoblash

Javob :
Taqribiy integrallash, integralni aniqlashda ishlatiladigan bir necha usullardan biridir. Bu usulga nisbatan osonroq hisoblash uchun funksiyonlarni nisbatan yaxshi ko'rib chiqib olgan hosilalarining yig'indisini hisoblashdan foydalaniladi. Taqribiy integrallash usuli quyidagi bosqichlarda amalga oshiriladi:

Hosilani hisoblash: Berilgan interval bo'yicha, integrallangan funksiya chizig'ini hosil qilish kerak. Hosilning aniqligi ko'rsatilgan metodlar orqali olingan xatolikka bog'liq bo'ladi. Hosilani hisoblashning qo'llaniladigan usullar quyidagilarini kiritish mumkin:

Rektangular hosilalar: Hosilani chiziqli oqimli bo'lgan chiziqqa ajratib, hajmi hisobida ishlatiladi. Xatoligi kamroq bo'lishi uchun boshqa usullarga nisbatan nisbatan kam n.

Trapetsiyal hosilalar: Hosilani trapetsiya shakliga olib, ularning yuqorisini va pastlarini yig'indisiga nisbatan chegaralash orqali hisoblashni tashkil etadi.

Simpsonning qo'llanishidagi hosilalar: Simpsonning qo'llanishidagi hosilalar, hosilaning xususiyatlari bilan foydalanadi. U hosilani parabolaga olib, uning yuqorisini hosil qilish orqali hisoblanadi.

Intervalni bo'lish: Berilgan intervalni bir nechta qismga bo'lib, har bir qismda integrallangan funksiya chizig'ini hosil qilish kerak. Bu, hosilani aniqlashda xatoliklarni kamaytirishga yordam beradi.

Integralni hisoblash: Hosillarni yig'indisi bo'yicha integralni hisoblash kerak. Bunda, hosillarni integralga qo'shib, xullangan qiymatga ko'paytiriladi.

Taqribiy integrallash usuli aniqligi funksiya, intervalning chegarasi va hosilalar aniqligi bilan bog'liq. Hosilalar sonining oshishi va intervalning chegaralari hosilalar aniqligiga ta'sir ko'rsatadi. Shuningdek, integrallangan funksiyaning xususiyatlari ta'sir ko'rsatishi mumkin. Taqribiy integrallash usuli aniqligini oshirish uchun, hosilalar sonini va yaqinlashtirish metodlarini o'zgartirish mumkin.

2.