4 -mustaqil ta’lim ish hisoboti Fan“ Algoritmlarni loyihalash” Guruh ki21-02 Topshirdi: Zarpullayev. U tekshirdi: Bobonazarov. A samarqand-2023

O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
"Dasturiy injiniring" kafedrasi

№ 4 -Mustaqil ta’lim ish hisoboti

Fan“ Algoritmlarni loyihalash”
Guruh KI21-02
Topshirdi: Zarpullayev .U
Tekshirdi: Bobonazarov.A

SAMARQAND-2023
1-Nazariy savollar.

1	Ketma-ketliklar, to’plamlar, daraxtlar, graflarni ifodalash usullari.
2	Graflarni eng arzon tayanch daraxtini qurishda Kruskal xasis algoritmi
3	“Ajrat va hukmronlik qil” tipidagi algoritmlar.

1Savol.
Matematikada to'plamni kelgusidagi ketma-ketlik ko'rinishida ifodalash odatdir. Ya'ni bir nechta elementlarni bir-biridan yoki bo'sh joylardan ajratib o'tirib, ulardan qator qilinadi. Masalan, quyidagi sonlarni qator ko'rinishida ifodalash mumkin:

3, 7, 10, 2
2, 4, 6, 8, 10
To'plamlar:
Matematikada to'plamni Sigma (Σ) belgisi bilan ifodalaydilar. Ya'ni bir nechta sonning yig'indisi bo'ladi. Misol uchun, quyidagi yig'indini topish mumkin:
Σ(1, 2, 3, 4, 5) = 1+2+3+4+5 = 15
Daraxtlar:
Matematikada daraxt elementlarini yuqoriga qarab radiatsiya ifodalab turadi. Misol uchun, quyidagi daraxtdan foydalanish mumkin:
√(9) = 3
Graflar:
Matematikada graflar ko'rinishida ifodalash ham juda odatiydir. Bu usulda asosiy elementlar tenglik yoki grafik ko'rinishda ifodalangan. Misol uchun x va y garm-darajalar yig'indisini grafik ko'rinishida ifodalash mumkin.
Albatta, ketma-ketliklar, to'plamlar, daraxtlar va grafiklarni ko'rsatish usullari haqida qisqacha ma'lumot:
1. Sequences: Ketma-ketliklar massivlar yoki bog'langan ro'yxatlar yordamida ifodalanishi mumkin. Massivlar elementlarga doimiy vaqt kirishini ta'minlaydi, lekin doimiy xotira ajratishni talab qiladi. Bog'langan ro'yxatlar dinamik xotira ajratishni ta'minlaydi, lekin elementlarga chiziqli vaqt ruxsatini talab qiladi.
2. Toʻplamlar: toʻplamlar massivlar, bogʻlangan roʻyxatlar, xesh-jadvallar yoki ikkilik qidiruv daraxtlari yordamida koʻrsatilishi mumkin. Massivlar va bog'langan ro'yxatlar ketma-ketliklar bilan bir xil o'zaro kelishuvga ega. Xesh jadvallari elementlarga doimiy kirishni ta'minlaydi, lekin yaxshi xesh funktsiyasini talab qiladi va to'qnashuvlar bo'lishi mumkin. Ikkilik qidiruv daraxtlari elementlarga logarifmik vaqt ruxsatini beradi, lekin eng yomon stsenariylarning oldini olish uchun muvozanatni talab qiladi.
3. Daraxtlar: Daraxtlar bog'langan ro'yxatlar yoki massivlar yordamida tasvirlanishi mumkin. Bog'langan ro'yxatlar dinamik xotira ajratishni ta'minlaydi, lekin elementlarga chiziqli vaqt kirishini talab qiladi. Massivlar elementlarga doimiy vaqt kirishini ta'minlaydi, lekin doimiy xotira ajratishni talab qiladi. Daraxtlarni ko‘rsatgichlar yoki ko‘rsatgichlar massivlari yordamida bola tugunlariga ham ko‘rsatish mumkin.
4. Grafiklar: Grafiklar qoʻshni matritsalar yoki qoʻshni roʻyxatlar yordamida tasvirlanishi mumkin. Qo'shni matritsalar chekkalarga doimiy kirishni ta'minlaydi, lekin O(n^2) xotirani ajratishni talab qiladi. Qo'shni ro'yxatlar dinamik xotira ajratishni ta'minlaydi, lekin chekkalarga chiziqli vaqt kirishini talab qiladi.
Umidjon Kursdosh, [01/06/2023 21:46]
Kruskal algoritmi - bu bog'langan vaznli grafikdagi minimal oraliq daraxtni topish uchun ishlatiladigan ochko'z algoritm. Algoritm grafik qirralarini og‘irliklarining ortib borish tartibida tartiblash, so‘ngra chekkalarni og‘irliklarining ortib borish tartibida daraxtga qo‘shish orqali ishlaydi, shu bilan birga sikllar hosil bo‘lmasligini ta’minlaydi. Kruskal algoritmi vaqt murakkabligi O(E log E)ga ega, bu erda E - grafikdagi qirralarning soni.

2.Savol
Kruskal algoritmi, graflarni eng arzon tayanch daraxtlariga ayirmoqda foydalaniladigan algoritm hisoblanadi. Bu algoritmni foydalanish keng doirada muhim boʻlib, bir nechta muammolar va xizmat koʻrsatkichlari yechishda amalga oshiriladi.

Kruskal algoritmi quyidagicha ishlaydi:
1. Grafdagi barcha birlashmalarni oʻzlashtirib, ularni qiymatlari boyicha tartiblang.
2. Eng arzon birlashmaga tegishli toʻplamlarni ulashni yuboring.
3. Agar birlashma ikki toʻplamni bogʻlasa, ularni birlashtiring.
4. Qayta qadam 2 va 3-ni amalga oshirib, barcha birlashmalarni bir-biriga bogʻlashishingizga qadar davom eting.
5. Qolgan birlashmalarni tashlash orqali eng arzon tayanch daraxtni olish.
Kruskal algoritmi tugatilgandan soʻng, graf eng arzon tayanch daraxtiga aylanadi, yani eng kam tikish nima boʻlishi mumkinligi bilan yaxshi daraxt hosil qilinadi.
3. "Ajrat va hukmronlik qil" tipidagi algoritmlar, bir nechta obyektlarni oʻzaro ajratib, majburiy ravishda ularni alohida tartibda ijaraga berish uchun ishlatiladi. Bu algoritmlarning zaruriyati, hisoblash jarayonida yuzaga keladigan koʻpchilik muammolarga ega boʻlboshqa so'zlar bilan, algoritmda kiritilgan obyektlarning xususiyatlariga qarab ularni ajratish va tahlil qilish imkonini berishdir.

3.savol
"Ajrat va hukmrònlik qil" tipidagi algoritmlar koʻp turdagi muzokaralar yoki mashinalarning chap qismidagi logikalar tuzilishida ham ishlatiladigan mahsulotlar boʻlib, quyidagilarning bir qismiga misol berish mumkin:

1. Kompyuter grafikasi algoritmi:
Bu algorithm, bir ekranda ko'rinadigan tarqoq qalinlikli tasvir, foto yoki boshqa obyektlarni ko'rinishida ishlatiladi. Tarqoq qalinlikli tasvirni hosil qilishda, tasvirdagi obyektlar ajratilib, unga xususiyatlar beriladi, keyinchalik ularni ko'pincha sizilgan bitmapga aylanadi. Ushbu algorithm masofa yoki ko'rinadigan barcha obyektlarni ko'rsatishni bajarish uchun ham ishlatiladi.
2. Tezkor qidiruv algoritmlari:
Bu algorithm, bir nechta obyektlarning bir-biriga mosligini aniqlash, qidiruv holda vaqtni tejash uchun ishlatiladi. Ulardan biri Qichiborlug'i algoirtmi bo'ladi va bu algoritimda oddiy ifodalash usullariga asoslangan.
3. Matematika algoritmi:
Matematikada esa, "ajrat va hukmronlik qil" algorithmi, matematik tadqiqotlari va savol-tartiblari yechishda, bitta mathematik modelni bo'sh joylardan ajratib o'tirish, koʻp elementli yechimlarni yechish uchun qo'llaniladi.
"Ajrat va hukmronlik qil" tipidagi algorithmalarga oʻrnatilgan mavjud mahsulotlar bir nechta ixtisoslashgan bo'lib kelgan savdo, logistic, tibbiyot va boshqa sanoatlar hisobidagi jarayonlarda joriy etiladi. Bu algorithmalar mahsulotni bir kunda yoki bir kechaga atib koʻtish, savdo ishlab chiqarish tezligini oshirish va kamaytirish, shuningdek, sanoat korxonalarining ish faoliyati yaxshilashish uchun foydalaniladi.