Представление (кодирование) информации.

Итак, условие задачи – это информация, текст алгоритма – информация, результат работы алгоритма – информация и т.п. Еще раз хочу подчеркнуть, что нет алгоритма без информации и наоборот.

Сначала поясним, что будет пониматься под количеством информации, кодированием информации и сжатием информации.

Будем считать, что информация создается и используется человеком (субъектом).

Как мы уже говорили, при математическом подходе к информации предполагается справедливость следующего тезиса.

Тезис. Любая информация может быть представлена словом в конечном алфавите.

Очевидно, что множество слов может быть представлено одним словом. (Например, с помощью операции конкатенации.)

Опр. Количество символов в слове α будем называть длиной слова α и обозначать черезl(α) или |α|.

Опр. Конкатенация слов и получается путем последовательной записи символов одного слова вслед за символами другого, т.е.

Поэтому понятия кодирование информации, количества информации и сжатие информации могут относиться как к одному слову, так и к множеству слов.

Кодирование информации – это создание слова α в алфавите А.

Количество информации – это некоторая количественная характеристика H(α), сопоставляемая слову (множеству слов) α.

Сжатие информации - это преобразование одного слова α в другое слово β. Поэтому сжатие – это преобразование информации, которое можно задать с помощью некоторого отображения φ. Таким образом, β=φ(α).

Вообще говоря, термин сжатие информации тесно связан с понятием количества информации. Сжатие происходит тогда, когда количество информации, приходящейся на один символ исходного слова α меньше, чем количество информации, приходящейся на один символ слова β=φ(α).

Понятие кодирование применительно к информации будет рассматриваться в двух аспектах:

1. Создание самого Информационного объекта. То есть нанесение на материальный носитель информации о некотором объекте в виде слова α в алфавите А. В этом случае данное слово будет рассматриваться как код объекта. То есть код объекта – это символ интерпретации субъектом информации об объекте. (Назовем это кодированием в широком аспекте.)

2. Преобразование информации. Вначале информация была представлена словом α, а затем эта же информация представляется словом β, которое получено из α в результате некоторого преобразования φ. Тогда слово β=φ(α) называется кодом слова α. (Назовем это просто кодированием.)

Преобразование одних слов в другие слова.

Код, Кодирование

Код объекта – символ интерпретации субъектом информации объекта.

 

 

Первый аспект возникает тогда, например, в программировании, когда нужно представить объект в виде набора данных. Эта проблема возникает как для математических объектов: числа, фигуры, группы, поля, алгоритмы и т.п., так и для объектов из других областей знаний: месторождения в геологии, болезни в медицине, каталоги в промышленности и т.п. Здесь результатом кодирования является слово, в то время как исходный объект кодирования либо представляет собой формализованный математический объект, либо вообще не формализован.

В Теории информации, как математической дисциплине, под кодированием понимался чаще всего второй случай. Здесь исходный и конечный объект кодирования – слова в алфавите.

Часто бывает, что кодирование (создание информационного объекта) - это итерационный процесс. То есть, сначала есть объект B, есть информация о нём I(B), потом есть информация об информации о нём I(I(B)) и т.д. В результате можно получить некоторую структуру данных, состоящую из всех таких информаций.

Примеры кодировок

Приведем простые примеры кодирования объектов.

Целые числа

Целое число n может быть представлено (закодировано), например, следующими тремя способами.

а) Словом α = 01…10 (n штук «1» и 0 по бокам) в алфавите А=(0,1). В этом случае длина кода l(α) (количество символов алфавита в слове) равна n+2;

б) Словом α = a ₁ a ₂ …a_k в виде десятичной записи в алфавите А=(0,1,…,9). Длина кода равна[lg n ]+1.

в) В мультипликативной форме (произведение степеней простых множителей) в виде слова α = a ₁ ^{p 1} a ₂ ^{p 2} …a_k^pk, (здесь a ₁ … a_k – простые числа).

Длина кода: .

Вектора и матрицы

Вектор с компонентами a ₁ … a_n, записанными в десятичной форме имеет, может быть представлен в виде слова длиныlg n + .

Матрица Mс компонентами в десятичной форме, M= ,может быть представлена словом длиныlg n + lg m + .

G = ( V, E ) – неориентированный граф.

Здесь множество вершин обозначено черезV, а множество ребер черезE. Пусть |V| = n, |E| = m.

Граф можно представить, например, следующими тремя способами (все числа в десятичной форме)

а) Списком ребер {(i ₁, j ₁), (i ₂, j ₂), …, (i_m, j_m)}.

б) Списком соседей (вершин), записанных последовательно для вершины 1, вершины 2,…, вершины n.

в) Матрицей смежности

A = | a_ij |_n×n, .

Алфавит А кроме арабских цифр будет включать вспомогательные разделители, например, «,» и «;».

Длина кодаl(α) без учета разделителей для каждого из трех случаев следующая:

а) 4n + 1 0m ≤ l(α) ≤4n + 1 0m + (n+ 2 n).

б) 2 n + 8m ≤ l(α) ≤ 2 n + 8m + 2log n.

в) l(α) = n ² – n – 1.

 

 

Пример.

 

 

1. (1 2), (1 4), (1 5), (2 3), (3 4), (2 4), (5 3)

2. (2 4 5), (3 4), (4 5)

3.

Свойства кодировок

К коду β объекта α обычно применяют следующие требования.

Декодируемость. В случае кодирования (как преобразования слов) это свойство не вызывает вопросов. Пусть есть объект α, код β= φ(α). Декодируемость означает умение восстанавливать α по коду β= φ(α). В случае же кодирования в широком аспекте словом является только β. Сам объект α словом не является. Поэтому в каждом конкретном случае нужно определять понятие восстановление. В качестве примера можно привести пример присвоения идентификатора (слово в алфавите) неформализованному объекту (изделие, книга, человек). Здесь под восстановлением понимается нахождение конкретного объекта по его идентификатору.

Неизбыточность. Это требование означает стремление уменьшить длину кода. Но пока речь не идет об оптимизации и минимизации. Неизбыточность в широком смысле означает не поиск минимально возможной (по длине кода) кодировки, а использование известной кодировки без искусственного увеличения ее длины.

Разумность. Это термин из теории сложности алгоритмов. Он означает, что способ кодировки должен соответствовать тем целям, для которых информация будет использоваться в дальнейшем. Например, если мы решаем задачу о простоте числа (по заданному натуральному числу N требуется ответить на вопрос, является ли это число простым), то кодировка в мультипликативной форме (см. пример выше) не является разумной. Для большинства практических задач кодировка а) числа nв Примере а)для кодирования целых чисел не является разумной.

Пусть мы теперь имеем "разумные" кодировки. На этом уровне принимается интуитивная гипотеза о некоторой эквивалентности всех возможных "разумных" кодировок входных данных одной и той же массовой задачи.

Второй пример показывает варианты длины кодировок в зависимости от способа задания чисел. Варианты длины кодировок в третьем примере зависят уже от структуры входных данных. Но в обоих случаях можно говорить о, так называемой, полиномиальной эквивалентности.

В дальнейшем нам полезно будет понятие полиномиальной эквивалентности двух функций. Две неотрицательные функции S(n) и R(n) полиномиально эквивалентны, если существуют два полинома Q(x) и P(x) такие, что для всех n справедливы неравенства S(n)£P(R(n)) и R(n)£Q(S(n)).

Пусть S и R две "разумные" схемы кодирования задачи массовой Z. Длины входа в этих схемах для задачи I обозначим через S(I) и R(I). К ним можно применить определение полиномиальной эквивалентности.

В примере кодирования графа все три схемы полиномиально эквивалентны.