«amaliy matematika va informatika» kafedrasi «O’yinlar nazariya va jarayonlar tadqiqoti» fanidan Mustaqil ishi

BILIMLARNI TAQDIM ETISH MODELLARI
Biror intellektual tizimda bilim olishni tashkil etish uchun, ularni EHM da aks ettirish lozim bo‘ladi. Buning uchun u qandaydir ko‘rinishga ega tizimlashtirilgan axborot shakliga keltiriladi. EHM da aks ettirilgan axborot prosedurali va deklarativ bo‘ladi. Prosedurali axborot dastur ko‘rinishida bo‘lib, masalani echish jarayonida amalga oshiriladi. Deklarativ axborot dastur qayta ishlovchi ma‘lumotlarda aks ettiriladi. Bilimlarni aks ettirishning mantiqiy, tarmoqli, produksionli, freymli modellari ishlatiladi. Bilimlarni hosil qilish ikki funksiya orqali amalga oshiriladi: axborotni tashqi muhitdan olish; olingan axborotni tizimlashtirish. Freym — bu qandaydir standart holat uchun mo'ljallangan ma'lumotlarni deklarativ keltirilishidir. Freymlarni tarmoq ko'rinishida ko'rsatish mumkin. Unda yuqori tabaqalar ularning ma'nosini namoyish etadi va har qanday sharoitda chin qiymatga ega bo'ladi. Pastki tabaqa muayyan informatsiyaga ega bo'lgan slotlar bilan to'ldiriladi. Freymlar nazariyasini, bilimlarni freymlar bilan tasvirlash G’OYASINI va «freym» termi-nini 1975 yilda M. Minski degan olim taklif kilgan. «Freym» so’zi ingliz tilidan olingan bulib, ramka, deraza, reshyotka, ichki skelet kabi mazmunlarda ishlatiladi. Freymlar nazariyasining moxiyati quyidagicha. Inson yangi xolatga tushib qolgan paytda, u o’zining xotirasidagi freymlar deb nomlanuvchi asosiy strukturani tuzilishiga murojat qiladi. Ya’ni bunday xolatda turli yechimni qabul qilish uchun nimalar qilish kerakligini eslaydi. Freym — bu oldin eslab qolingan bilimlarni tasvirlash birligi. Bu birlikning detallari davr va talab taqozosi bilan o’zgarishi mumkin. Freym — ma’lumotlar tuzilishhini ifodalaydi, uning yordamida, masalan, sizning xonangizdagi xolatni tasvirlash mumkin. Xar bir freym xar xil axborotlar bilan to’ldirilishi mumkin. Agar oqibat kutilgan natijani bermasa, bu axborot — kurilayotgan freymning qo’llanish usullariga aloqador bo’lishi mumkin. Freym ko’p jixatdan o’zining tuzilishiga kura semantik tarmoqqa o’xshash boladi. Freym — ierarxik tuzilgan, tugun va munosabat (aloka) lar tarmoridir. Bu erda yukori tugunlar umumiy tushun-chalarni ifodalasa, pastki tugunlar esa bu tushuncha-larning xususiy xollaridir. Semantik tarmoklardan farkli ularok, freym sistemalarda x,ar bir tugundagi tarmoklar tushunchasi atributlar tuplami (masalan, ism, rang, ulcham, shakl) va bu atributlarning kiymatlari (masalan, Rustam, kuk, kichkina, dumalok) bilan beriladi. Atributlarni esa slotlar (tirkishlar) deyiladi. Slotlar freym ichida axborotning anik, joyini kursata-di. Masalani echish uchun axborot etarlimi yoki kaysi-lari etishmaydi, agar etarli bulmasa ularni freymning kaeridan olishi kerak? Bu kabi vazifalarni slotlar bajaradi. Atributlar uzgaruvchan xarakterga ega bulgan xolatda slotlar shpats (oralik)larni .uz ichiga oladi. Bu shpatslarga slotlarning xozirgi ahamiyati (kiyma-ti)ni tasvirlovchi ayrim ob’ektlar joylashadi. Muno¬sabat (aloka)lardan tashkil toptan freymlar tuplamini yirib freymlar sistemasini kurish mumkin. Bilimlarni freymlar yordamida tasvirlanishining matematik tuzilishini kuyidagi kurinishida yozish mumkin: {i ..., { Bu erda i freymlarning nomlari, vj — slotlarning nomlari, gj — slotlarning kiymati. Slotlarning kiymati sifatida boshka freymlarning nomlari ham bulishi mumkin, ular freymlar orasidagi munosabat (aloka)larni ta’minlaydi. Agar boshka freymlarga mu-rojaat kilinayotganda, slotlar nomlari xisobga olin-masa, u xolda bir jinsdagi freymlar tarmogi xosil buladi. Aks xolda, boglanishlar kaysi slotlardan xosil bulgan bulsa shu slotlarning nomlari bilan ataladi va freymlar bir jinsli bulmaydi. Muvofiklashtirish protseduralaridan bosh-laymiz. Buning uchun xotiradan odam xarakteristika-larini tasvirlovchi «odam» freymini chakiramiz. Hamma slotlarning shartlarini kanoatlantiradigan ma’lumot-lar olinganda, ob’ekt odam sifatida aynan teng-lashtiriladi (identifikatsiyalanadi). Agar EXMga kira-digan ma’lumotlar «odam» freymida berilgan shart-larga moe kelmasa, masalan ob’ekt (sub’ekt) ning 15 massa-si 300 kg va ob’ektning dumi bor deyilsa, bu ma’lu-motlardan xulosa shuki, kurilayotgan ob’ekt odam emas. SHundan sung uxshashlik freymining kursatkichidan foydalanib va xotiradan «maymun» freymini chakirib, shunga uxshash muvofiklashtirish utkaziladi. Bunday usul, xatto axborotlar tulik berilmagan xolda ham xolatning mazmunini tushunishga imkon beradi.
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. Eng afzal yo’lni topish masalasi qaralyapti. Distance massivining har bir elementiga shunday qiymat beriladiki, ixtiyoriy potensial yo’ldan katta bo’lsin (odatda, bu qiymatni cheksiz katta qiymat deb qaraladi, ammo dasturda berilgan toifaning qiymatlar diapazonidagi eng katta qiymat sifatida olinadi). Boshlang'ich nuqta sifatida s tugun tanlanadi va unga nol yo'l belgilanadi: distance [s] = 0, chunki s-dan s-gacha hech qanday qirra yo'q (bu usulda ilmoqlar qaralmaydi). Shundan keyin, barcha qo'shni tugunlar topiladi (s dan chiquvchi qirralar orqali) [ularni t va u deb belgilaylik] va ular birma-bir tekshirib ko'riladi, ya'ni s tugundan har bir tugungacha birma-bir marshrut bahosi hisoblanadi:

- distance[t]=distance[s]+ s va t orasidagi qirraning vazni;

- Distance[u]=distance[s]+ s va u orasidagi qirraning vazni.
Ehtimoldan xoli emaski, u yoki bu tugunga s dan bir qancha yo’llar bo’lishi mumkin. Shu sababli, distance massivida bu tugunga bo’lgan yo’lning vaznini qayta ko’rib chiqish kerak bo’ladi. Shunda kattaroq (nooptimal) qiymat yo’qotiladi va tugunga mos yo’lning vazniga kichikroq qiymat beriladi. s tugun bilan qo’shni bo’lgan va qarab chiqilgan tugunlar tashrif buyurilgan sifatida belgilab chiqiladi, yani visited[s]=true va natijada, s dan chiquvchi, minimal vaznga ega bo’lgan yo’l eltuvchi tugun faol element sifatida belgilab olinadi. Faraz qilamiz, s dan u gacha masofa t ga qaraganda qisqa bo’lsin. Kelib chiqadiki, u tugun faollashadi va yuqoridagi kabi uning qo’shnilari ( s dan tashqari) o’rganilib chiqiladi. u tugun tashrif buyurilgan deb belgilanadi: visited[u]=true, endi t tugun faollashadi va yuqoridagi prosedura uning uchun takrorlanadi. Deykstra algoritmi s tugundan borish mumkin bo’lgan barcha tugunlar tadqiq qilinmaguncha davom ettiriladi.

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. Bu algoritm manfiy vaznga ega bo’lgan graflar bilan ishlashda ham qo’llanilishi mumkin (istisno holatlar ham mavjud). s tugundan qolgan barcha tugunlargacha bo’lgan qisqa masofani Bellman-Ford algoritmidan foydalanib topish dinamik dasturlashtirish usulini qo’llash demakdir, ya’ni uni qism masalalarga ajratib, ularni yechimi orqali umumiy asosiy masalani hal qilishdir. Bunda qism masala bo’lib, bitta alohida qaralayotgan tugundan boshqasigacha eng qisqa yo’lni aniqlash masalasi hisoblanadi. Algoritm natijalarini saqlash uchun d[] bir o’lchovli massiv qabul qilamiz. Uning har bir i-elementida s gundan i-elementgacha qisqa masofa qiymatini saqlanadi (agar mavjud bo’lsa). Dastlab, d[] massiv elementlariga shartli sheksiz katta qiymat berib chiqiladi, d[s] ga 0 o’zlashtiriladi. G={V, E}, n=|V|, m=|E| graf berilgan bo’lsin. Qo’shni tugunlarni v va u deb, (v,u) orasidagi qirrani w deb belgilab olamiz. Boshqacha aytganda, v tugundan chiquvchi va u tugunga kiruvchi qirra vazni w ga teng. U holda, Bellman-Ford algoritmining muhim qismi quyidagicha ko’rinishga ega bo’ladi:I=1 dan n-1 gacha bajaramiz