|
O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA-MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETI
RAQAMLI TEXNOLOGIYALAR FAKULTETI
DASTURIY INJINIRING YO’NALISHI
110-GURUH TALABASI
QOBULOV ASRORNING
“ALGORITMLAR VA MA’LUMOTLAR STRUKTURASI” FANIDAN
“PRIMA ALGORITMI” MAVZUSIDA TAYYORLAGAN
KURS ISHI
Tekshirdi: Eshonqulov E.
SAMARQAND – 2021
Reja:
Kirish
Graflar va ularning tasvirlanishi
Graflarda eng kichik daraxt algoritmini qurish
Prima algoritmi
Xulosa
Foydalanilgan adabiyotlar
KIRISH
Avvalo algoritm tushunchasi IX asrlarda yashab ijod etgan buyuk bobokalonimiz Muhammad al-Xorazmiy nomi bilan uzviy bog’liqligini tushuntirish lozim. Algoritm so’zi al-Xorazmiyning arifmetikaga bag’ishlangan asarining dastlabki betidagi “Dixit Algoritmi” (“dediki al-Xorazmiy” ning lotincha ifodasi) degan jumlalardan kelib chiqqan. Shundan so’ng al-Xorazmiyning sanoq sistemasini takomillashtirishga qo’shgan hissasi, uning asarlari algoritm tushunchasining kiritilishiga sabab bo’lganligi ta’kidlab o’tiladi.
Algoritm nima degan savolga, u asosiy tushuncha sifatida qabul qilinganligidan, uning faqat tavsifi beriladi, ya’ni biror maqsadga erishishga yoki qandaydir masalani yechishga qaratilgan ko’rsatmalarning (buyruqlarning) aniq, tushunarli, chekli hamda to’liq tizimi tushuniladi.
Algoritm tushunchasi aniq shaklda XX-asr boshlarida D. Gilbert, K. Gyodel, S. Klin, A. Chyorch, E. Post, A. Tyuring, N. Viner, A. A. Markov singari olimlarning asarlari tufayli shakllandi.
Eng qadimiy raqamli algoritmlardan biri Yevklid algoritmi (miloddan avvalgi III asr) deb hisoblanadi - ikki sonning eng katta umumiy bo'luvchisini topish. Algoritmlarning zamonaviy nazariyasi nemis matematikasi Kurt Gyodel (1931) asarlari bilan boshlandi, ular o'zlarining rasmiy, izchil aksiomalar tizimi doirasida yechib bo'lmaydigan muammolar mavjudligini ko'rsatdi.
Graf tushunchasi
Graf - bu abstrakt obyekt bo’lib, uchlar to'plami (tugunlar) va qirralarning to'plami - uchlar juftliklari orasidagi bog'lanishlardan tashkil topadi (ulanishlar). Graf mavzusi juda keng. Graflar diskret matematikaning o'rganish mavzusidir (bu yerda graf tushunchasining aniqroq ta'rifi berilgan). Graf murakkab tuzilgan ma'lumotni tavsiflash uchun ishlatiladi va shuning uchun katta amaliy ahamiyatga ega. Matematikada graflar paydo bo'lishiga Eyler asarlari yordam berdi.
Graflar bilan qayerda uchrashamiz? Ehtimol, ular bilan qayerda uchrashmasligimizni aytish osonroq. Ya’ni biz graflarda juda ko’p holatda uchratamiz. Misol qilib quyidagilarni keltirishimiz mumkin:
Lokal yoki global tarmoq modeli
Algoritmlarning blok-sxemasi
Elektr sxemalar
Oila daraxti (Shajara)
Metro xaritasi
Ma'lumotlar bazasi modeli
Aqlli xaritalar
va boshqa ko'plab narsalar. Ushbu darsda butun graflar nazariyasini olish mumkin emas. Shuning uchun qisqacha ma’lumotlarni keltirib o’tamiz.
G graf - G: = (V, E) tartiblangan juftlik, bu yerda V - uchlarning (yoki tugunlarning) bo'sh bo'lmagan to'plami, E esa qirralar deb nomlangan uchlarning
1-rasm. Yo’naltirilmagan graf.
juftlari to'plamidir. Grafning uchlari va qirralari (ular graf elementlari deb ataladi), grafdagi uchlar soni | V | - graf tartibi, qirralarning soni | E | - graf hajmi deb ataladi.
2-rasm. Daraxt - bu bog'langan asiklik graf
Grafning asosiy atamalari. Bu yerda biz graflar nazariyasidan (diskret matematikaning bir bo'limi) atamalarning kichik tanlovini qildik, ammo bu atamalar boshqa adabiyotlarda boshqacha berilgan bo’lishi mumkin.
Boshlang’ich terminologiya
|
O’zbek
|
Рус
|
En
|
Tavsif
|
Uch
|
Вершина
|
vortex
|
Grafning elementi
|
Tugun
|
Узел
|
node
|
Uch tushunchasi bilan bir xil
|
Qirra
|
Ребро
|
edge
|
Ikki qo'shni uchlarning bog’lanishi
|
Yoy
|
Дуга
|
arc
|
Qirra bilan bir xil, lekin orgrafda emas
|
Aloqa, bog’lanish, munosabat
|
Связь
|
link
|
Graf elementi (qirra yoki yoy)
|
Qo’shnilik
|
Смежность
|
adjacent
|
Ikkita uch o’rtasida aloqa mavjud bo’lganini bildiruvchi atama
|
Insidentlik
|
Инцидентность
|
incident on
|
Uchga nisbatan qirra haqida
|
Daraja
|
Степень
|
degree
|
Uchga tutashgan qirralarning soni
|
1-jadval. Ternimlarning boshqa tillarda tarjimasi
Grafdagi marshrut - bu har bir uch (oxirgisidan tashqari) ketma-ketlikdagi keyingi uchga qirra bilan bog'langan uchlarning cheklangan ketma-ketligi.
Yo'l - bu qirralarning takrorlanmagan yo'lidir. Oddiy zanjir - bu uchlarni takrorlamaydigan marshrut (bu oddiy zanjirda takrorlanadigan qirralarning yo'qligini anglatadi)
Orgrafdagi yo'naltirilgan marshrut (yoki yo'l) - bu har bir element oldingi va keyingi qismga tushadigan uchlar va yoylarning cheklangan ketma-ketligi.
Birinchi va oxirgi uchlar bir-biriga to'g'ri keladigan zanjirlar sikl deb ataladi (1-rasmda ACD va ACDE sikllar)
Yo'lning (yoki siklning) uzunligi uni tashkil etuvchi qirralarning soni deyiladi
Agar uning qirralari takrorlanmasa, yo'l (yoki sikl) oddiy deb nomlanadi; agar u sodda bo'lsa va undagi tepaliklar takrorlanmasa u elementar deb nomlanadi.
Graf turlari
Yo'naltirilgan graf - (qisqacha orgraf) - qirralari yo'naltirilgan graf (4-rasm pastga qarang).
Yo'naltirilmagan graf - uchlar juftligi tartiblanmagan graf (3-rasm, pastga qarang).
Bog'langan graf - bu har qanday uch juftligi o'rtasida kamida bitta yo'l mavjud bo'lgan graf.
Daraxt - bu bog'langan asiklik grafik, ya'ni sikllar yo'q va tepalik juftligi orasida bitta yo'l bor (2-rasm). Kirishning nol darajasiga ega bo'lgan uch daraxtning ildizi, chiqish nol darajaga ega tugunlar esa barglar deb nomlanadi.
Do'stlaringiz bilan baham: | 
