close

Вход

Забыли?

вход по аккаунту

?

eroshmihaijlov

код для вставкиСкачать
??????????? ????????? ?? ???????????
??????????????? ??????????????? ??????????
??????? ????????????????? ???????????
?????-????????????? ??????????????? ???????????
???????????????? ???????????????
?. ?. ????, ?. ?. ????????
??????????????
???????? ?????????
??????? ???????
????? 1
?????-?????????
2009
??? 519.713(075.8)
??? 32.973-04?73
?78
??????????:
??????? «????????????» ?????-?????????????? ????????????????
??????????????????? ???????????? ??. ?. ?. ?????? (????),
???????? ??????????? ????, ?????? ?. ?. ????????;
?????????? ???????? ??????????? ??????????? ????????????????
??????????????? ???????????? ??. ?. ?. ???????,
?????? ??????????? ???? ?. ?. ?????????
??????????
???????????-???????????? ??????? ????????????
? ???????? ???????? ???????
???? ?. ?., ???????? ?. ?.
?78 ?????????????? ???????? ?????????: ????. ???????. ?. 1 /
?. ?. ????, ?. ?. ????????. ? ???.: ????, 2009. ? 80 ?.
ISBN 978-5-8088-0478-4
? ????? I ????????????? ???????, ?????????? ?? ???? ??????,
??????????????? ?????? ???????????? ? ???????????? ??????? ?????????, ?????????????? ??????????? ???????????? ??? ???????
??????????.
????????????? ??? ?????????, ????????? ???????, ?????????
? ???????? ? ???????? ???????? ?????????, ? ??????????? ???????? ?????? ?? ??????????????? ???????????. ??? ????? ????
??????? ????? ?????????? ? ????????????, ???????????? ??????????? ?????? ?????????? ? ???????? ????????????? ?????????????.
??? 519.713(075.8)
??? 32.973-04?73
ISBN 978-5-8088-0478-4 © ?. ?. ????, ?. ?. ????????,
2009
© ????, 2009
????????
???????? ?????????? ???????? ? ?????????? ????????????? ????????????? ???????????? ?????????? ??????. ??? ????? ???? ???? ?
????? ????????????? ??? ?????????????????? ?????????????? ?????, ?????????? ? ??????? ?????????? ???????????? ????????????? ? ??????????? ????????????, ?????????? ???????? ? ??????????
??????? ????????: ?????????? ???????????, ??????????????, ??????????????? ???????- ? ???????? ??????? ? ?. ?. ? ????????? ???? ?????? ??????? ???????? ????????? ??????????? ? ?????????, ??? ????????? ????????? ????? ? ???????? ??? ???????? ??????? ?? ??????????.
????????? ??????????? ???????? ? ??? ?????????? ????? ? ?????? ??????????? ?????? ????????????? ? ????????????? ??????? ???????????? ??????.
? ??????? ????????? ???????? ????????? ????????????? ??????
??????? ????????? (??????????? ? ??????????? ??????), ? ????? ????
????? ?????? ?????????????? ??? ?????????? ???????????????? ?????????, ??? ????????? ?? ??????? ????????????? ?????????? ?????????????? ?????????.
??????? ?? ?????????????? ????????? ???????? ????? ?????????????? ??????? ?????????. ???, ??? ??????? ????????? ? ??????? ????????????? ??? ??????? ? ??????????????? ?? ???????? ??????????????????. ????? ?????? ??????? ?????????? ???????? ???????? ? ???? ????????? ????????????.
? ??????? ?????????????? ??? ???????, ??????? ?????? ????????????? ???????? ????????????, ? ????????? ??????? ?????? ???????????
???? ???????. ?? ????????? ???????? ???? ???????? ???? ??? ????????
???? (? ??????????? ?? ???????). ?? ????? ???????? ??????? ??????????
??????? ???????????? ???????? ???? ??? ?????????? ??????? ?????????
???????? ????. ?????????? ?????? ??????????? ????? ????????? ??????????? ?????????.
???????? ?????????? ?????????? ????? ???????????? ??????? ????????? ? ?????? ???? ????????, ????????? ???????????? ????????? ?
?????? (??????? ??? ?????) ??? ?????????? ?????????????? ????.
??? ????? ??????? ???????? ????????? ??????? ????? ?????????
???????? ????????? ???????? ???? ?????? ?????????? ????????, ??????? ?????? ????????? ??? ????????? ????????? ??????? ????????????? ???????. ?????????? ????? ????? ??????? ????????????????
????????? ? ???????.
??? ????? ??????? ??????? ???????? ????? ?????????????? ????????? ???????? ???????? ????????? ?????????????? ?????, ???????????? ?? ????????? ????????? ??????. ?????? ? ??????????? ?? ??????? ??????? ???????? ?????????? ?????? ??????????????.
??????? ??????? ?? ???? ??????. ? ????? I ???????? ?????????????
??????? ?????????????? ?????????, ? ????? II ?????????? ????????
??????? ?? ?????????????? ????????? ?????? ?????, ?????? ????????
???????????????? ??????????? ????????? ? ??????? ?????????? ????????????? ???????.
3
1. ?????? ????????, ????????? ??????????
1.1. ??????? ? ?????????? ?????????
??? ?????? ???????? ?????? ????????? ????? ???????????? ??????, ?????????? ?????????? ????????? (???.??????????????????
?????????????????
1). ?? ???? ???????? ? ?????????? ??????? ??????? t?=?1, 2, 3,... ????????? ?????,
???????????? ?? ???? ???????? ????????: {x0, x1, x2, ?, xn?1}.
?? ?????? ???????? ??????????
x
Дискретный
y
?????, ???????????? ?? ???? ?????автомат
???? ????????: {y1, y2, y3, ?, ym?1}.
?????????? ??????? ????????????
???. 1. ?????? ??????????
?????????????? ??????? ???? ? ???????????????? ??????????
??????.
?????????? (??????????
??????? ??????????????? ????????????)
??? ?????? ????????? {a0, a1, a2, ?,
an?1}, ???? ?? ??????? (?????? ?0) ?????????? ????????? ?????????? ????????.
?????? ????? ???????? ? ????????? ?????????, ? ????? ????????? ???????? ??????????????? ? ??????? ? ????????????
??????? ????????? (???????? ??? ??????????). ??????? ?????????? ???????? ????? ???????? ?????????.
? ???????? ???????? ?????????? ?????????????? ????????
?????????? ?? ????????? ??????????? ?????? ???????. ???,
????? ?? ???????? ?????? ????????? ???????? ?????????????
? ???????? ????? ????????? ????????. ??? ???? ?? ????????????
??????????? ?????????? ???????? ????????? ??????????, ???
??????????? ????????? ?????? ? ?????? ????? ?????????. ??????????????, ??? ??????? ??????? ?????????? ? ?????? ???????????? ??????? ??????? ? ????? ?????? ??????????? ????????.
?? ????? ???? ??????? ?????? ????? ????????????? ?????????
?????? ???????????????? ??????? ??????? ? ????? ????? ???????? ????????????. ??? ???????? ???????? ???????? ?? ?? ?????????, ????? ????, ??????????????, ??? ???????? ??????, ????????? ? ????? ?????? ?? ???????? ??????? ? ????????? ????????,
?????????? ? ??? ?? ?????? ??????? t, ??? ? ??????? ?????? x(t).
???????? ???????? ?????? ?????????? ?????? ?????.
????? ?? ?????? ????? ????? ?????? ????????? ???????? ?????????? ??????????????? ??????? ???????, ??????????? ??????? ?? ????????????? ??????????.
?????????? ??????? ?? ????????????? ?????????? ?????? ????????? ???????????? ????? ???????? ? ????????? ?????????????4
???????. ? ?????????? ??????, ???? ????? ??????? ? ???????? ??????????????????? (????) ???????, ????? ????????? ???????, ? ??????? ??????? ???????? ????? ????????????? ????????. ? ????? ???????? ???????, ??? ??????? ?? ??????? ?????????????? ? ???? ????????? ???????????? (??????? ? ???????? ????). ??????? (????????)
?????? ???????????, ?????????????? ??????????? ?????????.
???? ????? ??????? ? ???????? ??????????????????? (????
?? ?????) ??????????, ?????????? ????????? ? ???????? ??????????. ? ???? ?????? ????????? ???????????? ?????? ???????
????????. ????? ?? ???????? ???????? ??????????? ??????????????????? ? ???????????? ????? ???? ???????? ???? ?????????? ????????? [1, 2].
?????? ?????????? ?? ???????? ????? ??????? ?? ??????????
????? ??????? ?? ???? ???????? ??????: ???????????? ? ???????????? ???????.
?? ????? ???????????? ??????? ??????? ? ???????? ???????
??????????????? ??? ????? ???????? ? ????????? ?????????.
??? ?????? ????????? ??????? ???????????? ?? ?????, ??? ????
??????????????, ??? ??? ??????? ????? ????????? ??????????
???????? ?????.
?? ????? ???????????? ??????? ?????????? ?????? ????????????? ??????? ? ???????? ????????, ? ????? ?????? ????????????? ????????? ????????. ???????? ????? ???????????? ??????? ???????? ????????? ?????, ????????? ?? ???????????? ?????
????????? ????????? ??????.
1.2. ??????? ??????? ?????????
??????????? ??????? ????? ?????? ??? ???????????? ?????
????????: ???????? ???????? {x0, x1, x2, ?, xn?1}, ????????? ???????? {y1, y2, y3, ?, ym?1}, ???????? ????????? {a0, a1, a2, ?, an?1},
?????????? ????????? ?0, ??????? ????????? d(a, x), ???????????? ????? ????????? ???????? ? ?????? ??????????? ? ????????
????????, ??????? ??????? l(a, x), ???????????? ???????? ?????? ? ??????????? ?? ????????? ? ???????? ???????.
?????????? ??????????????? ???????? ???????? ???? ? ???? [1, 3, 4].
??????? ????????? ? ??????? ???????? ???? ???????? ? ????
a(t)?=?d[a(t?1), x(t)], y(t)?=?l[a(t?1), x(t)], t ?=? 1, 2, 3,
? ?? ?? ??????? ???????? ???? ? ? ????
a(t)?=?d[a(t?1), x(t)], y(t)?=?l[a(t)], t ?=? 1, 2, 3.
5
???????? ????? ???????? ???? ? ???? ??????? ? ???, ??? ???????? ?????? ? ???????? ???? ??????? ??? ?? ??????????? ?????????, ??? ? ?? ???????? ???????, ? ? ???????? ???? ? ??????
?? ????????? ? ??????????????? ?????? ???????.
??????? d ? l ???????? ??????????? ?????????, ???????
?? ?????? ???????? ? ????????? ?????.
? ????. 1 ? 2 ?????????????? ???????????? ??????? ?????????
? ??????? ???????? ????.
??????? 1
??????? 2
a(t?1)
x0
x1
x2
a(t?1)
x0
x1
x2
a0
a3
a0
a1
a0
y0
y3
y2
a1
a2
a3
a0
a1
y1
y0
y3
a2
a1
a2
a3
a2
y2
y1
y0
a3
a0
a1
a2
a3
y3
y2
y1
????????? ??????? ??????????? ??????? d ? l ?????????, ??????? ????????? ? ??????? ????? ???? ??????? ? ???? ???????
?????????-??????? (????. 3), ? ??????? ?? ??????????? i-? ??????
? j-?? ??????? (i ? {0, 1, 2, ?, (h?1)}, j ? {0, 1, 2, ?, (n?1)}) ???????????? ????? ????????? ???????? a(t) ? ???????? ??????, ???????????? ??? ???????? ? ??? ?????????.
??????? 3
a(t?1)
x0
x1
x2
a0
a3/y0
a0/y3
a1/y2
a1
a2/y1
a3/y0
a0/y3
a2
a1/y2
a2/y1
a3/y0
a3
a0/y3
a1/y2
a2/y1
??????? ????????? d ? ??????? l ???????? ???? ?????????
? ????. 4, 5.
??????? 4
??????? 5
a(t?1)
x0
x1
x2
a(t)
y(t)
y3
a0
a3
a1
a2
a0
a1
a2
a0
a1
a1
y2
y1
y0
a2
a1
a2
a0
a2
a3
a0
a3
a3
a3
????????? ??????? ??????? l ??? ???????? ???? ???????
?????? ?? ?????? ????????? a(t), ??? ?????????? ?????? ??????6
??? ? ??????? ?????????? ??????? ????????? ???????? ????????? ?
???????????? ??????? ???????? ???????? (????. 6). ????? ???????
?????????? ?????????? ???????? ????????? ???????? ????.
??????? 6
y(t?1)
a(t?1)
x0
x1
x2
y3
a0
a3
a1
a2
y2
a1
a2
a0
a1
y1
a2
a1
a2
a0
y0
a3
a0
a3
a3
?????? ??????? ??????? ?????????-??????? ?????? ?????????? ???????? ???????, ?. ?. ??????? ? ????????????? ???????
????????. ???, ????. 3 ?????? ??? ?????????? ???????? ???? ??
???????? ????????? x0, x1 ? x2 ?????????????? ??? ???????. ?????????? ??????? ????????? (??. ????. 6) ?????? ??? ??????????
???????? ???? ? ?????? ?? ???????? ?????????.
???????? ? ???? ??????????? ??????? ????????? ? ???????
????????. ?? ???. 2 ? 3 ???????????? ????? ????????? ???? ?
????, ??????? ?????????-??????? ??????? ??????????? ?????.
??? ???????? ???? ?? ???????, ??????????? ????????? ai ?
aj, ???????? ???????? ???????? ??????? ?, ??? ????????? ???????? ?????????????? ?????? ???????, ? ????????? ??????? y, ??????? ?????????????? ??? ???? ???????? (???. 2).
??? ???????? ???? ?? ???????, ??????????? ??? ?????????,
???????? ?????? ???????? ???????? ???????, ???????????????
???? ???????. ???????? ??????? ?????? ??????? ? ???????????,
??????? ???????????? ? ??? ?? ??????? (???. 3).
x1 /y3
a0
x2 /y3
x1 /y2
a0
y3
a1
a3
x1 /y0
x2 /y0
x2 /y1
x0 /y2
x0 /y1
x0 /y3
x0 /y0
x1 /y2
x0
x0
a3
y0
a2
x1 /y1
???. 2. ???? ???????????????? ???????? ????
x1 x2
x2
a1
a1x1
y2
3
y2
x2
x
x0 2 x0
x0 x0 x0 x0
x2
x2
x1
a0
x1 y
a3
y0
x1 ? x2 x1 Ъ x2
a2
y1
a2
y1
x1
x1
???. 3. ???? ?????????-???????
???????? ????
7
? ??????????? ???????? ??????? d ? l ?????????? ??? ????
????????? a(t?1) ? x(t). ????? ???????? ?????????? ?????????
?????????????. ???? ??????? d ? l ?????????? ?? ?? ???? ?????
a(t?1) ? x(t), ?? ??????? ?????????? ?????????. ?? ????? ?????????????? ????????? ??? ??????? ???????? ????????.
???????? ??????? ???????????? ??????? ???????? ???????? ??????? ?? ??????? ???????? ?? ???????? ????? ? ??????? ??? ??
??????????????? ????? (?????? ? ???????? ?????????-???????
???? ??????).
??????? ? ??????? ?????? ????????? ????????? ???????????
???????, ??? ??????? ? ??????? ?????? ?????????. ??????? ??
????? ???????????? ??????? ????? ????????? ?????? ?????????
???????? ? ?????????? ????????? ?????? ?????????, ???????????? ???????? ???????. ????? ?????? ?????????? ???????????? ????? ????????? ???????????? ????????. ??? ??????? ??
?????????? ?????? ??????? ??????????????? ????????? ????????? ? ??????????????? ?????????.
????????? A/ai ??????? A ? ????????? ai. ????????? ai ????????
A1 ???????????? ????????? aj ???????? A2, ???? A1/ai ? A2/aj ???
???????????? ????? ?????????????????? ??????? ???????? ???????????? ?????????? ???????? ??????????????????. ?????????
ai ? aj ????? ???????????? ?????? ???????? (?. ?. A1?=?A2).
??? ???????? A1 ? A2 ????????????, ???? ??????? ????????? ai ???????? A1 ????????????, ?? ??????? ????, ???? ????????? ???????? A2 ? ??? ???? ??????? ????????? ?j ???????? A2
????????????, ?? ??????? ????, ???? ????????? ???????? A1.
?????? ????????????? ????????? ???????? ????? ??????????
????? ??????????. ? ?????????? ????? ?????? ????? ????????
????? ???????, ????????????? ?????????, ?? ? ??????? ?????? ?????????. ????? ???????, ?????? ??????????? ????? ????????? ???????????? ???????? ???????? ? ????????? ????????, ?????????????? ?????????, ? ?????????? ????????? ?????? ?????????.
1.3. ??????????? ????? ????????? ???????????? ????????
????? ??????? ?. ?? ?????? ?????????, ????????????? ???????? ?, ????????? ??????? ??????? ?min ? ??????????? ??????
?????????? ?????????. ????????????? ?????????????? ??????
???????? ? ???????? ?min ? ??????????? ?????? ?????????? ????????? ??????? ???? ???????? ?????.
8
?????????? ???????? ??????????? ????????? ???????????? ????????? ????, ???????????? ?. ?. ????????? [1], ??????? ??????? ? ??????????? ???????? ?????? ??????????? ??
???????, ?????????? ????? ?. ??????????? ? ?. ?????.
??? ????????? ????????? ???????? ??????????? ?? ???????
???????????????? ?????? ????????????? ?????????, ?????
?????? ?????? ????????????? ????????? ?????????? ????? ??????????. ???????????? ??????????? ??????? ????? ???????
?? ?????????, ?? ??????? ????? ????????????? ????????? ??????????? ????????? ????????? ????????. ??????? ????????? ????????? ?? ?????? ????????????? ????????? ???????? ????????????.
??? ????????? ???????????? ???????? ?????????? ??????????????????, ???? ???????, ???????? ? ????? ?? ???? ???? ?????????, ??? ?????? ?????????? ??????? ???????? ???????????? ?????????? ???????? ???????. ??????????? ???? ????????????????? ????????? ???????????? ???????? ???????? I ?????
???????????????.
????????????????? ????????? ???????? ?????????? ??????????????????, ???? ??? ????? ??????? ???????? ??????????? ? ????????????????? ?????????. ??????????? ???? ????????????????? ????????? ???????? II ????? ??????????????? ? ?. ?.
?????????? ??????????? ????? ?????????????? ?? i-?? ?????? ????????????? ????????? ? i-?? ?????? ???????????????.
???? ????????? ????? ??????????????? i ????????? ? (i+1)-?
???????, ?? ?? ????????? ? ?? ????? ???????????? ?? ???????????? ?????? ? ?????????? ???????????, ??? ?????????, ??????? ???????????????.
????????? ????????? ????????? ???????????? ???????? ??
?????? ??????????????? ???????????? ????????? ??????? ???????????????. ???????????, ??? ????????? ????? ??????????????? ????? ???????? ?? ???????? ????? ?????.
??????. ????? ???? ????????? ????????????? ???????? ???? (???.?????????????????????????????????????????????????????
????????????????????????????????????????????????????
4). ????? ???? ???????? ? ??????????? ?????? ?????????, ?????????????? ?????????.
???????? ??????? ?????????-??????? ????????? ????????
(????. 7).
????????? ????????????????? ????????? ?? ?????? ???????? ????????? ???????: {a0}, {a1, a4}, {?2, a3}.
?????????????, ???? ??????? ????????? ? ????????? ?1 ????
a4, ?? ??? ?????? ???????? x0 ? x1 ??????? ???????????? ?????9
a2
a1
x1/y0
x0/y0
x1 /y1
x1/y0
a0
x0/y1
x1 /y0
x0 /y0
x0/y1
a4
x1 /y0
a3
x0 /y0
???. 4. ???? ????????? ????????? ????????????? ???????? ????
??????? 7
a(t?1)
x0
x1
a0
a0/y0
a1/y1
a1
a0/y0
a2/y0
a2
a4/y1
a3/y0
a3
a1/y1
a2/y0
a4
a0/y0
a3/y0
????? ???????? ??????? y0. ???? ??????? ????????? ? ????????? a2 ??? ?3, ??? ?????? ???????? ?1 ? ?2 ?????????????? ????? ?????????? ???????? ??????? ?1 ? ?0.
????????? ?0 ?????? ???????? ?? ? ???? ?? ???? ????? ????????????????? ?????????, ??? ??? ??? ?????? ???????? ?0 ? x1 ??????? ? ????????? a0 ???????????? ???????? ??????? y0 ? y1.
?????? ????????? ?? ?????? ????????????????? ?????????.
?? ????????? a1 ? a4 ??? ?????? ??????? x0 ??????? ????????? ?
???? ? ?? ?? ????????? a0, ? ??? ?????? ??????? ?1 ? ? ????????? a2 ? ?3, ??????? ??????????? ? ????? ?????? I?????????????
??????????????
?????? ???????????????. ?? ????????? a2 ? a3 ??? ?????? ??????? ?0 ???????
????????? ? ????????? a4 ? a1, ? ??? ?????? ??????? ?1 ? ? ????????? ?3 ? a2, ?? ???? {?4, ?1} ? {a3, ?2} ???????? ??????????????????. ?????????????, II ????? ??????????????? ?????????
? I??????????????????????????????????????????????????????????
???????????????????????????????????????????????????????????
??????? ???????????????, ? ??????, ????????? ???????? ????????? ???????.
????????? ?????? ?????? ?????????? ?????? ????? ????? ?????????:
{a0} ? b0, {a4, a1} ? b1, {a3, a2} ? b2.
10
x0/y0
x1/y1
b0
x0/y0
b1
x1/y0
x0/y1
x1/y0
b2
???. 5. ???? ?????????????? ???????????? ???????? ????
??????? ????????? ?????????????? ???????????? ????????
???????????? ????. 8, ? ???? ???????????? ???????? ?????????
?? ???. 5.
??????? 8
b(t?1)
x0
x1
b0
b0/y0
b1/y1
b1
b0/y0
b2/y0
b2
b1/y1
b2/y0
?????? ??????????????? ????? ???????? ? ??????? ??????????? ???????, ??????? ???????? ????????? ???????:
?????? ???????????? ??????????? a1, a2, ?3, ..., ?h?1, ? ???????
a0, a1, a2, ..., ?h?2, ??? h ????????????????????????????????????
? ????? ????????? ???????????? ????????.
?? ??????????? i-? ?????? ? j-?? ??????? ???????????? ???????, ??? ??????? ???????? ??????????? ????????? ai ? ?j. ???? ????????? ?????? ?????????? ?? ??? ????? ????????, ???????? ???? «Ч», ???? ??? ???????????? ??????????, ?? ????????
???? «?». ????????????? ??????????? ????????? ???????????? ??
????????? ??????? ?????????????????? ???????. ??? ???????????????? ??????? ??????????? ??????? (????. 9) ???????? ????????? ???????:
??????? 9
a1
Ч
a2
Ч
Ч
a3
Ч
Ч
a 1, a 4
a 2, a 3
a4
Ч
a 2, a 3
Ч
Ч
a0
a1
a2
a3
11
??? ????? ?? ????. 9, ????????? a1 ? ?4 ????? ?????????? ???
??????? ??????????? ? ???? ?????? ????????? ?2 ? ?3, ?????????
?? a2 ? ?3 ???????????? ??? ??????? ??????????? ? ???? ??????
????????? ?1 ? a4, ? ????? ????????? ?2 ? ?3. ??? ??????? ?? ???????? ???????????????, ??????? ???????????? ???? a1 ? a4, ?
????? ?2 ? ?3.
??? ??????????? ????????? ???? ???????? ??????? ????????????????? ????????? ? ????-?????? ???????????????.
????-?????????????? ?????????? ????? ????????? ?????????? ????????? ????????? ????. ???? ??? ????-?????????????
????????? ????? ??????? ???????? ??????????? ? ??? ????????????????? ?????????, ?? ??? ?????????? ??????????????????. ??? ??????????? ?????? ??????????????? ????????? ???
???????? ???? ???????????? ?????????? ????, ??? ??? ???????
??? ????????? ????.
??????. ??????? ???? ????? ?????????? ???????? ?????????
(????. 10).
????????? ?? ?????? ??????????????? ???????? ?????????
???????:
{?0, ?2, ?4} ? {?1, ?3} ? ????-?????,
{a0, ?2, ?4}, {a1} ? {?3} ? I ?????, {?0, a2, ?4},
{a1} ? {?3} ? II ?????,
? ?????????????, ? ????????? ????? ???????????????.
????????? ?????? ?????? ?????????? ?????? ??????????????? ????? ?????????? (?????????????? b0, b1 ? b2), ???????? ?????????? ??????? ????????? ?????????????? ???????????? ???????? ???? (????. 11).
??????????? ??????? ??? ???????? ???? ???????? ?????????? ??????? ??? ???????? ????, ??????? ? ??? ???????????????? ??????? ???????? ????????? ???????: ????? «Ч» ???????? ?
??????? 10
??????? 11
y(t?1)
a(t?1)
x0
x1
y1
a0
a2
a4
y1
y0
a1
a1
a2
y1
a2
a0
a2
y0
a3
a3
a1
y1
a4
a4
a0
12
y(t?1) b(t?1)
x0
x1
b0
b0
b0
y0
b1
b1
b2
y0
b2
b2
b1
???????, ??????????????? ????? ????????? ? ??????? ????????? ?????????. ????? ? ?????????? ?????? ??????????? ???????, ??? ??????? ??? ????????? ????? ???? ??????????, ? ??????????? ??????????? ?????????? ????????? ???????. ???? ??????? ???????????, ? ?????? ???????? ???? «Ч» (????. 12).
??????? 12
a1
Ч
a2
a0, a2
a2, a4
Ч
a3
Ч
a1, a3
a1, a2
Ч
a4
a2, a4
a0, a4
Ч
a0, a4
a0, a2
Ч
a0
a1
a2
a3
?? ????????? ??????? ?????????????????? ??????? ????????? ???????????? ? ?????? ???????????????. ?? ????. 12 ?????,
??? ????????? ?1 ? ?3 ????? ?????????? ? ???? ?????? ??????????????? ??? ??????? ??????????? ????????? ?1 ? ?3, ? ????? ?1
? ?2. ?????? ??????? ??????????, ? ?????? ???????????, ??? ???
?? ??????????? a1 ? ?3 ????? ???? «Ч».
?????????? ?????? ???????? ???????????????? ???????, ??????? ????????? a0, a2 ? a4 ????? ?????????? ? ???? ?????? ???????????????.
??? ????????? ????????????? ???????? ?????? ????????????? ????????? ?? ????????????, ? ??????? ????????? ?????? ???????? ? ??????????? ?????????? ??????????.
??? ??????????? ????????? ????????? ????? ???????????? ??????? ???????????? ???????, ? ????? ?????????????? ???
??? ????????? ????????????. ?????? ? ???? ?????? ??????????
?????????????, ??? ????? ??????? ??????? ? ??????????? ?????? ?????????. ??? ????? ???????????? ?????? ?????????.
??? ????????? ???????? ??????????? ?? ?????????????? ?????? ???????????????, ?????? ? ????? ?????? ???????? ???? ?????????, ??????? ??? ????????? ??????? ????????????? ?????
??????????. ????? ?? ?????????? ?????????????? ????? ??????????? «??????» ???, ?????: ?) ?????? ????????? ?????????
???????? ?????? ???? ?? ? ???? ?? ?????????? ????? ????????????? ????????? (??????? ???????); ?) ??? ????? ???? ?????????,
??????????? ? ????? ?????????? ??????, ??? ????? ???????
13
??????? ??????? ????????? ? ?????????, ???????????? ? ?????????? ?????? (??????? ??????????? ?? ???? ??????).
??? ??????????? ????????? ????????? ????? ?????? ???????????? ??????????? ???????.
???????.
1. ????? ????????? ??????? ???? (???.??????????????????????????
?????????????????????????
6). ? ????? ????????? ???????????? ???????? ?? ????????? ?????? ???????? ?????? (?? ????????? ?0 ??? ?????? ?? ???? x1).
???????? ?????????, ??? ??x1/y0
a1
??????????? ????????? ?0 ???? y1
x1/y0
?? ???????? ? ?????????? ???a0
x 0/ ?
x0/y0 x0/y1
?? ????????? ??????????? ????????? ????????????? ????????. ??x1/y0
a2
??? ?????????????? ??????? ???
?????????. ??? ????? ????????
???. 6. ???? ????????????????
????????? (????. 13) ? ?????????? ????????? ??????????
???????? ??????? (????. 14).
???????? ????
??????? 13
??????? 14
a(t?1)
x0
x1
a1
a0, a1
a0, a2
a0
a0/?
a1/y0
a2
a0, a1
Ч
a1
a2/y0
a0/y0
a0
a1
a2
a1/y1
a0/y0
???????, ??????? ? ??????? ??????????? ???????, ???????????????, ??????? ?? ??? ????? ???????? ????????? ???? ????????????? ?????????:
{?0, ?1}, {?0, ?2}.
?? ???? ?? ?????????? ????? ????????? ?????? (?? ????? ??????????? ??????? ???????), ???????, ????????? ?????? ?????? ????? ?????????? (b0 ? b1 ??????????????), ???????? ???????
?????????-??????? ???????????? ???????? (????. 15).
??????? 15
14
b(t?1)
x0
x1
b0
b1/y0
b0/y0
b1
b0/y1
b1/y0
2. ??????????? ??????? ???? ????? ???????? ???????????????? (????. 16).
??????? 16
a(t?1)
x0
x1
a0
a2/y0
?
a1
a3/y0
a2/y0
a2
?
a4/y0
a3
a5/?
a5/y1
a4
a5/y0
a5/?
a5
?
?
???????? ??????????? ??????? (????. 17). ??? ?????????
?????? ? ?????? ??????? ?????? ?????? ??????? ?????????
0, 1, 2,... ?????? ????????? ?0, ?1, ?2.
??????? 17
a1
2, 3
?
a2
?
Ч
a3
2, 5
?
3, 5
2, 5
?
Ч
a4
2, 5
?
3, 5
2, 5
?
4, 5
?
?
a5
?
?
?
?
?
a0
a1
a2
a3
a4
?? ??????????? ??????? ??????? ???? ????????????? ?????????
(0, 2), (1, 3), (2, 4), (3, 4), (4, 5),
(0, 3), (1, 4), (2, 5), (3, 5),
(0, 4), (1, 5),
(0, 5).
???????? ?????? ????????????? ?????????. ??? ????????? ? ???? ?????? ???? ????????? ?????????? ? ??????????, ???15
?? ??? ????????? ???? ??????? ????????????. ???, ?? ??????????????? ??? ????????? (3, 4), (3, 5), (4, 5) ???????, ??? ????????? 3, 4, 5 ????? ?????????? ? ???? ?????? (3, 4, 5). ?????????
??????????, ????? ???????? ????????????? ??????: (0, 3, 4, 5),
(1, 3, 4, 5), (0, 2, 4, 5).
???????? «??????» ?????? ???????????????. ??? ????? ?????? ?????????????? ????????? ??????? ?????????? ????: ???????
????????? ????????? ???????? ?????????, ?????????????????
??????????
? ???????????????? ???????? ???????????????, ? ?? ??????????? ??????
? ??????? ???????? ???????, ???? ?????????, ???????????????
???????, ?????? ? ?????? ??????????????? ?????? (????. 18).
??????? 18
?????????
??????
???????????????
0
(0, 2, 4, 5)
1
(0, 3, 4, 5)
1
(1, 3, 4, 5)
1
2
3
4
5
1
1
1
1
1
1
1
1
1
1
?? ?????????? ??????? ?????????? ??????? ???????????
????? ????? ???, ????? ? ?????? ??????? ????? ??????? ??????
???? ?? ???? ???????. ??? ????????? ??????????? ????? ????????? ?????????????? ???????? (?. ?. ?????? ?????????? ??????
??????????????? ????? ????? ?????????? ????? ??????????). ???????????? ?????????????? ??????? ??????? (??? ??? ?????? ????????? ????????? ???????? ????? ???????? ???? ?? ? ???? ????????? ?????????????? ????????).
?????? ? ?????????? ???????????? ????? ????? ???????????????, ?????????????? ??????? ???????, ????? ?????? ??????? ???????? (? ?????? ????????? ??????). ??? ????? ???????
??????? ????????????? ???????????? ????????? ???????????
???????? (????????, ????? ?????? ? ??????, ???????? ???????
[1] ? ?. ?.). ??? ??????????? ???????????? ???????? ??????????,
????? ????, ????????? ??????? ???????????. ???? ??? ??????? ??????? ????????? ??????? ???????????, ????? ???????? ?????????, ? ????????? ?????? ?? ??????? ??????? ????? ?????? ??????? ? ????????? ??? ?? ???????????.
??? ???????????????? ??????? ?? ????.????????????????????????
???????????????????????
18 ??????? ???? ????????? ??????????? ???????, ??????????????? ??????? ???????:
(1, 3, 4, 5),
(0, 2, 4, 5).
16
???????? ??????? ?? ??????????? ?? ???????? ??????? ?????????, ????????, ??? ??????? ????????????? ??????? ???????????. ?????????
(1, 3, 4, 5) ? b0,
????????
(????. 19).
???????
(0, 2, 4, 5) ? b1.
????????? ??????????????
????????
??????? 19
b(t?1)
x0
x1
b0
b0/y0
b1/y0
b1
b1/y0
b0/y1
???????? ??????????????? ????????? ? ???????????? ?????????. ??? ?????? ???????? ??????????????? ????????? ?? ?????????? ?????????? ? ????????????? ????????? ?????????, ??????
?? ??? ??? ????????? ?????????? ??????? ??????????????????
? ?????????, ??? ???????? ?????????????????? ????? ?????????
?????????. ?? ??????????? ??????? ????? ?????????? ???????
??????????????????, ?????? ?????????? ????? ???????? ??????????????????, ??????? ?? ???????? ? ???????? ???????? ? ?????????????? ?????????.
? ???????? ????????? ???????? ????????? a0 ? b1 (?????????? ? ???? ????????? ?0). ????????? ???????? ??? ??????? ?????????????????? x0x1x0 ???????? ? ????. 20 ? 21.
??????? 20
????
?????????
?????
a0
??????? 21
x0
x1
x0
????
a2
a4
a5
?????????
y0
y1
y0
?????
b1
x0
x1
x0
b1
b0
b0
y0
y1
y0
???????? ?????????????????? ????????? ?????????.
3. ??????????? ??????? ???? ????? ?????????? ???????? ????????? (????. 22).
??? ??????????? ???????? ??????????? ??????? (????. 23), ?
??????? ??????? ???????? ??????? ??????????? ?????????.
17
??????? 22
??????? 23
y(t?1)
a(t?1)
x1
x2
a1
Ч
y1
a0
a2
a2
a2
2, 5
0, 2
?
y2
a1
a5
?
a3
Ч
?
0, 1
?
a2
a5
a0
a4
Ч
?
0, 3
1, 3
y2
a3
a5
a1
a5
?
2, 5
?
Ч
Ч
y2
a4
?
a3
a0
a1
a2
a3
a4
y1
a5
a2
?
???????? ???????????? ???????. ? ?????????? ??????? ??????? (????. 24), ? ??????? ????????? ?????? ??? ???? ????????: «Ч» ?
??????????, ??? ????????? ?? ???????????? ?? ??? ????? ????????, ? «?» ? ??????????, ??? ????????? ????? ??????????.
??????? 24
a1
Ч
a2
?
?
a3
Ч
?
Ч
a4
Ч
?
Ч
?
a5
?
Ч
?
Ч
Ч
a0
a1
a2
a3
a4
?? ?????????? ??????????? ??????????? ??????? ???????
???? ????????????? ?????????, ??? ???? ??? ?????????, ??? ?
?????, ??????? ?????? ??????? ?????????:
(0, 2), (1, 2), (2, 5), (3, 4),
(0, 5), (1, 3),
(1, 4).
? ?????????? ?????????? ????????? ????????? ?????? ????????????? ?????????:
(0, 2, 5), (1, 2), (1, 3, 4).
????????? ?????? ?????? ????????????? ????????? ?????
??????????:
(0, 2, 5) ? b0, (1, 2) ? b1, (1, 3, 4) ? b2.
????? ??????, ??? ??? ?????? ????????????? ??????? ???????, ??? ??? ? ??? ?????? ??? ????????? ????????? ????????.
18
???????? ?????????? ??????? ????????? ???????? ???? (????. 25)
? ???????? ??????? ???????????.
??????? 25
y(t?1)
a(t?1)
x1
x2
y1
b0
b0
b0
y2
b1
b0
b0
?
b2
b0
b2
???????? ??????????, ??? ?? ????? ????????? ??? ?????
??????? ???????? ??????? ????????? ? ?????????, ????????????
? ???? ?????? ? ????????? ???????, ??????? ??????? ? ???????????? ???????? ?.
??? ???????? ??????????????? ????????? ? ? ? ??????????
?????????? ??? ???????? ? ????????????? ????????? ?????????
? ???????? ???????????? ??????? ??????????????????. ???? ???
???? ?? ???? ??????? ????? ?????????????? ?????????? ???????? ??????????????????, ?? ???????? ????????????. ?????? ??????????????? ????????? ? ? ? ???????? ? ????? ????????? ???????????, ?????????? ? ???? ???????? ??????? ??????? ?
???????????.
1.4. ?????? ???????????? ??????? ????????,
????????? ? ???? ????????? ????????????
????? ????? ????????
x1x2x2x1x3
y1y4y1y3
x2x3
y2y4
x2x1
y3y1
x1x2x3x1
y3y2y2
??????? ??????? ??????? ?? ???? ????: ?1, ?2, ?3, ???????? ?
?? ???????: y1, ?2, ?3, y4.
??? ?????????? ?????????? ????????? ? ???? ??????????? ???????? ?????? ??????????? ??? ??????? [5]:
????????????????????????????????????????????????????????
??????????????????????????????????????????????????????
??????????????????????????????????????????????????????
????????????????????????????????????????
? ???????? ?????? ???????????? ??????????? ??????????? ????????? ??????? ???? ? ????????;
? ?????????? ????? ????? ? ????? ????????? ????? ??????
????????? ????? ????????;
? ???????, ?. ?. ?????? ? ??????? ?????? ???????? ??????
???????? ? ???? ??????????? ???? ??? ????????? ???????? (???,
19
??? ????? x1x2?3x1 ???????? ?????? ????????? ??????????? ???
????????? ???????? {?1x2, ?1?2?3};
???????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????
?????????? ????? ????????? ???????? ?????, ?.????????????
???????????
?. ?????????? ??????????? ?????? ?????????? ????????? ??????? ???????? ????? ? ??????? ?? ?? ????? ????????? ??????? ?????????
?????.
???????? ???????? ?? ????????????? ???? ???????? ????????????, ?????? ?????????? ??????????? ?????????, ??????? ????????? ???????? ????? ??????????? ???????? ? ????????? ??????????? ???? ????? ???????? «??????» ????????.
???, ???? ? i-? ?????? ????????? ????? ???????? ????? mi, ? ????????? ? ni, ??, ???????? ?? ???????? ????? ?????? ni «??????»
???????? a, ? ? ????????? ????? mi «??????» ???????? b, ?? ???????????? ??? ?????? ?????? ???? ??????????? ????????????.
???????? ??? ???????? ??? ???? ?????, ??????? ???????????
?????????? ????????.
??? ???????????????? ?????? ??????????? ????????? ???????? ? ?????????
x1x2x2x1x3aaaa
bbbbby1y4y1y3
x2x3aa
bby2y4
x2x1aa
bby3y1
x1x2x3x1aaa
bbbby3y2y2
?????? ? ??????????? ??????? ????? ???????? ?????????
???????? ????? ????????, ???? ????????? ?????????? ??? ?????????. ??? ??????? ?????? ??????? ???????????? ????? ????????? ???:
x1x2x2x1x3a
bby1y4y1y3
x2x3a
by2y4
x2x1a
by3y1
x1x2x3x1a
bby3y2y2
?? ??????????? ????????? ???????? ???? ????????? ????????
???? (???. 7).
???? ???????? ????????? ???????. ????? ????????? ????????? ???????? ???? a0. ??????? ?????????????????? ?????????? ?
???? x1 ???? x2. ????? ?????? ?? ???? ???? (??????? ????????)
????????? ??????? ? ????? ????????? (?????????????? a1 ? a2). ???
????? ?? ?????????, ??????? ??????? ??????? ??????????????????? ????? ???? x1, x2 ???? ?3. ?????? ???? ?????? ?????? ????
20
a1
x2 / ?
x2 /?
a6
x3 /y 3
a7
a3
x 1/ ?
a0
x2 /y1
x3 /y 2
a4
x1 /y 3
a5
a2
?/y 4
x1 /y 4
x1 /y 2
a8
a9
x 3 /y1
? /y2
? /y 3
а0
a 10
а0
а0
?/y 1
а0
???. 7. ???? ?????????-??????? ???????? ????
x1, ?? ?????? ????? ???? ?????? x2, ? ???? ?????? ?????? ???? x2,
?? ?????? ????? ???? ????? ???? ?1, ???? ?3. ?? ????????? a1 ??????? ???? ???????, ?????????? ??????? ???????? x2, ? ?? ????????? a2 ? ??? ??????? ? ???????????????? ????????? ?3 ? ?1.
????????? ?? ????? ???????????? ??????? ??????? ??? ???
???????????? ?????? ????? ????????? ????????, ? ?? ???? ?????????, ??????? ????????? ?? ???????????. ?? ???? ???????? ????????? ????????? ?????, ???????????? ?? ???? ???????? ????????,
?? ?????? ???????? ?? ???? ????????? ???????? ??????????? ??????????????? ???????? ?????. ????????, ??? ????????? ?????
??????? ???????? ????? ?????? ???????????? ??????? ???????? ?
????????? ????????? a0, ????? ?? ??? ????? ? ??????????? ?? ???
???? ?????????? ?????.
?? ????? ???????? ??????? ?????????-??????? (????. 26).
??????? 26
a(t?1)
a
x1
x2
x3
a0
?
a1/b
a2/b
?
a1
?
?
a3/b
?
a2
?
a5/y3
?
a4/y2
a3
?
?
a6/y1
a7/y3
a4
a0/y4
?
?
?
a5
a0/y1
?
?
?
a6
?
a8/y4
?
?
a7
?
a9/y2
?
?
a8
?
?
?
a10/y1
a9
a0/y2
?
?
?
a10
a0/y3
?
?
?
21
???????? ??????????? ??????? (????. 27).
??????? 27
2
2,3
Ч
Ч
?
3
Ч
Ч
Ч
4
?
?
?
?
5
?
?
?
?
Ч
6
Ч
?
Ч
?
?
?
7
Ч
?
Ч
?
?
?
Ч
8
?
?
Ч
Ч
?
?
?
?
9
?
?
?
?
Ч
Ч
?
?
?
10
?
?
?
?
Ч
Ч
?
?
?
Ч
0
1
2
3
4
5
6
7
8
9
1
??????? ?? ??????? ???? ????????????? ?????????:
(0, 4), (1, 2), (2, 4), (4, 6), (5, 6), (6, 8), (7, 8), (8, 9),
(0, 5), (1, 4), (2, 5), (4, 7), (5, 7), (6, 9), (7, 9), (8, 10).
(0, 8), (1, 5), (2, 9), (4, 8), (5, 8), (6, 10), (7, 10),
(0, 9), (1, 6), (2, 10),
(0, 10), (1, 7), (3, 4),
(1, 8), (3, 5),
(1, 9), (3, 6),
(1, 10), (3, 7),
(3, 9),
(3, 10),
???????? ??????, ???????
(0, 4, 8),
(1, 2, 4),
(2, 9),
(3, 4, 6),
(0, 5, 8),
(1, 2, 5),
(2, 10),
(3, 5, 6),
(0, 8, 9),
(1, 4, 6, 8),
(3, 7, 9),
(0, 8, 10), (1, 4, 7, 8),
(3, 7, 10).
(1, 5, 6, 8),
(1, 5, 7, 8),
(1, 6, 8, 9),
(1, 6, 8, 10),
(1, 7, 8, 9),
(1, 7, 8, 10),
22
??? ?????? ?????????? ?????? ?????? ????.??????????????????
?????????????????
28. ??????? ???????????? ???????? ???????? ?? ??? ???????
(0, 5, 8), (1, 4, 6, 8), (2, 9), (3, 7, 10).
??????? 28
?????????
?????
???????????????
0
(0, 4, 8)
1
(0, 5, 8)
1
(0, 8, 9)
1
1
(0, 8, 10)
1
1
1
2
3
4
5
6
7
1
8
1
(1, 2, 4)
1
1
(1, 2, 5)
1
1
(1.4, 7, 8)
1
1
(1, 4, 6, 8)
1
1
(1, 5, 6, 8)
1
1
(1, 5, 7, 8)
1
1
(1, 6, 8, 9)
1
1
1
(1, 6, 8, 10)
1
1
1
(1, 7, 8, 9)
1
1
1
(1, 7, 8, 10)
1
1
1
1
(2, 10)
1
10
1
1
(2, 9)
9
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
(3, 4, 6)
1
1
1
(3, 5, 6)
1
(3, 7, 9)
1
1
(3, 7, 10)
1
1
1
1
1
1
???????? ?????????, ??? ???????, ???????????? ?? ???? ?????,
? ?????? ??????? ????? ?? ??????? ???? ???? ???????, ?. ?. ?????????????? ??????? ???????.
23
??? ??????? ????????????? ? ??????? ???????????.
?????????????, ?? ??????????? ??????? ?????, ??? ??? ????
?????????, ???????? ? ????????? ??????, ???????????? ??????????, ??????? ??? ???????? ??????????? ?? ????????? ??????????? ?????????, ????????? ? ????. 3.
????????? ?????? ?????? ????? ?????????? (b0, b1, b2 ? b3 ??????????????), ???????? ??????? ?????????-??????? ?????????????? ???????????? ???????? (????. 29).
??????? 29
b(t?1)
a
x1
x2
x3
b0
b0/y1
b1/b
b2/b
b3/y1
b1
b0/y1
b1/y4
b3/b
b3/y1
b2
b0/y2
b0/y3
?
b1/y2
b3
b0/y3
b2/y2
b1/y1
b3/y3
??? ???? ????? ?????????, ??? ?????????? ??????????? ??????? ???????????? ?????????, ????????? ??? ???????? ? ????????????? ????????? (???????? ? ? a0 (????. 26?33), ??????????? ? ? b0 (????. 34?37)) ? ??????? ?? ?? ????? ??? ?????? ??????? ??????????????????.
??????? 30
??????? 31
????
x1
x2
x2
x1
x3
a
x2
x3
a
?????????
a1
a3
a6
a8
a10
a0
a2
a4
a0
?????
b
b
y1
y4
y1
y3
b
y2
y4
??????? 32
??????? 33
x2
x1
a
x1
x2
x3
x1
a
a2
a5
a0
a1
a3
a7
a9
a0
b
y3
y1
b
b
y3
y2
y2
??????? 34
24
??????? 35
x1
x2
x2
x1
x3
a
x2
x3
a
b1
b3
b1
b1
b3
b0
b2
b1
b0
b
b
y1
y4
y1
y3
b
y2
y4
??????? 36
??????? 37
x2
x1
a
x1
x2
x3
x1
a
b2
b0
b0
b1
b3
b3
b2
b0
b
y3
y1
b
b
y3
y2
y2
?????? ???????? ??????????????????? ??????????, ??? ???????? ???????????? ???? ?????.
?? ???? ????????????? ???? ???????????? ??????? ????????.
???? ???????? ????, ??????????? ???????? ????????, ??????????? ? ????????? ??????????? ????, ??????????? ?? ???. 8.
???? ????????? ???????? ???? ???????? ?????????? ????? ????????? ???????? ????. ?????? ??????? ??????? ? ???, ??? ???????? ??????? ???????????? ? ???????, ?????????? ??? ?????????, ??? ??? ???????? ?????? ???????? ???? ???????????? ?????? ?????????? ? ?? ??????? ?? ???????? ???????.
?????? ??????? ? ? ????? ????????? ?????????. ???, ???????
???? ????? ???? ????????? ?????????, ? ??????? ???? ??? ??????? ????????? ? ??????, ? ??????, a0? , a0?? , a0??? ? a0IV , ??? ???
????????? ????? ??????? ???????? ????? ?????? ?????????? ??????? ? ????????? ?????????, ?? ??? ???? ?????? ?????????????? ????????? ???????? ???????. ????? ????????? ?????????
?
a0?
y3
a ??0
y4
x1
x2
x1
x1
a1
?
x2
a3
?
x1
?
a???
0
y1
x2 x2
x2
x2
aIV
0
y2
x3
a2
?
?
a6
y1
x1
a8
y4
a7
y3
x1
a9
y2
x3
a10
y1
x3
a4
y2
x1
a5
y3
???. 8. ???? ????????? ???????? ????
25
???????? ???? ???????????? ?????? ????????? ????, ????????
????????????? ???????? ?????, ????????????? ? ?????????.
???????? ?? ????? (??. ???. 8) ?????????? ??????? ???????????????? (????. 38).
??????? 38
y(t?1)
a(t?1)
a
x1
x1
x1
y3
a0?
?
a1
a2
?
y4
a0??
?
a1
a2
?
y1
a0???
?
a1
a2
?
y2
a0IV
?
a1
a2
?
b
a1
?
?
a3
?
b
a2
?
a5
?
a4
b
a3
?
?
a6
a7
y2
a4
a0???
?
?
?
y3
a5
a0IV
?
?
?
y1
a6
?
a8
?
?
y3
a7
?
a9
?
?
y4
a8
?
?
?
a10
y2
a9
a0??
?
?
?
y1
a10
a0?
?
?
?
??? ?????????? ?????????? ?????? ?????? ??????????? ??????? (????. 39).
??????? ?? ??????? ???? ????????????? ?????????:
(0I, 5) (0II, 8), (0III, 10), (0IV, 4), (0IV, 9), (1, 2), (5, 7), (6, 10).
??? ?????? ?????????? ?????? ?????? ??????? (????. 40).
26
??????? 39
a0??
Ч
a0???
Ч
Ч
a0IV
Ч
Ч
Ч
a1
Ч
Ч
Ч
Ч
a2
Ч
Ч
Ч
Ч
a3
Ч
Ч
Ч
Ч
a4
Ч
Ч
Ч
?
Ч
Ч
Ч
a5
?
Ч
Ч
Ч
Ч
Ч
Ч
Ч
a6
Ч
Ч
1, 8
Ч
Ч
Ч
Ч
Ч
Ч
Ч
a7
1, 9
Ч
Ч
Ч
Ч
Ч
Ч
Ч
Ч
?
Ч
a8
Ч
?
Ч
Ч
Ч
Ч
Ч
Ч
Ч
Ч
Ч
Ч
Ч
Ч
Ч
a9
Ч
Ч
Ч
?
?
3, 6 4, 7
Ч
Ч
Ч
Ч
Ч
a0? ,
a0???
Ч
a10
Ч
Ч
?
Ч
Ч
Ч
Ч
Ч
Ч
?
Ч
Ч
Ч
a0?
a0??
a0???
a0IV
a1
a2
a3
a4
a5
a6
a7
a8
a9
?? ????. 40 ?????, ??? ??? ???? ????????? (0I, 5), (0II, 8) (0III, 10),
(0IV, 9), (1, 2), (5, 7) ? (6, 10) ??????????? ?????? ?????
? ??????????? ????????, ??? ??? ? ???????? 0I, 0II, 0III, 1, 2, 4,
6?9 ?????????? ?????? ?? ????? ???????.
??? ??????????? ??????? ??????? ?????????? ?????? ????????? 3 (??? ????? ?????? ???????? ? ????????? ?????).
????????? ? ??????????? ???????? ?? ????? ?? ???????????
??????? ??? ?????? ???????????????, ??????????? ???????? ??
??????????? ?? ???? ?????? ??????????? ?? ????????? (??? ??????? ??????????? ?????????????).
(0IV, 4),
27
??????? 40
????? ???????????????
0I
(0I, 5)
(0II, 8)
?????????
0II
0III
0IV
1
2
3
4
1
5
6
7
8
9
10
1
1
(0III, 10)
1
1
1
(0IV, 4)
1
(0IV, 9)
1
(1, 2)
1
1
1
1
(5, 7)
1
(6, 10)
1
1
1
????????? ?????????? ?????? ?????? ???????????:
(0I, 5) ? b0? , (0IV, 4) ? b0IV ,
(0III, 8) ? b0?? , (0IV, 9) ? b1,
(0III, 10) ? b0??? , (1, 2) ? b2,
(5, 7) ? b3, (3) ? b5,
(6, 10) ? b4.
???????? ?????????? ??????? ????????? ?????????????? ???????????? ???????? (????. 41).
??????? 41
28
y(t?1)
b(t?1)
a
x1
x2
x3
y3
b0?
b0IV
b2
b2
?
y4
b0??
?
b2
b2
b4
y1
b0???
b0?
b2
b2
?
y2
b0IV
b0???
b2
b2
?
y2
b1
b0??
b2
b2
?
b
b2
?
b3
b5
?
y3
b2
b1
b1
?
?
y1
b4
b0?
b0??
?
?
b
b5
?
?
b4
b3
????? ?? ???? ????????? ? ???????????? ???????? ??? ??????
???????? ??????? ??????????????????, ????????, ??? ??? ???????? ?????????????? ?? ? ?????????? ???????? ??????????????????, ?. ?. ???????? ??????????????.
1.5. ??????????? ?????? ????????? ????????
???????, ?????????? ?? ????? ???????????? ???????, ???????? ?????????????? ??????? ?????????????? ??????????, ???
?????????? ??????? ?? ??????????? ?? ?????????? ??????????
???????, ???????? ???????? ? ????????? ????????.
????????? ?????? ??????? ???????? ???? ???????????? ??????? ????????. ? ?????????? ?????????? ????? ????? ?????? ????
???????? ??????????? ????? ???????? ? ???? ?????????? ???????????? ?????????, ????????????? ? ??????? ????????? ????????? ????? ?????.
?????? ???????????? ???????????? ????? ???????????? ??????? ?????????, ??? ??????? ??????? ??????????? ? ???? ????
????????????????? ??????: ????? ?????? ? ??????????? ?????.
???? ?????? ???????????? ????? ????? ????????? ?????? (???????????? ?????????), ?????????? ???? ???????? ?????????????? ?????? ?? ???????????? ????? ?????? ? ??????? (???. 9).
Y
...
ЭП
ЭП
ЭП
ЭП
...
Логический блок
X
ЭП
?
Блок памяти
???. 9. ????-????? ????????, ???????????? ???????????? ???????:
?? ? ??????? ?????? (???????????? ???????); j ? ???????
??????????? ????????? ??????
29
? ???????? ???????????? ????????? ?????? ???????? ??????
???????? ???? (?????????? ?? ????, ???????? ??? ?????????? ? ???? ???????? ???? ??? ????).
????? ?????? ???? ???????????? ????????? ???????????? ??
?????. ???, ???? ????? ????????? ???????????? ????????? ?????
?, ?? ????? ???? ?????????
H =] log ? h [,
??? ]q[ ? ?????????? ?????, ??????? ??? ?????? q; h ? ????? ????????? ?????????????? ????????.
??????? ????????? ???????????? ???????? ???????? ? ???????????? ???????????????????????????????????????????????????
???????????????????????????????????????????????
? ????? ????????? ???????????? ?????????. ??????? ???????? ?? ?????? ????????? ? ?????? ??????????? ? ????????? ????????? ???????????? ?????????.
??????? ??????????? ????????? ?????? ?????????????? ?????????? ?????? ? ??????????? ?? ????????? ????????? ?????? ?
?????????? ?????? ??????? ? ??????? ????????.
????? ??????? ? ???????? ??? ???????? ???????? ? ??????????? ?? ????? ???? ?? ??????? ? ???????? ????????? ? ?????
????????? ????????, ??????? ????? ???????? ?? ?????? ????.
L?=?]loghn[,
N?=?]lognm[,
??? L ? N ? ?????????????? ????? ??????? ? ???????? ???; n ?
? ? ????? ???? ???????? ? ????????? ?????????; h ? n ? ?????
????????? ????????, ???????????? ?? ??????? ? ???????? ????? ??????????????.
?????? ???????????? ???????? ??????????? ???????, ?. ?.
h?=?n?=?2 (?? ?????? ???? ?????????? ???? ????, ???? ???????).
? ???????? ???????????? ????????? ???? ????? ???????????? ???????? ? ????? ??????????? ???????????, ?. ?. ??=?2. ?????????? ?????????? ????? ????? ???????????? ????????? ????? ??????? ? ??????????? ??????? (??? RS), ??????? ?? ???????
?????? (??? T), ??????? ???????? ?? ???? (??? D).
??????? ? ??????????? ??????? ????? ???? ?????????? ??
???? ????????? ???? (???. 10) ???? ?????? (???. 11).
??????? ????? ??? ?????, ?? ?????? ?? ??????? ????? ??????
??????? ??? ????. ????? ???????, ??? ????? Q ???????? ????????,
?. ?. ?????? ?? ???? ?????? ????????? ? ?????????? ????????.
???????????? ??????? ????????? ?????????, ????????????
?? ???. 10 ? 11, ????????? ? ????. 42 ? 43.
30
Q
Q
&
&
s
1
r
1
1
s
???. 10. ??????? ? ???????????
??????? ?? ????????? ???????
Q Q
Q
s
r
1
r
???. 11. ??????? ? ???????????
??????? ?? ????????? ?????
??????? 42
Q(t?1)
0
1
s, r
00
01
10
11
?
?
0
0
1
1
0
1
Q
??????? 43
Q(t?1)
0
1
s, r
00
01
10
11
0
1
0
0
1
1
?
?
??? ????????, ???????????? ?? ????????? ????, ??????? ?????????? 00 ???????? ???????????, ??? ??? ??? ?? ?????? ???????
??????????????? ? ?????? (????????????) ?????????. ??? ????????, ???????????? ?? ????????? ??????, ??????? ??????????
11 ???????? ???????????.
??? ?????????? ??????? ??????????? ?????????? ?????, ????? ??????? ??????? ?????? ?? ???? ????????, ????? ??????????
??? ? ????????? ?????????. ?? ????.????????????????????????????
???????????????????????????
42 ? 43 ????? ???????? ??????? s ? r, ??????????? ??????? ?? ?????? ????????? ? ??????.
???, ??? ????????, ???????????? ?? ????????? ????, ????????
????? ????????????
s
?
1
0
1
r
1
0
1
?
Q(t?1) ? Q(t)
0 ? 0
0 ? 1
1 ? 0
1 ? 1
??????? ????????, ??? ??????????????? ?????? ????? ????
???????, ???? ????.
??? ????????, ???????????? ?? ????????? ??????, ????????
s
0
1
0
?
r
?
0
1
0
Q(t?1) ? Q(t)
0 ? 0
0 ? 1
1 ? 0
1 ? 1
31
??????? ?? ??????? ?????? (???. 12) ????? ???? ???? ? ????
?????. ?????????? ??? ????? ???? ????????, ??????? ?? ??????????? ????????????? ??? ??????? ?????????-??????? (????. 44).
??????? 44
Q
T
D
Q
???. 12. ???????
?? ??????? ??????
Q(t?1)
T
Q
0
1
0
0
1
1
1
0
??? ????? ?? ???????, ??? ????????? ????????? ???????? ??
??????? ?????? ?????????? ?????? ?????? ??=?1. ???? ??????? ??
?????? ?????? ?????? ?????????, ?? ??????? ?????? ??=?0. ??????? ????????? ? ???? ?????:
Q
Q
D
Q
???. 13. ???????
???????? ?? ????
T
Q(t?1) ? Q(t)
0
0 ? 0
1
0 ? 1
1
1 ? 0
0
1 ? 1
??????? ???????? ?? ???? (???. 13), ??? ? ??????? ?? ???????
??????, ????? ???? ???? ? ???? ?????. ?? ???????????? ???????? ??????? ?? ???? ????. ???????? ???????? ???????? ???????????? ? ????. 45.
??????? 45
D
Q(t?1)
a(t?1)
0
1
0
0
0
1
1
1
0
1
??? ???????? ???????? ?? ???? ??????? ?????? D, ??????????? ??????? ? ???????? ????????? (0 ??? 1), ?????? ????????? ?
???? ??????????, ??????????? ?? ?????:
32
D
Q(t?1) ? Q(t)
0
0 ? 0
1
0 ? 1
0
1 ? 0
1
1 ? 1
??????? ?????????-??????? ???????????? ????????? ?????????? ??? ?????????? ??????? ??????????? ?????????????? ????????. ??? ????? ?????? ?????????????? ??????? ????????????????, ? ??????? ?????????, ??????? ? ???????? ??????? ???????? ???????????????? ??????. ??????? ??????????? ??????? ???????? ?????? ??????????? ?????????????? ??????, ??????????? ??????? ???????? ????????? ???????????? ????????? ?
??????? ?? ??????? ????? ?????????????? ????????.
???????? ?????? ????? ??????????? ?????????????? ??????,
??????????? ??????? ???????? ????????? ???????????? ????????? ? ??????? ??????? ??? ??? ?????? ???? ???? ?????? ????????? ???????????? ????????? ??? ?????? ????.
???????? ??????????? ?????? ???????? ????, ??????? ?????????-??????? ???????? ???? ????????? ? ????. 1.4 (??. ????. 29).
??????? ????? ?????? ?????????, ?????????????, ??? ??? ?????????? ????????? H?=?]log24[?=?2 ???????? ???????? ??????.
?????????? ????????? ???????? ????????? ???????:
Q1 Q0
b0 ? 0 0,
b1 ? 0 1,
b2 ? 1 0,
b3 ? 1 1.
??????? ??????? ???????? ??????? ?? ??????? ????, ???????? ? ?? ????, ?????????????, ????? ??????? ? ???????? ???
????? ??????????????
L?=?]log24[?=?2,
N?=?]log25[?=?3.
?????????? ??????? ? ???????? ??????? ????????:
t1 t0
?2 ?1 ?0
a ? 0 0,
b ? 0 0 0,
x1 ? 0 1,
y1 ? 0 0 1,
x2 ? 1 0,
y2 ? 0 1 0,
x3 ? 1 1;
y3 ? 0 1 1,
y4 ? 1 0 0.
????? ?2, ?1 ? ?0 ? ???????? ??????? ?? ???????? ????? ????????.
???????? ???????????? ??????? ?????????-??????? (????. 46),
??? ???? ????????? ???? ????????? ??????? ? ???????? ????????
? ????. 29.
33
? ????. 46 t1 ? t0 ? ???????? ??????? ?? ??????? ????? ????????, Q1 ? Q0 ? ???????? ??????? ???????????? ?????????.
??????? 46
Q1(t?1)
Q0(t?1)
0
0
1
1
0
1
0
1
t1
t0
t1
t0
t1
t0
t1
t0
0
0
0
1
1
0
1
1
00/001
00/001
00/010
00/011
01/000
01/100
00/011
10/010
10/000
11/000
?
01/001
11/001
11/001
11/010
11/011
??????? ? ???????? ????????? ?????? ???????? ? ??????????? ???????, ???????????? ?? ????????? ????. ?????????
??????? ??????????? ??? ??????? ???????? (s1, r1, s0, r0), ? ????? ?????????? ???????, ???????????? ???????? ??????? ?? ???????? ????? ????????.
??????? ??????????? (s1, r1, s0, r0) ??????? ?? ??????? ??????????: Q1, Q0, t1 ? t0. ?????????? ???????????? ???????
?????????-???????, ???????? ????? ??? ?????? ????????? ?????
??? ??????? ??????????? (????. 47?50).
??????? 48
??????? 47
t1
t1
t0
t0
Q1
?
1
1
?
1
0
0
1
0
?
1
0
1
?
?
1
0
0
1
1
1
1
?
?
1
0
0
r1
1
?
1
Q0
1
s1
Q1
?
Q0
??????? 49
??????? 50
t1
t1
t0
Q1
Q0
34
t0
?
?
1
1
?
?
1
?
1
?
0
1
0
1
1
0
1
?
?
1
0
1
1
s0
1
1
?
?
r0
?
1
Q1
Q0
1
0
0
?? ????????? 00 ??? ???????? ??????? 00 ??????? ?????????
? ????????? 00. ?????????????, ?? ????? ????? ????????? ???????
?????? ?????????? ???????? ? 1. ? ????? ??????? ??????? ????
???????? ????? ????????????? ??????????????? ???????.
?? ????????? 00 ??? ???????? ??????? 01 ??????? ?????????
? ????????? 01, ?. ?. ??????? ??????? ?????? ????????? ? 0 ?? 1,
? ??????? ?? ??????: 0?0. ?? ????? ???????? ???????? (s1, r1)
??????? ?????? ?????????? ???????? ? 1, ? ?? ????? ????????
(s0, r0)?????????????????????????????????????????????????????
????????????????????????????????????????????????????
? ?????????? 10, ?????? ???????? ??????????? ? ??????, ??????????????? Q1Q0t1t0. ?????????? ??????????? ????????? ?????? ???????? ?????.
?? ??????????? ???????? ?????????? ??????????? ????????? ? ????????????? ?????????? ?????:
s1 = Q1 Ъ ?0 ?1 Ъ Q0 ?0 ,
s0 = ?1 Ъ ?0 Q1,
r1 = ?1 Ъ Q1,
r0 = ?0 Ъ ?1Q1.
??????? 52
??????? 51
t1
t1
t0
t0
Q1
Q0
0
0
0
0
0
0
0
0
0
?
0
0
1
?
1
1
0
0
0
0
1
0
1
1
0
0
0
V2
1
0
0
0
V1
0
Q1
Q0
??????? 53
t1
t0
Q1
Q0
1
0
1
0
0
?
0
0
1
1
1
0
1
0
1
V0
0
?????????? ???????? ????????? ????? ??? ???????? ???????? ???????? (????. 51?53):
V2 = Q1Q0 ?1?0 ,
35
V1 = ?0 Q1 Ъ ?1Q1,
V0 = ?0 ?1 Q1 Ъ ?0 Q0 Q1 Ъ ?0 ?1Q0 Ъ ?0 ?1 Q1.
1.6. ??????????? ???????????? ????????? ????????
? ?????????? ??????????? ??????????
?? ????? ???????????? ??????? ?????????? ?????????? ???????????? ????????? ???????? ? ????????? ??????????? ??????????
(?????) ????????? ??????.
???? ??? ?????-???? ??????? ??????? xi ??????? ?? ?????????
?s ????????? ? ????????? ?k, ? ?? ????????? ?k ? ? ????????? ?n, ??
????????? ?k ????? ????????? ????????????. ???, ???? ???????
?????? xi ???????? ?????????? ?????, ?? ??????? ?? ????????? ?s
????? ???????? ? ????????? ?n, ?? ???????????? ? ????????? ak.
??????????? ??????????, ??? ?????, ? ????????? ??????????
?????? ????????? ???????????? ????????? ??????. ???, ???? ??????? ??? ?????-?? ??????? ??????? ?? ?????????, ??????????????? ??????? 101, ????????? ? ????????? 011 ? ???????? ???????????? ???????? ???????? ????, ??? ????????, ??????? ?????????
??????? ? ????????????? ????????? 001, ? ????? ??? ? ????????
011. ???? ??? ???? ??????? ??????? ??????? ?? ????????? 001 ?????????, ????????, ? ????????? 000, ?? ??????? ????? ????? ??
??????? ???? ? ?? ????????? 101 ??????? ? ????????? 000.
??? ??????????? ???????????? ????????? ????????? ? ?????????? ??????????? ?????????? ??????? ????? ???? ??????????
?? ??????????? ????????.
? ???? ?????? ? ????? ???????? ????? ?????? ????????? ???????????????? ????????? (???). ???????????? ????????? ?????? ? ????? ????????? «???????????» ?????????? ????? ??????????. ???????????? ????????????????? ???????? ????????
???, ????? ???????? ?????? ????????????? ? ????? ?????????, ?
????? ??????? ??????????? ?? ?????? ??????? ?? ???? ?????????
??????. ??? ??????????? ?????????? ????????????-??????????
?????????? ?? ?????? ????? ????????? ?????? (???. 14).
??????? ?????????? ???????????????? ????????? ????????
? ????? ????????, ????? ?? ?????????? ??????? ????? ?????????? ? ???????? ??????????? ??? ?????????? ????????. ? ???????????? ???????????? ????????? ??? ????????????? ?????
??????? ??????????. ??? ?????????? ???????? ?? ??????????36
Y
...
X
Логический блок
ЭП ЭП
ЭП
Блок памяти
&
&
&
ГСИ
???. 14. ????-????? ??????????? ????????
??? ????????? ?????????? ??????? ????????? ??????? ??????????? ? ??????? ???????????? ?????? ? ????? ????????? ?????
?????????? ????? ???????? ??????????????? ?????? (????? ??????? ??????) (???. 15).
Y
...
X
T
Логический блок
...
Блок основной
памяти
...
Блок конъюнкций
T
...
Блок вспомогательной
памяти
...
???. 15. ?????????? ????? ? ???????? ? ??????? ???????? ??????
37
T
1
0
t
T
1
0
t
???. 16. ????????? ????????? ??????????? ?????????????
???????? T ? T
?? ????????? ?????????? (???. 16) ??? ??=?1 ? ??????????
????? ?? ????????? ????????? ???????? ?????? ? ???????? ??????? X ?????????????? ??????? ???????????, ??????? ??????????? ???????? ??????????????? ?????? ? ????? ?????????.
????? ? ?????????? ?????? ???????, ????? ????????? ?? ??????????????? ?????? ????? ???? ?????????? ?????????????? ?
????????. ????????? ????????? ??????? ??????????? ? ???????????? ???????? ?????? ? ????? ????????? ????????? ?? ???????, ??????????? ?????????? ????????? ????????? ?????????.
?????????? ??????? ?????????? ???????? ????????? ??????????? ?????????? ? ???????????? ???????????? ????????? ????????.
???????? ??????????? ?????????, ??????????? ?? ??????????? ????????, ???????? ?? ???????????? ?????? ??????????????.
??? ??????????? ???, ??? ?????? ????????? ????????????????? ??????? ?????????? ? ???????, ??????????? ????????? ??????? ?????????? ?????????? ?????????.
??????????? ?????????? ? ????????? ????? ????????? ? ???
???????? ?????????????. ????? ???????? ?????????? ????????????. ??? ????? ???????????? ??????????? ??????????? ????????? ?????????. ???, ???? ??? ?????-???? ????????????? ??????? ??????? ?i ??? ???????? ??????? ? ?????????? ?????????
xi
?????? ?????? ???????? ?????? (????????, 0110 ѕѕ
®1110 ????
x
i
0110 ѕѕ
® 0100 ? ?. ?.), ?? ??? ???? ??????? ??????? ????? ? ???????? ?? ?????????. ???? ??? ??????? ??????????? ??? ????
??????? ????????, ?? ? ????? ??????????? ???????? ????? ?????????? ?? ?????. ?????? ?????? ??????????? ????????? ???????? ?????????? ???????? ????????????.
?????? ???????? ????? ????????? ? ???????????? ??? ?????????? ????????? (???.??????????????????????????????????????
?????????????????????????????????????
17). ????????, ??? ?????????? ?????????? ??????? ? ????????????? ??????? ????????, ?. ?. ??????
38
?)
a1
x1 ?x2
a3
?)
a1
x1 ?x2
x2
x1 ?x2
x1
x1
a4
a2
x1
x1
a3
a2
x1
a4
?)
x2
a1
x2
a3
a2
x2
x2
a4
???. 17. ????????? ????? ???????? ??? ??????????????? ???????????.
???? ????????? ????????: ? ? ?????????; ? ? ??????? ???????????;
? ? ??????? ???????????
??????? ??????? ????????? ?????? ?????????? ??????? ? ????????????? ??????? ????????.
????? ? ??????????? ???????? ????? ?????????, ???? ?? ????????? ??? ???? ??????????????? ??? ?????????? ?????????.
??? ????? (???. 17, ?) ?????? ??????????? ????????? ?????????? ?????????? ??????, ????????:
a1?000, ?2?001, ?3?100, ?4?101.
??? ???????? ??? ????????? ??????? ?1 ??????? ?????????
?????? ?????? ???????? ??????. ?????? ????? ?????? ??????????? ????????? ??????????? ???????? (???. 17, ?) ??????? ??? ???????? ?? ????????? a2 ? ????????? ?3 ????????? ????????? ????
????????? ??????. ??????? 001?100 ????? ????????? ????? ?????????, ?????????????? ??????????? 101, ?. ?. ?????? «??????»
????????? ?? ???????? a2??3. ?????? ??? 101 ??? ???????????
???? ??? ????????? a4. ??????? ?? a2 ? ?3 ????? ????????? ????????? ???????: 001?011?111?110?100, ?.????????????????????
???????????????????
?. ?????? ??? «??????» ?????????, ???????????? ?????????.
???????? «??????» ????????? ????? ???????? ? ??????????
????? ????????? ?????? ? ?????????? ?????????????? ????????. ??? ??????? ????????? ? ??????? ???????? ????? ???????
???????? ??????????? ????????? ? ?????????? ????? «??????»
?????????. ??? ???? ?????????? ????? ? ????, ??? ??? ?????????
????? ? ??????????????? ?????????? ????????? ?????? ????????? ?????? ????? ?????????.
39
???????? ? ?????? ??????? ??????????? ????????? ??????????? ????????? ??? ?????????? ?????. ??? ???? ???? ????????
????? ??????? ??????????? ???????? ? ??????????: ???? n ?
????? ????????? ???? ???????? ????????, ?? ??????? ???????????? ?? n ?????????? ????????? ? ???????????????? ?????????????? ???????? ?????????. ????? ??? ??????? ???????????
???????? ??????????????? ??? ???? ?????????, ????????:
x
x
i
i
a1 ѕѕ
® a2 , a3 ѕѕ
® a4 .
????? ?????????, ????? ?????? ???????? ?1??2 ??? a3??4 ??????????? ?????? ??????? ?1??4 ???? ?3??2. ??? ??????????
?????? ????????? ? ???? (a1, ?2) ??????????? ???????? ??????
????????, ????????, Qj?=?0, ????? ? ???? (?3, a4) ??????????? ??????????????? ???????? ????? ?? ???????? Qj?=?1. ????? ?????????
??????????? ??? ???? ??? ????????? ??????? ??????????? ????????, ???????????????? ?????????. ???????, ??? ???? ?????????
????
?1??2, ?1??2,
?3??3, ?2??3
? ?????? ??????????? ?? ??????, ??? ??? ??? ?????? ?? ??? ????? ?????? ?? ?????????, ? ??? ?????? ???? ????? ?? ????????
????????????, ?.??????????????????????????????????????????????
?????????????????????????????????????????????
?. ?? ???????? ? ?????? ?????????. ???? ? ?????????? ?????????? ????????? ????????? ???? ????????? ????????? ?????????, ?? ????????? ?????????????? ????????? ?????? ?????????? ?? ??????? ???????.
40
2. ?????? ???????????????? ?????????
????????? ?????? ???????????????? ????????? ??????? ?
??????????? ????????? ?????????? ????????????? ? ?????????????????? ??? ? ????????? ?????????????? ????????? ?????
???? ?????? ? ???? ??????????? ??? ????????? ???? ?????????? [6].
?????????? ????????? ??????? ???????? ?????????? ? ??????????? ??????? ?????????? ???????? ?????????, ?? ???????????.
2.1. ????-????? ??????????
????-????? ????????? ? ??????????????? ??????? ????, ?????????? ??????? ??????? ?????, ? ?????????, ????????,
??????????? ? ???????? (???. 18).
Начало
Конец
у
x
Да
Нет
???. 18. ???? ?????? ????-????? ?????????
????????? ??????? ????? ???? ????? ? ?? ?????? ?????, ???????? ? ???? ???? ? ?? ?????? ??????, ??????????? ? ???? ????
? ???? ?????, ???????? ? ???? ???? ? ??? ??????, ??????????
????????? «??» ? «???».
????-????? ????????? ????????????? ????????? ????????:
1) ???????? ???????? ????? ??????, ?????? ?? ??????? ??????????? ?????? ?? ????????????? ?????;
2) ????? ????? ???? ????????? ? ???? ???????? ???????;
3) ????? ? ?????? ?????? ??????????? ???? ? ?????? ? ??????? ???, ???????????? ?????? ?? ?????? ?? ?????;
4) ?????? ????? ???????? ????? ? ????? ??????;
5) ????? ???? ???????? ?? ??????? ???? ? ????? ???????;
6) ??? ????? ??????? ????? ?????????? ?? ??????? ????
???? ???? ?? ???? ??????? ? ????????;
7) ???? ?? ??????? ???????? ??????? ????? ??????????? ? ??
??????;
8) ? ?????? ?? ???????? ?????? ???????????? ???? ?? ????????? ????????? ??=?{?1, ..., xl}, ??????????? ?????????? ?????????? ???????;
41
Начало
a1
0
1
x1
у2
у1
a2
x2
1
x3
1
у5
0
у3
a3
у4
a1
Конец
???. 19. ?????? ????-????? ?????????
9) ? ?????? ??????????? ??????? ???????????? ????????????
???????????? Y? ????????? Y?=?{y1,..., yl}, ??????????? ?????????? ?????????????.
? ???????? ??????? ?????????? ????-????? ?????????, ?????????????? ?? ???. 19.
????????? ??=?{x1, x2, ?3}, ? ????????? Y?=?{y1, ?2, ?3, y4, y5}.
???????????????? ???????, ????????? ???????? ???????? ??????????, ?????? ????? ??? ??????? ? ???? ???????? ???????.
?????????????? ?????? ???????? ?????????? p, ??? ???????
?????? ??????????? ?????. ????????? ??????? ????? ????????????? ????????? ????????? ????????, ??? ??????? ?? ???? ???????? ??????? ?????????????? ??????? ??????. ????? ????????? ?? ????????? ??????? ? ??????????? ?????????? ??? ?????,
??????? ???????? ??????? ?? ??????? «??» (1), ???? ??????????
??????? ???????????, ? ?? ??????? «???» (0), ???? ??? ?? ???????????.
???? ? ????????? ????????? ?? ???? ?1 ???????? ??????, ?????? ???????, ?? ?????????? ?? ??????? ?? ?????? ?2 ? x3 ??? ?????? ????????????????? ???????? ??????? ???????? ? ????? ?????????, ?? ?????? ???????? ?????? ???????? ??????, ??????
???????, ? ?? ????????? ? ??????, ?????? ????. ?????????
??????? ????????, ??????????????? ????? ??????, ?????????
1Ч x?2 Ч x? 3 , ??? x? i ? ???????????? ???????? xi. ??? ???????????
?????????? ????????? ???????? ??????? ??????? x?1 Ч1Ч 0 ???
x? 0 Ч 0 Ч x? 3 ??????? ????????? ???????? ???????? ?? ??????? ???
????????? ???????? ?????? ?????????????? ? ??????? ???????? ?
????? ?????????, ? ?. ?.
42
??????????? ?? ???? ?????????.
уr
1. ????? ??????????? ??????? ?m
??????? ??????????? ??????? yl. ? ????
?????? ?????? yl ???????? ????? ?????0
xk
?? ????????????????? ???????? ?????????? ?? ????????? ??????.
1
2. ???? ????? ??????????? ??????? ????? ?????????? ???????? ???????
???. 20. ??????????
???????
? ?????????? ???????? ?k (???. 20), ??
???????? ??????? ?k?=?0 ?????????????
??????? ???????? ??????. ? ??????? ?????????? ???????? ??????? ????? ????????? ???????? ? ?????? ????????.
??? ??????? ????????????????? ???????? ?????? ???????????? ????? ?????????? ????-????? ????????? ? ?????????? ????????. ?????????????? ???????? ???????? ????-????? ????????? ?1,...,?h ?? ????????:
1) ???????? ?1 ?????????? ???? ???????, ????????? ?? ?????????, ? ???? ???????? ???????;
2) ???? ?????? ???????, ????????? ?? ???????????, ?????????? ???????? ai, ??? ???? ?????? ???????? ?????????????
?????? ???????;
3) ???? ???? ??????? ???????? ? ???????? ?????????? ??????????? ??????, ?? ?? ?????????? ???? ???? ???.
?????? ??????? ???? ???????? ?? ????-????? ?? ??????? ?? ?
??????? ?l ??? ???? ? ??????????? ??? ?????, ??????????? ?? ????? ??? ????? ???? ??????????? ???????:
???(??, ?l)?(??, ?l)al,
??? ?(??, ?l) ? ?????????? ??????????? ???????? ?????? ??
???? ????????, ?????? ? ?????? ????, ???? ???? ??????? ?? ??????? ?? ??????? «??» (1), ??? ? ?????????, ???? ???? ??????? ??
??????? «???» (0); ?(ym, yl) ? ?????????? ??????????? ???????.
????, ?????????? ??????????? ???????, ????????????? ? ?????? ??????? ????? ???? ???????.
????????? ????, ??????? ? ?? ?? ????? ???????:
???(??, ?m)?(??, ?m)am;
????, ?? ?????????? ???????? ??????:
???(??, ?l)?l,
? ????, ?? ?????????? ??????????? ???????:
?mx(?m, al)?l.
43
??? ????-????? ????????? (??. ???. 19) ?????? ??????? ?1, a2,
?3 ? ??????? ?????? ????????? ????? ????????:
{a1x1y2 a2 , a1 x1y1a2 , a2 x2 y3 a3 , a2 x2 x3 a3 ,
a2 x2 x3 y4 a1, a2 x2 x3 y5 a1, a3 y4 a1 }.
?? ??????? ????????? ????? ???????? ?????????? ??????????? ???????????? ? ???????????? ? ??????????????? ???????????? ? ?????????????? ????????.
???? ????????? ?????????????? ????? ?????????? ??????
??????????????, ?? ???????????? ???? ????, ?????????? ??????????? ???????. ????????????? ??????? ?? ????? ????????
?????????? ???? ?? ???????????. ????? ???????, ???????????
??????? ??????? ?? ???????? ???? amx(??, ?l)?l, ??? ??????? ??????????? ???????? ???????.
???? ????????? ?????????????? ??????? ????????????, ?? ??
??????? ????????? ?????????? ????, ??????????????? ? ????????? ???????. ????? ????? ????? ???????? ????????? ????????? ?????????????? ????? ????????.
????? ??????????? ????????? ????? ???????? ???????????????? ??????? ????? ???? ??????????? ? ??????????? ??????????? ??? ????????? ?????. ?????????? ???????? ?????? ?
???????????? ??????? ?? ????-????? ?????????. ?? ????????? ????????? ????????? ??????? ?1. ????????, ??? ????? ??????????? ???????? ??????? ????????, ???? ??????????????? ???????
?? ????-????? ??????? ????? ????????. ??????? ??????, ???????????? ???????, ???????? ?????? ?(??, ?l) ? ?????????? ??????????? ???????? ?????? ?? ???? ????????, ? ???????? ?????? ? ?????? ?(??, al) ? ??????????? ??????????? ??????? ??
???? ????????. ??? ????? ???????? ???? ??y(??, ?l)al ???? ???????? ??????? ????? ????????? ???????????????? ?????? p.
??? ????? ???????? ???? ???(??, ?l)?l ???????? ?????? ???????? ?????? ????.
? ?????????? ?????????????? ???????? ??????? ????, ??????? ??????? ?? ?????????, ??????? ???????? ????????????? ???
??????? ?????? ?? ????-????? ?????????. ???????? ???????,
????????????? ????-????? ????????? (??. ???. 19), ????? ??????????? ? ??????????? ????? (???. 21). ??????????? ?????? ???????? ???????????? ?? ??????????? ???????? (??. ????. 50 ? 51),
??????? ???????? ?? ?????? ????-????? ????????? ??? ????? ????????.
44
px1 / y1 Ъ px1 / y2
a2
01
px2 x3 / y4 Ъ px2 x3 / y5
a1
00
a3
10
p / y4
px2 / y3
???. 21. ???? ????????
????. 54 ???????????? ????? ?????? ??????????? ??????? ????????, ???????????? ?? ???. 21.
??????? 54
???
????????
????????? ?????????????????? ????- ???????
?? ?????
????
????????
???????
a1
a2
a3
00
01
10
??????
???????
???????????? ???????
???????? ???????????
a2
01
px1
y2
s2
a2
01
px1
y1
s2
a1
00
px2 x3
y4
r2
a1
00
px2 x3
y5
r2
a3
10
px2
y3
s1r2
a1
00
p
y4
r1
? ?????? ??????????? ??????? ??????????????? ????????????? ???? ???????? ?? ???? ?????????, ??????? ? ???????. ?????????, ?? ??????? ?????????????? ????????, ??????????? ? ?????? ???????, ???? ???? ????????? ????????? ?? ?????? ???????. ?
?????? ? ????????? ??????? ???????????? ????????? ?????????
? ?? ????. ????? ? ?????? ??????? ???????? ????????? ??????? ? ???????? ??????? ??? ???????????????? ????????. ? ??????? ??????? ??????? ????????????? ???????????? ??????? ???????????, ?????????????? ?? ??????????????? ?????????, ?. ?.
??????? ???????????, ?????????? ???????????? ?????????
??????.
???? ????? ????? ??????????? ??????? ????????? ????? ????????, ???? ?????????? ???? ? ??? ?? ???????? ??????, ?? ???
??????? ???? ? ??????? ????????? ????????? ???????.
45
? ???? ??????? ??????? ???????????? ???????? ???????????
???????? ????????, ??????? ?????????? ?? ?????? ??????? ???,
??? ? ??? ??????????????? ????????????? ??? ???????? ? ??????
?????????, ????? ?? ?????? ? ?. ?. (????. 55).
??????? 55
????????
???
????????????- ????????? ??? ???????
?????????
????
a2
01
a2
01
a3
10
a1
00
a1
00
?2
01
a1
??? ?????????
????????
00
a2
01
a3
10
??????
???????
????????
???????????? ???????
???????????
px2 x3
y4
r2
px2 x3
y5
r2
p
y4
r1
px1
y2
s2
px1
y1
s2
px2
y3
s1r2
?? ??????????? ???????? ???????????? ????????? ???????? ???????? ???????? ? ????????? ???????? ???????????:
y1 = Q1 Q2 px1, y2 = Q1 Q2 px1, y3 = Q1Q2 px2 ,
y4 = Q1Q2 px2 x3 Ъ Q1 Q2 p, y5 = Q1Q2 px2 x3 ,
s1 = Q1Q2 px2 , r1 = Q1 Q2 p,
s2 = Q1 Q2 px1 Ъ Q1 Q2 px1 = Q1 Q2 p,
r2 = Q1Q2 px2 x3 Ъ Q1Q2 px2 x3 Ъ Q1Q2 px2 = Q1Q2 p,
??? Q1 ? Q2 ? ???????? ??????? ??????? ? ??????? ????????? ?????? (? ?????? ??????? ???????????? ???????? ???? r ? s).
???????? ?????????? ??? ?????????, ??????? ????? ?????????? ? ????? ??????? ????:
y1 = A1 px1, y2 = A1 px1,
y3 = s1 = A2 px2 , r1 = A3 p,
s2 = A1 p, r2 = A2 p,
y4 = A2 px2 x3 Ъ r1, y5 = A2 px2 x3 ,
A1 = Q1 Q2, A2 = Q1Q2 , A3 = Q1 Q2 .
46
x1
x2
&
&
А2
x2 &
p
p
&
r1
T1
А3
p &
А1
p &
x3
s1
А2
p &
& А3
& А2
s2
r2
T2
& А1
y3
А1
x1 &
p
y2
А2
x1
p
y1
&
А2
x2 &
x3
p
1
А2
x2 &
x3
p
y4
y5
???. 22. ?????????????? ????? ????????
?? ?????????? ???????????? ?????????????? ????? ????????
(???. 22). ??????????? ?????????? ? ??????????? ?????????????? ???? ????????? ??????????? ? ????. 2.4.
2.2. ????????? ????? ?????????
????????? ????? ????????? ? ??? ????????????? ???????, ?????? ??????? ???????? ????????? y0, ?1, ?, yn, ? ??????? ? ????????? y1, y2, ..., ??, yk, ??? Y?=?{y0, yk, y1, ..., ??} ? ????????? ??????????
[6]. ?? ??????????? i-? ?????? ? j-?? ??????? ???????????? ???????
???????? aij, ??????????????? ?????????? ?????????? ???????,
?????????? ??????? ?? ????????? yi ? ????????? ?j?. ?????????????
?????? ????????, ??? ??????? ?? yi ? yj ???????????. ???? aij?=?1, ??
????? ????? ??????????? ??????? ?? ????????? yi ? yj?.
??? ???????? ?? ??????? ????????? ? ???? ????-????? ? ????????? ????? ????????? y0 ? yk ???????????? ????????? ? ??47
?????? ???????, ? aij ????????????? ?????????? ???????????
???????? ?????? ?? ???? ???????? ?? ????????? yi ? yj. ????????? ????? ?????????, ??????????????? ????-????? (??. ???. 19),
???????????? ? ????. 56.
??????? 56
y3
y4
y5
y1
x2
x2 x3
x2x3
y2
x2
x2 x3
x2x3
y0
y1
y2
x1
x1
y3
yk
1
y4
1
y5
1
??? ???????? ?? ????????? ????? ? ????-????? ????????? ??????????? ????????? ????????:
1. ?? ????????? ????? ???????????? ??????? ?????? ????????
yi ® ? ik yk Ъ ? il yl Ъ ... Ъ ? im ym = Ъ ? ij yj ,
j
i = 0,n.
????? ?????????? ???????? ? ???? ??? ?????????, ? ???????
??????? ???????? ?? yi. ?????? ????? ?????? ???????? ?????
??????????????? ??? ?????????? ???????, ? ??????? ????????? ?????? ? ??????? ??????? ??????.
2. ??????? ?????? ???????? ?????????? ? ????????? ?????,
??????? ?????????? ????????? ???????: ?p ? ????????? ?????,
xj A Ъ xj B ? ????????? ?????, ???? ?, ? ? ????????? ?????.
?????????? ????????? ? ??????? ???? ?????????? ?????? ?????? ?????? ???????? ?? ?????????? xi:
A = xi B Ъ xi C,
??? A, B, C ? ?????????? ???????.
???? ??????? ???????? ????? ??? yi??k?, ?? ?????????? ??????? ?? ?????????? ???????? ?????????? ????????? yi. ?????????? ? ????????? ????? ? ???? ?????? ???????????? ???????????
???????? ?????:
xk A = xk A Ъ xk [xk ] ,
48
?)
?)
уi
уl
уj
?)
уi
1
xk
0
уm
уi
A
1
xk
0
???. 23. ???? ????-????, ??????????????? ??????
????????? ?????? ?????? ????????
???????????, ??? ??? ????????? ??????? ?k ????? ????????????
? ??? ????????. ????? [?k] ??????????????? ??? ??????????????.
3. ?? ??????? ????????? ?????? ???????? ????-????? ?????????. ??? ???? ????????? ??????
yi ® yj , yi ® xk yl Ъ xk ym , yi ® xk A Ъ xk [xk ]
????????????? ?????, ?????????????? ?? ???. 23.
?????????? ?????? ?????????? ????-????? ?? ????????? ????? ?????????, ??????????????? ? ????. 57.
??????? 57
y1
y0
1
y1
x1 x2 x3 x4
y2
y3
y4
x1x2
x1 x2 x3
x1 x2 x3 x4
y2
y5
1
y3
y4
yk
1
x4 x5
x4 x5
x5
y5
1
?????????? ??????? ?????? ????????:
y0 ® y1,
y1 ® x1 x2x3 x4 y1 Ъ x1x2y2 Ъ x1 x2 x3y3 Ъ x1 x2x3x4 y4 ,
y2 ® y5,
y3 ® yk ,
y4 ® x4 x5y1 Ъ x4 x5y4 Ъ x5y5,
y5 ® yk .
49
Начало
у1
0
x1
1
x2
0
1
x3
0
1
x4
0
у2
1
у3
у5
у4
0
x5
1
Конец
???. 24. ????-????? ?????????, ??????????????? ????????? ?????
(??. ????. 57)
????????? ? ????????? ??????:
y0 ® y1,
y1 ® x1 (x2 (x3 (x4 y4 Ъ x4 y1 ) Ъ x3 y3 ) Ъ x2 y2 ) Ъ x1 [x1 ],
y2 ® y5 ,
y3 ® yk ,
y4 ® x5 y5 Ъ x5 (x4 y4 Ъ x4 y1 ),
y5 ® yk .
?????? ????-????? ????????? (???. 24).
2.3. ??????????? ????????? ???? ??????????
??? ?????????? ?????????? ????????? ????? ?????? ??????
??????????? ??????????, ??????????????? ??? ?????????? ????????? ???????? ?? ????????? ????????? Q ? ??????????????
????? ???????????? ? ??????????? ??????. ? ???? ?????? ???
????? ????????? ???????????? ?????????? ??????????? ?????
??????????? ?????????? ? ?????????? ???????.
???? ????????? ?????? ? ???? ????-????, ?? ??????? ???????
? ????????? ??????.
??????????? ????????? ???? ?????????? ?????????? ? ????????? ???????:
1) ?????? ????????? ????? Mq ???????? ? ???????????? ????????? ???
50
Mq ® Kq = eq1 , ..., eqn ,
eql О {0,1}, i = 1,n,
q = 1, Q, n =]log2 Q[;
2) ??????? ???? Kq ???????? ? ???????????? ??????????
e
e
e
1
2
n
Rq = rq q1 rq q2 ... rq qn ,
???
пмп rqi ,
e
rq qi = н
i
ппrq ,
по i
eqi = 1,
eqi = 0;
3) ???????? ???????????? ????????? ????? ?????????, ????????? ?????????? ? ?????????? ??????? ??????? ???? ??????????? ????????? ?????????? ? ?????????? ??????? ????????? ????????? ????;
4) ???? ? ??????? ?q ?? ??????????? ?????? ?i ? ??????? ?j ????? ? qij , ?? ? ???????????? ???????
Q
? ij = Ъ Rq ? qij .
q=1
???????????? ????-????? ????????? ????? ????????? ??????
???????, ??????? ?????? ?????? ?? ???????????. ????????? ??????????? ???????, ??-??????, ? ????????? ??????? ????????
aij ????? ????? ????????????? ??????? ????????? ?, ??-??????, ?
????????? ??????? ?????? ???????? ??? ?????????? ?????????
????. ??? ?????????? ??????????? ???????? ?????? ? ?????????? ??????????? ?? ?????? ????? ???????????? ????????? ????????? ?? ??????????? ???????? ??????? ?. ?. ???????? [6].
????????????? ??????? ????????? ?????????? ???????????
???????? ?????????? ?????????? ?? ?????????? ?????????? ????????? ? ???????? ???????
?i?=?{?e, ..., ??}, i?=?0, 1, ..., n, k,
??? ?i ? ????????? ?????????? ??????????, ???????? ???????
????? ?????????? ? ?????????? ?????????? ????????? yi. ???,
???? ???????? yi ??????????? ??? ???????? ?????????? xj?=?1 ?
?????? ?????????? ?? ??????? ?? yi, ?? ??? ????????? ???????? ??
???? ????????? ?? yi. ?????? ?? ???????? ??? ???? ????????? ??51
?????????. ? ??????? ???????? ?? yi ?????????? xj ????? ???????? ?????????? 1, ? xj ? ?????????? 0.
????????????? ??????? ? ????????? ????? ????????? ??????????? ????????? ???????:
1. ??? ??????? ??????? ?????, ????? ?????????, ???????????? ???????
fyi = Ъ ? ij .
j
2. ??????? fyi ?????????? ? ???????? ????
fyi = ? yi ? yi ,
??? ? yi ? ?????????? ?????????? xj, ?, xm; ? yi ? ????????????? ?????, ?? ????????? ?? xj, ?, xm.
3. ??????? ? yi ? ? yi ????????????? ? ??????? ?*yi ? ?*yi .
? ?????????? ?????? ?????????? «1» ???? ?????????? ??????????, ????????? ?? yi, ??????? ?*yi ????????????? ????????
?????????? ??????????, ?? ???????????? ?? ????????? ?? yi,
??????? ?*yi ?????????? ?????????? ???????? ?????????? ??????????, ?? ???????????? ?? ???? ?? ?????????. ????????,
???? ?*yi = x1, ?*yi = x2 Ъ x3 , ?? ?? ????????? ?? ?i ????????? ??????????? ???????? x1?=?1 ? ?????????? ???????? ?????????? ?2
? ?3, ? ??????? x2?=?1 ??? x3?=?0.
4. ??? ?????? ?????? ?i ????????? ????? ???????????? ?????? ?????????? ?j, ???????? ? ?*yi , ?? ???????????? ?????????? ? ????????? ??????? ???????? ? ??????? ?????????? ???????? ??????????, ?????????? ?*yi .
? ?????? ????????????? ??????? ???????????? ????????? ?????
?? ????????. ????????? ????????? ??????? ? ?????????: ????????
???????????? ????????? ?????? A11 = {y0 } ? ???????????? ???????? ?????? B11, ?????????? ? ???? ??? ??????????? ???????,
? ??????? ??????? ???? ?? y0. ??????????? ?????? ??????????
A11 ® A12 ? B11 ® B12 ? ??????? ?????????? ? A11 ??????, ????-
??? ???? ? B11, ? ? B11 ? ??????, ?????????? ???? ?? A12 . ?????????? ?????????? ?????? ??????????, ? ?. ?. ??????? ??????????? ????? ???????? ????? ????? ?????????? ???????????? ??????
A1n ® A1 ? B11 ® B1. ????? ?????????? ????????? ?? ?????? ?? y0
??????????? ???????, ?? ???????? ? A1, ? ??????????????? ??????
???? ???????????? A2 ® B2 , ?????????? ????????? ?? y0 ???????, ?? ???????? ? A1 ? A2, ? ???????????? ???? A3 ® B3 , ? ?. ?.
52
???????? ? ???????????? ?????? ???? Ai - Ai ???? ?i, ??????? ????????? ????????? ????? ?? ???????? ?1, ?2, ..., ?n.
????? ?? ????? ????????? ??????? ?? ????????????:
Ai ? Aj = Ж, Bi ? Bj = Ж, Pi ? Pj = Ж,
??? ? ? ????????? ???????? ??????. ??? ????????? ?????????
??????????? ?????? ?????? ????????? ? ?????????? ????-?????
??? ??????? ???????? ??????????.
??????????? ?????? ???????? ?????? ?????????? ? ??????????? ????????? ????. ? ?????? ?????? ????? ???????????? ????????? ????? ??? ?????? ?????? ? ???????????? ?????? ???????????, ?????????? ????????? ?*yi .
?????????? ?????? ??????????? ????????? ???? ??????????.
????? ?????? ????????? ????? ???-1, ???-2, ???-3 (????. 58?
60). ?????????? ??????????? ????
МСА-1 ® r1r2 , МСА-2 ® r1 r2 , МСА-3 ® r1r2 .
??????? 58
???-1
y1
y2
y0
x1
y1
y3
yk
???-2
y1
x1
y0
1
1
y1
x4
x2
y2
??????? 59
y3
x2
y2
1
y3
y2
y3
yk
x2
x2
x1
x3
??????? 60
???-3
y2
y0
1
y2
y4
x2
y4
y5
y5
yk
x2
x3
x1
x5x3
? ????. 61 ???????????? ???????????? ????????? ????? ?????????.
53
??????? 61
y0
y1
y1
y2
r1r2 x1 Ъ r1 r2
r1r2 x1 Ъ r1r2
r1 r2 x4
r1r2 Ъ r1 r2 x4
(r2 x4 )
(r2 Ъ r2 x4 )
y2
y3
y4
r1r2 x2
r1 r2 x2 Ъ
y5
r1 r2 x2 Ъ
r1r2 x2 Ъ
r1r2 x2
r1r2 x2
r1r2
(1)
y3
y4
yk
r1 r2 x3
r1r2 x3
r1r2 x3 x5
y5
(x3 x5 )
r1r2 x3 x5
(x3 x5 )
????????????? ??????? ????????? ??????? ? ????
B0 = B1 = B2 = {x1, x2 , x3 , x4 , x5 },
B3 = Ж, B4 = B5 = {x3 },
Bk = {r1,r2 }.
????????? ??????? ??????????, ??? ????? ??????????????
????? ?????????? ???? ????? ?????????? ??????????.
??? ????? ????????????? ??????? ?????????? ??????? ??????? fyi :
fy1 = r1r2 x1 Ъ r1 r2 Ъ r1 r2 x4 Ъ r1 r2 x3 = r1 (x1 Ъ r2 ),
fy2 = r1r2 x1 Ъ r1r2 Ъ r1r2 Ъ r1 r2 x4 = x4r1 Ъ r2 ,
fy3 = r1r2 x2 ,
fy4 = r1 r2 x2 Ъ r1r2 x2 Ъ r1r2 x3 x5 ,
fy5 = r1r2 x3 .
????????? ? ?????????? ??????? j* ? ?*:
54
?*y1 = r1,
?*y1 = 1,
?*y2 = 1,
?*y2 = r1 Ъ r2 ,
?*y3 = r1r2 x2 ,
?*y3 = 1,
?*y4 = 1,
?*y4 = r1 r2 x2 Ъ r1r2 (x2 Ъ x5 ),
?*y5 = r1r2 ,
?*y5 = 1.
? ????. 61 ? ?????? y1 ???????? ?????????? «1» ?????????? r1,
? ?????? ?3 ? ?????????? r1 ? r2, ? ?????? y5 ? ?????????? r1
? r2. ????? ???????? ??????? ???????? ? ????. 61 ????????? ?
???????. ??????????? ????????? ????? ?? ??????? ???????????????? ???????? ?? ???????????? ????????? ?????
y1 пьп
y4 пьп
пмпy0
пмпy2
п
п
п
п
п
п
п
y2 э B1, ? 2 : A2 нy3
y3 пэ B2 .
-?1 : A1 н y1
пп
пп
пп
п
y5 пюп
yk ппюп
попy4
попy5
???????? ??????? ????????? ? ??????? ???????? ?????,
???????????? ?????? ?? ???? ?????? ??? ?????????????????
????????????? ??????????? ??????? ???????? ?????????? ?i,
ri, ?????????? ??????? ?????? ????????? ????????? yl. ??????????? ??????? ????? ???????, ????? ???????? ????????? ?????
???????? ???????? ????.
??????? ???????? ?? y0 ???????????? ?? ??????????? ??????? r1 r2 x1 ? r1 r2 x1 ?????????? y2. ? ?????????? ?????
r1
x1
?
y2
y2
y1
?
y2
y1
y1
r2
?????
y0 ® r1 (r2 (x1y1 Ъ x1y2 ) Ъ r2 y1 ) Ъ r1y2 .
??? ??????? ???????? ?? y1 ???????
r2
y1
y2
y2
y2
x4
55
у0
0
r1
1
0
r2
1
1
x1
0
у1
0
1
0
x4
x2
1
у2
0
0
x2
0
r1
1
1
r2
у4
1
x3
0
r2
1
0
у5
1
0
у3
1
1
x5
x3
0
уk
???. 25. ????-????? ????????????? ?????????
? ???? ??????
y1 ® r2 y2 Ъ r2 (x4 y2 Ъ x4 y1 ).
? ??????? ???????? ?? y0 ?????? ???????? ???????? [x3] ? ?????????? ????????????? ?? ??????????? ??????? r1 r2 ? r1r2:
r1
x3
?
[x3]
?
[x3]
?
y5
?
y1
r2
56
?????? ?????
y4 ® x3 (r2 y5 Ъ r2 y1 ) Ъ x3 [x3 ] .
???????? ?? ??????? ????????? ?????????? ?????? ??????:
y2 ® x2 yk Ъ x2 (r1 (r2 y3 Ъ r2 y4 ) Ъ r1y4 ),
y3 ® yk ,
y5 ® x3 (x5 yk Ъ x5 y4 ) Ъ x3 [x3 ].
?? ?????????? ?????????? ?????? ????-????? ?????????
(???. 25).
2.4. ?????????? ?????????????? ????? ????????
????? ?????????? ??????????? ??????? ???????? ? ??????
????????? ???????? ???????? ? ???????? ??????????? ???????????? ??????????? ?????????????? ?????. ?? ???? ????? ???????????? ???????????? ?????? ??????????? ??????? ?????????? ??????? ? ?????????????? ??????, ????????? ?? ?????????? ???? ?????????.
2.4.1. ?????????? ???????? ???????? ?????
??? ????????? ???????? ???????? ????? ? ????????? ?????
????????? ?????? ??????????? (??????????????? ???????????) ??? ??????????????? (??????????????? ???????????). ???
???????????? ???????? ????????????? ???????????????? ????????? ????????? ????? ????????, ??? ???? ???? ????????? ??????????? ?? ??? ?????:
K(??)?=?aebj?.
????????, ??? ??????? ????????? ??????
i
i
i
i
K(am ) = Q11 Q22 Q33 Q44 ,
?
???
??
???
?
?l
?j
??? Qs ? ????????? s-?? ???????? ??????; <i1i2> ????????????????
? ???????? ????????????? ????? ?; <i3i4> ? ???????? ????????????? ????? j;
пм Q при is = 1,
Qis = пн
ппQ при is = 0.
о
????????? ???????? ???????????, ?? ???????? ? a ? b ?????
???????????? ????????? ????????. ???????????? a? ? bi ????????
57
s1
r1
Q1
T1
s2
r2
Q2
T2
Q3
s3
r3
T3
Q4
s4
r4
T4
&
? 3 = Q1Q2
&
?2 = Q1 Q2
&
?1 = Q1Q2
&
? 0 = Q1 Q2
&
?3 = Q3Q4
&
?2 = Q3 Q4
&
?1 = Q3Q4
&
?0 = Q3 Q4
???. 26. ????? ??????????????? ????????? ?????? ????????
? ??????? ????????? ????????????. ??? ?????? ??? ?????????? ????????? ?????????????? ????? ????????. ????? ??????????????? ????????? ?????? ???????? ???????????? ?? ???. 26.
????? ? ???????????????? ??????????? ??????????? ????? ?
?????? ????????????, ???? K < 2?, ??? ? ? ????? ?????????
????????; ? ? ????? ?????????? ????? ????????.
?????????? ????? ???????? ?? ????????? ?? ? ????????? ?s
?????????? ???????????? ?????, ????????????? ???????? ?????????.
2.4.2. ????????????? ??????? ???????????
????????????? ??????? ??????????? ???????? ??????? ? ?????????? ??? ??????? ????????? ?s ??????? ??????????? ?(?s),
?????????? ? ???? ????? ???????????? ????? ??????????????
??????? ???????????, ??????? ?? ???????? ????????? ????????? ??????. ????????????? ????????? ? ???? ??????? ?????????
?????????????? ????? ????????.
??????? ?(?s) ?????????? ???????????? ???????????? ??????? ??????????? F(??, ?s) ?? ???? ????????? ? ????????? ?s:
?(as ) = ? F (am , as ).
m
????????? ????, ??????????? ???????????? ? ?????????????? ??????? ???????????, ??????????? ???????????? ????????? V1 ? V2:
58
?)
a1
0101
a2
0001
x1 / y1
x3 / y3
x2 / y2
a3
1111
?)
?)
A1
x1
A1
x2
A2
x3
A2
x4
A1
x1
A1
x2
A2
x3
A2
x4
&
x4 / y4
s1
1
&
s2
1
&
s3
1
&
&
1
&
1
1
&
1
&
s1
s2
s3
T1
T2
T3
T1
T2
T3
???. 27. ??????? ????? ???????? (?), ????? ????????? ???????
???????????: ???????????? (?) ? ?????????????? (?)
V1 = е K(am , as ) P(F (am , as )),
m
V2 = е K(am , as ) + P(?(as )),
m
??? K(?m, ?s) ? ????? ?????????? ??????? ????????, ?????????? ??????? ?m?as; ?(F), ?(?) ? ???????? ????????????????
?????????.
????????????? ???????????? ? ??????, ???? V1 > V2. ??? ??????? ????-????? ???????? (???. 27) ?????
F (a1, a3 ) = {s1, s3 }, F (a2 , a3 ) = {s1, s2 , s3 },
?(a3 ) = {s1, s2 , s3 },
K(a1, a3 ) = 2, K(a2 , a3 ) = 2,
P(F (a1, a3 )) = 2, P(F (a2 , a3 )) = 3, P (?(a3 )) = 3, V1 = 10, V2 = 7,
? ????????????? ???????? ? ????????? ?????.
59
2.4.3. ???????????? ?????????
?????????????? ????? ????????
???????? ??????? ?????????? ??????????? ????????? ?????????????? ????? ???????? ???????? ????? ??????????????
????????????. ??????????? ?????????????? ????????????
??????? ?? ????????? ?????????, ??????? ??????????? ?????? ??????????? ??????????????? ?? ????-?????. ??? ????? ???????? ??????? «????» q, ??????? ?????????? ???? ???????? ???????, ???? ??? ???????? ?? ????? ???? ????? ?? ??????? «?????????», ????????? ????? ?????? ???????? ???????. ???? ??
???? ????? ????? ????? ??????? ????? ???? ?iq. ? ???? ??????
???? ???????? ??????? ?????????? ?????? ? ??? ????????? ?
??? ????.
???? ??????? ????? ??????? ???????: «????????? ? ????», ??
???? ? ???, ?????????? ??????????? ???????, ?????????????
? ??????? «?????????», ? ????, ?? ?????????? ??????????? ??????, ? ? ??????? «????».
??? ??????????? ????????? ?????????????? ????? ???????????? ????????? ??????? qi, ??????????? ??????? ????????
????????? ???????? ? ??????? ???????, ?????????? ??????? ?
qi. ????? qi ???????????? ??? ????????? ???????? ??????????? ?
???????? ???????? ????????. ??????? «????» ?? ??????????????? ? ?????????? ????????, ? ???????? ???? ??? ????????? ?????????????? ?????.
a1
0
a3
x1
у1
a2
1
1
у2
x2
x4
q
0
0
у3
a4
x3
a5
у4
???. 28. ??????? ????-????? ????????
60
1
??????? 62
????????
?????????
???
a1
A1
q
?
px1
?
?
a2
A4
q
?
p
?
?
a3
A5
q
?
px4
?
?
a4
?
x2
y2
?(a3)
a5
?
x2
y3
?(a4)
??????
???
?????????
?????????
????????
???????? ??????? ????????
q
?????????????? ???????
???????????
?
?? ???. 28 ? ? ????. 62 ???????????? ??????? ????-????? ???????? ? ????????? ????? ? ??????????????? ????? ???????????
???????. ????????? ?????????????? ????? ????? ???
y2 = ?(a4 ) = x2 q,
y3 = ?(a5 ) = x2 q,
q = A1x1 p Ъ A2 p Ъ A3 x4 p,
??? A1, A2 ? A3 ? ???? ????????? ?1, ?2 ? ?3.
A1
x1
p
A2
p
A3
p
x1
x2
&
&
&
1
&
y2= Ф(a3)
q
x2
&
y3= Ф (a4)
???. 29. ?????????????? ????? ????????
????? ???????????
61
A1
x1
x2
p
A1
x1
x2
p
A2
x2
p
A2
x2
p
A3
x4
p
x2
A3
x4
p
x2
&
&
1
y2= Ф(a4)
&
&
&
1
y3= Ф (a5)
&
???. 30. ?????????????? ????? ???????? ?? ???????????
????? ?? ???. 29 ????????????? ?????????? ??????????. ???
????????? ?? ???. 30 ?????????? ????? ??? ?? ????? ???????? ??
???????????.
2.5. ?????? ????????????????? ????????
?????????? ??????? (?????? 1)
?????????? ?????? ????????????????? ???????? ??????????
??????????, ???????????? ???????? ??????? ????? ? ????????????? ??????? ??? ?????????????? ???????.
???????? ??????? ??????????? ????????? ??????????????????? ????????:
1) ???????????? ???? ????????;
2) ???????????? ????? ????? ???????? ????? ????????? ?? ???????? ????????; ???? ???????? (?????? ???????) ????????????,
?? ????? ????? ???????? ????? ???? ? ?????????? ????????????; ???? ???????? ?????? ??? ????? ????, ?? ??????? ?????? ???????, ??????? ?????????? ? ?????????????? ?????????????;
3) ??????? ??????????? ??????? ?? ?????? ?????;
4)??????????????????????????????????????????????????????????
?????????????????????????????????????????????????????????
???? ??????? ?????? ????, ?? ??????? ?????????? ?? ???????, ???? ??????, ?? ?? ??????????? ? ????????;
5) ???? ?????????? ??????? ?????? ??? ????? ????, ?? ???????
????? ???????, ???? ??? ?????? ????, ?? ??????? ????? ????;
62
Частное
1
Цифра частного
n+1
Делимое ( остаток)
Знак остатка
n
1
Вычитание
Сложение
Делитель
1
n
???. 31. ????-????? ?????????? ???????
6) ???? ????? ???? ???????? ?????? ?+1, ?? ????????? ? ?. 3,
???? ??? ????? ?+1, ?? ????????? ?????????;
7)???????????????????????????????????????????????????????
??????????????????????????????????????????????????????
???????? ????????????? ????, ? ?????????????? ?????????????.
??????????????? ???????? ??????? ????? ??????????? ????????? ?????? (???. 31), ?? ????????? ??????? ????????????
????????? ???????????? ?????.
???????????? ????? (???.??????????????????????????????????????
?????????????????????????????????????
32) ????? ????????? ??? ????????: ??????? P1 ??? ???????? ???????? ? ?????????? ??????? P2 ??? ?????? ????????. ??? ???????? ???????? ? ???????? ? ??????????
???????? ???????? ? ????????? ?????????? ???????? ??, ? ???
??????????? ????? ??????? ??? ?????????? ???????? ? ???????
??. ????? ??????? ?????????? ?????????????? ??????? ????S3=P2[n+1]
y2
±
P2
1
y10
y1
± П
S1= sgn См
y3
S2 =sgnP 1
±
1
1
См
1
n+1
y9
y8
1
n
yj
y5
y 11
y7
y4
P1
yi
x
n
y6
k
Сч
y8
1
???. 32. ???????????? ????? ?????????? ???????
63
????? ? ????????, ? ???????? ? ? ?????? ???????. ????? ?????????? ?????????????? ??????? ????????? ? ?????????. ?? ???????? ?????? ???????? ?2 ???????? ?????? ?? ????????????????.
?????????????? ????-????? ????????? ???????????? ??
???.????????????????????????????????????????????????????????
???????????????????????????????????????????????????????
33. ???????? ??????????? ? ???????? ??????? ????? ? ???????????? ? ????. 63 ? ????????? ? ?????????????? ????-?????
(???. 34). ?? ???? ????? ???????? ????????? ? ???? ? ?????????
? ??????????? ??????? ???????? (????. 64). ? ???????? ?????????
?????? ? ???????? ?????????? ???????? ???? r?s.
??????? 63
??????????
???????
???
?????????? ???????
???
P2:?=?0
y1
P2 (n + 1) := S1
y9
sgn P2:?=?1
y2
C?:?=?P2
y10
sgn C?:?=?00
y3
C?:?=???+2?n
y11
C?:?=???+(P1)???
y4
??????? ?????????
y12
C?:?=?L1(??)
y5
??:?=?1
y13
??:?=?n+1
y6
S1 S2 Ъ S1S2 = 1
x1
C?:?=???+P1
y7
S1?=?1
x2
C??=?0
x3
P2 (n + 1) = 1
x4
P2:?=?L1(P2)
??:?=????1
y8
??? ?????????? ????? ? ?????????? ?????? ???????? ????????? ??????? ??????. ????????? ??????????? ?????????, ???????
? ?????????. ????? ?? ??????????? ??????? ?????????? ?????????
?????????????? ????? ???????? ? ?????? ???????? ? ???? ?
?????? ?????????????? ????? ?? ????????? ????????? ????.
????????? ?????????????? ????? ? ?????? ???????? ????? ???
A1 = Q1 Q2 Q3 Q4 p = ? 0?0 , A2 = Q1 Q2 Q3 Q4 p = ? 0?1,
A3 = Q1 Q2 Q3 Q4 p = ?1?3 , A4 = Q1 Q2 Q3 Q4 p = ? 0?3 ,
A5 = Q1 Q2 Q3 Q4 p = ? 0?2 , A6 = Q1 Q2 Q3 Q4 p = ?2?2 ,
A7 = Q1 Q2 Q3 Q4 p = ?2?3 , A8 = Q1 Q2 Q3 Q4 p = ? 3?1,
A9 = Q1 Q2 Q3 Q4 p = ?2?1, A10 = Q1 Q2 Q3 Q4 p = ?2?0 ,
A11 = Q1 Q2 Q3 Q4 p = ?1?0 ,
64
Начало
P 2 :=0
См :=L1 (См)
P2 :=L1(P2 )
Сч := Сч ? 1
0
S1 S2 Ъ S1S2 = 1
P2 (n +1) : =S1
s gn P 2 :=1
0
s gn См := 00
1
См :=P 2
См := См+(P1 ) обр
S 1 =1
0
ПП:= 1
1
S1 =1
См:=См +(P1) обр
P2(n+1)=1
0
1
?n
См:= L1(См )
Сч:= (n+ 1)
0
Сч=0
Cм:=См +2
1
См:= См+P1
Деление
закончено
Конец
???. 33. ?????????????? ????-????? ?????????.
L1 ? ????? ????? ??????????? ???????? ?? ???? ??????; ?? ? ????????????
y1 = A1, y2 = A2 x1, y3 = A2 x1 Ъ A3 , y4 = A4 Ъ qx2 ,
y5 = A5 x2 Ъ A7 = y6 Ъ A7 , y6 = A5 x2 , y7 = qx2 , y8 = A7 , y9 = A8 ,
y10 = A9 x3 , y11 = A10 x4 , y12 = A10 x4 Ъ A11, y13 = A5 x2 ,
q = A6 Ъ A9 x3 ,
s1 = y6 , r1 = A10 ,
s2 = A7 Ъ y2 Ъ y11, r2 = A3 Ъ A8 Ъ A11,
s3 = A2 Ъ q, r3 = A7 Ъ y13 ,
s4 = A1 Ъ q, r4 = A4 Ъ y10 .
65
??????? 64
???
????????
??????
???????- ?????????
????????
???
?????????
???????????- ????????
???
???????? ???????
???
???
a1
000
???????
???????????
?????????????????? ????????
a2
0001
p
y1
s4
s4
a3
0111
px1
y2
s4, s3
s2, s3
a4
0011
px1
y3
s3
s2, s3
r2, s3
a2
0001
a3
0111
a4
0011
p
y3
r2
a4
0011
a5
0010
p
y4
r4
r4
a6
1010
px2
y5, y6
s1
s1
a1
0000
px2
y13
r3
r1, r2, r3
q
?
p
?
?
?
a7
1011
x2
y4
?
s3, s4
a7
1011
x2
y7
?
s3, s4
a8
1101
p
y5, y8
s2, r3
s2, r3
a5
0010
a6
1010
q
?
a7
1011
a8
1101
a9
1001
a10
1000
a11
0100
a9
1001
p
y9
r2
r2
a10
1000
px3
y10
r4
r4
q
?
px3
?
?
?
a11
0100
px4
y11
r1, s2
r1, s2
a1
0000
px4
y12
r1
r1, r2, r3
a1
0000
p
y12
r2
r1, r2, r3
????????? ?????????????? ????? ? ?????? ????? ???????
?????????? ? ????
? 0 = Q1 Q2 , ?1 = Q1 Q2 , ?2 = Q1 Q2 , ? 3 = Q1 Q2 ,
?0 = Q3 Q4 p, ?1 = Q3 Q4 p, ?2 = Q3 Q4 p, ?3 = Q3 Q4 p,
A1 = ? 0 ?0 , A2 = ? 0 ?1, A3 = ?1 ?3 , A4 = ? 0 ?3 , A5 = ? 0 ?2 ,
A6 = ?2 ?2 , A7 = ?2 ?3 , A8 = ? 3 ?1, A9 = ?2 ?1, A10 = ?2 ?0 ,
A11 = ?1 ?0 ,
y1 = A1, y2 = A2 x1, y3 = A2 x1 A3 , y4 = A4 q x2 , y5 = y6 A7 ,
66
Начало
a1
y1
a7
a2
y5, y 8
0
x1
a8
y9
1
a9
y2
0
a3
y3
x3
1
a4
y10
y4
a10
a5
0
x2
1
1
y11
y5 , y 6
0
y4
a11
q
a6
x2
0
x3
y13
y12
1
a1
y7
Конец
???. 34. ?????????????? ?????????? ????-????? ?????????
y6 = A5 x2 , y7 = q x2 , y8 = A7 , y9 = A8 , y10 = A9 x3 , y11 = A10 x4 ,
y12 = A10 x4 A11, y13 = A5 x2 ,
q = A6 A9 x3 ,
s1 = y6 , r1 = A10 ,
s2 = A7 y2 y11, r2 = A3 A8 A11,
s3 = A2 q, r3 = A7 y13 ,
s4 = A1 q, r4 = A4 y10 .
67
2.6. ?????? ????????????????? ???????? ??????????
???????? ??????? ??????? (?????? 2)
?????????? ?????? ?????????????? ?????????? ??????????
????????, ?????????????? ???????? ??????? ??????? ? ???????? ??????????.
? ???????? ???????????? ????? ??????? ??? ????????????
??????????: ?1 ? ??? ?????? ??????? ?? ??????? ? ?2 ? ??? ???????? ?????????? ? ??????????? ??????? ?? ???????, ??????????? ????????? ????????, ??????????? ? ??????????? ???????????, ?????????? ???? ? ?????????? ???????? ???????? ?????????? ?????? (???. 35).
???????? ???????????????? ??????? ?????????. ????? ??????? ?????? ?????? ?? ??????? ????? ????????? ? ???????? ?????????. ?? ???????????? ??????? Y1 ???????????? ??????????
?1 ???????????? ?? ???? ???????. ???? ?? ?????? ????????? ??Закалочная
печь
x1
Счетчик
Y6
b
Y5
Y10
Устройство
контроля с
x2
Y7
Контейнер для
неисправных
деталей d
Манипулят ор
с программным
управлением
a
e
Y1
T1
Y1
Y2 Y3 Y4 Y8 Y9 Y10 Y11 Y13 Y14
T2
T2
Y12
???. 35. ???????????? ????? ????????????????? ??????? ???????
? ???????? ???????
68
???? ???????????? ? ????? ?. ?? ??????? Y2 ??????????? ???????? ??????, ????? ?????? ?? ?????? ? ???????????? ? ????? ?. ??
??????? Y3 ?????? ???????????? ? ??????? ???????????? ? ?????
b. ?? ??????? Y4 ?? ?????? ?????? ? ????, ????????? ?? ? ???????????? ? ????? b.
???????? Y5 ?????????? ????? ???????. ???? ????????? ?????????? ??????? ? ??????? ??????-?? ???????, ?? ? ????????????
????? ??????? ?????? ??????? ??????. ???????? Y6 ? ??????? ???????? ?????, ??????????????? ???????????? ????? ??????. ?????? ???? ???????? Y7 ????????? ????????? ?? ????? ???????, ????? ???? ????????? ????????? ????????. ????? ????????? ????????
?????? ?????? ????, ???????? ?????????????? ?????? x1?=?1.
??????????? ??????????? ???????? Y8 ?????? ?????? ? ????,
??????? ?????? ? ????? ???????? ? ????? b. ????????? ????????
Y5 ?????????? ????? ???????.
????? ??????????? ???????? Y9 ??????????? ? ??????? ???????? ? ????? ?. ?? ??????? Y10 ?? ??????? ?????? ?? ???????
????????, ????? ???? ????????? ????? ????????. ? ?????????? ???????? ?????????????? ?????????????? ?????? x2. ????
Начало
Y1
Y8
Y2
Y9
Y3
Y10
0
Y4, Y5
Y13
Y6
0
Y7
x1
x2
1
Y11
Y12
1
Y14
Конец
???. 36. ?????????????? ????-????? ????????? ??????????
?????????? ??????????????? ????????? ??????? ? ???????? ???????
69
x2?=?1, ?????? ????????, ? ???????? Y11 ??????????? ????? ????????? ? ????? ?, ??? ???? ?????? ????? ???????? ? ?????? ????????????? ?????????? ?2. ??????????? ???????? Y12 ??????????
? ??????????? ?????? ????? ?????????? ? ??????????? ???????,
???????????? ????????? ??????????????? ????????. ???? ??
x2?=?0, ?????? ??????????. ? ???? ?????? ??????????? ????????
Y13 ?????? ???????????? ?????????? ?????? ? ????? d ? ???????
?? ? ????????? ??? ??????????? ???????. ???????? ?????????,
??????? ???????? Y14 ??????????? ????? ????????? ? ????????
?????????.
?????????????? ????-????? ????????? ?????????? ?????????? ??????????????? ????????? ??????? ? ???????? ???????
????????? ?? ???. 36.
????-????? ???????? 15 ??????????? ??????. ?????????????,
?????????? ?????????? ???? ???????????? ?????? ???????? ? ???? ?? ????? ??????? ????????? ??????, ?. ?. ???????? ??????????
???????.
70
3. ?????????? ???????????? ??????
????????? ????????
3.1. ????????? ????????? ? ??????????
??????? ??????????? ???? ?? ?????????? ?? ??????????
????? ????? ???????? ???? ????????? ? ?????? ?????????, ?. ?.
?????????? ?? ?????? ????????? ? ??????????? ?????. ??????????
?????? ???????? ??????????????? ????????? ????????????? ?
????????????? ???????? ????????.
?????????? ????????????? ?????????? ???????? ? ?????
UML (Universal Modeling Language), ??????? ? ????????? ?????
?????????? ??? ???????? ????????????? ???????? ? ?????? ????????? ???? ?? ????? ?????????? ???????, ?. ?. ?? ????????? ?????
?? ???????????? ??? ??????? ????? ???????????? ??? ??????????????.
??? ??????? ?????????? ??????? ???????? ? UML ??????? ????????? ?????????, ?????????? ??????????? ?????? ?????????
??????????? ????????. ??? ???? ??????????? ?????? ??????????
??????? ????????? ? ???????????? ?? ??? ???? ????????? ????????. ????????? ????? ????????? ?? ????? ????????? ??????? ?
?????? ?????????? ???? ????????? ????????. ????? ????????? ????????? ??????? ?????????? ???????? ? ?????????.
????????? ? UML??????????????????????????????????????
?????????????????????????????????????????
??????????????? ?????? ? ??????? ?????????? ????????. ??? ????????? ?????????? ????????? ????????, ?????????? ??????? ???????? ? ????????? ?????????
??? ???????? ???????? ????????? ??????????. ? ??????????? ??
???????????? ?????????? ???????? ????? ??????????? ? ??????
????? ? ?????????, ? ?????? ?????? ?? ???? ??? ? ??????? ?????
???????, ???? ?????? ????? ?????????? ? ?????? ?????????. ??
????????? ??????????? ???????? ??????? ?? ????????? ????????? ??????????.
??????? ?? ?????? ????????? ? ?????? ???????????? ? UML
???????????? ?????????? ???????. ??? ????? ???? ??????? ???????, ????????? ????????????? ???????? ???????, ?????? ?????????? ????????? ????????.
??? ??????? ?????????????? ?????? ????????? ??????? ??
????????? ?????????. ???? ?????? ?????????? ??????, ???????????? ??????? ?? ?????? ????????? ? ??????, ?? ??????? ?????????? ??????????. ???? ?????? ?? ??????, ?? ??????? ??????????
???????????? ? ??????????? ??????????????? ????? ?????????
71
????????, ????????? ? ???????? ??????????. ?????? ??????????? ??????????? ???????? ????? ???????????????? ?????????? ?????????? ????????. ??????? ???????????, ???? ????????
?????????? ?????? ???????? ? ?????????? ??????? ????? ???????? «??????».
? ??????? ?? ???????????? ?????? ????????, ??????????????? ? ?????? ???????, ????????? ????????? UML?????????????
????????????????
???????? ????? ?????????????? ???????. ? ????? ????????? ?????????:
? ????????? ?????????. ????? ??????? ????????? ? UML?????
????????
???????? ????????????? ????????? ?????????, ?????????? ? ????
????????? ???????????? ? ???????????????? ?? ??????? ????????? (???. 37, ????????? ?). ?????? ????????? ?????????? ????? ????? ????????? ? ???????? ?????????;
? ???????????? ?????????. ????????? ???????? ???????? ??
????????? ????????? ??????????? ? ???????? ????????????? ????????? ???????. ?????? ???????????????? ???? ?????? ???????? ?? ??????????? ?????? ?? ?????????? ????????? ? ??????????? ????????? ? ?? ?? ?????????. ??? ???? ???? ? UML ??????
???????????? ?????????. ??? ???????????? ??? ??????????? ????????????, ??????? ???? ??????? ? ?????? ?????? ?? ?????????? ?????????. ??? ????????? ????? ? ????????? ????????? ???????????? ????????? ????? ?????????? ?????????? ? ???????????
????????????, ????? ??? ??????????????;
? ??????? ????????. ? ????????? ??????? ??????? ?????
????? ????????? ?????????-?????????? (???????-??????????) ???
????????? ??????? ????????? (???????-?????????). ????? ??????? ?????????? ???????????? ????????? ? ???????????? ???????????? ????????? (???. 37). ???????-?????????? ???????????,
???? ??????????? ??? ???????? ?????????-??????????. ? ??????
????????-????????? ?????????? ??????????? ???????? ?? ??? ???-
A
a
1
e
2
j
3
c
C
d
D
E
B
b
4
f
5
g
6
???. 37. ??????? ???????? ?? ?????????? ?????????
72
?????????, ?????????? ???????????? ????? ????????? ????????????.
????? ???????????? ????????-????????? ??????? ????? ?????????? ?? ???? ??????? ?????????? ????? ????????:
? ???????????????? ?????????. ????? ????????? ????????????? ? ????????????? ??????????? ????????? ??????? ???????????? ?????????. ??? ???? ???? ???????? ??????????? ????????????, ??????? ?????????? ???????????????? ?????????? ? ???????????? (*). ??? ???????????? ????????? ? ???????????????????? ??? ?????????-?????????? ??? ????, ????? ????
??????? ?? ??????? ? ?????? ????????, ??????????? ???????????????? ??????? ?? ????????? ??????? ???????????. ???, ??????? ?? ????????? 4 ? ????????? 5 ???????????????? ???????? ?, ?
??????? ?? ????????? 2 ?????????????? ??????? g;
? ???????? ? ????????? ?????????. ???????, ??????? ???????? ????????? ? ???????? ?????????? ?????????, ???????? ???????
? ????????? ????????? ? ???????????? ???????? ? ????????? ????????? ???? ????????? ????????????. ??? ??????? b ?? ???. 37.
??????? d, ????????? ?? ?????????? ?????????, ?????????? ???
?????????? ??????? ? ??????????? ??????? ?????????? ?? ????,
? ????? ????????? ?????????? ??? ???? ????????? ????????.
??????? ? ?????????? ????? ?? ?????????? ????????? ??? ?????? ??????????? ?? ????????? 2. ?????????? ????? ??????? ? ????????????? ???????? ????? ? ?????????? ????????? ??????????
???????????.
???????? ? UML ???? ???????? ????????? (???????????)
??? ?????????? ?????? ????????? ??????????? ???????? ??????? ??? ?????? ?. ??????? ??? ???????? ?????? ???????????????????? ????. ???? ??????????? ???????? ??????? ? ????????? ???????????? ??? ???????? ????????????????? ?????????? ???????????? ?????????, ????????????? ? ??????????? ???????. ????? ????????? ????????????? ? ??????????
????????? ????? ????? ? ??????????? ???????????? ?? UML
[7, 8].
? ????? ????????????? ????????????? AnyLogic [9] ????????? ??????????? ??????????? ?????????? ? ??????????????
??????? ???????????? ??????????????. ?????????? ???????? ??
??????????? ????????? ???????? ????????? ? ????????? ???????????? ??????? ????? ?????????, ??????? ????????? ? ???????????? ????????? ? ?????? ?????????, ???????????? ? ?????????? ????????? UML.
73
P0
go
Движение разрешено
Внимание
attention
P1
A
B
t4
slow
Приготовиться к остановке
t5
stop
Движение запрещено
t6
ready
Приготовиться к движению
t7
???. 38. ????????? ?????????
? ???????? ??????? ?? ???. 38 ???????? ????????? ?????????
?? [9]. ?? ??????? ???????????????? ???????????? ?????????,
?????? ? ????????.
????????? ???????? ?????? ??????? ?????????:
go ? ???????? ????????? (??????? ??????? ??????);
slow ? ????????????? ? ????????? (??????? ?????? ??????);
stop ? ???????? ????????? (??????? ??????? ??????);
ready ? ????????????? (???????? ?????? ? ??????? ???????).
????????? «????????» ????????????? ???????? ???????
??????. ????? ????????? ???????????? ????????? ??????????.
? ???????????? ? ??????? ?????? ?????, ? ???????????? ? ? ??
?????, ?0 ? ????????? ????????? ??????????, ?1 ? ????????? ????????? ?????????? ????????. ? ?????? ??????? ??? ????????
??????????? ?? ????????, ?. ?. ?? ????????? ???????, ???????
?????? ????? ???????? ??????? ? ?????? ?????????.
74
3.2. ????????? ????????
????????? ??????? ?? [10] ???????? ????????? ??????????
?????????:
H?=?{t, G, V, C, P, A, F},
??? G?=?{S, s0, E} ? ??????????????? ????, ??????? ???????? ???????????? ????????? ????????? ?????????? ????????? ???????? S?=?{si | i?=?1, ?, m}, ? ???? ? ????????? ????????? ???????? ??
?????? ????????? ? ?????? ? E: S?S. ???? ?? ????????? s0 ???????? ?????????;
t?T М R ? ??????????? ??????????, ???????????? ????????
???????????? ???????;
V?=?{Vc, Vd} ? ????????? ??????????, ? ??? ?????:
Vc?=?{vi?R | i?=?1, ?, nc} ? ????????? ??????????? ?????????? ?
Vd?=?{vi?R И Z И B | i?=?1, ?, nd} ? ????????? ?????????? ?????????? (B?=?{false, true} ? ????????? ?????????? ????????);
C?=?{ci : (t, V)?Vc | i?=?1, ?, kc} ? ????????? ??????????? ???????????;
P?=?{pi(t, V) ?B | i?=?1, ?, kp} ? ????????? ?????????? ??????????;
A?=?{ci : (t, V)?V | t?=?1, ?, ka} ? ????????? ?????????? ????????;
F?=?{Fc, Fp, Fa}, ??? Fc: C?S ? ???????????, ??????????????
????????? ??????????? ??????????? ????????? ?????????
(?????? ?????), Fp: P?E ? ???????????, ?????????????? ????????? ?????????? ????????? ????????? (??? ?????), Fa: A?E ?
???????????, ?????????????? ????????? ?????????? ????????
????????? ????????? (??? ?????).
????? ???????, ????????? ??????? ? ??? ???????????????
????, ???????? ???????? ???????????? ????????? ????????????
????????? ??????? ? ????????? ??????????? ????????, ???????
???????????, ???? ?????? ????????? ???????? ???????. ? ?????? ??????? t?=?0 ??????? ???????? ???????? s0. ????? ????????? ??????? ????????????? ????????? ???????. ?????????? t
?????????? ??????????, ? ??????????? ??????????? ????????
ci, ??????????? ???????? ????????? si. ??? ?????????? ?? ???
???, ???? ?????????? ???????? py?=?Fp(ey), ??????????? ???????? ey ?? ????????? si ? ????? ????????? sj ?? ?????? ???????? true.
? ???? ?????? ??????????? ???????? ci ????????? ???????????,
??????????? ?????????? ????????? ???? ????????? ??????????? ????????. ??????????? ??????? ey, ??????????? ??????????? ??? ?????????? ???????? ay?=?Fa(ey), ?????????? ????????
75
????????? ?????????? ? ???????????? ????????? ???????? ???????????? ???????????, ???????????? ????????? sj. ?????????
sj ?????????? ???????.
?????????????, ????????? ??????? ????? ????????????? ???
???????? ???????????????? ?????????? ??????????? ?????????, ????????????????? ? ??????? ????????? ???????.
????????? ??????? ? ????? ?????????? ????????????? ??????????? ???????. ????????? ???????, ?????????? ???????? ??
????????? ?????????
Документ
Категория
Без категории
Просмотров
1
Размер файла
4 073 Кб
Теги
eroshmihaijlov
1/--страниц
Пожаловаться на содержимое документа