|
O'zbekiston respublikasi raqamli texnologiyalar
|
| bet | 1/2 | | Sana | 25.05.2024 | | Hajmi | 337,56 Kb. | | #253425 |
Bog'liq Algoritmlarni loyihalash 25.05(Maruza)
O'ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
SAMARQAND FILIALI
'Dasturiy injinering' kafedrasi
N°__ Mustaqil ta'lim ish hisoboti
Fan "Algoritlarni loyihalash"
. Guruh: DI 22-11
Talaba: Bo'ronov D.
Rahbar: Bobonazarov A.
Samarqand - 2024 y.
Ketma-ketliklar, to’plamlar, daraxtlar, graflarni ifodalash usullari.
Graflarni eng arzon tayanch daraxtini qurishda Kruskal xasis algoritmi
“Ajrat va hukmronlik qil” tipidagi algoritmlar.
Graflar nazariyasining asosiy tushunchalari. Matematik nazariyada va informatikada graf — bu tugunlar(uchlar)dan iborat bo'lgan bo'sh bo'lmagan to'plam va tugunlarni birlashtiruvchi yoylar majmuidir.
Graf - bu murakkab chiziqsiz ko'pbog'lamli dinamik tuzilma bo'lib, murakkab ob'ektlarning xususiyatlari va munosabatlarini aks ettiradi.
Ob'ektlar tugun yoki graf uzellari ko'rinishida va munosabatlar yoy yoki yo'naltirilgan qirralar kabi ifodalanadi.
«Graf» tushunchasini birinchi marotaba 1936 yil vengriya matematigi Denni Kyonig kiritgan. Lekin graflar nazariyasi bo'yicha 1-ish Leonard Eylerga tegishli bo'lgan va u 1736 yilda bajarilgan edi.
XVIII asrda mashhur shvetsariyalik matematik, mexanik va fizik Leonard Eyler (1707-1783 yy) Kyonigsberg ko’prigi haqidagi masalani yechish uchun birinchi marta graf tushunchasidan foydalanadi.
Graflarni ifodalash usullari. Yo’naltirilmagan, yo’naltirilgan va o’girlikka ega bo’lgan graflarni kompyuter dasturlash tillari hotirasida ifodalash, ya'ni xotirada tashkil etish uchun statik tuzilmasi matritsadan yoki dinamik tuzilmasi ro’yxatlardan foydalanish mumkin. Har qanday masalalarida har bitta usulining o’zining afzalligi va kamchiliklariga egadir. Yo’naltirilmagan, yo’naltirilgan va o’girlikka ega bo’lgan graflarni ifodalash uchun har usulining o’zining qoida asosida shakllanadi. Shunday to’rtta usullarga to’xtalib o’tamiz:
Qo'shma matritsa (adjacency matrix);
Intsidientlik matritsa (incidence matrix);
Qo'shnilik ro'yxati (adjacency list);
Qirralar ro'yxati (edges list).
Ketma-ketliklar
Ma’lumki, axborot texnologiyalari jadal suratlar bilan EXMda ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri bo’lib hisoblanadi. Uning vazifasi berilgan argument bo’yicha massiv ma’lumotlari ichidan mazkur argumentga mos ma’lumotlarni topishdan iborat.
Ixtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi. Ixtiyoriy ma’lumot (yoki tuzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noyob bo’lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagona bo’lishi mumkin. Bunday noyob kalitga boshlang’ich (birinchi) kalit deyiladi. Ikkinchi kalit bir jadvalda takrorlansada u orqali xam qidiruvni amalga oshirish mumkin.
|
| |
