ДМ Практикум

Говорят, что машина Тьюринга Т применима к слову Р, если начав рабо- ту на Р (начальная конфигурация) она остановится через конечное число шагов получив слово Q (конечная конфигурация). При этом пишут T (P) = Q . Если Т не остановится, то она не применима к слову Р.

Программу МТ удобно задавать системой (1) или таблицей (2) (рис. 6.2).

	…		…	am	…
	qi am q j an S	q	…	q a S	…
		i		j n
	(1)
			(2)

Рисунок 6.2

Пусть F (x1, x2 ,..., xn ) - функция, определенная на множестве всех слов в алфавите А. Машина Тьюринга правильно вычисляет функцию F , если для лю- бых слов u1,...,un в алфавите А, начав работу в конфигурации q1a0u1a0u2a0...a0un , машина закончит ее в конфигурации q0a0 F (u1,u2 ,...,un ) . В состоянии q0 головка должна оставаться над той же ячейкой, над которой она была в начальной кон- фигурации.

Далее будем рассматривать машины Тьюринга с внешним алфавитом A = {0,1} , пустой символ a0 будем считать равным 0.

Пример 6.1. Пусть число n записывается на ленте машины Тьюрин-

га как 01...10 . Написать программу машины Тьюринга, правильно вычисляю-

n

щей функцию F (n) = n + 1.

	q1 0 q2 0R;
	q 1 q 1R;
	2	2
		0 q31L;
	q2
	q 1 q 1L;
	3	3
	q 0 q 0E.
	3	0

51

А) Контрольные вопросы

6.1Дайте ответ на вопрос: что такое алгоритм? Какие характерные свойства присущи любому алгоритму?

6.2Дайте определение машины Тьюринга. Опишите устройство МТ и шаг работы МТ.

6.3Сформулируйте тезис Тьюринга.

Б) Задачи и упражнения

6.4Задана программа машины Тьюринга Т и начальная конфигурация Р. Найдите Т(Р), если

	q 0 q 0R;
		1	1
	q11 q2 0R;
а) P = q1 001001;	Т = q 0 q 1E;
		2	0
б) P = q1 011101;	q 1 q 1R.
		2	2

в) P = q1 000000 .

6.5Задана программа машины Тьюринга Т и начальная конфигурация Р.

Найдите Т(Р).

а) P = q1 01110 ; б) P = q1 0100 ; в) P = q1 000000 ; г) P = 0111q1 0 .

Т	0	1
q1	q1 0R	q2 0R
q2	q31L	q21R
q3	q0 0R	q31L

6.6Напишите программу машины Тьюринга Т( 0q11...10 )= 01...1q 0 (правый

0

n n

сдвиг).

6.7Напишите программу машины Тьюринга Т( 01...1q 0 )= 0q 1...10 (левый

1 0

n

n

сдвиг).

6.8Пусть число n записывается на ленте машины Тьюринга как 01...10 .

n

Напишите программу машины Т, если:

52

а) Т( 0q 1...10 )= 0q 1...10 ;
1		0
	n	n+2
б) Т( 0q 1...101..10 )= 0q 1...10 ;
1		0
	n m		n+m
в) Т( 0q 1...10 )= 0q 1...10 ;
1		0
	n	2n
г) Т( 0q 1...10 )= 0q 1...101...10 ;
1		0
	n	n	n

д) Т( 0q 1...101...10 )= 0q 1...101...10 ;
1			1
	n	m		m	n

е) Т( 0q11...10 )= 0101...01q0 0 .

n 2n

6.9Напишите программу машины Тьюринга, обладающей следующими свойствами:

а) T имеет две команды, не применима ни к какому слову и зона её рабо- ты бесконечна;

б) T имеет две команды, не применима ни к какому слову и зона её рабо- ты конечна.

6.10Пусть число n записывается на ленте машины Тьюринга как 01...10 .

n

Напишите программу машины Тьюринга, правильно вычисляющей функцию:

а) F (n) = 0 ; б) F (n) = n −1;	в)	F (n) =	0, если n ≤ 2
			n + 2, если n > 2 .

В) Тестовые задания (укажите единственный верный ответ)

q10 q21R;

q 1 q 0R;

6.11 Дана программа машины Тьюринга T = 1 1

q2 0 q11R;q21 q01E.

и начальная конфигурация P = q1 0000101. Заключительная конфигурация T (P) имеет вид…

а) 111101q01;

б) 111111q01;

в) 111101q0 0 ;

г) 111100q01.

53

	q 0 q			1L;
		1	2
	q 1 q 1R;
6.12 Дана программа машины Тьюринга	T =	1	1
	q2 0 q01E;
				0L.
	q21 q2

и начальная конфигурация P = 10q1111101. Заключительная конфигурация T (P) имеет вид…

а) 1q01000011 ;

б) q011000011;

в) 1100001q01 ;

г) машина T не применима к слову P .

6.13Конечную зону работы имеет машина Тьюринга…

а) T1 = q10 q11R; ;q11 q10R.

б) T2 = q10 q10R; ;q11 q10R.

в) T3 = q10 q11E; ;q11 q10E.

г) T4 = q10 q11L; .q11 q11L.

6.14К слову P = 01110 не применима машина Тьюринга…

		q 0 q 0R;					q 0 q 0R;
			1	1				1	1
а)	T = q11 q21R;				б)	T = q11 q2 0R;
	1		q 1 q 1R; ;			2		q 1 q 0R; ;
			2	2				2	2
		q 0 q 0E.					q 0 q 1E.
			2	0				2	0

		q 0 q 1R;					q10 q1 0R;
			1	1			q11 q21L;
		q 1 q 1L;
в)	T =		1	2	г)	T =		q 0 q 1L; .
	3		q 0 q 1L; ;			4
			2	2				2	2
		q 1 q 0E.					q 1 q 0E.
			2	0				2	0

54

Глава VII. Графы

Графом G называется пара (V,E), где V ={v1,v2 ,...vn} - множество вершин, а

E ={(u,v) | u V ,v V} - множество ребер графа. Если пары (u,v) упорядочен- ные (т.е., в общем случае, (u,v) ¹ (v,u)), то граф называется ориентированным или орграфом. В таком графе ребра принято называть дугами. Вершины u и v называются смежными, если (u,v) E . При этом говорят, что вершина u (или v) инцидентна ребру (u,v). Если граф ориентированный, то вершину u называют

началом (исходом), а v – концом (заходом) ребра (u,v). Степенью вершины v

называется число deg(v) инцидентных ей ребер. В орграфе различают также полустепени исхода ( deg+ (v) ) и захода ( deg− (v) ), которые равны числу исхо- дящих и заходящих ребер, соответственно. Подграфом графа G(V , E) называ- ется граф G* (V * , E* ) такой, что V * V и E* E .

∙Матрица смежности неориентированного графа (н-графа) G(V , E) - квадратная матрица A(G) порядка n (n =|V |) , у которой элемент aij равен числу ребер, соединяющих вершины vi и v j (ребра вида (u,u), называе-

мые петлями, считаем дважды).

∙
	Матрица смежности	ориентированного графа G(V , E) - квадратная
	матрица A(G) порядка n (n =|V |) , у которой элемент aij					равен числу дуг,
	исходящих из vi и заходящих в v j .
∙	Матрица инцидентности н-графа G(V , E)				- матрица B(G) размера n × m
	(n =|V |, m =| E |) , у которой bij = 1, если vi и ej инцидентны и bij = 0, если
	vi и ej не инцидентны.
∙
	Матрица инцидентности орграфа G(V , E)				- матрица A(G) размера n × m
	(n =|V |, m =| E |) , у которой bij = 1,		если vi		- начало дуги ej , bij = -1, если
	vi - конец дуги ej и bij	= 0, если vi	и ej	не инцидентны.

Если граф содержит петли, то значение соответствующего элемента матри- цы инцидентности bij выбирается в зависимости от дальнейшего применения

этой матрицы (например, bij = ±1).

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

55

, vik

Маршрутом в н-графе называется последовательность vi1 ,ei1,vi2 ,ei2 ,....eik−1 ,

где любые два соседних элемента инцидентны. При этом говорят, что вершина vik достижима из вершины vi1 . Маршрут, все ребра которого различны, назы-

вается цепью, замкнутая цепь называется циклом. Маршрут, все вершины кото- рого различны, называется простой цепью, замкнутая простая цепь называется

простым циклом. В орграфе цепь называется путем, а цикл –	контуром. Длина
маршрута равна количеству ребер в нем (с повторе-
ниями).
Н-граф называется связным, если для любых двух
вершин существует соединяющий их маршрут.
Компонентой связности н-графа называется макси-
мальный по включению связный подграф. Напри-
мер, граф на рисунке 7.1 состоит из трех компонент
связности. Вершина (ребро), удаление которой уве-
личивает число компонент связности, называется	Рисунок 7.1
точкой сочленения (мостом).
Для орграфа различают несколько типов связности (рисунок 7.2). Если

любые две вершины орграфа G достижимы друг из друга, то орграф G силь-

	u достижима из v или v из u , то орг-
но связный. Если для любых u,v V (G)

раф G связный. Если связным является н-граф G, полученный из G заменой

всех дуг на ребра, то G - слабо связный.

	сильно связный	связный	слабо связный
		Рисунок 7.2
∙	Матрицей достижимости орграфа G называется матрица R (G)			поряд-
	ка n , у которой rij =1, если вершина v j		достижима из вершины vi	и
	rij = 0 - в противном случае (при этом любая вершина достижима сама из
	себя).
∙
	Матрицей сильной связности орграфа G называется матрица S (G), эле-

	= rij & rji .
менты которой получены из R (G) следующим образом: sij

56

В н-графе матрица достижимости совпадает с матрицей связности.

Граф, полученный из данного отождествлением вершин, входящих в одну компоненту связности, называется конденсатом данного графа.

Пример 7.1. Выделить компоненты сильной связности орграфа G , задан- ного матрицей смежности:

	0	0	0	0	0	0	1	0
	1	0	0	0	0	0	0	0
	0	0	0	0	0	0	0	0
	0	0	0	0	0	1	0	0
A(G) =									.
	0	0	0	1	0	1	0	0
		0	0	0	1	0	0	0
0

0	1	0	0	0	1	0	1
0	1	1	0	0	1	0	0

	Вначале строим матрицу достижимости орграфа G , отмечая «куда» мож-
но попасть из каждой вершины:
		1	1	1	1	1	1	1	1
		1	1	1	1	1	1	1	1
		0	0	1	0	0	0	0	0
		0	0	0	1	1	1	0	0
	R(G) =									.
		0	0	0	1	1	1	0	0
			0	0	1	1	1	0	0
	0
	1		1	1 1 1 1 1					1
	1		1	1 1 1 1 1					1

Затем транспонируем матрицу достижимости, отмечая «откуда» можно по- пасть в каждую вершину:

1	1	0	0	0	0	1	1
1 1 0 0 0 0 1 1
1	1	1	0	0	0	1	1
				1
RT (G) = 1 1 0 1					1 1 1 .
1	1	0	1	1	1	1	1
	1	0	1	1	1	1
1							1

1	1	0	0	0	0	1	1
1	1	0	0	0	0	1	1

Элементы матрицы сильной связности находим как конъюнкции элемен-

тов матриц R(G) и RT (G) :

57

	1	1	0	0	0	0	1	1
	1	1	0	0	0	0	1	1
	0	0	1	0	0	0	0	0
	0	0	0	1	1	1	0	0
S(G) =									.
	0	0	0	1	1	1	0	0
		0	0	1	1	1	0	0
0
1		1	0 0 0 0 1					1
1		1	0 0 0 0 1					1

В первой строке матрицы S(G) единицы соответствуют вершинам v1 , v2 , v7 , v8 , следовательно, они образуют компоненту сильной связности

K1 = {v1,v2 ,v7 ,v8}. Вычеркиваем соответствующие им строки и столбцы матрицы

S(G) , получаем новую матрицу

	1		0	0	0
		0 1		1	1
S (G) =						,
		0	1	1	1
1
	0		1	1	1

в первой строке которой только одна единица, соответствующая вершине v3 ,

следовательно, K2 = {v3}. Вычеркиваем первые строку и столбец матрицы

S1 (G) , получаем новую матрицу

	1 1		1
			1 .
S2	(G) = 1	1
		1
	1		1

Матрица S2 (G) состоит только из единиц, следовательно, соответствующие им вершины v4 , v5 , v6 входят в одну компоненту сильной связности

K3 = {v4 ,v5 ,v6}. Теперь все вершины распределены по компонентам сильной связности, задача решена.

	K1 = {v1,v2 ,v7 ,v8},
Ответ: орграф G имеет три компоненты сильной связности:
K2 = {v3}, K3 = {v4 ,v5 ,v6}.

Связный граф без циклов называется деревом. Граф без циклов называется лесом. Остов или остовное дерево графа – любой его подграф, содержащий все вершины и являющийся деревом. Цикломатическое число γ (G) графа G - число ребер, которые необходимо удалить, чтобы связный граф стал деревом (не связный - лесом). Имеет место формула: γ (G) =| E(G) | − |V (G) | +k(G) , где k(G) - число компонент связности графа.

58

Представление сетей радиосвязи графами Сеть сотовой структуры представляет собой совокупность приемо-

передающих станций, обслуживающих определенную территорию. Вокруг ка- ждой приемо-передающей станции выделяется ее зона покрытия, называемая сотой. Расстояние между соседними станциями сети сотовой структуры назы- вается модулем сети радиосвязи R0 . Расстояние между станциями, работаю- щими в одном частотном канале, называется координационным расстоянием D . Зона обслуживания – область, в которой обеспечивается прием сигналов с заданным качеством.

Соты удобно представлять правильными шестиугольниками, так как ан- тенна, установленная в центре шестиугольника, покрывает почти всю его пло- щадь. В этом случае модуль сети вычисляется как расстояние между центрами смежных шестиугольников, а радиус зоны обслуживания – как расстояние от центра шестиугольника до его вершины.

Графом сети радиосвязи называется н-граф, вершины которого соответ- ствуют пунктам установки передающих станций, а ребра соответствуют парам станций, создающих помехи приему в зоне обслуживания друг друга. Посколь- ку распространение радиоволн одинаково во всех направлениях, то граф радио- связи – простой н-граф.

∙Матрица смежности графа радиосвязи G(V , E) - квадратная матрица

A(G) порядка n (n =|V |) , у которой элемент aij равен 1, если i ¹ j , рабо-

чие частоты станций vi и v j совпадают и расстояние между станциями не больше координационного. В остальных случаях элемент aij равен 0.

Пример 7.2. Сеть радиосвязи состоит из 8 станций, расположение которых показано на рисунке 7.3 (масштаб: 1 клетка=1 км). Координационное расстоя-

ние равно 4

км. Рабочие частоты станций удовлетворяют условиям:

f1 = f2 = f5 = f8 ,

f3 = f4 = f6 = f7 . Задать граф сети матрицей смежности.

Рисунок 7.3

59

Вначале строим матрицу Т(G) порядка n (n =|V |) , у которой элемент tij

равен 1, если i ¹ j и рабочие частоты станций vi								и v j совпадают:
	0	1	0	0	1	0		0	1
	1	0 0 0 1				0 0			1
	0	0	0	1	0	1		1	0
	0	0	1	0	0	1		1	0
Т(G)=	1	1	0	0	0	0		0	1	.
		0	1	1	0	0		1	0
0
0 0 1				1	0 1		0		0
1		1	0 0 1			0 0			0

Далее вычисляем расстояния между вершинами и сравниваем их с коор- динационным расстоянием:

d (1, 2) =

22 + 22

=

8

< 4 ;

d (1,3) = 6 > 4 ;

d (1, 4) =

32 + 22

=

13

< 4 ;

d (1,5) =

=

> 4 ;

d (1, 6) =

=

> 4 ;

22 + 92

32 + 92

85

90

d (1, 7) =

=

> 4 ;

d (1,8) =

=

> 4 ;

122 +12

122 + 62

145

180

d (2,3) =

=

> 4 ;

d (2, 4) =

=

> 4 ;

22 + 42

12 + 42

20

17

d (2,5) =

=

> 4 ;

d (2, 6) =

=

> 4 ;

72 + 42

72 +12

65

50

d (2, 7) =

=

> 4 ;

d (2,8) =

=

> 4 ;

102 +12

82 +102

101

164

d (3, 4) =

=

< 4 ;

d (3,5) =

=

< 4 ;

22 + 32

22 + 32

13

13

d (3, 6) =

=

> 4 ; d (3, 7) =

=

> 4 ;

32 + 32

62 +12

18

37

d (3,8) =

=

> 4 ;

d (4,5) = 6 > 4 ;

d (4, 6) =

=

> 4 ;

62 + 62

52 + 62

72

61

d (4, 7) =

=

> 4 ;

d (4,8) =

=

> 4 ;

92 + 32

92 + 42

90

107

d (5, 6) = 5 > 4

d (5, 7) =

=

> 4 ;

d (5,8) =

= 5 > 4 ;

32 + 32

32 + 42

18

d (6, 7) =

=

< 4 ;

d (6,8) =

=

> 4 ;

d (7,8) = 7 > 4 .

32 + 22

92 + 32

13

90

Строим матрицу D(G) порядка n

(n =|V |) , у которой элемент dij равен 1,

если i ¹ j и расстояние d (vi , vj )

между станциями vi

и v j не больше координа-

ционного:

0

1

0

1

0

0

0

0

1 0 0 0 0 0 0 0

0

0

0

1

1

0

0

0

1

0

1

0

0

0

0

0

D(G)=

0

0

1

0

0

0

0

0

.

0

0

0

0

0

1

0

0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0

Элементы матрицы смежности графа связи A(G) находим как конъюнк- ции соответствующих элементов матриц Т(G) и D(G)

60