Специальная математика (стр. 14 )

 

Т. П.	A	B	C
x1	A	B	A
x2	B	B	C
x3	C	A	C

Т. В.	A	B	C
x1	y1	y3	y1
x2	y3	y3	y2
x3	y2	y1	y2

x1

Переход от автомата Мили к автомату Мура.

qixj ® yij bij   Т. П.	q1/b0	q2	q3
x1	q1/b11	q3/b21	q2/b31
x2	q2/b12	q1/b22	q3/b32

Т. В.	q1	q2	q3
x1	y3	y1	y2
x2	y4	y5	y6

		y3	y4	y1	y5	y2	y6
	b0	b11	b12	b21	b22	b31	b32
x1	b11	b11	b21	b31	b11	b21	b31
x2	b12	b12	b22	b32	b12	b22	b32

Теорема : (Глушкова)

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

n * m + 1 состояний, где n - число входных сигналов, m - число состояний исходного автомата Милли.

4.Теория графов

4.1. Понятие графа

Начало теории графов часто ведут от 1736 года и связывают с решением Эйлером знаменитой задачи о Кенигсбергских мостах.

С C

A D A D

В B

Жителям в те далекие времена, чтобы придать воскресному гулянию осмысленность, предлагалось выйдя из дома (на любом участке суши (А, В, С или D) пройти по всем мостам строго по одному разу и вернуться домой….

На втором рисунке этот корявый план нарисован в виде графа.

Следует отметить некоторые практические особенности теории графов. Слово граф однокоренное со словом графика. Поэтому не удивительно, что многие задачи теории графов представляются в виде специального рисунка – графа. Однако, это, как правило, возможно только для простейших вариантов задач. Рисовать графы для задач с сотнями вершин и тысячами дуг, если и возможно, то бессмысленно. Теряется главное преимущество рисунка – наглядность. Кроме того, сегодня при решении задач теории графов широко используется вычислительная техника, а для нее - решение задачи, заданной рисунком – одно из самых неудобных представлений, какие можно придумать. А наглядность компьютер понимает по-своему :-|

Граф G задается как совокупность двух сущностей: множества вершин Х и множества соединений – множества дуг или ребер.Г. G = <Г, Х>,

Графически это может выглядеть следующим образом:

 

m

b

e

x5

j

x4

Традиционная «аналитическая» запись для этого рисунка будет:

Гx1 = {x2} Гx4 = {x3, x3}

Гx2 = {x2, x3, x4} Гx5 = {x2}

Гx3 = Æ

Другой способ задания графа - с помощью матрицы инциденций.

	a	b	d	h	j	e	m
х1	-1
х2	+1	2	-1			-1	+1
х3			+1	-1
х4				+1	-1	+1
х5					+1		-1

Самый популярный вид матрицы для графов – матрица смежностей

	х1	х2	х3	х4	х5
х1		1
х2		1	1	1
х3				1
х4					1
х5		1

Граф с ненаправленными соединениями (ребрами) - неориентированный.

Граф с направленными стрелками (дугами) – ориентированный (орграф).

Мультиграф – граф, между вершинами которого может быть больше одной дуги.

В графах важно их топологическое свойство: то есть соединение определенных вершин. А само по себе взаиморасположение роли не играет, как и расстояния между объектами.

a b c a

a 1

3 1

c b c 3

1 2 3 2 b

2