«Информатиканың теориялық негіздері»
жүктеу/скачать 0.6 Mb.
|
- Бұл бет үшін навигация:
- Зертханалық жұмыс №4 (3 сағат) Тақырып: Алгоритмдер теориясының негізгі ұғымдары
- Қысқаша мәлімет
| НЕМЕСЕ функциясы - бұл функция екі немесе одан да көп аргумент функциясы. НЕМЕСЕ функциясы 1-ге тең, егер оның ең болмағанда бір аргументі 1-ге тең болса (басқа атаулары: дизъюнкция). Белгіленуі: Ү=аЬ. Табиғи тілдерде дизъюнкция функциясы «немесе» шылауымен айтылып, мына түрдегі сөйлемдерде қолданылады: Біз келесі жағалауға өте аламыз, егер өзен таяз НЕМЕСЕ көпір бүтін болса.
Логикалық формула (логикалық өрнек) – логикалық шамалар мен логикалық амалдар таңбасынан тұратын формула. Логикалық формуланың есептелуінің нәтижесі тек қана АҚИҚАТ немесе ЖАЛҒАН болады. НЕМЕСЕ элементін жүзеге асыратын элемент – дизъюнктордың шартты белгісі төмендегідей. Тапсырмалар: 1. Аргумент мәндерінің барлық комбинациялары үшін ЕМЕС функциясының ақиқаттық кестесін құр. 2. ЖӘНЕ және НЕМЕСЕ функциялары үшін аргументтердің барлық комбинациялары үшін ақиқаттық кесте құр. 3. ЕМЕС функциясын жүзеге асыратын логикалық элемент – инвертордың жұмысы мен функционалдық схемадағы шартты белгісін сипатта. 4. ЖӘНЕ функциясын жүзеге асыратын логикалық элемент – конъюктордың жұмысы мен функционалдық схемадағы шартты белгісін сипатта. 5. НЕМЕСЕ функциясын жүзеге асыратын логикалық элемент – дизъюнктордың жұмысы мен функционалдық схемадағы шартты белгісін сипатта. Зертханалық жұмыс №4 (3 сағат) Тақырып: Алгоритмдер теориясының негізгі ұғымдары Тьюринг және Пост машиналарының көмегімен алгоритмдерді есептеу. Марковтың қалыпты алгоритмдері. Қысқаша мәлімет (Алгоритм ұғымын формальдандыру) Тьюринг машинасы туралы түсінік алгоритмге берілген ең ыңғайлы да қолайлы анықтама болды. Бұл түсінік ағылшын математигінің атымен аталды, 1937 жылы, яғни, ЭЕМ пайда болғаннан жыл бұрын берген болатын. Тьюринг машинасының анықтамасы: Тьюринг машинасы математикалық машина, сонымен қатар Тьюринг машинасын мынандай математикалық объектілермен салыстыруға болады: топ, интеграл, функция, туынды т.с.с. Тьюринг машинасының автоматты түрде жұмыс істейтін құрал ретінде елестетуге болады. Тьюринг машинасы елес машина, ол қандай да бір көзге көрініп жұмыс атқарып тұрған құрылғы емес. Біз ол машинаны бар деп санаймыз. Белгілі бір жағдайда бір ұяшықты қарасытрады, ол ұяшықтар лента бойында орналсқан. Лентадағы ұяшықтар жағдай ауысқанда өзгеруі немесе сол қалпында қалуы мүмкін. Жағдай ауысып отырады. Тьюринг машинасы программамен жұмыс істейді. Екі алфавит бар: ішкі және сыртқы алфавиттер. Мысалы, ішкі алфавит Машинаға берілген элементтер міндетті түрде ақырлы болуы керек. Жұмыс істеуге ыңғайлы болу үшін лента бойында бос ұяшық бар деп есептейміз. Сыртқы алфавит . Ішкі алфавит лента ішінде жазылған, сыртқы алфавит лента үстінде жазылған. q0 – бастапқы жағдай q1- соңғы жағдай. Программа былай берілуі мүмкін: Тьюринг машинасының командасының жалпы түрі: Егер Х=С болса, онда aj тұрған ұяшықты қарастырамыз және соны өшіреміз. Содан кейн al элементін жазамыз. Жағдай qi -дан qk –ға өзгереді. Одан кейін ешқандай қадам жасамай орнымызда қаламыз. Яғни, al элементі тұрған және qk жағдайы бар ұяшық өз-өзін қарастырады. Егер Х=П болса, онда бір қадам оңға (направо) ауысады. Егер Х=Л болса, онда бір қадам солға (налево) ауысады. Мысал: q1
q1
q2
q0
Қортыа келе, бастпқы сөз 101 болса, программа бойынша Тьюринг машинасымен жұмыс істегенде 10101 сөзін алдық. жүктеу/скачать 0.6 Mb. Достарыңызбен бөлісу:
|