Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұрақ деңгей
жүктеу/скачать 134.63 Kb.
|
- Бұл бет үшін навигация:
- Ақиқаттық таблицасы
- Импликацияны терістеу
| Дизъюнкция (Disjunction) - 1) тек екі аргументтің мәні бір мезгілде «жалған» болған кезде ғана мәні жалған болатын екі айнымалының функциясы. Логикалық «қосу операциясына барабар; 2) «немесе»
[1] Белгіленулері: {\displaystyle ~a} || {\displaystyle ~b,~a} | {\displaystyle ~b,a\lor b,a+b,~a~{\mbox{OR}}~b}{\displaystyle ,~max(a,b)}.
Импликация (Implication) - егер бірінші операнд «жалған», ал екіншісі «ақикат» мәнге ие болса, онда нәтиже «жалған» мәнге ие болатын екі орынды буль операциясы. [1] Импликацияны терістеу (Отрицание импликации; Implication) — тек А ақиқат, ал В жалған болғанда ғана ақиқат мәнді қабылдайтын А және В екі айнымалының логикалық функциясы. Пост машинасы ұғымын түсіндіріңіз? Посттың абстрактілі машинасы бірдей секцияларға бөлінген шексіз лентадан, және оқитын-жазатын головкадан тұрады. Әр секция немесе бос (яғни оған ештеңе жазылмаған), немесе толтырылған (белгіленген – яғни, оған белгі жазылған) болады. Лентаның қалпы деген ұғым енгізіледі, бұл ұғым қай секциялардың бос, қай секциялардың белгіленгендігі туралы ақпарат береді (басқаша айтқанда: лентаның қалпы – бұл белгілердің секциялар бойынша таралуы, яғни бұл секцияның әрбір сандық нөміріне не белгі, не «бос» белгісін сәйкес қоятын функция). Әрине, машина жұмысы процесінде лента қалпы өзгереді. Лентаның қалпын және головканың орналасуын Пост машинасының қалпы сипаттайды. Пост машинасыда орындалатын командалар атаңыз. Шолынулы секцияның үстіндегі головканы «» таңбасымен, ал белгіні секцияның ішіндегі «М» таңбасымен белгілеуге шарттасайық. Бос секцияда ешқандай белгі болмайды. Бір тактіде (оны қадам деп те болады) головка бір секцияға оңға немесе солға жылжып, белгіні қоя немесе өшіре алады. Пост машинасының жұмысы берілген жеке командалардан құрылған программа бойынша машинаның бір қалпынан екіншісіне өтуінен тұрады. Әрбір команда келесі құрылымға ие: xKy, мұндағы х – орындалатын команданың нөмірі; K – орындалатын әрекет туралы нұсқау; у – келесі команданың (ізбасардың) нөмірі. Пост машинасының пайда болу тарихы және қолдану аймағана мысал келтіріңіз. Абстракциялық Пост пен Тьюринг машиналары программа қасиеттері туралы әр түрлі пайымдауларды дәлелдеу үшін керек. Оларды 1936 жалы американ математигі Эмил Пост пен ағылшын математигі Аллан Тьюринг ұсынған. Бұл машиналар бастапқы мәліметтерді «енгізуге», және программа орындалғаннан кейін нәтижені «оқуға» мүмкіндік беретін, толық детерминирленген болып табылатын әмбебап орындаушыларды білдіреді. Пост машинасы Тьюринг машинасынан қарағанда қарапайымдылау. Ол арқылы ЭЕМ үшін программа құрудың бірінші дағдыларын үйретуге болады.Пост абстракциялық машинасы бірдей ұяшықтарға бөлінген үздіксіз таспа мен бүркеншіктен тұрады. Таспаның әрбіреуі бос немесе «V» таңбасымен толтырылуы мүмкін. Бүркеншік бір ұяшыққа сол жаққа немесе бір ұяшыққа оң жаққа таспа бойымен жылжи алады, егер бұл таңба алдын ала болмаса, онда таспа ұяшығына таңбаны енгізе алады, егер болса, оны өшіре алады немесе ұяшықта таңбаның бар болуын тексере алады. Таспаның ұяшықтары таңбамен толтырылған туралы ақпарат машина жұмысының процесі кезінде өзгере алатын таспаның күйін сипаттайды.Әрбір уақыт аралығында бүркеншік («–») таспаның бір ұяшығының үстінде орналасады. Таспа күйімен қоса бүркеншіктін орналасу орны туралы ақпарат Пост машинасының жағдайын сипаттайды, Постың абстракциялық машинасы Пост машина командасының құрлымы келесідегідей: n K m, мұнда n – команданың реттік нөмірі, K – бүркеншікпен орындалатын әрекет, m – орындауға жататын келесі команданың нөмірі.Пост машинасының алты командасы бар.
Тьюринг машиналары мысалында автоматтар теориясындағы алгоритм ұғымын формализациялауды келтіріңіз . жүктеу/скачать 134.63 Kb. Достарыңызбен бөлісу:
| |||||||||||||||||||||