Mavzu: Binar daraxtlarni tashkil qilish. Binar daraxtlar ustida amallar

tartibli o'tish sifatida tanilgan. Muqobil oʻtish strategiyasi chap
pastki daraxtni, oʻng pastki daraxtni va keyin operatorni rekursiv ravishda
chop etishdir. Ushbu oʻtish strategiyasi odatda buyruqdan keyingi
o'tish sifatida tanilgan. Uchinchi strategiya — avval operatorni chop
etish, soʻngra oldindan tartibli oʻtkazish deb nomlanuvchi chap va oʻng
pastki daraxtni rekursiv ravishda chop etish.
Ushbu uchta standartdan birinchi oʻtish uch xil ifoda formatlarining
ifodasidir: infiks, postfiks va prefiks. Infiks ifodasi tartibni kesib oʻtish orqali,
postfiks ifodasi buyruqdan keyingi oʻtish orqali va prefiks ifodasi oldindan
tartibli oʻtish orqali hosil boʻladi.
Infiks ifodasi chop etilganda, har bir ifodaning boshiga va oxiriga ochilish
va yopish qavslari qoʻshilishi kerak. Har bir pastki daraxt pastki ifodani
ifodalaganligi sababli, uning boshida ochilish qavslari va barcha sonlarni
qayta ishlagandan soʻng, yopish qavslari chop etiladi.
AMALIY MASHG’ULOT- 12
Mavzu: Muvozanatlangan binar daraxtlar. Graf tushunchasi. Tasvirlash
usullari.
Ishdan maqsad. Ushbu laboratoriya ishida talabalar binar daraxtlar
tushunchasi bilan tanishib chiqishi va inorder preorder hamda postorder
ko’rinishdagi tartiblar bilan tanishib chiqishlari kerak
Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda binar
darxtlar ustida berilgan amallar bilan ishlash ko’nikmasiga ega bo’lishlari
kerak.
Ish tartibi:

Tajriba ishi nazariy ma’lumotlarini o‘rganish;

Berilgan topshiriqning algoritmini ishlab chiqish;

C++ dasturlash muhitida dasturni yaratish;

Natijalarni tekshirish;

Hisobotni tayyorlash va topshirish.
Graf - bu ba'zi bir juft ob'ektlar havolalar orqali bog'langan ob'ektlar
to'plamining tasviriy tasviri. O'zaro bog'langan ob'ektlar tepaliklar deb

---

---

nomlangan nuqtalar bilan ifodalanadi va tepaliklarni bog'laydigan

bog'lanishlar qirralar deb nomlanadi.
Rasmiy ravishda, grafik - bu juftlik to'plami (V, E), bu erda V - tepaliklar
to'plami va E - qirralarning to'plami, tepalik juftlarini bir-biriga bog'lab turadi.
Quyidagi grafaga qarang

 Yuqoridagi grafikada,
 V = {a, b, c, d, e}
 E = {ab, ac, bd, cd, de}
 Amaliy mashg’ulot topshirig’i:

---

---

 Xulosa

Daraxt -
bu uning har bir tuguni nol yoki bir- necha bolaga ega bo‘lgan iyerarxik tuzilmadir.
Daraxt tuzilmasi quyidagi ko‘rinishda bo‘lishi mumkin: Bu daraxt oila tuzilmasini ifoda etmoqda.
Daraxt tugunlari odamlarni ifodalamoqda, chiziqlar esa ular orasidagi bog‘lanishni. Bu turdagi
maʼlumotlarni saqlash uchun daraxt tuzilmasi eng qulay tuzilma hisoblanadi.
Ikkilik (Binar) daraxt
Binar daraxt
yuqorida ko‘rsatilgan daraxtga o‘xshaydi, lekin baʼzi qoidalarga asosan quriladi:

Har bir tugundagi bolalar soni 2 tadan oshmasligi zarur

Xar qanday tugun qiymatidan kichik bo‘lgan qiymat chap farzandga yoki chap
farzandning chap farzandiga yoziladi

Xar qanday tugun qiymatidan katta bo‘lgan qiymat o‘ng farzandga yoki ong farzandning o‘ng
farzandiga yoziladi
Ahamiyat bering, bosh tugun (8)dan chapdagi barcha elementlarning qiymatlari sakkizdan kichik
undan o‘ngdagisi esa sakkizdan katta. Bu qoidalar daraxtning xar bir tuguniga tegishli.
Keling daraxt bo‘sh bo‘lgandan boshlab qanday qurilganini qarab chiqamiz. Birinchi navbatda 8 ni
qo‘shamiz. Dastlab daraxt bo‘sh bo‘lgani sabab u bosh tugun hisoblanadi. Undan keyin 4 ni
qo‘shamiz. 8 dan 4 kichik bo‘lgani uchun tepadagi qoidalarga amal qilgan xolda 4 ni 8 ning chap
tomoniga yozamiz. 8 ning hech qanday farzandi bo‘lmagani uchun 4 shu joyda qoladi.
Endi 2 kiritamiz. Maʼlumki 2 dan 8 katta, shu sabab chapga yuramiz. Chapda allaqachon qiymat

---

---

borligi sabab chap farzand qiymati 2 bilan solishtiriladi. Chap farzandning qiymati (4) 2 dan kata

bo‘lgani sabab 4 ning chap tomoni qaraladi. 4 ning chap tomonida element bo‘lmagani sabab 2 shu
joyga joylashtiriladi. Shunday qilib kiritilgan xar bir element uchun yuqoridagi solishtiruvlar qaytariladi.
Daraxtdan element olib tashlash
Daraxt elementini o‘chirish oddiy tuyulishi mumkin, lekin hisobga olish kerak bo‘lgan holatlari mavjud.
Algoritmning umumiy ko‘rinishi quyidagicha:

Qiymatga mos elementni topish

Uni o‘chirish
AMALIY MASHG’ULOT- 13
Mavzu: Graf tushunchasi. Eng qisqa yo’lni aniqlash algoritmlari. Sinov
turlarini o’rganish.
Ishdan maqsad. Ushbu laboratoriya ishida talabalar Grafning asosan
matritsali usuli bilan tanishib chiqishi kerak
Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda graf
ustida berilgan amallar asosan bog’langan ro’yhatlar bilan ishlash
ko’nikmasiga ega bo’lishlari kerak.
Ish tartibi:
 Tajriba ishi nazariy ma’lumotlarini o‘rganish;
 Berilgan topshiriqning algoritmini ishlab chiqish;
 C++ dasturlash muhitida dasturni yaratish;
 Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
Grafik tasvirlari
Grafik ma'lumotlar tuzilishi quyidagi tasvirlar yordamida namoyish etiladi ...
- Yaqinlik matritsasi
- Hodisa matritsasi
- Yaqinlik ro'yxati
Yaqinlik matritsasi
Ushbu rasmda grafika umumiy tepaliklar sonining umumiy sonlari
matritsasi yordamida namoyish etiladi. Demak, 4 vertikalli grafik 4X4
o'lchamdagi matritsa yordamida tasvirlangan. Ushbu matritsada ikkala satr
va ustunlar tepaliklarni aks ettiradi. Ushbu matritsa 1 yoki 0 bilan to'ldirilgan.
Bu erda 1 satr vertikalidan ustun tepasiga chekka borligini, 0 esa satr
tepasidan ustun vertikaligacha chekka yo'qligini bildiradi.

---

---

Masalan, quyidagi yo'naltirilmagan grafik tasvirini ko'rib chiqing

Amaliy mashg’ulot topshirig’i:
Xulosa
Graflar ixtiyoriy sistemaning topologiyasini ko`rish imkonini beradi. Graflar nazariyasi
asosida turli nazariy va amaliy masalalarni yеchish mumkin. Amaliy masalalardan biri 2
ta tugun va tugunlar orasidagi eng qisqa yo`lni topish masalasidir. Bunda bir necha
tugunlar va yoylardan iborat graf berilgan bo`ladi. Yoylarning vazni matritsa shaklida
quyidagicha beriladi: Ixtiyoriy 2 tugun orasidagi eng qisqa yo`lni topish masalasini
yеchishni turli usullari mavjud. Bularga barcha yo`llarni bir chekkadan qarab chiqish
(prostoy), optimallashning Bellman prinsipi, va Deykstra usullari kiradi. Ulardan eng
samaralisi Deykstra usulidir. Bu usul graflarning tugunlariga vaqtinchalik belgilar
qo`yishga asoslangandir. Bunda yoylarning vazni bo`lgan musbat sonlardan iborat
bo`lad Deykstra algoritmi quyidagi bosqichlardan iborat bo`ladi:  Graf tugunlariga
keyinchalik ma’lum qonuniyatga ko`ra doimiy belgiga almashtiriladigan vaqtinchalik
belgilashlar qo`yiladi:  Grafning boshlang`ich tuguniga 0 qiymat, qolganlariga esa

---

---

vaqtinchalik cheksiz belgisi qo`yiladi, . Jadval quyidagi tartibda tuzib olinadi: Jadvalning

qatorlariga qadamlar ketmaketligi, ustunlarga esa berilgan misoldagi barcha tugunlar
nomi, oxirgi ustundan bitta oldingi ustunga doimiy belgi olgan tugun nomi, oxirgi
ustunga esa belgi olgan (shu qadam uchun) tugunning kattaligi kiritiladi. Jadvaldagi
ustunlar va qatorlar soni berilgan misoldagi tugunlar sonidan kelib chiqadi. Jadvalning
oxirgi ikkita ustunidagi doimiy belgi olgan tugunlar ketma-ketligi va kattaliklar eng qisqa
yo`l ni beradi
AMALIY MASHG’ULOT- 14
Mavzu: Sinovni rejalashtirish. Modulli yoki iteratsion testlash ma’lumotlar
to’plamini yaratish.
Ishdan maqsad. Ushbu laboratoriya ishida talabalar testlashda
ishlatiladigan google test turi bilan tanishib chiqishi kerak
Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda gtestda
asosan mantiqiy amallar va xatoliklar bilan ishlash ko’nikmasiga ega
bo’lishlari kerak.
Ish tartibi:
 Tajriba ishi nazariy ma’lumotlarini o‘rganish;
 Berilgan topshiriqning algoritmini ishlab chiqish;
 iSpring da dasturni yaratish;
 Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.

---

---

Amaliy mashg’ulot topshirig’i:

---

---

Xulosa
UML modeli(UML modeli) - bu til konstruktsiyalarining chekli to'plami

bo'lib, ularning asosiylari ob'ektlar va ular orasidagi munosabatlardir.
Modelning ob'ektlari va munosabatlarining o'zi metamodelning meta-
sinflari misolidir.
UML modelini eng umumiy nuqtai nazardan ko'rib chiqsak, bu grafik
(aniqrog'i yuklangan ko'p psevdo-giper-digraf) deb aytishimiz mumkin,
uning cho'qqilari va qirralari qo'shimcha ma'lumotlar bilan yuklanadi va
murakkab ichki tuzilish. Bu grafikning uchlari ob'ektlar, qirralari esa
munosabatlar deb ataladi... Ushbu bo'limning qolgan qismi mavjud
ob'ektlar turlari va munosabatlarining tez (dastlabki), lekin to'liq
ko'rinishini taqdim etadi. Yaxshiyamki, ularning soni unchalik ko'p
emas. Kitobning keyingi boblarida barcha ob'ektlar va munosabatlar
yana batafsilroq va misollar bilan ko'rib chiqiladi.
AMALIY MASHG’ULOT- 15
Маvzu: Ma’lumotni tasvirlash modellarini o’rganish. UML modellashtirish
tili bilan ishlash.

---

---

Ishdan maqsad. Ushbu laboratoriya ishida talabalar UML muhiti bilan

tanishib chiqishi kerak
Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda
modellar bilan ishlash ko’nikmasiga ega bo’lishlari kerak.
Ish tartibi:
 Tajriba ishi nazariy ma’lumotlarini o‘rganish;
 Berilgan topshiriqning algoritmini ishlab chiqish;
 Code blocks dasturni yaratish;
 Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
UML qisqartirilgan so'z bo'lib, Unified Modeling Language degan
ma'noni anglatadi. Oddiy qilib aytganda, UML bu dasturiy ta'minotni
modellashtirish va hujjatlashtirishga zamonaviy yondashuv. Aslida, bu eng
mashhur biznes jarayonlarini modellashtirish usullaridan biridir.
UML-dan foydalanish nimadan iborat?
UML asosan dasturiy ta'minot muhandisligi sohasida umumiy
maqsadli modellashtirish tili sifatida ishlatilgan. Biroq, endi u bir nechta
biznes jarayonlari yoki ish oqimlari hujjatlarini topdi. Masalan, oqim
diagrammalarining o'rnini bosuvchi vosita sifatida UML diagrammasining
bir turi bo'lgan faoliyat diagrammalaridan foydalanish mumkin. Ular ish
oqimlarini
modellashtirishning
yanada
standartlashtirilgan
usulini,
shuningdek o'qish va samaradorlikni oshirish uchun kengroq xususiyatlarni
taqdim etadi.
UML diagrammalari bu holda tizimning turli jihatlari va xususiyatlarini
etkazish uchun ishlatiladi. Biroq, bu tizimning faqat yuqori darajadagi
ko'rinishi va, ehtimol, loyihani oxirigacha bajarish uchun barcha kerakli
ma'lumotlarni o'z ichiga olmaydi.
UML diagrammalarining turlari
UML diagrammalarining bir nechta turlari mavjud va ularning har biri
amalga oshirishdan oldin yoki undan keyin (hujjat qismi sifatida) ishlab
chiqilganligidan qat'i nazar, har xil maqsadga xizmat qiladi.
Boshqa barcha turlarni o'z ichiga olgan ikkita eng keng toifalar - bu
xatti-harakatlarning UML diagrammasi va Strukturaviy UML diagrammasi.
Nomidan ko'rinib turibdiki, ba'zi UML diagrammalar tizim yoki jarayonning
tuzilishini tahlil qilishga va tasvirlashga harakat qilsa, boshqalari tizimning
xatti-harakatlarini, uning aktyorlari va qurilish tarkibiy qismlarini tavsiflaydi.
Turli xil turlari quyidagicha taqsimlanadi:

---

---

Use case diagrammasi

Tizimning asosiy qismi bu tizim bajaradigan funktsional talablardir.
Use Case diagrammasi tizimning yuqori darajadagi talablarini tahlil qilish
uchun ishlatiladi. Ushbu talablar turli xil foydalanish holatlari orqali ifoda
etilgan. Ushbu UML diagrammasining uchta asosiy tarkibiy qismini
ko'rmoqdamiz:
Funktsional talablar - foydalanish hollari sifatida ifodalanadi;
harakatni tavsiflovchi fe'l
Aktyorlar - ular tizim bilan o'zaro aloqada bo'lishadi; aktyor inson,
tashkilot yoki ichki yoki tashqi dastur bo'lishi mumkin
Aktyorlar va foydalanish holatlari o'rtasidagi munosabatlar - to'g'ri
o'qlar yordamida tasvirlangan
Quyidagi misolda inventarizatsiyani boshqarish tizimi uchun UML
diagrammasi tasvirlangan. Bunday holda bizda egasi, etkazib beruvchisi,
menejeri, inventarizatsiya bo'yicha kotibi va inventarizatsiya inspektori
mavjud.
Amaliy mashg’ulot topshirig’i:

---

---

---

---

.
Xulosa

Strukturaviy ob'ektlar, siz taxmin qilganingizdek, tuzilmani tavsiflash
uchun mo'ljallangan. Odatda, tarkibiy tuzilmalar quyidagilarni o'z ichiga
oladi.
Ob'ekt(ob'ekt) 1 - noyob bo'lgan va holat va xatti-harakatni qamrab
oluvchi ob'ekt.
Sinf(sinf) 2 - holatni aniqlaydigan umumiy atributlarga ega bo'lgan
ob'ektlar to'plamining tavsifi va xatti-harakatni belgilaydigan
operatsiyalar.
Interfeys(interfeys) 3 - iste'molchi tomonidan so'ralishi mumkin bo'lgan
va xizmat ko'rsatuvchi provayder tomonidan taqdim etilishi mumkin
bo'lgan xizmatlar to'plamini belgilaydigan nomli operatsiyalar to'plami.
Hamkorlik(hamkorlik) 4 - maqsadga erishish uchun o'zaro ta'sir
qiluvchi ob'ektlar to'plami.
Aktyor(aktyor) 5 - modellashtirilgan tizimdan tashqarida bo'lgan va u

---

---

bilan bevosita o'zaro aloqada bo'lgan shaxs.

∇ Bunday munosabat, albatta, mavjud bo'lib, u rasmda
ko'rsatilgan. UML 1 uchun diagramma turi ierarxiyasi nozik stereotip
bilan bog'liqlik munosabatlari sifatida.
∇∇ UML 1da hamkorlik diagrammasi va bir xil nomdagi ob'ekt
o'rtasida ixtiyorsiz bog'lanish paydo bo'ldi, bu mutlaqo to'g'ri emas va
ba'zan noto'g'ri edi.
∇∇∇ UML 2 da holat diagrammasining sintaktik va semantik
yuklanishi shunchalik o'zgarganki, nom endi tarkibni aks ettirmaydi.
Ushbu kitobda foydalanilgan yangi jadvallar ro'yxati va ularning nomlari
quyida ko'rsatilgan.
Kompozit tuzilma diagrammasiPaket diagrammasiDavlat mashinasi
diagrammasiAloqa diagrammasiO'zaro ta'sirni ko'rib chiqish
diagrammasiVaqt diagrammasi
Shaklda. UML 2 uchun diagramma turi ierarxiyasi (1 va 2-qism) UML 2
da diagrammalarning munosabatini ko'rsatadigan sinf diagrammasi.
Keyinchalik ushbu bobda biz ma'lum bir kontekst va lug'atga ega
bo'lish uchun barcha o'n uchta kanonik diagrammalarni qisqacha
tasvirlab beramiz. Tafsilotlar kitobning qolgan boblarida keltirilgan.
Ammo keyingi bo'limga o'tishdan oldin, standart diagrammalarni
qanday formatlashni talab qilishi haqida kichik bir fikr yuritamiz.
Umumiy diagramma taqdimoti shabloni quyida ko'rsatilgan.
Ikkita asosiy dizayn elementi mavjud: tashqi ramka va diagramma
nomi bilan yorliq. Agar ramka bilan hamma narsa oddiy bo'lsa - bu
diagramma elementlari joylashishi kerak bo'lgan maydonni
chegaralovchi to'rtburchak bo'lsa, unda diagrammaning nomi rasmda
ko'rsatilgan maxsus formatda yoziladi. Diagrammalar uchun belgi.
Yorliqning ko'rsatilgan murakkab shakli barcha vositalar tomonidan
qo'llab-quvvatlanmaydi. Biroq, bu shart emas, chunki semantika
birlamchi, yozuv esa ikkinchi darajali. Bundan buyon biz to'rtburchakni
diagramma uchun yorliq sifatida ishlatamiz va bu hech qanday
chalkashlikka olib kelmasligi kerak.
Grafiklar uchun mumkin bo'lgan teglar (turlar) quyidagi jadvalda
ko'rsatilgan. Standart tomonidan taklif qilingan teglar ikkinchi ustunda

---

---

yoziladi. Biroq, amaliyot shuni ko'rsatadiki, standart tomonidan taklif

qilingan qoidalar har doim ham qulay va mantiqiy asoslanmaydi,
shuning uchun jadvalning uchinchi ustunida bizning fikrimizcha,
oqilona alternativ mavjud.
Tab. Diagramma turlari va teglari
Grafik sarlavhasiTeg (standart)Teg (tavsiya etiladi)Foydalanish
diagrammasifoydalanish holati yoki ucfoydalanish holatiSinf
diagrammasisinfsinfAvtomat diagrammasidavlat
mashinasi yoki stmdavlat mashinasiFaoliyat
diagrammasifaoliyat yoki harakatfaoliyatKetma-ketlik
diagrammasio'zaro ta'sir yoki sdsdAloqa diagrammasio'zaro
ta'sir yoki sdcommKomponent
diagrammasikomponent yoki cmpkomponentJoylashtirish
diagrammasianiqlanganjoylashtirishObyekt
diagrammasianiqlanganob'ektIchki tuzilish
diagrammasisinfsinf yoki komponentO'zaro ta'sirning umumiy
diagrammasio'zaro ta'sir yoki sdo'zaro ta'sirSinxronizatsiya
diagrammasio'zaro ta'sir yoki sdvaqtPaket
diagrammasipaket yoki pkgpaket
UML hozirda 1997 yilning kuzida Object Management Group (OMG)
tomonidan qabul qilingan dasturiy ta'minot tizimlarini vizual
modellashtirish uchun standart belgi bo'lib, ko'plab ob'ektga
yo'naltirilgan CASE mahsulotlari tomonidan qo'llab-quvvatlanadi.
UML standarti modellashtirish uchun quyidagi diagrammalar to'plamini
taklif qiladi:
· Foydalanish diagrammasi - tashkilot yoki korxonaning biznes
jarayonlarini modellashtirish va yaratilayotgan axborot tizimiga
qo'yiladigan talablarni aniqlash uchun;
· Sinf diagrammasi (sinf diagrammasi) - tizim sinflarining statik
tuzilishini va ular orasidagi bog'lanishlarni modellashtirish uchun;
Xulq-atvor sxemalari
· O'zaro ta'sir diagrammalari;
· Ketma-ketlik diagrammalari - bir martalik foydalanish doirasidagi
ob'ektlar o'rtasida xabar almashish jarayonini simulyatsiya qilish uchun;
· Hamkorlik diagrammasi - bitta foydalanish holati doirasidagi ob'ektlar

---

---

o'rtasida xabar almashish jarayonini modellashtirish uchun;

· Statechart diagrammasi - bir holatdan ikkinchi holatga o'tishda tizim
ob'ektlarining harakatini modellashtirish uchun;
· Faoliyat diagrammasi - turli xil foydalanish holatlari yoki
modellashtirish faoliyati doirasida tizimning xatti-harakatlarini
modellashtirish uchun;
Amalga oshirish sxemalari:
Komponent diagrammalari - axborot tizimining tarkibiy qismlari (quyi
tizimlar) ierarxiyasini modellashtirish uchun;
· Joylashtirish diagrammasi - loyihalashtirilgan axborot tizimining fizik
arxitekturasini modellashtirish uchun.
Shaklda. 1.1 axborot tizimining integratsiyalashgan modelini, shu
jumladan ushbu kurs loyihasida ishlab chiqilishi kerak bo'lgan asosiy
diagrammalarni taqdim etadi.

http://fayllar.org