Samarqand davlat universiteti raqamli texnologiyalar fakulteti dasturiy injiniring yo

O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA-MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETI
RAQAMLI TEXNOLOGIYALAR FAKULTETI
DASTURIY INJINIRING YO’NALISHI

“ALGORITMLAR VA MA’LUMOTLAR STRUKTURASI” FANIDAN

“PRIMA ALGORITMI” MAVZUSIDA TAYYORLAGAN

KURS ISHI


SAMARQAND – 2021

Reja:

Kirish
Asosiy qism:

1. 
   Graflar va ularning tasvirlanishi
   
2. 
   Graflarda eng kichik daraxt algoritmini qurish
   
3. 
   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.