Лабораторный Практикум по Дискрмат2

530		621		432		442		233		321		620
434		219		673		651		544		762		324
556		776		443		622		632		511		279
377		446		840		332		582		631		561
332		112		532		762		544		226		331
633		422		173		533		721		652		467
438		232		645		761		354		631		262
530	521		402		542		133		621		420
734	219		673		651		544		762		224
456	776		443		622		632		511		299
877	446		840		300		542		631		461
432	112		532		762		544		226		331
633	422		773		533		721		652		507
238	232		645		761		354		631		162

				Вариант 11.									Вариант 12.
530		301		432		402		533			621		120
534		219		673		551		344			762		324
356		776		443		622		632			511		209
177		446		840		332		542			631		761
432		112		532		762		544			226		331
633		422		773		533		721		652			560
438		232		345		761		354			231		362
200	321		132		442		533		221			520
634	219		673		651		340		562			224
456	776		443		622		632		511			200
877	446		840		122		542		631			761
432	112		532		762		544		226			331
333	422		773		533		721		652			467
538	232		645		761		354		631			262
				Вариант 13.									Вариант 14.

131

130		321		432		242		133		621		354
534		219		673		651		344		762		204
456		776		443		622		632		511		299
877		446		840		332		542		631		761
532		112		532		762		544		226		331
532		412		832		162		544		226		931
238		232		645		761		354		831		162
130	321		432		242		133		621		354
534	219		673		651		344		762		204
456	776		443		622		632		511		299
877	446		840		332		542		631		761
132	100		532		162		530		226		301
532	412		832		162		544		226		931
238	232		645		761		354		831		162

				Вариант 15.								Вариант 16.
230		321		432		442		533		621		320
334		219		673		651		344		762		224
456		776		443		622		632		511		299
877		446		840		332		542		631		761
432		112		532		762		544		226		331
633		422		773		533		721		652		567
238		232		645		761		354		631		562
630	321		432		542		500		121		720
234	219		673		651		344		762		424
456	776		443		622		632		511		299
877	446		840		332		542		631		761
432	112		532		762		544		226		331
633	422		773		533		721		652		567
438	732		645		761		304		631		560
				Вариант 17.								Вариант 18.

132

	330	321	432	542	500	121	420
	234	219	673	451	344	762	424
	456	776	443	622	632	511	299
	107	406	140	132	342	601	261
	632	112	532	762	544	226	331
	633	422	773	533	721	652	117
	438	732	645	761	304	631	760
310	321	832	542	540	121	220
434	219	373	451	344	262	924
456	776	443	622	632	511	299
107	406	140	132	342	601	261
632	112	532	762	544	226	331
613	422	773	533	721	652	117
738	732	645	761	304	931	360

				Вариант 19.								Вариант 20.
319		321		132		542		540		121		520
434		219		373		451		344		262		924
756		776		443		602		632		500		209
107		406		140		132		342		601		261
632		112		532		762		544		200		331
113		422		773		533		721		652		117
238		732		545		361		304		931		660
300	321		102		242		530		121		820
434	219		373		451		344		262		924
156	770		403		112		132		560		289
107	406		140		132		342		601		261
672	112		532		762		544		200		331
103	722		773		533		721		652		117
238	702		545		361		304		431		160
				Вариант 21.								Вариант 22.

133

388		321		102		242		530			101		420
434		219		373		451		344			262		924
156		770		403		112		132			560		289
107		406		140		132		342			601		261
600		112		532		762		544		200			331
103		722		773		533		721		652			117
238		702		545		361		304		131			760
230	321		432		442		533		621			320
334	219		673		651		344		762			224
456	776		443		622		632		511			299
877	446		840		332		542		631			761
432	112		532		762		544		226			331
633	422		773		533		721		652			567
238	232		645		761		354		631			562

				Вариант 23.										Вариант 24.
200		305		532			442		533			621		110
334		219		673			651		344			762		224
456		776		443			622		632			511		299
877		446		840			332		542			631		761
432		112		532			762		544			226		331
603		122		711		503			441		652			217
208		932		645			761		354			231		462
300	665		532		442			453		621			190
304	219		673		651			344		762			250
456	776		443		622			632		511			209
337	446		840		332			542		631			161
400	112		532		762			504		226			181
603	122		711		503			441		652			217
258	932		145		761			354		631			162

Вариант 25.

134

370	611	532	402	453	621	190
304	219	673	651	344	762	250
556	716	443	102	632	511	269
330	446	840	332	542	631	161
400	112	532	700	504	226	180
303	122	211	503	441	652	207
203	932	145	761	754	631	102

Практическое занятие 7

ПОНЯТИЕ АЛГОРИТМА. УТОЧНЕНИЯ ПОНЯТИЯ АЛГОРИТМА. ПРИМЕНЕНИЕ МАШИН ТЬЮРИНГА И АНАЛИЗ МАШИН

Цель работы

Проверить применимость заданной машины Тьюринга к данному слову и, в случае применимости, преобразовать данное слово. При помощи заданной машины Тьюринга преобразовать данное слово и выявить закономерность работы машины.

Краткая теория

Понятие алгоритма является настолько универсальным, что может включить в себя многие последовательные действия, которые выполняются за конечное число шагов и в строго определенном порядке. Такое понимание алгоритма называется интуитивным пониманием алгоритма. Однако для решения математических и прикладных задач такое понимание не является достаточным. Одной из форм уточнения понятия алгоритма является понятие машины Тьюринга.

Машина Тьюринга представляет собой мыслимое устройство, состоящее из конечного числа символов A ={a0, a1,…, an} - внешнего алфавита машины, множества Q = {q0, q1,…, qm} состояний читающего устройства воображаемой машины и программы работы машины. Кроме двух алфавитов и программы, машина Тьюринга имеет бесконечную, воображаемую ленту, разделенную на ячейки. Работа машины Тьюринга состоит в записи и чтении на воображаемую ленту последовательности символов внешнего алфавита. В результате работы машины Тьюринга, исходное слово, записанное на ленте, преобразуется в некоторое новое слово или пустое слово. Среди символов внешнего и внутреннего алфавитов есть специальные символы: a0 - символ пустой ячейки, q0, q1, - символы окончания работы машины и начала работы соответственно.

135

Символы внешнего алфавита записываются в ячейки и читаются при помощи команд трех видов

1) qi aj	qk al R
2) qi aj	qk al L
3) qi aj	qk al S,

где R, L, S – символы сдвига читающего устройства вправо, влево и записи без сдвига соответственно. Первая команда читается следующим образом: если в состоянии qi в просматриваемой ячейке ленты машина читает символ aj, то, согласно этой команде, состояние машины меняется на qk, в просматриваемую ячейку записывается символ al и читающее устройство перемещается по ленте вправо на одну ячейку. Аналогично работают две другие команды. Программа работы машины представляет собой последовательность команд вида 1) – 3).

Пример 1. Построим машину Тьюринга, уменьшающую данное слово из n единиц, на единицу. В качестве внешнего алфавита возьмем множество {0,1}. Алфавит внутренних состояний Q = {q0, q1, q2, q3}. Пусть

в начальном состоянии q1		машина читает третий слева символ 1 данного
слова. Далее,	находит	самую	правую единицу, стирает ее и
останавливается. Запишем эти действия в виде команд:
		q1 1	q2 1R
		q2 1	q2 1R.

Эти две команды выполняют циклический сдвиг читающего устройства вправо с сохранением содержимого ячеек ленты. Следующие две команды программы проверяют достижение правой границы слова, запись символа 0 вместо последнего символа 1 и останавливают работу машины Тьюринга:

q2 0	q3 0L
q3 1	q0 1S.

Работу машины Тьюринга можно представить в виде последовательного преобразования слова, записанного на ленте. Каждый символ данного слова записывается в отдельную ячейку ленты в следующем виде:

q1

	1	1	1	…	1	1	1
								q2
	1	1	1	…	1	1	1

136

q2

	1	1	1	…	1	1	1	0
q3
	1	1	1	…	1	1	1	0
q0
	1	1	1	…	1	1	0	0

Последовательность этих преобразований исходного слова можно представить в более упрощенной форме, без изображения ленты:

11q11… 111 111… 11q210 111… 111q20 111… 11q310 111… 11q00.

Программу работы машины Тьюринга удобнее представить в виде таблицы. Например, программу уменьшения n на одну единицу можно представить в виде следующей таблицы:

Таблица 10

Машина Тьюринга, уменьшающая n на одну единицу.

	q1	q2	q3
0	-	q30L	-
1	q21R	q21R	q01S

Таким образом, для построения машины Тьюринга сначала необходимо мысленно представить все действия, необходимые для достижения цели. Затем, подобрать команды для реализации этих действий на воображаемой ленте.

Машины с несколькими конечными состояниями. Машина Тьюринга устроена просто для того, чтобы можно было реализовать любые действия, даже самые элементарные. Однако при этом каждое действие требует своей специальной, программной реализации. В качестве примера рассмотрим реализацию условного оператора.

Пример 2. В исходном состоянии читается правая крайняя единица слова, составленного из единиц. Число единиц равно х+1. Необходимо построить машину, проверяющую условие х=0.

Решение. Если слева от правой крайней единицы 0, то состояние конца работы q01, в противном случае q02. Программа завершения работы машины будет следующей:

q1 1	q2 1L
q2 0	q01 1R
q2 1	q02 1R.
137

Машину, проверяющую условие х=0 можно использовать как условный оператор, то есть символы окончания работы q01 и q02 можно продолжить двумя независимыми машинами и, таким образом, присоединить две новые машины Тьюринга.

Порядок выполнения работы

1.Проверить применимость заданной машины Тьюринга к данному слову и, в случае применимости, преобразовать данное слово.

2.При помощи заданной машины Тьюринга преобразовать данное слово и выявить закономерность работы машины.

Образец выполнения заданий

а) Машина Тьюринга с внешним алфавитом {0, 1} и алфавитом внутренних состояний {q0, q1, q2, q3, q4, q5, q6, q7} задана в виде следующей программы:

Таблица 11.

Машина Тьюринга с алфавитом внутренних состояний {q0, q1, q2, q3, q4, q5, q6, q7}

	q1	q2	q3	q4	q5	q6	q7
0	q40R	q60R	q60R	q01S	q40R	q00S	q60R
1	q21L	q31L	q11L	q50S	q50S	q70S	q70S

Выяснить применимость машины к слову 11111. В случае применимости преобразовать слово 11111 при помощи данной машины. В начальном состоянии машина читает правую крайнюю единицу данного слова.

б) Машина Тьюринга с внешним алфавитом {0, 1, *} и алфавитом внутренних состояний {q0, q1, q2, q3} задана в виде следующей программы:

Таблица 12.

Машина Тьюринга с алфавитом внутренних состояний {q0, q1, q2, q3}.

	Q1	q2	q3
0	-	q31R	q10L
1	q20L	q21L	q31R
*	q00S	q2*L	q3*R

Преобразовать слово 111*1111 при помощи данной машины при условии, что в начальном состоянии машина читает правую крайнюю единицу данного слова.

138

Решение. а) Согласно условию задания, в начальном состоянии машина читает правую крайнюю единицу данного слова 11111. Поэтому исходное слово на ленте будет иметь вид 1111q11. Если в состоянии q1 машина читает символ 1, то из таблицы команд машины Тьюринга на пересечении соответствующих этим символам столбца и строки находим элемент команды q21L. Согласно этому элементу команды необходимо: в просматриваемой машиной ячейке ленты сохранить символ 1, сменить состояние читающего устройства на q2 и переместить читающее устройство влево на одну ячейку. Так как в левой ячейке данного слова символ 1, то условием новой команды машины будет следующее условие: в состоянии q2 машина читает на ленте символ 1. Следовательно, опять при помощи данной таблицы можем определить последующее действие машины. Продолжая последовательно выполнять эти действия и записывая результаты этих действий в форме последовательности слов, получим:

1111q11 111q211 11q3111 1q11111 q211111 q3011111

0q611111	0q701111	00q61111 00q70111	000q6111
000q7011	0000q611	0q701 00q61 00q70	0q60 0q00.

Машина Тьюринга завершает работу тогда, когда в результате действий приходит в состояние q0. Следовательно, в данном случае машина завершила свою работу и последнее слово и есть искомый результат. Проанализируем то, что получилось в результате. Один из символов внешнего алфавита всегда резервируется для обозначения пустой ячейки ленты. В данном случае таким символом является 0. Следовательно, исходное слово из пяти единиц машина Тьюринга преобразовала в пустое слово. В результате, лента оказалась пустой. Символы пустой ячейки всегда можно добавить в преобразуемое слово, если это необходимо, и могут быть также удалены - в противном случае. Эти действия применялись в процессе преобразований данного в этом задании слова. Если в процессе работы машины возникает ситуация, при которой невозможно выполнение дальнейших преобразований или же процесс требует неограниченного числа повторений, то считается, что машина не применима к данному слову.

б) Согласно условию задания, в начальном состоянии машина читает правую крайнюю единицу данного слова 111*1111. Поэтому исходное слово на ленте будет иметь вид 111*111q11. Если в состоянии q1 машина читает символ 1, то из таблицы команд машины Тьюринга на пересечении соответствующих этим символам столбца и строки находим элемент команды q20L. Аналогично предыдущему заданию построим последовательность слов в порядке выполнения команд программы. В отличие от предыдущего задания, в данном случае внешний алфавит

139

машины содержит новый символ (*). Внешний алфавит может содержать любые символы, если они имеют какой-либо смысл или значение. Значение, которое придается символу (*) в этой машине, предлагается самостоятельно выяснить из анализа работы машины. Выполняя аналогичные действия при помощи команд машины, получим:

111*111q11 111*11q210 111*1q211 111*q2111 111q2*111

11q21*111 1q211*111 q2111*111 q20111*111 1q3111*111

11q311*111	111q31*111	1111q3*111 1111*q3111
1111*1q311	1111*11q31	1111*111q30 1111*11q110
1111*1q2100 …	q201111*11	1q31111*11 …		11111*11q30
11111*1q110	11111*q2100	…	q2011111*1	1q311111*1 …
111111*1q30	111111*q110	111111q2*0 …		q20111111*0
1q3111111*0	… 1111111*q30		1111111q1*0	1111111q00.

В результате работы машины Тьюринга исходное слово 111*1111 преобразовалось в слово 1111111. Многоточие использованы для обозначения циклических операций, к которым приводят команды.

Вопросы для самопроверки

1.Что собой представляет машина Тьюринга?

2.Какую роль в машине Тьюринга играют внешний и внутренний алфавит?

3.Перечислите виды команд машины и поясните их действие?

4.Что собой представляет программа машины Тьюринга?

Литература: [3], гл. 5, с. 82 – 106; [2], Часть 8, с. 136 – 162; [7], гл. 10, стр. 144 –201. [6], гл. 2, стр. 179 –185. [12], §8, стр. 119 –134.

Задания для самостоятельной работы

а) Машина Тьюринга с внешним алфавитом {0, 1} и алфавитом внутренних состояний {q0, q1, q2, q3, q4, q5, q6, q7} задана в виде следующей программы:

140