Muhammad al-Xorazmiy nomidagi
Toshkent axborot texnalogiyalari universiteti
Qarshi filiali “Kompyuter injiniringi” Fakulteti
KI-11-21S guruh talabasi Qudratov Shavkat
Ma’lumotlar tuzilmasi va algoritmlar
4-MUSTAQIL ISH
Reja;
1 . Rekursiya va uni dasturlashda ishlatish. Rekursiv algoritmlar,
ularning tahlili.
2 . Daraxtlar klassifikatsiyasi. Daraxt ko‘ruvi. Ikkilik daraxtlar va
ular ustida amallar.
3 . Graf tushunchasi va uning ko‘rinishlari.
Rekursiya, dasturlashda bir amalni bajarish uchun o'zini qayta-
qayta ishlatish prinsipi hisoblanadi. Rekursiv algoritmlar esa,
rekursiya prinsipi asosida yaratilgan algoritmlardir. Rekursiya
dasturlashda eng qo'lda ishlatilgan konseptlardan biridir, chunki
uning orqali bajariladigan vazifalar moslashuvchan va qulaydir.
Rekursiv algoritmlar quyidagi tahlillarni o'z ichiga oladi:
Boshlang'ich shart (Base Case):Har qanday rekursiv algoritmni
bajarish uchun kerak bo'lgan boshlang'ich shartni belgilash
zarur. Bu shart bo'lmagan holda rekursiya doimiy tarzda davom
etadi va dastur infinite loop (noumoni uzatish) holatiga tushadi.
O'zini takrorlash (Self-referencing): Rekursiv algoritmning asosiy
xususiyati - u o'zini takrorlaydi. Boshqa so'z bilan, algoritm
o'ziga o'zi chaqiriladi.
O'zgaruvchilarning yangilanishi: Rekursiv funksiya
o'zgaruvchilarni yangilaydi va ularni doimiy ravishda
o'zgartiradi.
Rekursiv funksiyalarni misol orqali tushuntirish uchun, quyidagi
oddiy misolga e'tibor bering:
```python
def faktorial(n):
if n == 0 or n == 1:
return 1
else:
return n * faktorial(n - 1)
# Misol
print(faktorial(5)) # Natija: 120
```
Bu dastur faktorial hisoblash uchun rekursiv funksiyani yaratadi.
Boshlang'ich shart (base case) `n == 0 or n == 1` qo'llanilgan va
rekursiya o'zini takrorlaydi (`return n * faktorial(n - 1)`). Shu
tarzda funksiya o'zini takrorlay qo'lda ishlaydi va javobni
qaytaradi.
Rekursiv algoritmlar, bir qancha muammolarni yechish uchun
hamda kodni oson yozish uchun qulay bo'lishi mumkin. Ammo,
juda katta sonli vaqtga ega bo'lgan rekursiyalarni yozish uchun,
ko'p mashg'ulot va zahoti talab qiladi. Agar rekursiv algoritmlar
notinchilik va ishonch bilan yozilmasa, infinite loop va boshqa
muammo va hatolarni chaqirish muammoi paydo bo'ladi.
Yaxshi, bir necha sodda misol bilan boshlaymiz:
### 1. Faktorial hisoblash
```python
def faktorial(n):
if n == 0 or n == 1:
return 1
else:
return n * faktorial(n - 1)
# Misol
print(faktorial(5)) # Natija: 120
```
Bu misolda rekursiv funksiya `faktorial` yaratilgan va faktorial
hisoblash uchun ishlatilgan. Agar `n` 0 yoki 1 ga teng bo'lsa, `1`
qaytariladi. Aks holda, funksiya o'zini takrorlaydi.
### 2. Fibonachchi ketma-ketligi
```python
def fibonachchi(n):
if n <= 1:
return n
else:
return fibonachchi(n - 1) + fibonachchi(n - 2)
# Misol
print(fibonachchi(6)) # Natija: 8
```
Bu misolda `fibonachchi` rekursiv funksiya yaratilgan va
Fibonachchi ketma-ketligi elementlarini hisoblash uchun
ishlatilgan. Agar `n` 0 yoki 1 ga teng bo'lsa, `n` qaytariladi. Aks
holda, `n-1` va `n-2` elementlarning yig'indisi qaytariladi.
### 3. Daraja hisoblash
```python
def daraja(x, n):
if n == 0:
return 1
else:
return x * daraja(x, n - 1)
# Misol
print(daraja(2, 3)) # Natija: 8
```
Bu misolda `daraja` rekursiv funksiya yaratilgan va sonni
belgilangan darajaga ko'tarish uchun ishlatilgan. Agar `n` 0 ga
teng bo'lsa, `1` qaytariladi. Aks holda, `x` ni `n-1` marta
ko'paytirish jarayoni boshlanadi.
Daraxtsimon ma'lumotlar tuzilmalari (DBMS), ma'lumotlar
bazalarini yaratish, saqlash, yangilash va ulardan foydalanish
uchun dasturiy vositalarni ta'minlash uchun dasturiy vosita
tizimlaridir. Ushbu tizimlar ma'lumotlarni tuzib turishni, ularga
murojaat qilishni, ma'lumotlar bazasidagi ma'lumotlarni
saqlashni, ulardan foydalanishni va ularga ma'lumotlarni
qo'shishni, o'zgartirishni va o'chirishni (CRUD) ta'minlashni
maqsad qiladi.
Daraxtsimon ma'lumotlar tuzilmalari asosan quyidagi
xususiyatlarga ega bo'ladi:
1. **Ma'lumotlar tuzib turish (Data Organization):**
Ma'lumotlar tuzib turishda, odatda, jadval (table)
strukturasidagi qat'iy bir tartib (relational structure) qo'llaniladi.
Bu jadvallar, ma'lumotlar bazasidagi elementlarni (qat'iy
ma'lumotlar tuzilmasidagi biror narsa) saqlashda foydalaniladi.
Ma'lumotlar bazasi boshqarish (Database Management):
Daraxtsimon ma'lumotlar tuzilmalari, ma'lumotlar bazasidagi
ma'lumotlarni boshqarish uchun ma'lumotlar bazasini o'z ichiga
olgan boshqaruv tizimlarini (DBMS) o'z ichiga oladi. Ushbu
tizimlar ma'lumotlarga murojaat qilish, ma'lumotlarni qo'shish,
o'zgartirish va o'chirishni tashkil etishda yordam beradi.
Transaktsiyalar va amalga oshirish (Transaction Processing):
Daraxtsimon ma'lumotlar tuzilmalari, boshqaruv tizimlari orqali
transaktsiyalarni (amalga oshirilgan boshqaruv operatsiyalari
to'plami) amalga oshirish va ma'lumotlar bazasidagi to'g'ridan-
to'g'ri o'zgarishlarni ta'minlashda yordam beradi.
Tahlil va tahlil qilish (Query and Analysis): Ma'lumotlar
bazasidagi ma'lumotlarga murojaat qilish va ulardan tahlil qilish
uchun so'rovlarni tuzish va boshqaruv etish uchun vositalarni
taqdim etadi.
Ma'lumotlar bazasi xavfsizligi (Database Security): Ma'lumotlar
bazasi xavfsizligi muhimdir. DBMS, ma'lumotlarni himoyalash,
ro'yhatdan o'tkazilgan foydalanuvchilarga moslamalarni
bermoq va ma'lumotlarni maxfiy saqlash uchun xavfsizlik
tizimlarini o'z ichiga oladi.
Ma'lumotlar bazasi intizomiylik va qo'llab-quvvatlash (Data
Integrity and Support):Ma'lumotlar bazasi intizomiylikni
ta'minlash, qo'shimcha integritet tekshirishlarni o'tkazish,
ma'lumotlar bazasidagi to'g'ri ma'lumotlarni ta'minlash, amalga
oshirilayotgan to'g'ridan-to'g'ri operatsiyalarni boshqarish va
ma'lumotlar bazasidagi ma'lumotlarni saqlash uchun kerakli
qo'llab-quvvatlash tizimlarini o'z ichiga oladi.
Ikkilik daraxtlar, har bir tugun ichidagi har bir tugunni ikki
bo'limga bo'lgan strukturadagi ma'lumotlar tizimi. Bu struktura
quyidagicha tavsiflanadi:
1. **Birinchi tugun (Root Node):** Ikkilik daraxtni boshlang'ich
tuguni.
2. **Tugunlar (Nodes):** Har bir tugun ikki yoki undan ortiq
yengil tugunlar (left va right) bilan bog'langan.
3. **Yengil Tugunlar (Left va Right Children):** Har bir tugun
bitta "chap" va bitta "o'ng" yengil tugunlar bilan bog'langan.
4. **Ichki ta'rifiy tugun (Leaf Nodes):** Uchib ketadigan, yengil
tugunlari bo'lmagan tugunlar.
5. **Bo'lgan hajmi (Depth):** Daraxtning bir tugunidan boshlab
o'sha tugunga qancha yengil tugunlar orqali o'tishini ifodalovchi
o'zgaruvchi.
6. **Kengligi (Width):** Daraxtning bir satridagi yengil tugunlar
soni.
### Ikkilik Daraxtga Element Qo'shish, Element O'chirish va
Qidiruv Algoritmlari:
#### Element Qo'shish:
1. **Qidiruv (Search):** Qidiruv algoritmi asosan qiymatni
topib olish vaqtinchalik ko'rsatkichlar orqali qidirishni o'z ichiga
oladi.
2. **Qo'shish (Insertion):** Yangi element qo'shishda, daraxt
bo'sh yoki qator mavjud bo'lsa, yangi element boshlang'ich
tugun bo'ladi. Aks holda, qiymatni solishtirib, chap yoki o'ng
tomonda qidiruvni davom ettiradi va birinchi bo'sh joyda yangi
tugunni qo'shadi.
#### Element O'chirish:
1. **Tugunni Topish (Finding the Node):** O'chirish uchun,
o'chirilayotgan elementni topish kerak. Ushbu tugun
o'chirilgach, qolgan daraxtning strukturasi saqlanadi.
2. **O'chiruvchi Tugun (Node Deletion):** Tugunni o'chirishda,
uchun tanlangan element tugun bo'ladi. Agar o'chirilayotgan
tugun birinchi tugun bo'lsa, u o'zini o'chirishni o'z ichiga oladi.
Aks holda, tugunni o'chirishdan keyin, tugunni o'rniga kirishdan
avval o'ng yoki chap yengil tugunlari bilan almashtiriladi.
#### Qidiruv Algoritmi:
1. **Kengaytirilgan Tushuncha (Extended Definition):** Ikkilik
daraxt qidirish algoritmi, solishtirilayotgan qiymatni topish
uchun har bir tugunni tekshiradi va qidiruvni moslashtirishga
harakat qiladi.
2. **Qidiruv Tushunchasi (Search Algorithm):** Qidiruv
algoritmi asosan rekursiv yoki itterativ bo'lishi mumkin.
Rekursiv usul, daraxtni chap yoki o'ng tomonlarida qidiruvni
davom ettiradi, agar qidirilayotgan qiymat tugun qiymatidan
kichik bo'lsa, chap tomonni tekshiradi, aks holda o'ng tomonni
tekshiradi.
**AVL Daraxti:**
AVL daraxti, ikkilik daraxtlar (binary trees) oilasiga mansub bir
daraxt turi, lekin uni boshqarishda yuqori darajali avlavlantirish
(balanslashtirish) amaliyotlari o'tkazilgan. Har bir tugun uchun
chap va o'ng yengil subdaraxtlarining balansini ta'minlash
uchun qo'shilgan tugun kengaytmasi (height) orqali daraxtni
o'rganishni ta'minlaydi.
AVL daraxtida, har bir tugun uchun balans faktori hisoblanadi.
Balans faktori, o'ng yengil subdaraxtlarining kengaytmasi
(height) bilan chap yengil subdaraxtlarining kengaytmasi
orasidagi farqni ifodalaydi. Agar balans faktori +1, 0 yoki -1 ga
teng bo'lsa, daraxt balanslangan hisoblanadi. Aks holda, unga
qarshi chiqqan tomonlarda balanslash amaliyotlari o'tkaziladi.
AVL Daraxti Qo‘shish:
Qo'shish jarayonida daraxt balanslangan bo'lishi kerak.
Qo'shilayotgan element tugunni joylashish jarayonida, balans
faktori qo'shilayotgan tugunlarni ichiga olish va balanslash
jarayonida o'zgarishlarni amalga oshiradi.
AVL Daraxti O‘chirish:
O'chirish jarayonida ham daraxt balanslangan bo'lishi kerak.
O'chirilayotgan elementni o'chirish jarayonida, balans faktori
o'chirilayotgan tugunni ichiga olish va balanslash jarayonida
o'zgarishlarni amalga oshiradi.
Heap Tree:
Heap tree, avvalo, to'g'ri daraxt shaklida yaratiladi va
qoidalarga mos kelgandagi kamdan kam darajadagi daraxt
bo'lib, unda har bir tugun o'z qo'shimcha sharoyitasiga ega
bo'ladi. Ammo, heap tree bilan avlavlantirilgan daraxtlar
boshqarishda muvaffaqiyatli bo'lgan holda, heap tree
boshqarishda elementlarni chaqirish, qo'shish va o'chirish
jarayonlari uchun ishlatiladi.
Heap Tree Tuzilmasi:
1. **Max-Heap:** Har bir tugun o'z o'g'risi (left va right
subdaraxtlar) bilan solishtirib, o'zidan katta bo'lgan
elementlarni o'z ichiga oladi.
2. Min-Heap: Har bir tugun o'z o'g'risi (left va right subdaraxtlar)
bilan solishtirib, o'zidan kichik bo'lgan elementlarni o'z ichiga
oladi.
Max-heap yoki Min-heap hisoblanishi, daraxt balanslanmasa
ham uchun amaliyotlarni o'tkazishda yordam beradi. Bu tuzilma
oddiy daraxt shakli va o'zaro aloqa uchun yaxshi bo'lib,
amaliyotlarni tez, oddiy va samarali bajarish imkoniyatini
beradi.
Heap Tree Qo‘shish va O‘chirish:
Qo'shishda, yangi elementni daraxtning eng past yerga
joylashgan joyga joylashish va daraxtni qayta tuzish mumkin.
O'chirishda esa o'chirilayotgan elementni eng past yerga
joylashib, daraxtning qolgan qismini qayta tuzish mumkin.
**Graf** - bu matematik va informatika sohasida ishlatiladigan
abstrakt tushuncha, bir yoki bir nechta elementlarning (bu
elementlar birligini yoki elementlar orasidagi aloqani
ifodalovchi qatlamni bildiradi) ob'ektlar orasidagi aloqalarini
tasvirlash uchun ishlatiladi. Grafni tasavvur qilish uchun undagi
elementlarni "tik" (vertex, yoki bo'yoq) deb ataymiz, aloqalarini
esa "quloq" (edge) deyiladi.
### Grafning Asosiy Ko'rinishlari:
1. **Noto'g'ri Yo'nalishli Graf (Unidirectional Graph):** Ushbu
grafda aloqalar bitta tomonlama, ya'ni bir tikdan boshqa tikka
yo'naltiriladi. Aks holda, ikki uchun ham, aloqa mavjud emas.
2. **To'g'ri Yo'nalishli Graf (Bidirectional Graph):** Bu grafda
aloqalar ikki tomonlama, ya'ni bir tikning bitta uchun ham,
boshqa tikka ham aloqa bor.
3. **Birlamchi Graf (Connected Graph):** Ushbu grafda har bir
burchak aloqa bilan bog'langan bo'lib, bitta burchaktan boshqa
burchaklarga bor yollar mavjud.
4. **Chetlanmagan Graf (Disconnected Graph):** Bu grafda
biror ikki burchak aloqa bilan bog'langan bo'lsa ham, umuman
aloqa yo'q.
5. **Doiraviy Graf (Cyclic Graph):** Ushbu grafda aloqalar
orqali aylanadigan, ya'ni doiraga o'tkaziladigan yo'l bor.
6. **Doiraviy Emas Graf (Acyclic Graph):** Bu grafda aloqalar
orqali aylanmaydigan yo'l bor. Aks holda, doiraviy emas, to'g'ri
yo'nalishli (acyclic directed graph) deb ataladi.
7. **Yo'qotadi-chaqaradi Graf (Weighted Graph):** Ushbu
grafda aloqalarga bir "massa" (ya'ni og'irlik) asosan son tuziladi.
8. **O'zaro Aloqador Graf (Connected Graph):** Ushbu grafda
har ikki burchak aloqa bilan bog'langan bo'lib, bitta burchaktan
boshqa burchaklarga bor yollar mavjud.
Grafning yana boshqa ko'rinishlari ham mavjud. Bu usullar graf
turlariga, ulardagi aloqalarga, grafni rasmga olish usullariga, yo'l
yoki masofa hisoblash usullariga, yoki grafni topshirish yoki
sochuv usullariga asoslangan bo'lishi mumkin.
| 