Білім беру бағдарламасы: 6 B01506 Информатика Құрастырушылар : Амантурлина Г. К. аға оқытушы

жүктеу 430,16 Kb. бет 36/47 Дата 13.12.2022 өлшемі 430,16 Kb. #40599 түрі Білім беру бағдарламасы

Өткізу формасы: Конспект жазу, компьютерде жеке жұмыс Әдебиеттер: [5] Бағалау критерийлері: 8 апта №15-16 практикалық жұмыс Тақырыбы: Алгоритмдер теориясының негізгі ұғымдары. Әдістемелік нұсқаулықтар: Тьюринг машинасы туралы түсінік алгоритмге берілген ең ыңғайлы да қолайлы анықтама болды. Бұл түсінік ағылшын математигінің атымен аталды, 1937 жылы, яғни, ЭЕМ пайда болғаннан жыл бұрын берген болатын. Тьюринг машинасының анықтамасы: Тьюринг машинасы математикалық машина, сонымен қатар Тьюринг машинасын мынандай математикалық объектілермен салыстыруға болады: топ, интеграл, функция, туынды т.с.с. Тьюринг машинасының автоматты түрде жұмыс істейтін құрал ретінде елестетуге болады. Тьюринг машинасы елес машина, ол қандай да бір көзге көрініп жұмыс атқарып тұрған құрылғы емес. Біз ол машинаны бар деп санаймыз. Белгілі бір жағдайда бір ұяшықты қарасытрады, ол ұяшықтар лента бойында орналсқан. Лентадағы ұяшықтар жағдай ауысқанда өзгеруі немесе сол қалпында қалуы мүмкін. Жағдай ауысып отырады. Тьюринг машинасы программамен жұмыс істейді. Екі алфавит бар: ішкі және сыртқы алфавиттер. Мысалы, ішкі алфавит Машинаға берілген элементтер міндетті түрде ақырлы болуы керек. Жұмыс істеуге ыңғайлы болу үшін лента бойында бос ұяшық бар деп есептейміз. Сыртқы алфавит . Ішкі алфавит лента ішінде жазылған, сыртқы алфавит лента үстінде жазылған. q0 – бастапқы жағдай q1- соңғы жағдай. Программа былай берілуі мүмкін: Тьюринг машинасының командасының жалпы түрі: Егер Х=С болса, онда aj тұрған ұяшықты қарастырамыз және соны өшіреміз. Содан кейн al элементін жазамыз. Жағдай qi -дан qk –ға өзгереді. Одан кейін ешқандай қадам жасамай орнымызда қаламыз. Яғни, al элементі тұрған және qk жағдайы бар ұяшық өз-өзін қарастырады. Егер Х=П болса, онда бір қадам оңға (направо) ауысады. Егер Х=Л болса, онда бір қадам солға (налево) ауысады. Мысал: q1 1 0 1 q1 1 0 1 0 q2 1 0 1 0 0 q0 1 0 1 0 1 Қортыа келе, бастпқы сөз 101 болса, программа бойынша Тьюринг машинасымен жұмыс істегенде 10101 сөзін алдық. жүктеу 430,16 Kb. Достарыңызбен бөлісу:

©g.engime.org 2024
әкімшілігінің қараңыз