O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
"Dasturiy injiniring" kafedrasi
№4 мustaqil ta’lim ish hisoboti
Fan “ Algoritmlarni loyihalash”
Guruh :MT 22-09
Talaba: Sayfiddinov Doniyor Rahbar : Qayumov A. A
Samarqand-2024 y.
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.
|
1-nazriy savol javoblari:
Ketma-ketliklar, to'plamlar, daraxtlar va graflar, ma'lumotlarni tuzish va ifodalash uchun foydalaniladigan muhim ma'lumotlar strukturasi usullaridir. Ularning har biri ma'lum bir vazifani bajarishda foydalanilishi mumkin.
1. Ketma-ketliklar (Arrays):
Ketma-ketliklar, bir nechta o'zgaruvchilar to'plamini saqlash uchun ishlatiladi. Hamma elementlar bir qator tartibida joylashgan. Elementlar indekslar orqali chaqirilishi va o'zgartirilishi mumkin. Ketma-ketliklar o'z o'zgaruvchilari bilan bir xil turdagi ma'lumotlarni saqlaydi.
2. To'plamlar (Sets):
To'plamlar, bir nechta unikal (takrorlanmaydigan) elementlarn to'plamini saqlash uchun ishlatiladi. Elementlar tartib bo'lmagan holda saqlanadi va qo'shilishi, o'chirilishi va boshqa to'plamlar bilan operatsiyalar bajarishi mumkin. To'plamlar elementlarni takrorlanmaydigan holda saqlashda foydalaniladi.
3. Daraxtlar (Lists):
Daraxtlar, elementlarning tartibini saqlaydigan strukturadir. Elementlar indekslar orqali chaqirilishi, qo'shilishi, o'chirilishi va o'zgartirilishi mumkin. Daraxtlar hibrid turdagi ma'lumotlarni saqlash uchun foydalaniladi.
4. Graflar (Graphs):
Graflar, elementlar (bo'limlar) va ularga bog'liq aloqalar (yo'lnishlar) to'plamini ifodalaydi. Elementlar yoki bo'limlar grafdagi yarimchiliklar bo'yicha bog'liqlik bilan bir-biriga ulangan. Graflar ma'lumotlarni tashkil qilishda va ulardan foydalanishda ishlatiladi. Misol uchun, do'stlarning tarmog'ini, internet tarmog'ini, transport tarmog'ini ifodalashda graflardan foydalaniladi.
Bu strukturalar har birining o'ziga xos xususiyatlari va foydalanish sohalarini taqdim etadi. Ularning boshqa variantlari va turli algoritmalari mavjud bo'lishi mumkin. Asosiy maqsad, ma'lumotlarni moslashtirish va ulardan foydalanishni osonlashtirishdir.
2-nazariy savol javoblari:
Kruskal algoritmi, bir grafning eng arzon tayanch daraxtini topish uchun ishlatiladigan ego qator algoritmlardan biridir. Ushbu algoritm grafning aloqador bo'lmagan bo'limlarini bir-biriga bog'laydigan eng arzon tayanch daraxtni topishni maqsad qiladi.
Kruskal algoritmi tartiblangan zanjirlarga asoslangan algoritmdir. Quyidagi bosqichlar orqali Kruskal algoritmini amalga oshirishingiz mumkin:
1. Grafning barcha bo'limlarini aloqa bo'lmagan to'plamlarga ajratib oling.
2. Grafning barcha yo'lnishlarini to'plagan ro'yhatni tuzing.
3. Yo'lnishlarni qimmatlik (uzunlik, vazn yoki narx) bo'yicha tartiblangan ro'yhatga o'tkazing.
4. Tartiblangan yo'lnishlarni bir-biriga qo'shing va aloqador bo'limlarini birlashtiring. Shuningdek, yo'lnishlar aloqador bo'limlarni bir-biriga bog'lamasligini tekshiring.
5. Barcha yo'lnishlarni qo'shganingizda, eng arzon tayanch daraxtni olishingiz mumkin.
Kruskal algoritmi yordamida eng arzon tayanch daraxtni topish mumkin, lekin grafda sikl bo'lishi mumkinligini eslatadi. Sikllar yo'lnishlarda o'z-o'zini takrorlaydigan aloqalarga olib keladi. Shuning uchun, Kruskal algoritmini ishga tushirishdan oldin grafning siklsiz bo'lishini tekshirish juda muhimdir. Sikllarni aniqlash uchun Tarjan yoki Union-Find algoritmlari kabi boshqa algoritmalardan foydalanishimiz mumkin.
3-nazariy savol javoblari:
"Ajrat va hukmronlik qil" tipidagi algoritmlar, bir ma'lumotlarni ajratish va hukmronlik qilishga oid vazifalar uchun ishlatiladigan algoritmalardir. Bu algoritmlar, ma'lumotlarni kategoriyalash, filtrlash, tartiblash yoki tahlil qilishga yordam beradigan qo'llanmalardir. Bu tip algoritmlar, sodda ma'lumotlarni to'plamlar, ketma-ketliklar yoki boshqa ma'lumot strukturasi usullariga asoslangan hisoblash algoritmlari bo'lishi mumkin.
Misol uchun, quyidagi algoritmlar "Ajrat va hukmronlik qil" tipiga misol bo'lishi mumkin:
1. Kategoriyalash algoritmi:
Bu algoritmlar ma'lumotlarni kategoriyalarga bo'lishga yordam beradi. Misol uchun, bir ro'yhatdagi shaxslarni yosh bo'yicha kategoriyalash algoritmi, shaxslarni yosh bo'yicha guruhlarga ajratadi.
2. Filtrlash algoritmi:
Bu algoritmlar ma'lumotlarni belgilangan shartlarga muvofiq filtrlashga yordam beradi. Misol uchun, bir ro'yhatdagi shaxslarni yosh bo'yicha filtrlash algoritmi, faqat belgilangan yosh chegarasida bo'lgan shaxslarni tanlaydi.
3. Tartiblash algoritmi:
Bu algoritmlar ma'lumotlarni belgilangan tartibda joylashga yordam beradi. Misol uchun, bir ketma-ketlikdagi sonlarni o'sish tartibida tartiblash algoritmi, ketma-ketlikdagi sonlarni o'sish tartibida joylashtiradi.
4. Tahlil algoritmi:
Bu algoritmlar ma'lumotlarni tahlil qilishga, ma'lumotlardan ma'lum xususiyatlarni topishga yordam beradi. Misol uchun, bir matndan belgilangan so'zlar yoki satrlar tahlil qilish algoritmi, matndagi belgilangan so'zlarni yoki satrlarni topadi.
II. 1-Amaliy mashg’ulot topshiriqlari
|
