Ақпаратты өңдеу форматтары
жүктеу/скачать 1,6 Mb.
|
Итн толық жауаптарыменн
- Бұл бет үшін навигация:
- Тура код Кодтау
- Тьюринг машинасы
- Тьюринг машинасының тоқтау ережесі.
| Тұжырымы – берілген бір немесе бірнеше пайымдарды жылған не ақиқаттылығын қорытып шығаратын формасы.Логика алгебра (Бульдік алгебра) – бұл ағылшын математигі Джордж Бульдің атымен аталатын ХІХ ғасырда пайда болған математика бөлімі. Басында буль алгебрасының ешқандай практикалық маңызы болған жоқ. Бірақ ХХ ғасырда ол әр түрлі электрондық сұлбаларды дайындауда және қызмет атқаруын сипаттауда үлкен маңызы болды. Логика алгебрасының заңдары мен аппараты компьютердің әр түрлі бөліктерін (жады, процессор) жобалауда пайдалана бастады. Буль алгебрасының бастапқы ұғымы – пікір. Пікір деп тек қана ақиқаттық тұрғыдан бағаланатын кез келген тұжырым түсіндіріледі. Пікірдің әділетті, мазмұнды, дөрекі, жақсы деген сияқты сапалық сипаттамалары қарастырылмайды. Буль алгебрасы тұрғысынан қарағанда пікірдің ақиқат немесе жалған болуы. Әрине бұл осы ғылымды қолданудағы жалғыз сала емес.Логика алгебрасы нені білдіреді? Біріншіден, алгебралық әдістердің көмегімен күрделі логикалық айтылымдардың ақиқаттылығын немесе жалған екенін орнататын әдістерді қарастырады. Екіншіден, бұл күрделі логикалық айтылым буль алгебрасында есептеу нәтижесі не ақиқат, не жалған (1, немесе 0) болуы мүмкін функциямен сипатталады. Бұл жерде функция аргументтері (қарапайм айтылымдар) де тек қана 0 немесе 1 мәндерін қабылдай алады.Сонымен Буль алгебрасы деп екі бинарлық операциядан (конъюнкция, дизъюнкция), унарлық операциядан (теріске шығару) және екі ерекшелінген (0 немесе Жалған және 1 немесе Ақиқат) элементтерінен тұратын бос емес жиынды айтамыз.Қарапайым логикалық айтылым дегеніміз не? Мысал негізінде түсіндірейік. Екі сөйлемді қарастырамыз: «Екі бірден артық», «3,14 – бүтін сан». Бірінші жаңдайда айтылым нәтижесі ақиқат, екінші жағдайда – жалған. Логикалық операциялар. Дизъюнкция, конъюнкция және терістеу.Күрделі айтылымдарға мысалдар: «осы аптада, немесе келесі аптады күн суытады», «мен сабақ оқып болғаннан кейін қыдырамын», «5 пен 7 өз ара тең емес» т.т. міне, осындай күнделікті өмірде кездесетін оқиғаларды математика аппаратына салып қатаң ережелер енгізіп бір мәнді нәтиже алатындай іске асырылатын болды. Жоғарыда келтірілген мысалдардағы «және», «немесе» одақтары логикалық амалдарға түрлендірілді.Логика алгебрасы логикалық операциялардың жиынын құрайды. Соның ішінде, әсіресе үш операцияға ерекше көңіл бөлінеді: конъюнкция (ЖӘНЕ), дизъюнкция (НЕМЕСЕ) және терістеу (ЕМЕС). Көбінесе конъюнкцияны немесе &, дизъюнкцияны - немесе ||, ал терістеуді - ¬ немесе айнымалының үстінен сызықшақою арқылы белгіленеді. Басқа операциялар осы үш операция арқылы өрнектеледі.
Тура код Кодтау (кодирование; coding; кодировать; encode) — мәліметтерді олардың алдын ала тағайындадған кодтық комбинацияларыменбейнелеу немесе мәліметтер элементін олардың кодтық комбинацияларымен сәйкес келтіру; программалаупроцесі; 2) ақпараттың 8 биттік (байттық) кодтауын 7 биттік кодтауға түрлендіру. Мұндай түрлендірудің қажеттілігі кейбір желілік программалардың мәліметтерді тек 7 биттік кодтауда жеткізе алатындығынан туындайды. Байттық мәліметгерді осындай арналармен тікелей жеткізу ақпараттың бұрмалануына жол береді; 3) белгілі бір ереже бойынша дискреттік хабарды дискреттік сигнал түріне түрлендіру (аудармалау), яғни шарттаңбаларды қолдану. Тура коды - компьютер арифметикасындағы тіркелген екілік жүйедегі сандарды ұсыну әдісі. Негізінде теріс емес сандарды жазу үшін қолданылады. Санның тура коды 8 биттік кодтауға түрлендіреді, және компьютерде оң және теріс сандарды сақтау үшін пайдаланылады. Екілік санның тура коды санның жазбасында - таңба разряды( оң болса 0 ,теріс болса 1) және мәндер разряды бөліп қарастырамыз. 1 сан 1 байт 8 битке тең. Сандарды кодтағанда оны 2 жүйеге келтіреміз. Оң сандардың таңба разряды 0 цифрымен белгіленсе, теріс сандардың таңба разрядына 1 цифрымен беогіленеді.Мәндік бөлігінің разрядында сол санның екілік коды жазылады. 47 санының тура коды 00101111
Пост машинасына ұқсас, бірақ сәл басқаша жұмыс істейді. Тьюринг машинасы (ТМ) есепші таспадан (ұяшықтарға бөлінген және солынан шектелген, бірақ оңынан емес), оқып және жазатын түбіртектен, таспатартар механизм мен амал атқарушы құрылғыдан тұрады. Құрылғы кейбір ақырлы жиынға (ішкі күй-жай әріппесіне) жататын дискретті күйлерінің бірінде болады. Мұндағы - бастапқы күй деп аталады.Оқитын да, жазатын түбіртек жұмысшы әріппесінің әріптерін оқи да, өшіре де, баспаға шығара да алады. Таспаның әрбір ұяшығы әр мезет А жиыны әрпімен толтырылған. -“бос орын” әрпі бәрінен жиі кездеседі. Түбіртек әр мезет таспа ұяшығының бірі-ағымдағы жұмысшы ұяшық үстінде тұрады. Таспатар механизм түбіртек басының көрші ұяшығының үстінде болатындай етіп таспаны жылжыта алады. Онда таспаның сол жақ шетіне шығу жағдайы болуы мүмкін. Ол жағдай, тоқтау туралы бұйрықты машинаның орындау барысындағы машиналық тоқтау немесе апатты (болмайтын)тоқтау болып табылады. ТМ жұмыс реті ( жұмысшы әріппесі мен күйлері бар). Тьюринг машинасы кестесі арқылы өрнектеледі. Бұл кесте төрт тікжолды және (s+1) (t+1) жолы бар матрица болып табылады. Әр жол мына түрде болады Мұнда арқылы әріппесі мен таспатартар механизм үшін бүйрықтар жиынын біріктіру элементі белгіленген. Бұйрықтар жиыны: l-таспаны солға орналастыру, r-таспаны оңға орналастыру, s-машинаны тоқтату; vіj –a0, a1,...., at әріппесі таңбасын таспа ұяшығына жазудан, не түбіртекті қозғаудан, не машинаны тоқтатудан тұратын ТМ әрекеті; qіj келесі күй-жай болып табылады. ТМ мына ережелер бойынша жұмыс істейді: Егер ТМ qі күйінде болса, түбіртек жұмысшы ұяшығынан aj таңбасын оқиды. qі aj таңбаларынан басталатын qі aj vіj qіj жолы кестеде бір-ақ рет кездеседі. Егер vіj- жұмысшы әріппесінің әрпі болса, онда түбіртек жұмысшы ұяшықтағыны өшіріп, оған осы әріпті апарып жазады. Егер vіj- таспатартар механизм үшін r немесе l командасы болса, онда таспа оңға немесе солға бір ұяшыққа жылжиды (егер таспаның сол жақ шетіне шығып кетпесе).Тюринг машинасы А әріппесінің бір таңбасы бар таспаның белгілі ұяшығы үстін оқып-жазатын түбіртектің орны мен бастапқы күйден (әдетте q0) тұратын бастапқы конфигурацияның бірінен жұмысын бастайды. ТМ жұмысшы әріппесінде әртүрлі таңбалардың болуы таспада кезкелген мәтіндік және сандық ақпаратты көрсетуге мүмкіндік береді, ал ТМ басқару орталығының әртүрлі күйге ауысуы Тюринг машинасының жұмыстың аралық нәтижелерін жадында ұстауын модельдейді. ТМ жұмысы ретін анықтайтын кесте тура мағынада программа емес (оның бұйрықтары кезекпен бірінен соң бірі орындалмайды, таспадағы әлдебір мәтіннің таңбаларын түрлендіруді өрнектейді). ТМ кестесін жиі Тюринг машинасының сүлбесі деп атайды немесе ТМ құрылысы мен жұмыс істеу негізі белгілі болғандықтан Тюринг машинасының өзімен теңдестіре салады. Машинаның жұмыс істеу ережелері Машина дискретті түрде жұмыс істейді (қадам қадам бойынша). Әр қадамда бір конфигурациядан басқасына өту орындалады. Жұмыс бастаудан алдын машина бастапқы конфигурацияда болады: оқып-жазушы құрылғы сөздің бірінші әріпіне шолу жасайды, ал машина q1 бастапқы жағдайында болады. Оқып-жазушы құрылғы шолу жасалған ұяшықтағы әріпті оқиды. Басқару құрылғысы машинаның программасынан оқылған әріп пен машинаның жағдайына сәйкес клетканы табады. Бұл клеткада (а, q, s) үштік болсын. Онда шолу жасалған ұяшыққа а әріпі жазылады, машина qжағдайға өткізіледі, егер s=-1 болса, онда оқып-жазушы құрылғы бір ұяшыққа сол жаққа жылжыйды, егер s=+1 болса, онда оқып-жазушы құрылғы бір ұяшыққа оң жаққа жылжыйды, егер s=0 болса – қозғалмайды. Осымен машинаның бірінші қадамдағы жұмысы аяқталады. Машинаның жұмыстары машинаның қадамы q0 ға жеткенше жалғаса береді. Бұл жағдайда басқару құрылғысы машинаны тоқтатады. Пайда болған конфигурация қорытынды, ал алынған сөз – машинаны берілген сөзге қолдану нәтижесі деп аталады.
(ТМ) есепші таспадан (ұяшықтарға бөлінген және солынан шектелген, бірақ оңынан емес), оқып және жазатын түбіртектен, таспатартар механизм мен амал атқарушы құрылғыдан тұрады. Құрылғы кейбір ақырлы жиынға (ішкі күй-жай әріппесіне) жататын дискретті күйлерінің бірінде болады. Мұндағы - бастапқы күй деп аталады. Оқитын да, жазатын түбіртек жұмысшы әріппесінің әріптерін оқи да, өшіре де, баспаға шығара да алады. Таспаның әрбір ұяшығы әр мезет А жиыны әрпімен толтырылған. -“бос орын” әрпі бәрінен жиі кездеседі. Түбіртек әр мезет таспа ұяшығының бірі-ағымдағы жұмысшы ұяшық үстінде тұрады. Таспатар механизм түбіртек басының көрші ұяшығының үстінде болатындай етіп таспаны жылжыта алады. Онда таспаның сол жақ шетіне шығу жағдайы болуы мүмкін. Ол жағдай, тоқтау туралы бұйрықты машинаның орындау барысындағы машиналық тоқтау немесе апатты (болмайтын)тоқтау болып табылады. ТМ жұмыс реті ( жұмысшы әріппесі мен күйлері бар). Тьюринг машинасы кестесі арқылы өрнектеледі. Бұл кесте төрт тікжолды және (s+1) (t+1) жолы бар матрица болып табылады. Мұнда арқылы әріппесі мен таспатартар механизм үшін бүйрықтар жиынын біріктіру элементі белгіленген. Бұйрықтар жиыны: l-таспаны солға орналастыру, r-таспаны оңға орналастыру, s-машинаны тоқтату; vіj –a0, a1,...., at әріппесі таңбасын таспа ұяшығына жазудан, не түбіртекті қозғаудан, не машинаны тоқтатудан тұратын ТМ әрекеті; qіj келесі күй-жай болып табылады. ТМ мына ережелер бойынша жұмыс істейді: Егер ТМ qі күйінде болса, түбіртек жұмысшы ұяшығынан aj таңбасын оқиды. qі aj таңбаларынан басталатын qі aj vіj qіj жолы кестеде бір-ақ рет кездеседі. Егер vіj- жұмысшы әріппесінің әрпі болса, онда түбіртек жұмысшы ұяшықтағыны өшіріп, оған осы әріпті апарып жазады. Егер vіj- таспатартар механизм үшін r немесе l командасы болса, онда таспа оңға немесе солға бір ұяшыққа жылжиды (егер таспаның сол жақ шетіне шығып кетпесе). Тюринг машинасы А әріппесінің бір таңбасы бар таспаның белгілі ұяшығы үстін оқып-жазатын түбіртектің орны мен бастапқы күйден (әдетте q0) тұратын бастапқы конфигурацияның бірінен жұмысын бастайды. ТМ жұмысшы әріппесінде әртүрлі таңбалардың болуы таспада кезкелген мәтіндік және сандық ақпаратты көрсетуге мүмкіндік береді, ал ТМ басқару орталығының әртүрлі күйге ауысуы Тюринг машинасының жұмыстың аралық нәтижелерін жадында ұстауын модельдейді. ТМ жұмысы ретін анықтайтын кесте тура мағынада программа емес (оның бұйрықтары кезекпен бірінен соң бірі орындалмайды, таспадағы әлдебір мәтіннің таңбаларын түрлендіруді өрнектейді). ТМ кестесін жиі Тюринг машинасының сүлбесі деп атайды немесе ТМ құрылысы мен жұмыс істеу негізі белгілі болғандықтан Тюринг машинасының өзімен теңдестіре салады. Тьюринг машинасының тоқтау ережесі. Тьюринг машинасында оңға жылжу,солға жылжу,стоп командалары орындалады. Программада машина нәтижелі және шексіз тоқтайды. жүктеу/скачать 1,6 Mb. Достарыңызбен бөлісу:
|