Fanidan 1-mustaqil ishi bajardi

Download 122.89 Kb.
Sana	20.04.2024
Hajmi	122.89 Kb.
	#203105

Bog'liq
algoritim 1
Informatikaa sho\'ba ma\'ruza, Tariх-darslarida-pedagogik-teхnologiyalar, file (1), Koreya va Xitoy, Agrosanoat integratsiyasi, uning motivlari va xususiyatlari. Rossiyaning agrosanoat majmuasi, engil va oziq-ovqat sanoati, 49147, Yakor rekasiyasi Ayon va noayon qutbli sinxron generatorning ten-fayllar.org, JTD tayyorgarlik darajasi uchun ariza, 6-y-Moliyaviy-tahlil-2-Oquv-qollanma-M-Raximov-T2003 (2), 1, 2, 13065 2 08750CBC25F4CB7AB0730E540F77CE828F69C4FE, Abdullayeva A rus tili, Abdullayeva Azizaxon english 1-topshiriq

Qabul qildi

O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNALOGIYALAR
VAZIRLIGIMUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI

DI-11-22 GURUH TALABASINING

ALGORITMLARNI LOYIHALASH

FANIDAN
1-MUSTAQIL ISHI

Bajardi: Abdurahmonova.S
Qabul qildi: Begulov.O

Reja
1:Algoritim murakkabligining statik va dinamik o’lchovlari ,vaqt va xotira hajmi bo’yicha qiyinchiliklar

2: Algoritimlarni eng yomon va o’rtacha holatlarda baholash
3: Algoritimlarni vaqt va hajmiy murakkabligini baholashda tekis va logorofmik solishtirma mezolari
Algoritm deb hisoblash yoki masalani yechish jarayonlarining ketma-ketligi yig’indisi tushuniladi. Algoritmlar biror dasturlash tiliga bog’liq bo’lmaydi, ular istalgan tilda kod yozilgan taqdirda ham bir xil natijaga olib keladigan instruksiyalardir.
Ammo barcha instruksiyalar ham algoritm bo’lavermaydi. Algoritm bo’lishi uchun, instruksiya bir necha xarakteristikalarga ega bo’ladi:
Barcha qadamlar aniq koʻrsatilgan boʻlishi kerak
Input va Output turi aniq belgilangan bo’lishi kerak
Chegarali. Algoritm doimiy siklga tushib qolmasligi, ohirgi qadamlarigacha yetib borishi zarur Oson. Algoritm istalgan dasturlash tilida amalga oshirish mumkin bo’ladigan darajada oson tuziladi
Algorithm Murakkabligi
Algoritmning murakkabligi (complexity) Space (joy) va Time (vaqt) miqdori asosida o’lchanadigan qiymat. Bunda Time dasturning ishlash jarayonida ketqizadigan vaqti; Space esa input, o’zgaruvchilar, output uchun kerak bo’ladigan joy miqdori. Bu ikki faktor algoritmni effektivligini aniqlaydi. Yaxshi algoritmlarda Space va Time kam miqdorda bo’ladi, bu esa usha algoritmda yozilgan kodning ishlash tezligini, performanceni oshiradi.
Endi savol tug’ilishi mumkin, nimaga oddiy bir masalani yechish uchun algoritmining effektivligi haqida qayg’urishimiz kerak? Yoki dasturlash jarayonida frameworklardan foydalanganda ham performance haqida o’ylash kerakmi?
Ko’p hollarda katta proyektlarda millionlab qator ma’lumotlar ustida amallar bajarishga to’g’ri keladi. Shunda kichik masalalarda sezilmagan kodning performance muammosi, katta hajmdagi ma’lumotlarni qayta ishlashda yaqqol ko’rinadi. Performance muammosi kodning ishlash tezligiga ta’sir qiladi, ishlashda xotiradan ko’proq joy egallashiga olib keladi.
Asl maqsad tech giant korporatsiyalarga ishga kirish ekan, performance’ni birinchi o’ringa qo’yish, yozilgan kodni tahlil qilib, complexity’ni aniqlay olish kerak bo’ladi.
Yaqinda o’zimizda bo’lib o’tgan performance muammosi haqida:
Backendni optimizatsiya qilish jarayonida bir millionga yaqin foydalanuvchi ma’lumotlarini yig’ib, bazada bir jadvalga saqlash kerak bo’lib qoldi. Frameworkning tayyor funksiyalari yordamida yozilgan kod, ishni tugatish uchun 5 soatdan ko’p vaqt olishi ma’lum bo’ldi. Turgan gapki, shuncha foydalanuvchisi bor saytni 5 soat o’chirib qo’yolmaymiz. Keyin kodni optimizatsiya qilib, frameworkni ishlatmasdan yozib chiqqanimda 40 minutda import qiladigan bo’ldi.
Algoritmlarni tahlil qilishni yana Asymptotic analysis ham deyiladi. Bunda kiritilgan input kattaligiga qarab algoritmning ishlash vaqti hisoblanadi.
Asymptotic analysis ga misol sifatida tartiblangan array’dan berilgan X sonni topish uchun Linear Search va Binary Search algoritmlarini taqqoslaymiz.
Linear search siklda arrayning birinchi elementidan boshlab X ni topguncha array elementlarini bittalab tekshirib chiqadi. Array uzunligini N deb oladigan bo’lsak, X ni topish uchun minimal 1 maksimal, N solishtirishni amalga oshiradi.
Binary search array’ning o’rtasidagi element qiymatini – M ni oladi va uni X bilan solishtiradi:
X M ga teng bo’lsa, bingo! birinchi urinishdayoq kerakli element topildi.
Agar X M dan kichik bo’lsa, demak qidirishni arrayning birinchi yarmidan davom ettirish kerak.
Agar X M dan katta bo’lsa, demak qidirishni arrayning ikkinchi yarmidan davom ettiriladi.
Hudi shunday uslubda, avval qismning o’rtasi M topiladi, keyin X ni M bilan solishtirib boriladi.
Bunda minimal urinish 1, maksimal urinish log N marta bo’ladi. Ya’ni array uzunligi 10 ta bo’lsa binary searchda maksimum 3 ta urinishda X ni topish mumkin. Linear searchda esa maksimum 10ta urinish bo’lgan bo’lardi. Endi 100,000 elementi bor katta arrayni oladigan bo’lsak:
Linear searchda max 100,000 urinish
Binary searchda max 16 urinish!
Har bir urinishni shartli ravishda 1 sekund deb hisoblaganda, linear search 27,78 soatda ishni tugatadi. Binary search 16 sekundda. Demak, ikki algoritmni solishtirganda eng yomon holatda (worst case) binary search 6250 marta tez ishlaydi.
Kerakli tanlangan algoritm dasturning ishlash tezligini oshiradi. Katta loyihalarda bo’lsa mablag’ tejalishiga olib keladi.
Biz aytib o’tgan urinishlar sonini aniqlashda ko’pincha best case, average case va worst case hisoblanadi.
Linear searchda va binary search’da best case 1.
Best case’ning yana bir nomi lower bound.
Worst case’niki – upper bound.
Lower bound va upper bound grekcha Θ harfi bilan yoziladi.
Linear search va binary search algoritmlari Θ da yozilganda:
Worst case:
– linear search – Θ(n)
– binary search – Θ(log n)
Ba’zi algoritmlarda lower bound va upper bound bir xil bo’ladi, bu degani algoritm input kattaligidan qat’iy nazar, bir xil amalni bajaradi. Bunga misol qilib MergeSort ni keltirish mumkin. MergeSort‘da upper va lower bound bir xil – Θ(n log n).
Algoritmning vaqt bo'yicha murakkabligi - bu uning ishlash vaqtini unga kiruvchi (input) ma'lumot(lar)ga nisbatan o'zgarishiga aytiladi.
Algoritmning xotira bo'yicha murakkabligi - huddi yuqoridagi kabi, algoritm ishlashi uchun unga kerak bo'lgan xotira hajmini (operativ xotiradan olinadigan joy) kiruvchi (input) ma'lumot(lar)ga nisbatan o'zgarishiga aytiladi.
Dasturiy masalalar yechishda yuqoridagi ikkita omil eng muhimlari sanaladi. Shuning uchun sizning yechimingiz qanday holatdlarda o'rtacha qancha vaqt ishlashi va operativ xotiradan qancha joy egallashini bilish muhim hisoblanadi.
Dasturlash musobaqalarida, asosan, birinchi jihatga ko'proq e'tibor qaratiladi. Lekin aniq vaqt, judayam ko'p omillarga bog'liq: kompyuter qurilmalari, protsessori, operatsion tizim va hokazolarga. Shuning uchun ham bizga faqat uning nazariy jihatdan ishlash vaqtini baholash qiziq. Bunda O() (O - notatsiya)dan foydalaniladi.
O notatsiya ta'rifiga o'tishdan oldin bitta misol keltirib o'tamiz:
N ta elementli massivdan x elementni qidirish kerak bo'lsin. Oddiy yechim, chiziqli qidiruvni ko'ramiz, ya'ni massiv har bir elementni berilgan elementga birma-bir solishtirib ko'ramiz.
Abstrakt va raqamlar
Kod sifati va ishlashini ta'minlashda texnik xizmat ko'rsatishda dasturiy ta'minot ko'rsatkichlari turli dasturiy ta'minot tashkilotlari tomonidan keng qo'llaniladi. Dasturiy ta'minot ko'rsatkichlari o'lcham ko'rsatkichlari, nazorat oqimi ko'rsatkichlari va ma'lumotlar oqimi ko'rsatkichlari kabi dasturiy ta'minotning turli xil murakkabliklarini aniqlaydi. Ushbu dasturiy ta'minotning murakkabliklarini doimiy ravishda hisoblash, kuzatish va nazorat qilish kerak. Dasturiy ta'minot ko'rsatkichlarining asosiy maqsadlaridan biri statik va dinamik ko'rsatkichlarni tahlil qilishdir. Har doim fragmentdagi yuqori darajadagi murakkablik, fragmentdagi past darajadagi murakkablik bilan solishtirganda yomon deb hisoblanadi. Dasturiy ta'minot ko'rsatkichlari dasturiy ta'minotning hayot aylanishining turli bosqichlarida qo'llanilishi mumkin. Ushbu maqolada biz turli ko'rsatkichlarni va statik va dinamik ko'rsatkichlarni taqqoslashni muhokama qilamiz. Biz regressiya testida dasturiy ta'minotning statik va dinamik ko'rsatkichlarining turli jihatlarini baholash va tahlil qilishga harakat qilamiz, bu esa test uchun zarur bo'lgan harakatni baholashni taklif qiladi.
Abstrakt va raqamlar
Kod sifati va ishlashini ta'minlashda texnik xizmat ko'rsatishda dasturiy ta'minot ko'rsatkichlari turli dasturiy ta'minot tashkilotlari tomonidan keng qo'llaniladi. Dasturiy ta'minot ko'rsatkichlari o'lcham ko'rsatkichlari, nazorat oqimi ko'rsatkichlari va ma'lumotlar oqimi ko'rsatkichlari kabi dasturiy ta'minotning turli xil murakkabliklarini aniqlaydi. Ushbu dasturiy ta'minotning murakkabliklarini doimiy ravishda hisoblash, kuzatish va nazorat qilish kerak. Dasturiy ta'minot ko'rsatkichlarining asosiy maqsadlaridan biri statik va dinamik ko'rsatkichlarni tahlil qilishdir. Har doim fragmentdagi yuqori darajadagi murakkablik, fragmentdagi past darajadagi murakkablik bilan solishtirganda yomon deb hisoblanadi. Dasturiy ta'minot ko'rsatkichlari dasturiy ta'minotning hayot aylanishining turli bosqichlarida qo'llanilishi mumkin. Ushbu maqolada biz turli ko'rsatkichlarni va statik va dinamik ko'rsatkichlarni taqqoslashni muhokama qilamiz. Biz regressiya testida dasturiy ta'minotning statik va dinamik ko'rsatkichlarining turli jihatlarini baholash va tahlil qilishga harakat qilamiz, bu esa test uchun zarur bo'lgan harakatni baholashni taklif qiladi.

Berilgan massivning ichidan kerakli elementni topish muammosi

Download 122.89 Kb.