‘l texnikumi “Temir yo'l transportida intellektual axborot tizmlari va ularni loyihalash

Mavzu:10.Ma'lumotlarning to'r (tarmoqlangan) modellari.
Reja:
1. Tarmoqli modellar to‘g‘risida tushuncha.
2. Tarmoqli graflar va ularni tuzish yo‘llari.
3. Tarmoqli rejalashtirish masalasining algoritmi.
Tarmoqli tahlil (setevoy analiz) – loyiha xarakteridagi, ya’ni qoidaga ko‘ra operatsiyalari takrorlanmaydigan ishlarni rejalashtirish usulidir. Ushbu usuldan operatsiyalarni bajarishning kalendar rejasini tuzishda, qurilish ishlarining bajarilishini rejalashtirishda ko‘proq foydalaniladi.
Tarmoqli tahlil usullari katta miqdordagi o‘zaro bog‘liq operatsiyalarni o‘z ichiga olgan loyihalarni tahlil etishga imkon beradi. Ushbu usullar yordamida ishlar bajarilishining davom etish ehtimolligini, ularning qiymatini, vaqt va pul mablag‘larini tejash kabi ko‘rsatkichlarni hisoblash mumkin.
Tarmoq modellari - U asosiy tashkiliy asbob. Taqvim rejalashtirishga ruxsat berish, ishning davomiyligini kamaytirish, ishning narxini optimallashtirish, operatsion boshqaruvni tashkil etish va loyihani amalga oshirish monitoringi. Texnik ketma-ketlikda barcha zarur jarayonlar (boshqaruv vazifalari) tasvirlangan tarmoq modeli - yo'naltirilgan grafik.Tarmoq matritsasi UE jarayonining grafik tasviridir, unda barcha operatsiyalar, boshqaruv vazifalari, loyiha uchun zarur bo'lgan barcha operatorlar va kalendar kunlarining texnologik ketma-ketligi bo'yicha belgilanadi. Tarmoq matritsasidan foydalanish sizga barcha ish kompleksini tezda hisoblash va boshqaruv qarorlarini qabul qilishga imkon beradigan keng qamrovli ma'lumot loyihasini boshqarishga imkon beradi.
Bo'shliqlar daraxti.
Bo'sh joy uchun ajdodlar makonida yotgan barcha , uchlari ko'rinadi qolganlari ko'rinmas. "Ko'rinish" munosabati "istiqbollar" to'plami tartibida makonni guruhlash imkonini beradi. Ierarxik tarmoqlarni grafik tasvirlash uchun qoidalar yoki konventsiyalarni ko'rib chiqing: 1. bir xil bo'shliqdagi vertikal va yoylar to'g'ridan-to'g'ri yoki ko'pburchak bilan bog'langan; 2. yoy uning nomi joylashgan bo'sh joyga tegishli; 3. bo'sh joy i ichki bo'shliq tasvirlangan avlod deb hisoblanadi (ichki daraja), ya'ni. dan "Aftidan" . mavjud bo'lgan "eng yuqori" deb hisoblash mumkin . Semantik tarmoq tipidagi ma'lumotlar bazasida echim topish muammosi, etkazib berilgan tarmoqqa mos keladigan ma'lum bir pastki tarmoqqa mos keladigan tarmoq qismini topish muammosiga qadar kamayadi.
Graflar
Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plamidan iborat bo’lgan abstrakt matematik ob’ektdir. Grafning elementlari tarkibi va munosabatlar tuzilishi beriladi. Grafning tarkibiy qismlari bu uning tugunlari va qirralaridir.
Tarmoq
Bir nechta juft tugunlararo qirralardan iborat bo’lgan turlicha yo’llar to’plami mavjud bo’lishi mumkin. Yopiq yo’llar – sikllarning mavjud bo’lishi tarmoqlarga xos xususiyatdir. Yonaltirilmagan graf yoki simmetrik bog’liqlik
qirra yoylar. Ilmoq – aynan bitta tugundan chiqib, yana shu tugunga kiruvchi qirra.
Deykstra algoritmi
Gollandiyalik olim Edsger Deykstra algoritmi grafning boshlang’ich berilgan tugunidan boshlab qolgan barcha tugunlargacha bo'lgan barcha eng qisqa yo'llarni topadi. Uning yordamida, agar barcha zarur ma'lumotlar berilgan bo'lsa, masalan, neft va shu kabi mahsulotlarni eksport qilish uchun bitta shahardan boshqa shaharlarning har biriga borish uchun qaysi yo'llar ketma-ketligini tanlash afzalroq ekanligini bilib olish mumkin. Ushbu usulning salbiy tomoni shundaki, manfiy vaznga ega bo’lgan qirralari mavjud bo'lgan graflarni qayta ishlash imkonining mavjud emasligi, ya'ni, masalan, ba'zi tizim birorta kompaniya uchun foydasiz bo'lgan marshrutlarni taqdim qilsa, u holda u bilan ishlash uchun Dijkstraning algoritmidan foydalanib bo’lmaydi.
Algoritmni dasturiy ta'minotini amalga oshirish uchun ikkita massiv kerak bo'ladi: mantiqiy toifadagi visited - tashrif buyurilgan tugunlar haqidagi ma'lumotlarni saqlash uchun va topilgan eng qisqa yo'llar kiritiladigan butun toifadagi - distance. G={V,E} graf berilgan bo’lsin. V to’plamga tegishli barcha tugunlar dastlab tashrif buyurilmagan deb belgilanadi, ya’ni visited massivining elementlariga false qiymat berib chiqiladi.
Bellman-Ford algoritmi
Algoritm tarixi uchta mustaqil matematiklar bilan bog'liq: Lester Ford, Richard Bellman va Edward Moore. Ford va Bellman algoritmni 1956 va 1958 yillarda nashr etishdi, Moore esa 1957 yilda taqdim qilgan. Va ba'zan uni Bellman-Ford-Moore algoritmi deb ham atashadi. Usul ba'zi vektorli-marshrutlash protokollarida, masalan, RIPda (Routing Information Protocol) qo'llaniladi. Deykstra algoritmi singari, Bellman-Ford algoritmi ham vaznga ega bo’lgan graflarda bitta tugundan qolgan barcha tugunlarga bo’lgan eng qisqa masofani aniqlashda ishlatiladi.
Tarmoqli rejalashtirish masalasining algoritmi.
Bajariladigan ishlar oddiy bo‘lsa, yuqorida ko‘rib o‘tgan grafik usuli yordamida rejalashtiriladi. Agarda bajariladigan kompleks ishlar murakkab bo‘lsa (ayrim hollarda ishlar soni va mantiqiy aloqalar mingdan va undan ortiq bo‘lishi mumkin), albatta EHM yordamida hal qilinishi uchun ishlarning aniq ketma-ketligi yoki algoritmi tuzib olinadikritik yo‘l” usulini ko‘rib o‘tamiz. (CPM – Critical Path Method). Bu usul asosida yangi mahsulotni yaratish, bino va inshootlar qurilishi, murakkab uskunani ta’mirlash masalalarini yechish mumkin.
Loyihani amalga oshirishda ishlarni bajarish grafigi tuziladi. Bunda murakkab omil bo‘lib, ishlarning o‘zaro bog‘liqligi hisoblanadi. Ayrim ishlar boshqa ishlarning bajarilishiga bog‘liq va boshqa ishlar bajarilmasdan turib ushbu ishlar boshlanmaydi.

Ma’lumotlarning ierarxik va tarmoq modellari

Mashina muhitidagi ma’lumotlarning murakkabroq modellari - tarmoqli va ierarxik modellar bo‘lib hisoblanadi. Bu modellar ularning o‘zlariga xos turdagi ma’lumotlar bazasini boshqarish tizimida ishlatiladi. MBBTda ma’lumotlarni mantiqiy tashkil etish usuli ma’lumotlarning tarmokli yoki ierarxik modeliga mos holda ko‘rsatiladi. Bunday model o‘zaro bog‘liq ob’ektlarning majmuidir. Ikki ob’ektning aloqasi ularning bir-biriga tobeligini aks ettiradi. Tarmokli yoki ierarxik modelida ob’ekt bo‘lib, MBBT kiritilgan ma’lumotlar tuzilmasining asosiy turlari hisoblanadi. Turli MBBTlarda bu turdagi ma’lumotlarning tuzilmasi turlicha aniqlanishi va nomlanishi mumkin.

Modellarda ma’lumotlarning tuzilmalari. Ma’lumotlarning namunaviy tuzilmalariga quyidagilar kiradi: ma’lumotlarning elementi, ma’lumotlarning agregati, yozuv, ma’lumotlar bazasi va h.k. Bu elementlar va agregatlai o‘zaro aloqada bo‘lgan tuzilma bilan tavsiflanadi. SHuning uchun yozuvning tuzilmasi ierarxik xarakterga ega bo‘lishi mumkin. Bir xil tuzilmaga ega bo‘lgan yozuv nusxalari to‘plamining hammasi yozuv turini tashkil etadi.

Ma’lumotlarning elementi - bu ma’lumotlar tuzilmasining nomlangan minimal birligi (faylli tizimlardagi maydonning o‘xshashi).

Ma’lumotlar agregati - bu ma’lumotlar elementlarning quyi to‘plami yoki yozuvlar ichidagi boshqa agregatlarning nomlangan quyi to‘plami.
YOzuv - umumiy holda agregat bo‘lib, u boshqa agregatlarning tarkibiga kirmaydigan tarkibli agregatdan iborat.
Ob’ektlarning modellardagi aloqasi. Ma’lumotlar modeli bir necha turidagi yozuvlarni (obьektlarni) o‘z ichiga olishi mumkin. Ma’lumot modeli ob’ektlar o‘rtasida aloqalar o‘rnatadi. Qandaydir bir predmet sohasi uchun modelning o‘zaro bog‘langan muayyan ob’ektlar to‘plami ma’lumotlar bazasini tashkil qiladi.
Ikki turdagi yozuvlarning (model ob’ektlari) o‘rtasidagi aloqalar, ularning nusxalari o‘rtasidagi guruh munosabatlari bilan aniqlanadi. Guruh munosabati - bu ikki turdagi yozuvlar o‘rtasidagi kat’iy ierarxik munosabat bo‘lib, ular asosiy yozuvlar to‘plami va tobe yozuvlar to‘plamidan iboratdir.
Ierarxik modellarda kalit bo‘yicha bevosita kirish odatda, faqat boshqa ob’ektlarga tobe bo‘lmagan eng yuqori pog‘onadagi ob’ektgagina mumkin. Boshqa ob’ektlarga kirish modelning eng yuqori pog‘onasidagi ob’ektdan aloqalar bo‘yicha amalga oshiriladi. Tarmoqli modellarda esa kalit bo‘yicha bevosita ixtiyoriy ob’ektga kirish (uning modelda joylashgan pog‘onasidan qa’tiy nazar) ta’minlanishi mumkin.. SHuningdek, aloqalar bo‘yicha har qanday nuktadan kirish ham mumkin. Tarmokli modellarda ob’ekt (yozuv, fayl)ning tuzilmasi ko‘pincha chiziqli va kamroq hollarda esa ierarxik bo‘ladi. Quyi pog‘onadagi ma’lumotlarning tuzilmasi ham o‘z xususiyatga va nomiga ega bo‘lishi mumkin. Masalan, atribut bu ma’lumotlar elementining analogi. CHiziqli tuzilmaga ega bo‘lgan ob’ekt faqat oddiy va kalit atributlardan iborat. Ierarxik modellardagi ob’ekt (yozuv, segment) tuzilmasi ierarxik yoki chiziqli bo‘lishi mumkin.
Turli predmet sohalari uchun ma’lumotlarning tarmokli modeli ierarxik modeliga nisbatan mashinaning ish muhitida axborot tuzilmalarini aks ettiruvchi umumiy vosita hisoblanadi. Ko‘plab predmet sohalarining maьlumotlari o‘rtasidagi aloqalar tarmoqli ko‘rinishga ega. Bu esa ma’lumotlarning ierarxik modeliga ega bo‘lgan MBBTdan foydalanishni cheklab qo‘yadi. Tarmoqli modellar, ma’lumotlarning ierarxik aloqasini ham aks ettirishga imkon beradi. Bundan tashqari, tarmoqli modellar bilan ishlash texnologiyasi foydalanuvchi uchun qulaydir, chunki ma’lumotlarga kirishni amalga oshirishda hech qanday cheklashlar yo‘q va bevosita ixtiyoriy pog‘onadagi ob’ektlarga kirish imkoni mavjud.
Ierarxik ma’lumotlar bazasida - ma’lumotlar ierarxiya (daraxt) ko‘rnishida saqlanadi. Uning ko‘rinishini quyidagicha tasvirlash mumkin.

Ma’lumotlarning ierarxik modeli
Masalan, bu erda A12 tugunidagi ma’lumotni olish uchun, oldin MBdan A tugun, keyin A1 tugun va undan keyin A12 topiladi.
Tarmoq ma’lumotlar bazasi - ichki ma’lumotlar strukturasi, biri ikkinchisiga boqliq ravishda bo‘ladi. Uning ko‘rinishini quyidagicha tasavvur qilish mumkin.

Ma’lumotlarning tarmoq modeli
Ierarxik va tarmoq modellarida ma’lumotlar tasvirining murakkabligi va bu ma’lumotlar orasidagi aloqani MBni loyihalashda aniqlash kerak bo‘lib, bu esa MBga so‘rov berilganda rellyasion MB jadvallari orasida aloqa o‘rnatishni taminlab beradi.