Задачи по “Принятие решений”

 

.

 

2) Построим уравнения состояния:

 

   

Состояние данной цепи определяется зарядом на емкости C в вышеуказанной схеме.

Введем обозначения:

Запишем выражение (*) в новых обозначениях:

 

1) Определим Y в 1-ом случае:

 

2) Определим Y в 2-ом случае:

 

 

Задача №10

Два города A и B соединены 3 дорогами. Сколько существует способов совершить поездку A-B-A, и сколько их, если обратно (из B) нельзя ехать по дороге, по которой мы прибыли в B.

 

Решение:

Обозначим N=3 (количество путей).

Для первого случая N постоянно и при пути из A в B и обратно. Для второго случая при возвращении в A число N=3-1=2.

Следовательно, при условии, что переезды A-B-A по путям 1-2 и 2-1 и т.д., считаем одинаковыми получим для наших случаев (1) и (2) соответственно:

N₁=3+3=6 (число путей A-B-A с повторениями)

N₂=3         (число путей A-B-A без повторений)

Если же пути, например, 2-1 и 1-2 считать различными, то число путей соответственно, очевидно, равно N₁=9 (с повторениями) и N₂=6 (без повторений).

 

 

 

Задача №11

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

 

Решение:

Рассмотрим 1-ый случай (без запоминания нажатий).

Входные данные вводятся пассажиры, отсутствие входных данных  также сигнал. Состояние лифта - его положение на этажах (5 состояний). На выходе сигналы указывают соответственно движение лифта вверх, вниз или останов.

Состояния автомата М = {m₁,m₂,m₃,m₄,m₅}

Входной алфавит X = {x₀,x₁,x₂,x₃,x₄,x₅}, где x₀ – кнопка не нажата, x₁,x₂,x₃,x₄,x₅ – нажата кнопка соответствующего этажа.

Выходной алфавит Y = {y₀,y₁,y₂}, y₀ – движение вверх, y₁ – движение вниз, y₂ – останов.

Строим таблицы переходов и  выходов (аналогично алгоритму в  задаче №18):

Таблица переходов:                                            Таблица выходов:

 

m1

m2

m3

m4

m5

m1

m2

m3

m4

m5

x0

m1

m1

m2

m3

m4

x0

y2

y1

y1

y1

y1

x1

m1

m1

m2

m3

m4

x1

y2

y1

y1

y1

y1

x2

m2

m2

m2

m3

m4

x2

y0

y2

y1

y1

y1

x3

m2

m3

m3

m3

m4

x3

y0

y0

y2

y1

y1

x4

m2

m3

m4

m4

m4

x4

y0

y0

y0

y2

y1

x5

m2

m3

m4

m5

m5

x5

y0

y0

y0

y0

y2

 

 

Граф разрабатываемого автомата:

 

 

 

 

 

 

 

 

 

 

 

 

Матрица соединений:

	m1	m2	m3	m4	m5
m1	x0,x1(y2)	x2,x3,x4,x5 (y0)	-	-	-
m2	x0,x1(y1)	x2(y2)	x3,x4,x5(y0)	-	-
m3	-	x0,x1,x2(y1)	x3(y2)	x4,x5(y0)	-
m4	-	-	x0,x1,x2,x3(y1)	x4(y2)	x5(y0)
m5	-	-	-	x0,x1,x2,x3,x4(y1)	x5(y2)

Рассмотрим 2-ой случай (с запоминанием нажатий).

Состояния автомата обозначаем –  M(ijk). Каждое состояние означает, на каком этаже лифт находится сейчас и на какие идет далее. Если в очередь поступает команда, которая там есть или соответствующая состоянию в котором сейчас находится лифт, она не обрабатывается. Лифт запоминает три команды перехода. Схема для пяти этажей сложна приведем более простую схему: т.к. лифт воспринимает 3 команды возьмем лифт 3-хэтажного здания.

 

Состояния автомата M = {m₁,m₂,m₃,m₁₂,m₂₁,m₁₃,m₃₁,m₂₃,m₃₂,m₁₂₃,m₃₂₁,m₂₁₂,m₂₃₂}

Входной алфавит X = {x₀,x₁,x₂,x₃}, где x₀ – ни одна кнопка не нажата, x₁,x₂,x₃ – нажата кнопка определяющая номер этажа.

Выходной алфавит Y = {y₀,y₁,y₂}, где y₀ – движение вверх, y₁ – движение вниз, y₂ – останов

Таблица переходов:

m1

m2

m3

m12

m13

m21

m23

m31

m32

m123

m312

m212

m232

x0

m1

m1

m2

m2

m23

m1

m3

m21

m2

m23

m21

m12

m32

x1

m1

m1

m21

m2

m23

m1

m31

m21

m21

m23

m21

m12

m321

x2

m2

m2

m2

m2

m232

m1

m3

m212

m2

m23

m21

m12

m32

x3

m23

m3

m3

m23

m23

m13

m3

m21

m2

m23

m21

m123

m32

Таблица выходов:

m1

m2

m3

m12

m13

m21

m23

m31

m32

m123

m312

m212

m232

x0

y2

y1

y1

y0

y0

y1

y0

y1

y1

y0

y1

y1

y0

x1

y2

y1

y1

y0

y0

y1

y0

y1

y1

y0

y1

y1

y0

x2

y0

y2

y1

y0

y0

y1

y0

y1

y1

y0

y1

y1

y0

x3

y0

y0

y2

y0

y0

y1

y0

y1

y1

y0

y1

y1

y0

 

Граф разрабатываемого автомата:

 

 

 

 

 

 

 

 

 

 

Матрица соединений:

 

m1

m2

m3

m12

m13

m21

m23

m31

m32

m123

m321

m212

m232

m1

x0; x1 (y2)

x2, x3 (y0)

-

-

-

-

-

-

-

-

-

-

-

m2

x0; x1 (y1)

x2 (y2)

x3 (y0)

-

-

-

-

-

-

-

-

-

-

m3

-

x0, x2 (y1)

x3 (y2)

-

-

x1 (y1)

-

-

-

-

-

-

-

m12

-

-

-

x0; x1; x2 (y0)

-

-

x3 (y0)

-

-

-

-

-

-

m13

-

-

-

-

-

-

x0; x1; x3 (y0)

-

-

-

-

-

x2 (y0)

m21

x0; x1; x2 (y1)

-

-

-

x3 (y1)

-

-

-

-

-

-

-

-

m23

-

-

x0; x2; x3 (y0)

-

-

-

-

x1 (y0)

-

-

-

-

-

m31

-

-

-

-

-

x0; x1; x3 (y1)

-

-

-

-

-

x2 (y1)

-

m32

-

x0; x2; x3 (y1)

-

-

-

x1 (y1)

-

-

-

-

-

-

-

m123

-

-

-

-

-

-

x0  x1 x2 x3 (y0)

-

-

-

-

-

-

m321

-

-

-

-

-

x0 x1 x2 x3 (y1)

-

-

-

-

-

-

-

m212

-

-

-

x0; x1; x2 (y1)

-

-

-

-

-

x3 (y1)

-

-

-

m232

-

-

-

-

-

-

-

-

x0 x2 x3 (y0)

-

x1 (y0)

-

-