55.Теорема Форда-Фалкерсона о максимальном потоке. Расчет максимального потока в сети.
Теорема: для любой сети с одним источником и одним стоком макс величина потока fmax через эту сеть равна мин из пропускных способностей cmin её простых сечений.
Алгоритм нахождения макс потока:
1 этап(расчёт полного потока):предположим что в сети f имеется некоторый путь из αsв βs и поток вдоль этого пути, путь содержит ненасыщенные дуги. Значит, поток можно увеличить на величину Δ равную минимуму из остаточных пропускных способностей дуг входящих в этот путь. Перебирая все возможные пути из αs в βs и проводя такую же процедуру увеличением потока пока это возможно получим полный поток для которого каждый путь из αs содержит по крайней мере одну насыщенную дугу.
2 этап(расчет макс потока):рассмотрим сеть в которой уже построен полный поток. Берем произвольный путь из х1х6. Дуги образующие этот маршрут делятся на прямые и обратные. Если существует путь в котором прямые дуги не насыщенные, а потоки на обратных дугах положит, если Δ1 минимальный из остаточных пропускных способностей прямых дуг, а Δ2 минимальный из величин потоков отрицательных дуг, величину потока в этой сети можно увеличить на величину Δ, прибавляя это значение к потокам на прямых дугах и отнимая эту величину от обратной длины.
56.Общие принципы помехоустойчивого кодирования. Примеры.
Пусть
имеется канал связи С, содержащий
источник помех: S→S’,
S
из A*,
S’
из D*,
где S-
множество переданных, а S*-
множество принятых по каналу сообщений.
Кодирование F,
обладающее таким св-вом что:
,
F-1(C(F(s)))=S называется помехоустойчивым.
Далее будем считать, без потери общности, что A=D={0,1} и что содержательное кодирование выполняется на устройстве, свободном от помех. Кодирование с исправлением ошибок представляет собой метод обработки сообщений, предназначенный для повышения надёжности передачи по цифровым каналам.
Свойства:
1. Использование избыточности: закодированная последовательность всегда содержит дополнительные, или избыточные, символы.
2.св-во усреднения, означающее, что избыточные символы зависят от нескольких информационных символов.
57.Типы ошибок. Сжатие информации.
Типы ошибок:
1. 0→1, 1→0 – ошибка типа замещения разряда.
2. 0→ᴧ - ошибка типа выпадения разряда.
3.ᴧ→0, ᴧ →1 - ошибка типа вставки разряда.
Опр: методы кодирования, которые позволяют построить(без потери информации) коды сообщений, имеющие меньшую длину по сравнению с исходным сообщением, называются методами сжатия(или упаковки) информации.
Качество сжатия обычно определяется коэффициентом сжатия, измеряется в процентах и показывает, насколько сжатое сообщение короче исходного.
Способ кодирования:
1. исходное сообщение по некоторому алгоритму разбивается на последовательность символов, называется словами.
2. полученное множество считается буквами нового алфавита. Для этого алфавита строится разделимая схема алфавитного кодирования. Полученная схема обычно называется словарём, так как сопоставляет слову код.
3.Далее код сообщения строится как пара-код словаря и последовательность кодов слов из данного словаря.
4.При декодировании исходное сообщение восстанавливается путём замены кодов слов на слова из словаря.