အဆုံးအဖြတ်မရှိသော စက်တစ်ခုတွင် ကျွန်ုပ်တို့တွင် လမ်းကြောင်းနှစ်ခု သို့မဟုတ် ထို့ထက်ပို၍ လက်ခံနိုင်သောလမ်းကြောင်းများ ရှိသောအခါ၊ မည်သည့်အရာကို ကျွန်ုပ်တို့ရွေးချယ်ပြီး မည်သည့်စံနှုန်းများကို အသုံးပြုနိုင်မည်နည်း။

/ / Published in ပြည်တွင်းသတင်း ဆိုက်ဘာလုံခြုံရေး, EITC/IS/CCTF တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ အခြေခံအချက်များ, ကနျ့ပြည်နယ်စက်များ, Nondeterministic ကနျ့ပြည်နယ်စက်မှနိဒါန်း

ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ၏နယ်ပယ်တွင်၊ အထူးသဖြင့် ကန့်သတ်ပြည်နယ်စက်များကို လေ့လာရာတွင်၊ အဆုံးအဖြတ်မဟုတ်သော သဘောတရားသည် အရေးကြီးသောအခန်းကဏ္ဍမှ ပါဝင်ပါသည်။

သတ်မှတ်ထားသောအခြေအနေတွင်မဆို လက်ခံနိုင်သောလမ်းကြောင်းများစွာကို ယူဆောင်နိုင်စေသည့် သီအိုရီပိုင်းဆိုင်ရာပုံစံများ (Non-deterministic finite state machines) များဖြစ်သည်။ သို့သော် ထိုသို့သော အခြေအနေမျိုးနှင့် ကြုံတွေ့ရသောအခါတွင် မည်သည့်လမ်းကို ရွေးချယ်သင့်သနည်း။

ဤမေးခွန်းသည် NFSMs တွင် "လက်ခံသည်" ဟူသော အယူအဆနှင့် ဆုံးဖြတ်ချက်တစ်ခုချရန် အလုပ်ခန့်နိုင်သည့် စံနှုန်းများအပေါ် သက်ရောက်သည်။

ရွေးချယ်မှုလုပ်ငန်းစဉ်ကို နားလည်ရန်၊ NFSMs တွင် အဆုံးအဖြတ်မရှိသော သဘောသဘာဝကို ဦးစွာစူးစမ်းကြည့်ကြပါစို့။ အဆုံးအဖြတ်ပေးသော ကန့်သတ်ပြည်နယ်စက်များ (DFSMs) နှင့် မတူဘဲ၊ NFSM များသည် ပြည်နယ်တစ်ခုစီရှိ ဖြစ်နိုင်သည့် ထည့်သွင်းသင်္ကေတတိုင်းအတွက် သီးသန့်အကူးအပြောင်းကို မပိုင်ဆိုင်ပါ။ ယင်းအစား၊ ၎င်းတို့သည် တူညီသောထည့်သွင်းမှုသင်္ကေတအတွက် အသွင်ကူးပြောင်းမှုများစွာကို ခွင့်ပြုထားသည်။ ဤဝိသေသလက္ခဏာသည် အခြေအနေတစ်ခုတည်းမှ လိုက်ရန် လမ်းကြောင်းများစွာရှိနိုင်ခြေကို ဖြစ်ပေါ်စေပြီး မတူညီသောရလဒ်များကို ဖြစ်ပေါ်စေနိုင်သည်။

ထိုသို့သောအခြေအနေနှင့်ရင်ဆိုင်ရသောအခါ၊ NFSM များသည် ဖြစ်နိုင်ခြေလမ်းကြောင်းအားလုံးကို တစ်ပြိုင်နက်ရှာဖွေရန် "အကိုင်းအခက်" ဟုခေါ်သော ယန္တရားတစ်ခုကို အသုံးပြုသည်။ ဆိုလိုသည်မှာ စက်သည် မတူညီသောလမ်းကြောင်းတစ်ခုစီကို လိုက်လျှောက်ခြင်းဖြင့် သူ့ဘာသာသူ ကော်ပီများစွာကို ဖန်တီးပေးသည်။ ရလဒ်အနေဖြင့် NFSM သည် အကိုင်းအခက်တစ်ခုစီသည် မတူညီသောတွက်ချက်မှုလမ်းကြောင်းကိုကိုယ်စားပြုသည့် သစ်ပင်ပုံစံဖွဲ့စည်းပုံကို စူးစမ်းလေ့လာခြင်းအဖြစ် ရှုမြင်နိုင်သည်။ ဤအကိုင်းအခက်နည်းပညာသည် NFSMs များကို ခွဲခြမ်းစိတ်ဖြာခြင်းနှင့် ၎င်းတို့၏ တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုတွင် အခြေခံဖြစ်သည်။

ယခု၊ လက်ခံနိုင်ဖွယ်ရာများစွာရှိသည့်အနက်မှ တိကျသောလမ်းကြောင်းတစ်ခုကို ရွေးချယ်ရန် အလုပ်ခန့်ထားနိုင်သည့် စံနှုန်းများကို သုံးသပ်ကြည့်ကြစို့။ ဘုံချဉ်းကပ်နည်းတစ်ခုမှာ NFSMs တွင် "လက်ခံခြင်း" သဘောတရားကို ထည့်သွင်းစဉ်းစားရန်ဖြစ်သည်။ လက်ခံခြင်းဆိုသည်မှာ စက်မှ ပေးထားသော ထည့်သွင်းမှုအား မှန်ကန်မှု ရှိ၊ မရှိ ဆုံးဖြတ်သည့် အခြေအနေအား ရည်ညွှန်းသည်။ NFSMs တွင် လက်ခံမှုကို အဓိကနည်းလမ်းနှစ်မျိုးဖြင့် သတ်မှတ်နိုင်သည်- "နောက်ဆုံးအခြေအနေဖြင့် လက်ခံခြင်း" နှင့် "အလွတ်အစုအဝေးမှ လက်ခံမှု"။

Input string တစ်ခုလုံးကို စားသုံးသောအခါ၊ NFSM သည် နောက်ဆုံးအခြေအနေတစ်ခုအဖြစ် သတ်မှတ်ထားသော အခြေအနေတွင် ပြီးဆုံးသောအခါတွင် နောက်ဆုံးအခြေအနေမှ လက်ခံမှု ဖြစ်ပေါ်သည်။ ဤစံသတ်မှတ်ချက်သည် နောက်ဆုံးအခြေအနေတစ်ခုသို့ ဦးတည်သည့် အနည်းဆုံးတွက်ချက်မှုလမ်းကြောင်းတစ်ခုရှိလျှင် စက်ထည့်သွင်းမှုကို လက်ခံသည်ဟု ဆိုလိုသည်။ အပြန်အလှန်အားဖြင့်၊ မည်သည့်လမ်းကြောင်းမှ နောက်ဆုံးအခြေအနေသို့ ဦးတည်သွားပါက ထည့်သွင်းမှုကို ပယ်ချမည်ဖြစ်သည်။

အခြားတစ်ဖက်တွင်၊ NFSMs များသည် stack တစ်ခုအား အပိုအစိတ်အပိုင်းတစ်ခုအဖြစ် ထည့်သွင်းသောအခါတွင် အချည်းနှီးသော stack မှလက်ခံခြင်းသည် သက်ဆိုင်ပါသည်။ ဤအခြေအနေတွင်၊ ထည့်သွင်းမှုစာကြောင်းကို အပြည့်အဝလုပ်ဆောင်ပြီး အစုအပုံသည် လွတ်သွားသည့်အခါ လက်ခံမှုဖြစ်ပေါ်ပါသည်။ နောက်ဆုံးအခြေအနေက လက်ခံခြင်းကဲ့သို့ပင်၊ အလွတ်အစုအဝေးတွင် ရလဒ်ထွက်သည့် အနည်းဆုံးတွက်ချက်မှုလမ်းကြောင်းတစ်ခုရှိလျှင် ထည့်သွင်းမှုကို လက်ခံပါသည်။ မဟုတ်ရင် ငြင်းပယ်တယ်။

ဤစံနှုန်းများကို ပေးထားသောကြောင့်၊ လက်ခံနိုင်ဖွယ်မရှိသော စက်တစ်ခုရှိ တိကျသောလမ်းကြောင်းကို ရွေးချယ်ခြင်းအား လက်ခံမှုအခြေအနေများကို ဦးစားပေးခြင်းဖြင့် ဆုံးဖြတ်နိုင်သည်။ ဥပမာအားဖြင့်၊ နောက်ဆုံးအခြေအနေမှ လက်ခံမှုသည် မူလစံသတ်မှတ်ချက်ဖြစ်လျှင် စက်သည် အခြားဖြစ်နိုင်ချေရှိသော လမ်းကြောင်းများကို မခွဲခြားဘဲ နောက်ဆုံးအခြေအနေသို့ ဦးတည်မည့်လမ်းကြောင်းကို ရွေးချယ်မည်ဖြစ်သည်။ အပြန်အလှန်အားဖြင့်၊ အချည်းနှီးသော stack မှလက်ခံမှုသည် အဓိကစံသတ်မှတ်ချက်ဖြစ်ပါက၊ စက်သည် အချည်းနှီးသော stack ဖြစ်ပေါ်လာသည့်လမ်းကြောင်းကို ဦးစားပေးမည်ဖြစ်သည်။

NFSMs တွင်ရှိသောလမ်းကြောင်းရွေးချယ်မှုသည်စက်၏တွက်ချက်မှုစွမ်းအားကိုမထိခိုက်စေကြောင်းသတိပြုရန်အရေးကြီးပါသည်။ ရွေးချယ်ထားသောလမ်းကြောင်း မည်သို့ပင်ရှိစေ၊ NFSM သည် ပေးထားသည့်ထည့်သွင်းမှုအတွက် အခြားသော NFSM ကဲ့သို့တူညီသောဘာသာစကားများကို အသိအမှတ်ပြုနိုင်သေးသည်။ ရွေးချယ်ရေးလုပ်ငန်းစဉ်သည် သတ်မှတ်ထားသော စံနှုန်းများအပေါ် အခြေခံ၍ ထည့်သွင်းမှုအား လက်ခံခြင်း သို့မဟုတ် ငြင်းပယ်ခြင်းကို ဆုံးဖြတ်ပေးပါသည်။

အဆုံးအဖြတ်မဟုတ်သော စက်တစ်ခုတွင် လက်ခံနိုင်သောလမ်းကြောင်းများစွာနှင့် ရင်ဆိုင်ရသည့်အခါ၊ နောက်ဆုံးအခြေအနေမှ လက်ခံမှု သို့မဟုတ် အလွတ်အစုဖြင့် လက်ခံခြင်းကဲ့သို့သော လက်ခံမှုအခြေအနေများကို ဦးစားပေးခြင်းဖြင့် လမ်းကြောင်းရွေးချယ်မှုကို ဆုံးဖြတ်နိုင်သည်။ ရွေးချယ်မှု လုပ်ငန်းစဉ်သည် စက်၏ တွက်ချက်မှုဆိုင်ရာ စွမ်းအားကို သက်ရောက်မှုမရှိသော်လည်း ထည့်သွင်းမှုကို လက်ခံခြင်း သို့မဟုတ် ငြင်းပယ်ခြင်း ရှိမရှိအပေါ် သက်ရောက်မှုရှိသည်။

အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ EITC/IS/CCTF တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ အခြေခံအချက်များ:

EITC/IS/CCTF Computational Complexity Theory Fundamentals တွင် နောက်ထပ်မေးခွန်းများနှင့် အဖြေများကို ကြည့်ပါ

နောက်ထပ်မေးခွန်းများနှင့် အဖြေများ-

အောက်တွင် tag လုပ်ခဲ့သည် , , , , , ,