Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Кодирование информации. Количество информации. Сжатие информации.




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

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

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

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

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

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

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

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

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

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

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

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

Кодирование информации.

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

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

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

       
   
 
 

 

 


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

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

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

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

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

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

1) Целые числа

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

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

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

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

Длина кода: .

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

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

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

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

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

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

а) Списком ребер {(i 1, j 1), (i 2, j 2), …, (im, jm)}.

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

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

A = | aij |n, .

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

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

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

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

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

Пример.

 
 


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

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

3)

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

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

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

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

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

 

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

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

В дальнейшем нам полезно будет понятие полиномиальной эквивалентности двух функций. Две неотрицательные функции 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). К ним можно применить определение полиномиальной эквивалентности.

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

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...