При кодировании сообщений, как правило, происходит передача закодированных сообщений. При этом в канале связи могут возникать помехи, в результате которых на выходе получается искаженное сообщение, что затрудняет его декодирование. Помехи бывают четырех видов:
1) Замена бита на другой бит.
2) Удвоение разряда.
3) Потеря разряда.
4) Комбинация этих помех.
Все зависит от технических характеристик канала связи.
Предположим, что канал связи таков, что для сообщения длины n – битов, в нем происходит одна ошибка замещения бита. Тогда можно произвести кодирование так, что возникшие ошибки могут быть исправлены автоматически.
Одним из способов исправления таких ошибок является, так называемый, «способ голосования», то есть каждый бит заменяется тремя одинаковыми битами. И на выходе всё сообщение разбивается на тройки. Может оказаться, что в какой-то тройке два бита одинаковые, а третий нет. Следовательно, отличающийся бит неправильный. Его можно исправить.
Таким образом, вся цепочка передачи сообщения может иметь вид:
Сообщение – составление алфавита А и выявление частоты появления каждой буквы – упорядочивание алфавита по убыванию частот – кодирование – утроение каждого бита – передача кода по каналу связи – разбиение кода на тройки – исправление ошибок – сброс лишних бит – декодирование.
Существуют и другие методы помехоустойчивого кодирования.
Графы.
Задача:
Имеется 3 домика и 3 колодца. От каждого домика к каждому колодцу проложена тропинка. Требуется проложить тропинки так, чтобы они не пересекались.
Эта задача решений не имеет.
Польский математик Куратовский и советский Понтрягин независимо друг от друга в 1930 году доказали, что при решении этой задачи хотя бы одно пересечение будет.
|
|
Понятие графа.
Рассмотренная задача относится к числу классических задач теории графов, создании которой приняли люди самых разных профессий: математик Эйлер, химик Кэли, физик Кирхгоф….
Пусть задано некоторое множество V={V 
,V 
,…,V 
}. Образуем множество Е, элементами которого являются неупорядоченные пары, составленные из элементов множества V: Е={(V ,V ), (V ,V 
)….}, причем (V ,V )=(V ,V ). Множество V называется множеством вершин, а множество Е – множеством ребер. Совокупность этих множеств называется графом G(V,E).
Очень широкое распространение получило изображение графа в виде диаграммы, в которой вершины изображаются точками, а ребра – линиями (необязательно прямыми).
Рис1. Граф Понтрягина Куратовского
Смежность.
Если вершина V принадлежит ребру Е , то V и Е называются инцидентными.
Две вершины, инцидентные одному ребру, называются смежными. Два ребра, инцидентные одной вершине, тоже называются смежными.
Рс.2. Пример графа.
Вершина V1 смежнасвершинами V2 и V4. Ребро Е 1 является смежным с ребрами Е2, Е3, Е5.
Количество ребер, инцидентных данной вершине, называется степенью вершины d(V).
Например, для рис2 имеем d(V )=3, а d(V )=2.
Если d(V)=0. то вершина называется изолированной. Если d(V)=1, то вершина называется висячей или концевой.
Если все вершины графа имеют одинаковую степень к, то граф называется регулярным степени к.
Рис. 3. Регулярный граф степени 3.
Виды графов.
1) Если множество Е составлено из упорядоченных пар, то есть является подмножеством Декартового квадрата, то граф называется ориентированным, или ор – графом. В орграфе ребра называются дугами
|
|
.
Ьис.4. Орграф.
Примеры дуг: (V , V ), (V , V 
),(V 
,V ), (V ,V ), (V ,V ).
Заметим, что (V 
,V 
) 
(V ,V ).
Если вершина является началом дуги, то будем говорить, что «дуга исходит из вершины». А если вершина является концом дуги, то «дуга заходит в вершину». Количество заходящих дуг называется полустепенью захода, а количество исходящих дуг – полустепенью исхода.
2) Если допустить, что элементами множества Е являются пары с одиночными вершинами, то такое ребро называе6тся петлей, а граф – псевдографом.
3) Если допустить, сто V является не множеством, а набором элементов, то есть допустимо наличие одинаковых элементов, то у нас могут появиться кратные ребра, а граф будет мультиграфом.
4) Если множество Е содержит элементы, состоящие более чем из двух вершин, то такой граф называется гиперграфом.
В дальнейшем будем рассматривать графы плоские и не содержащие петель.