Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
автомобилей в сети автострад, при проектировании нефтепроводов, при
передаче информации в информационных сетях и т. д.
79
Рассмотрим в качестве примера задачу транспортировки некоторого продукта
из пункта s в пункт t по сети, состоящей из железных дорог и автострад
штриховой кривой:
Здесь указаны пропускные способности дуг, а пунктиром указана фиктивная
дуга. Ее пропускная способность предполагается неограниченной.
Когда определен некоторый поток в сети, величина f(u, v) может
трактоваться как кратность соответствующей дуги, а с учетом фиктивной
дуги законы сохранения превращают сеть в эйлеров мультиграф. Поэтому
задача о максимальном потоке трансформируется в задачу отыскания эйлерова
подграфа с максимальным значением f(t, s). Соответствующий эйлеров контур
можно найти, проходя из s в t по некоторому маршруту, разрушая пройденные
"мосты". Затем можно вернуться в 5 по фиктивной дуге и выбрать новый
маршрут по изменившейся сети. Поскольку мы хотим найти максимальный
контур, разрушения каждый раз должны быть минимальны, так что следует
выбирать маршрут с наименьшим количеством промежуточных вершин. Таким
образом, алгоритм состоит из многократного применения алгоритма "Поиск
пути".
1-й маршрут:
s
a s
b a
с s
d с
e с
t d
I 100 125 125 Is, С, d, t
/, = ЮО.
2-й маршрут:
S
а S
b а
с а
d с
е b
t d
100 100 25 25
s, а, с, d, t
f2 = 25.
3-й маршрут:
S
а S
b а
с а
d
е b
t е
75 25 20 80 ) , _
s, а, Ь, е, / ' }3 ~ и'
4-й маршрут:
S
а S
Ь а
с а
d
е с
t е
55 75 55 60
s, а, с, е, t
/4 = 55.
(c) 20
.Д.Гоппа
81
Теперь пути из s в t не существует. Максимальный поток равен /j + / + /3
+ /4 = 100 + 25 + 20 + 55 = 200.
Объединяем все маршруты в переходной матрице, вписывая туда для всех дуг
i-ro маршрута значения f . Если для разных
маршрутов i и j встречаются одинаковые дуги, то соответствующие значения
f. и f суммируются:
При правильном проведении вычислений суммарная строка должна совпадать с
суммарным столбцом, поскольку мы получили эйлеров мультиграф.
5. ПАМЯТЬ В СЛОВАХ
5.1. 1-информация слова
В любом слове х присутствует некоторая память, которая проявляется в том,
что появление буквы на некоторой позиции зависит от того, какая буква
занимает предшествующую позицию. Обозначим, как и ранее, через Тх
циклический сдвиг слова х. Назовем величину /j(x) = /Q(x/Tx) 1-
информацией слова х.
Ясно, что /j(x) </Q(x), а равенство IQ(x) = /j(x) равносильно
отсутствию памяти в слове, поскольку слово х в этом случае не зависит от
своего сдвига, так что появление определенной буквы на некоторой позиции
совершенно не влияет на следующую букву. Рассмотрим, например, слово
х = (010011110010).
Поскольку число нулей здесь совпадает с числом единиц, то /0(х) = Я(х) =
12Я(1/2) = 12 бит.
Чтобы вычислить /j(x), составляем переходную матрицу х -* Тх:
0 1
0 3 3 6
1 3 3 6
6 6 12
Мы видим, что /j(x) =/Q(Tx/x) = 12 бит. Таким образом, в этом
слове отсутствует память на один шаг (соседние буквы независимы) .
Наоборот, в слове
х = (01010101),
обладающем регулярной структурой, память очень сильна: появление буквы 0
означает, что следующей буквой станет обязательно 1. В переходной матрице
х -* Тх это отражается следующим образом:
0 1
0 0 4 4
1 4 0 4
4 4 8
83
Мы видим, что /j(x) = 0 (функциональная зависимость х -* Тх).
В то же время IQ(x) максимально: IQ(x) = 8 бит.
В гл. 1 мы видели, что /Q(x) равно логарифму числа слов
0-орбиты слова х. 0-орбита состоит из всех слов с одной и той же
композицией.
По аналогии назовем 1-орбитой слова х множество слов х' с такой же
композицией х' (r) Тх', чтс и композиция х (r) Тх. Иначе говоря, два слова х
и х' принадлежат одной и той же 1-орбите тогда и только тогда, когда
переходная матрица х -* Тх совпадает с переходной матрицей х' -* Тх'.
Ясно, что 1-орбита является подмножеством 0-орбиты, так что 0-орбита
разбивается на непересекающиеся 1-орбиты.
Теорема 5.1. Логарифм числа Л^1-* слов 1-орбиты асимптотически совпадает
с 1-информацией:
log М1) = /jO) - о(п),
| о(п) | < (g - 1) log п,
где q-размер алфавита.
Доказательство. Отсортируем пару х <8> Т х применяя отображение <р,
введенное в п. 4.10:
х(r)Тх -?+ Xq <g> yQ.
Если в слове xQ <8> yQ фиксировать последний столбец для каждой
буквы, кроме начальной (фиксировать дерево D ), а затем подействовать на
оставшиеся позиции слова у^ подстановкой из
Gx, то получим новое слово у^, которому соответствует при
алгоритме вычеркивания (отображение <р~1) эйлеров контур, т.е. слово х'
из 1-орбиты слова х. Допустим, что слово х имеет композицию (wij, ...,
m^), а переходная матрица х -* Тх имеет вид
IlmJI, где ^ т.. = т.. Если удалить из пары х(r) Тх дерево D,
j
то остается матрица llm^.ll, где
'Z m!j=m'i = mi-l, т[. = тц
]
за исключением одного индекса j = к, для которого
^ik = mik ~ '•
Число различных слов х' из 1-орбиты, которые мы можем
