ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6577
Скачиваний: 50
31
тественный язык обладает большой
избыточностью
(в европейских языках - до 7%), чем объясня-
ется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков.
Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложе-
ние «в словох всо глосноо зомононо боквой о». Здесь 26% символов «поражены», однако это не
приводит к потере смысла. Таким образом, в данном случае избыточность является полезным
свойством.
Избыточность могла бы быть использована и при передаче кодированных сообщений в
технических системах. Например, каждый фрагмент текста («предложение») передается трижды, и
верным считается та пара фрагментов, которая полностью совпала. Однако, большая избыточ-
ность приводит к большим временным затратам при передаче информации и требует большого
объема памяти при ее хранении. Впервые теоретическое исследование эффективного кодирования
предпринял К.Шеннон.
Первая теорема
Шеннона декларирует возможность создания системы эффективного ко-
дирования дискретных сообщений, у которой среднее число двоичных символов на один символ
сообщения асимптотически стремится к энтропии источника сообщений (в отсутствии помех).
Задача эффективного кодирования описывается триадой:
Х = {X
4
i
} - кодирующее устройство -
В.
Здесь
X, В -
соответственно входной и выходной алфавит. Под множеством
х
i
можно пони-
мать любые знаки (буквы, слова, предложения).
В -
множество, число элементов которого в случае
кодирования знаков числами определяется основанием системы счисления (например,
т
= 2). Ко-
дирующее устройство сопоставляет каждому сообщению
х
i
из
Х
кодовую комбинацию, составлен-
ную из
п
i
символов множества
В.
Ограничением данной задачи является отсутствие помех. Требу-
ется оценить минимальную среднюю длину кодовой комбинации.
Для решения данной задачи должна быть известна вероятность
Р
i
появления сообщения
х
i
,
которому соответствует определенное количество символов
п
i
алфавита
В.
Тогда математическое
ожидание количества символов из
В
определится следующим образом:
n
cр
=
п
i
Р
i
(средняя величина).
Этому среднему числу символов алфавита
В
соответствует максимальная энтропия
Нтаx
=
n
ср
log
т.
Для обеспечения передачи информации, содержащейся в сообщениях
Х
кодовыми ком-
бинациями из
В,
должно выполняться условие H4mах ≥
Н(х),
или
п
cр
log
т
≥
- Р
i
log
Р
i
.
В этом слу-
чае закодированное сообщение имеет избыточность
п
cр
≥
H(x) /
log
т,
n
min
=
H(x) /
log
т.
Коэффициент избыточности
К
u
= (
H
max
–
H
(
x
)) /
H
max
= (
n
cp
–
n
min
) /
n
cp
Выпишем эти значения в виде табл. 1.8. Имеем:
N
min
=
H
(
x
) / log
2
= 2,85,
K
u
=
(2,92 - 2,85) / 2,92 = 0,024,
т.е. код практически не имеет избыточности. Видно, что среднее число двоичных символов стре-
мится к энтропии источника сообщений.
Таблица 1.8 Пример к первой теореме Шеннона
N
Рх
i
x
i
Код
n
i
п
i
-
∙
Р
i
Рх
i
∙ log
Рх
i
1
0,19
X
1
10
2
0,38
-4,5522
2
0,16
X
2
001
3
0,48
-4,2301
3
0.16
X
3
011
3
0,48
-4,2301
4
0,15
X
4
101
3
0,45
-4,1054
5
0,12
X
5
111
3
0,36
-3,6706
32
6
0,11
X
6
111
3
0,33
- 3,5028
7
0,09
X
7
1011
4
0,36
-3,1265
8
0,02
X
8
1001
4
0,08
-3,1288
Σ=1
Σ=2,92
Σ=2,85
Вторая теорема Шеннона
гласит, что при наличии помех в канале всегда можно найти та-
кую систему кодирования, при которой сообщения будут переданы с заданной достоверностью.
При наличии ограничения пропускная способность канала должна превышать производительность
источника сообщений. Таким образом, вторая теорема Шеннона устанавливает принципы помехо-
устойчивого кодирования. Для дискретного канала с помехами теорема утверждает, что, если ско-
рость создания сообщений меньше или равна пропускной способности канала, то существует код,
обеспечивающий передачу со сколь угодно мглой частотой ошибок.
Доказательство теоремы основывается на следующих рассуждениях. Первоначально после-
довательность
Х
=
{xi}
кодируется символами из
В
так, что достигается максимальная пропускная
способность (канал не имеет помех). Затем в последовательность из
В
длины
п
вводится
r
симво-
лов и по каналу передается новая последовательность из
п + r
символов. Число возможных после-
довательностей длины и +
т
больше числа возможных последовательностей длины
п.
Множество
всех последовательностей длины
п
+
r
может быть разбито на
п
подмножеств, каждому из которых
сопоставлена одна из последовательностей длины
п.
При наличии помехи на последовательность
из
п
+
r
выводит ее из соответствующего подмножества с вероятностью сколь угодно малой.
Это позволяет определять на приемной стороне канала, какому подмножеству принадлежит
искаженная помехами принятая последовательность длины
п + r,
и тем самым восстановить ис-
ходную последовательность длины
п.
Эта теорема не дает конкретного метода построения кода, но указывает на пределы дости-
жимого в создании помехоустойчивых кодов, стимулирует поиск новых путей решения этой про-
блемы.
4.4. МЕЖДУНАРОДНЫЕ СИСТЕМЫ БАЙТОВОГО КОДИРОВАНИЯ
Информатика и ее приложения интернациональны. Это связано как с объективными по-
требностями человечества в единых правилах и законах хранения, передачи и обработки инфор-
мации, так и с тем, что в этой сфере деятельности (особенно в ее прикладной части) заметен при-
оритет одной страны, которая благодаря этому получает возможность «диктовать моду».
Компьютер считают универсальным преобразователем информации. Тексты на естествен-
ных языках и числа, математические и специальные символы - одним словом все, что в быту или в
профессиональной деятельности может быть необходимо человеку, должно иметь возможность
быть введенным в компьютер.
В силу безусловного приоритета двоичной системы счисления при внутреннем представле-
нии информации в компьютере кодирование «внешних» символов основывается на сопоставлении
каждому из них определенной группы двоичных знаков. При этом из технических соображений и
из соображений удобства кодирования-декодирования следует пользоваться равномерными кода-
ми, т.е. двоичными группами равной длины.
Попробуем подсчитать наиболее короткую длину такой комбинации с точки зрения челове-
ка, заинтересованного в использовании лишь одного естественного алфавита - скажем, английско-
го: 26 букв следует умножить на 2 (прописные и строчные) - итого 52; 10 цифр, будем считать, 10
знаков препинания; 10 разделительных знаков (три вида скобок, пробел и др.), знаки привычных
математических действий, несколько специальных символов (типа #, $, & и др.) — итого ~ 100.
Точный подсчет здесь не нужен, поскольку нам предстоит решить простейшую задачу: имея, ска-
жем, равномерный код из групп по
N
двоичных знаков, сколько можно образовать разных кодо-
вых комбинаций. Ответ очевиден
К
= 2
N
. Итак, при
N
= 6
К
= 64 - явно мало, при
N
= 7
К
= 128 -
вполне достаточно.
Однако, для кодирования нескольких (хотя бы двух) естественных алфавитов (плюс все от-
меченные выше знаки) и этого недостаточно. Минимально достаточное значение
N
в этом случае
8; имея 256 комбинаций двоичных символов, вполне можно решить указанную задачу. Поскольку
8 двоичных символов составляют 1 байт, то говорят о системах «байтового» кодирования.
33
Наиболее распространены две такие системы: EBCDIC (Extended Binary Coded Decimal In-
terchange Code) и ASCII (American Standard Information Interchange).
Первая - исторически тяготеет к «большим» машинам, вторая чаще используется на мини-
и микро-ЭВМ (включая персональные компьютеры). Ознакомимся подробнее именно с ASCII,
созданной в 1963 г.
В своей первоначальной версии это - система семибитного кодирования. Она ограничива-
лась одним естественным алфавитом (английским), цифрами и набором различных символов,
включая «символы пишущей машинки» (привычные знаки препинания, знаки математических
действий и др.) и «управляющие символы». Примеры последних легко найти на клавиатуре ком-
пьютера: для микро-ЭВМ, например, DEL - знак удаления символа.
В следующей версии фирма IBM перешла на расширенную 8-битную кодировку. В ней
первые 128 символов совпадают с исходными и имеют коды со старшим битом равным нулю, а
остальные коды отданы под буквы некоторых европейских языков, в основе которых лежит лати-
ница, греческие буквы, математические символы (скажем, знак квадратного корня) и символы
псевдографики. С помощью последних можно создавать таблицы, несложные схемы и др.
Для представления букв русского языка (кириллицы) в рамках ASCII было предложено не-
сколько версий. Первоначально был разработан ГОСТ под названием КОИ-7, оказавшийся по ряду
причин крайне неудачным; ныне он практически не используется.
В табл. 1.9 приведена часто используемая в нашей стране модифицированная альтернатив-
ная кодировка. В левую часть входят исходные коды ASCII; в правую часть (расширение ASCII)
вставлены буквы кириллицы взамен букв, немецкого, французского алфавитов (не совпадающих
по написанию с английскими), греческих букв, некоторых спецсимволов.
Знакам алфавита ПЭВМ ставятся в соответствие шестнадцатиричные числа по правилу:
первая - номер столбца, вторая - номер строки. Например: английская 'А' - код 41, русская 'и' - код
А8.
Таблица 1.9 Таблица кодов ASCII (расширенная)
Одним из достоинств этой системы кодировки русских букв является их естественное упо-
рядочение, т.е. номера букв следуют друг за другом в том же порядке, в каком сами буквы стоят в
русском алфавите. Это очень существенно при решении ряда задач обработки текстов, когда тре-
буется выполнить или использовать лексикографическое упорядочение слов.
Из сказанного выше следует, что даже 8-битная кодировка недостаточна для кодирования
всех символов, которые хотелось бы иметь в расширенном алфавите. Все препятствия могут быть
сняты при переходе на 16-битную кодировку Unicode, допускающую 65536 кодовых комбинаций.
34
Контрольные вопросы
1. Как определяется алфавит?
2. Что такое код?
3. Как объяснить большую помехоустойчивость передаваемых сообщений, составленных на
русском языке?
4. Что определяют первая и вторая теоремы Шеннона?
§ 5. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
5.1. ОСНОВНЫЕ ПОНЯТИЯ
Такая структура, как
граф
(в качестве синонима используется также термин «сеть») , имеет
самые различные применения в информатике и в смежных прикладных областях, поэтому позна-
комимся с основными понятиями теории графов.
Граф
G = (V, Е)
задается парой конечных множеств
V
и
Е.
Элементы первого множества
V1,
v2,..., vM
называются
вершинами
графа (при графическом представлении им соответствуют точ-
ки). Элементы второго множества
е1, е2, ...,eN
называют
ребрами.
Каждое ребро определяется па-
рой вершин (при графическом представлении ребро соединяет две вершины графа). Если ребра
графа определяются упорядоченными парами вершин, то такой граф называют
ориентирован-
ным
(на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, ука-
зывающую его направление). Ориентированный граф с пятью вершинами и семью ребрами изо-
бражен на рис. 1.6.
Рис. 1.6.
Пример ориентированного графа
Если две вершины соединены двумя или более ребрами, то эти ребра называют параллель-
ными (например, ребра е4 и
е5).
Если начало и конец ребра совпадают, то такое ребро называется
петлей
(например, ребро
е7).
Граф без петель и параллельных ребер называется простым.
Если ребро
ek
определяется вершинами
vi
и
vj
(будем обозначать этот факт следующим об-
разом:
ek
=
(vi, vj),
то говорят, что ребро
ek
инцидентно
вершинам
vi
и
vj.
Две вершины
vi
и
vj
на-
зываются смежными, если в графе существует ребро
(vi, vj).
Последовательность вершин
vi1, vi2,..., vik,
таких, что каждая пара
(vi,(j-1), vij)
при 1
< j ≤ k
определяет ребро, называется
маршрутом
в графе
G.
Вершины
vil
и
vik
называют
концевыми
вершинами маршрута, все остальные входящие в него вершины -
внутренними.
Маршрут, в котором все определяемые им ребра различны, называют цепью. Цепь считают
замкнутой, если ее концевые вершины совпадают. Замкнутая цепь, в которой все вершины (за ис-
ключением концевых) различны, называется циклом. Незамкнутая цепь, в которой все вершины
различны, носит название путь. Если в ориентированном графе существует путь из
vi
в
vj,
то гово-
рят, что вершина
vj
достижима из вершины
vi.
Две вершины
vi
и
vj
называют связанными в графе
G,
если в нем существует путь, для ко-
торого эти вершины являются концевыми. Граф
G
называется связным, если каждые две вершины
в нем являются связанными. На рис. 1.7 изображен простой неориентированный связный граф.
Последовательность вершин
v1, v5,
i4,
v3 ,
например, определяет путь, а последователь-
ность вершин
v1, v5,
i4,
v3, vl, v1 -
цикл.
Деревом
будем называть неориентированный связный
граф без циклов.
Лес
- это любой граф без циклов. На рис. 1.8 показаны возможные деревья с пя-
тью вершинами.
35
Рис. 1.7.
Пример неориентированного связного графа
Рис. 1.8.
Примеры деревьев
Анализ приведенных здесь понятий и определений показывает, что в качестве моделей
графы удобно использовать в тех случаях, когда рассматривается система каких-либо объектов,
между которыми существуют определенные связи, отношения, когда изучается структура систе-
мы, возможности ее функционирования. В информатике графы используются в разделах: опера-
ционные системы, алгоритмизация, структуры данных, информационное моделирование и др.
5.2. ПРЕДСТАВЛЕНИЕ ГРАФОВ
Важным вопросом, особенно для приложений теории графов, является определение воз-
можных способов представления графов. Самый простой способ - полное перечисление множеств
V
и
Е.
Однако, очевидно, что в этом случае выявление у графа различных характеристик и свойств
будет крайне затруднительным. Граф можно представить в виде некоторого графического изобра-
жения и визуально определить некоторые свойства и характеристики заданного графа. Однако,
при наличии в графе'большого числа ребер и вершин этот способ также мало пригоден. Рассмат-
ривая различные возможные способы представления графов, мы должны иметь в виду потреб-
ность ввода соответствующей информации в компьютер. В этой связи ввод информации в число-
вом виде предпочтителен, хотя современные технические средства допускают ввод и графической
информации (таблиц, текста, графиков, рисунков и т.д.), после чего может производиться обра-
ботка такой информации.
Матрица смежности.
Если вершины графа G помечены метками
v1, v2,..., vn,
то элементы
матрицы смежности
A(G)
размера
V, xV
определяются следующим образом:
A(i.j) =
1, если
vi
смежна с
vj; A(ij)
= 0 в противном случае (рис. 1.9,
а).
Матрица инцидентности.
Если вершины графа
G
помечены метками
v1, v2,..., vm,
а ребра
- метками
е1, е2,..., еп,
то элементы
матрицы инцидентности
I(G)
размера
М
х
N
определяются
правилом:
B(ij) =
1, если
vi
инцидентна
ej; B(iJ)
= 0 в противном случае (см. рис. 1.9,
б).
Рис. 1.9, а.
Матрица смежности
Рис. 1.9, б.
Матрица инцидентности