Mavzu: Nodeterminiztik modellar

Mavzu: Nodeterminiztik modellar.
Model turlari:
Deterministik va stokastik (yoki tasodifiy) modellar, shuningdek, uzluksiz va diskret formulalar o'rtasida muhim farqlarni amalga oshirish kerak.
Deterministik va stoxastik:
Deterministik modellar katta populyatsiyalarga tasodifiy og'ishlarsiz ma'lum o'rtacha stavkalar qo'llanilishini taxmin qiladi. Misol uchun, agar 10 000 kishining har birida 1 yil omon qolish ehtimoli 95% bo'lsa, ularning 9500 nafari haqiqatan ham omon qolishiga ishonch hosil qilishimiz mumkin. Stokastik modellarda, aksincha, parametr bo'yicha noaniqliklar yoki kichik populyatsiya kattaligi tufayli tasodifiy o'zgarishlar mavjud bo'lib, ular uchun o'rtacha stavkalarni qo'llash oqilona bo'lmasligi mumkin. Misol uchun, har birining yana bir yil omon qolish ehtimoli 0,7 ga teng bo'lgan 20 asrlik aholini ko'rib chiqaylik. Omon qolganlarning o'rtacha soni 20 × 0,7 = 14 bo'ladi. Biroq, aholi sonining kichikligi sababli, tasodifiy o'zgarishlar bo'ladi va yil oxirida aholining ehtimollik tavsifi afzalroq bo'ladi. Bunday holda, populyatsiyani tasvirlash uchun binomial modeldan foydalanamiz. Binomial model nol omon qolgan, bitta omon qolgan, ikkita omon qolgan va hokazo, yil oxirida 20 tagacha omon qolish ehtimolini ta'minlaydi. Boshqacha qilib aytganda, ehtimollik taqsimoti o'rtacha raqam emas, balki omon qolganlar soni uchun berilgan.
Uzluksiz va diskret:
Uzluksiz modelda voqealar vaqtning har bir nuqtasida sodir bo'lishi mumkin. Masalan, tug'ilish va o'lim o'rtasidagi vaqt har qanday musbat o'nlik son bo'lishi mumkin. Diskret modelda hodisalar vaqt oralig'ida toifalarga bo'linadi. Masalan, biz 0 yoshdan 1 yoshgacha, 1 yoshdan 5 yoshgacha, 5 yoshdan 10 yoshgacha, 10 yoshdan 15 yoshgacha va hokazo oʻlimlar sonini sanashimiz mumkin. (Odat bo'lgan bu misol, intervallarning uzunligi bir xil bo'lishi shart emasligini ham ko'rsatadi.) Deterministik va stokastik modellar ham uzluksiz yoki diskret bo'lishi mumkin.
Dastlab hayot jadvali va uning ilovalari taqdim etiladi. Klassik chiziqli va chiziqli bo'lmagan deterministik modellar. Kirish stoxastik modellar bilan yopiladi, ularning aksariyati 1970-yillardan beri ishlab chiqilgan.
Ushbu maqola kompyuter dasturlashda nodeterminizm haqida. Hisoblash murakkabligi nazariyasida nodeterminizm uchun, Hisoblashning nodeterministik modeliga qarang.Kompyuter dasturlashda deterministik bo'lmagan algoritm - bu bir xil kirish uchun ham, deterministik algoritmdan farqli o'laroq, turli ishga tushirishlarda turli xatti-harakatlarni ko'rsatishi mumkin bo'lgan algoritm. Algoritm o'zini ishga tushirishdan ishga tushirishgacha boshqacha tutishi mumkin bo'lgan bir necha usullar mavjud. Poyga holati tufayli bir vaqtda algoritm turli yugurishlarda turlicha ishlashi mumkin. Ehtimoliy algoritmning xatti-harakatlari tasodifiy sonlar generatoriga bog'liq. Muammoni deterministik bo'lmagan polinom vaqtida echadigan algoritm bajarish paytida qilgan tanloviga qarab polinom yoki eksponensial vaqtda ishlashi mumkin. Deterministik bo'lmagan algoritmlar ko'pincha yechimga yaqinlashishni topish uchun ishlatiladi, agar aniq echim deterministik yordamida olish juda qimmat bo'lsa.Bu tushuncha 1967-yilda Robert V. Floyd tomonidan kiritilgan.
Ko'pincha hisoblash nazariyasida "algoritm" atamasi deterministik algoritmga ishora qiladi. Nodeterministik algoritm o'zining ko'proq tanish deterministik hamkasbidan turli yo'llar yordamida natijalarga erishish qobiliyati bilan farq qiladi. Agar deterministik algoritm kirishdan natijagacha bo'lgan yagona yo'lni ifodalasa, deterministik bo'lmagan algoritm ko'p yo'llardan iborat bo'lgan yagona yo'lni ifodalaydi, ularning ba'zilari bir xil chiqishga, ba'zilari esa noyob natijalarga kelishi mumkin. Bu xususiyat deterministik bo'lmagan chekli avtomat kabi hisoblashning "nodeterministik" modellarida matematik tarzda olinadi. Ba'zi stsenariylarda barcha mumkin bo'lgan yo'llarning bir vaqtning o'zida ishlashiga ruxsat beriladi.

Algoritmni loyihalashda deterministik bo'lmagan algoritmlar ko'pincha algoritm tomonidan echilgan muammo tabiatan bir nechta natijalarga imkon berganda qo'llaniladi (yoki natijani aniqlashning bir nechta yo'llari bo'lgan bitta natija mavjud bo'lsa, har biri bir xil darajada afzalroqdir). Eng muhimi, deterministik bo'lmagan algoritm ishlab chiqaradigan har bir natija, algoritm ishlayotganda qaysi tanlovlarni amalga oshirishidan qat'i nazar, haqiqiydir.

Hisoblash murakkabligi nazariyasida deterministik bo'lmagan algoritmlar har bir mumkin bo'lgan bosqichda bir nechta davomiylikka imkon beradigan algoritmlardir (tasavvur qiling, odam o'rmonda yo'l bo'ylab ketayotgan va har safar oldinga qadam qo'yganida, u yo'lning qaysi vilkasini tanlashi kerak). olmoq). Bu algoritmlar barcha mumkin bo'lgan hisoblash yo'llari uchun yechimga etib bormaydi; ammo, ular qandaydir yo'l uchun to'g'ri yechimga kelishlari kafolatlanadi (ya'ni, o'rmon bo'ylab yurgan odam "to'g'ri" yo'llarning kombinatsiyasini tanlagan taqdirdagina o'z kabinasini topishi mumkin). Tanlovlar qidiruv jarayonida taxminlar sifatida talqin qilinishi mumkin.

Ko'p sonli muammolarni deterministik bo'lmagan algoritmlar orqali kontseptsiyalash mumkin, jumladan, hisoblash nazariyasidagi eng mashhur hal qilinmagan savol, P va NP. Deterministik algoritmda, ma'lum bir kirish uchun kompyuter har doim bir xil holatlardan o'tgan bir xil chiqishni ishlab chiqaradi, ammo deterministik bo'lmagan algoritm bo'lsa, bir xil kirish uchun kompilyator turli ishga tushirishlarda turli xil chiqishlarni ishlab chiqishi mumkin. Aslida deterministik bo'lmagan algoritmlar muammoni polinom vaqtida hal qila olmaydi va keyingi qadam nima ekanligini aniqlay olmaydi. Deterministik bo'lmagan algoritmlar turli xil bajarishda bir xil kirish uchun turli xatti-harakatlarni ko'rsatishi mumkin va buning tasodifiy darajasi mavjud.

1-rasm. Nodeterminiztik algoritm va determiniztik algaritm.
Deterministik tizimlari modellari, ular yetarlicha oddiy bo'lsa analitik o'rganildi mumkin xususiyatga ega. qarama-qarshi holda, bu maqsadda tenglamalar va o'zgaruvchilar, bir qator foydalanish paytida elektron kompyuterlar operatsiya qilinishi mumkin. Bundan tashqari, bir kompyuterni foydalanib, qoida tariqasida, ularni hal etish va javoblarni topish ko'proq haqida. Shu sababli, siz tenglamalar tizimini o'zgartirish va turli masal foydalanish kerak. hisob-kitoblarda xato xavfi ortishiga, bu vlochet. ma'lum oralig'ida parametrlari ilm o'rganib, deb aslida bilan xarakterlanadi deterministic modellari Barcha turdagi to'liq xorijda mashhur arboblaridan rivojlanish dinamikasini aniqlash uchun, bizga yordam beradi.
XUSUSIYATLARI
Deterministik matematik modellar ko'p omillar ta'sirida bir vaqtda aniqlanadi ruxsat bermaydi, va fikringiz tizimida ularning değiştirilebilmesi hisobini tutmang. ularning funktsional qurilgan qanday? Bu ob'ekt jismoniy va kimyoviy jarayonlar tasvirlab matematik qonunlar asosida. Shuning uchun juda aniq tizim xatti oldindan qurilishi uchun ham issiqlik va moddiy manfaatlar muvozanati umumiy tenglamalar, belgilangan macrokinetics jarayonini ishlatiladi. deterministic modeli aniqroq prognozlash uchun ob'ekt o'tmishda haqida boshlang'ich ma'lumotlarni maksimal mumkin raqami bo'lishi lozim. Bu parametrlar qiymatlariga har qanday haqiqiy o'zgarishiga qarab, ularning o'lchash natijalarini mensimaydigan nima uchun ruxsat texnik muammolar, nisbatan qo'llanilishi mumkin. Shuningdek foydalanish uchun alomatlardan biri tasodifiy xatolar tizimi yakuniy hisob-kitob kuni oz ta'sir ega bo'lishi mumkin, deb hisoblanadi.
Fizikada:
Differensial tenglamalar bilan tavsiflangan fizik qonunlar deterministik tizimlarni ifodalaydi, garchi tizimning ma'lum bir nuqtadagi holatini aniq tasvirlash qiyin bo'lishi mumkin.

Kvant mexanikasida tizim toʻlqin funksiyasining uzluksiz vaqt evolyutsiyasini tavsiflovchi Shredinger tenglamasi deterministikdir. Biroq, tizimning to'lqin funktsiyasi va tizimning kuzatiladigan xususiyatlari o'rtasidagi bog'liqlik deterministik bo'lmagan ko'rinadi.

Matematikada:
Xaos nazariyasida o'rganiladigan tizimlar deterministikdir. Agar dastlabki holat aniq ma'lum bo'lsa, unda bunday tizimning kelajakdagi holatini nazariy jihatdan taxmin qilish mumkin edi. Biroq, amalda, kelajakdagi holat haqidagi bilimlar dastlabki holatni o'lchash mumkin bo'lgan aniqlik bilan chegaralanadi va xaotik tizimlar dastlabki shartlarga kuchli bog'liqlik bilan tavsiflanadi. Dastlabki sharoitlarga nisbatan sezgirlikni Lyapunov ko'rsatkichlari bilan o'lchash mumkin.

Markov zanjirlari va boshqa tasodifiy yurishlar deterministik tizimlar emas, chunki ularning rivojlanishi tasodifiy tanlovlarga bog'liq.

Kompyuter fanida:
Hisoblashning deterministik modeli, masalan, deterministik Tyuring mashinasi, mashinaning ketma-ket holatlari va bajarilishi kerak bo'lgan operatsiyalar oldingi holat tomonidan to'liq aniqlanadigan hisoblash modelidir.
Deterministik algoritm - ma'lum bir kirish berilganda, har doim bir xil natijani beradigan algoritm bo'lib, asosiy mashina har doim bir xil holatlar ketma-ketligidan o'tadi. Deterministik mashinada ishlaydigan deterministik bo'lmagan algoritmlar bo'lishi mumkin, masalan, tasodifiy tanlovlarga tayanadigan algoritm. Odatda, bunday tasodifiy tanlovlar uchun psevdor tasodifiy raqamlar generatoridan foydalaniladi, lekin kompyuter soati tomonidan berilgan vaqtning oxirgi raqamlari kabi ba'zi tashqi jismoniy jarayonlardan ham foydalanish mumkin.
Soxta tasodifiy sonlar generatori deterministik algoritm bo'lib, u tasodifiy ketma-ketliklar kabi harakat qiladigan raqamlar ketma-ketligini ishlab chiqarish uchun mo'ljallangan. Uskuna tasodifiy sonlar generatori deterministik bo'lmasligi mumkin.
Abstrakt
Ilm-fanning ko'plab sohalarida, shu jumladan populyatsiya dinamikasida, eng oddiy tizimlardan tashqari hamma yashaydigan keng davlat bo'shliqlari deterministik tahlilni istisno qilishi mumkin. Bu erda epidemiologiya sohasiga taxminiy deterministik modellar sinfi kiritilgan bo'lib, bu davlat makonini son jihatdan mumkin bo'lganiga qisqartiradi. Biroq, bu qisqartirilgan holat fazosining asosiy tenglamalari umuman yopiq to'plamni tashkil qilmaydi. Buni hal qilish uchun tenglamalar yopilish yaqinlashuvlari yordamida yaqinlashadi. Ushbu jarayon vaqtga bog'liq parametrlardan foydalangan holda dinamik yo'naltirilgan aloqa tarmoqlari va geterogen tizimlarni o'z ichiga olgan potentsial keng ko'lamli deterministik differentsial tenglama modellarini qurish usulini keltirib chiqaradi. Usul SIR (sezuvchan-infeksion-olib tashlangan) epidemiologik modeli misolida keltirilgan va fazoviy mahalliydan tasodifiygacha bo'lgan bir qator tarmoqlarda raqamli baholanadi. Kontakt tarmoqlarida tarqalgan epidemiyalar kontekstida ushbu ish stokastik simulyatsiya va an'anaviy populyatsiya darajasining deterministik modellari o'rtasidagi bog'liqlikni aniqlashga yordam beradi.
Matematik modellashtirishda deterministik simulyatsiyalar tasodifiy o'zgaruvchilarni va tasodifiylik darajasini o'z ichiga olmaydi va asosan tenglamalardan, masalan, farq tenglamalaridan iborat. Ushbu simulyatsiyalar ma'lum kirishlarga ega va ular noyob natijalar to'plamiga olib keladi. Tasodifiy o'zgaruvchilarni o'z ichiga olgan kontrastli stokastik (ehtimollik) simulyatsiyasi.
Deterministik simulyatsiya modellari odatda ba'zi bir asosiy mexanizm yoki tabiiy jarayonni qo'lga kiritish uchun mo'ljallangan. Ular statistik modellardan farq qiladi (masalan, chiziqli regressiya), ularning maqsadi o'zgaruvchilar o'rtasidagi munosabatlarni empirik baholashdir. Deterministik model voqelikning foydali yaqinlashuvi sifatida qaraladi, uni stokastik modelga qaraganda qurish va izohlash osonroqdir. Biroq, bunday modellar juda ko'p sonli kirish va chiqishlar bilan juda murakkab bo'lishi mumkin va shuning uchun ko'pincha o'zgartirilmaydi; sobit yagona chiqishlar to'plami bir nechta kirishlar to'plami tomonidan yaratilishi mumkin. Shunday qilib, parametr va model noaniqligini ishonchli hisobga olish, ehtimol, standart statistik modellarga qaraganda, juda muhim, ammo bu statistik mutaxassislar tomonidan kam e'tiborga olingan sohadir.