Подход а н колмогорова к определению количества информации сообщение

Обновлено: 01.07.2024

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

§ 2. Подходы к измерению информации

Информатика. 10 класса. Босова Л.Л. Оглавление

Информация и её свойства

Информация и её свойства являются объектом исследования целого ряда научных дисциплин, таких как:

? теория информации (математическая теория систем передачи информации);

? кибернетика (наука об общих закономерностях процессов управления и передачи информации в машинах, живых организмах и обществе);

? информатика (изучение процессов сбора, преобразования, хранения, защиты, поиска и передачи всех видов информации и средств их автоматизированной обработки);

? семиотика (наука о знаках и знаковых системах);

? теория массовой коммуникации (исследование средств массовой информации и их влияния на общество) и др.

Рассмотрим более детально подходы к определению понятия информации, важные с позиций её измерения:

1) определение К. Шеннона, применяемое в математической теории информации;

2) определение А. Н. Колмогорова, применяемое в отраслях информатики, связанных с использованием компьютеров.

2.1. Содержательный подход к измерению информации

Информация — это снятая неопределённость. Величина неопределённости некоторого события — это количество возможных результатов (исходов) данного события.

Такой подход к измерению информации называют содержательным.

Итак, количество возможных результатов (исходов) события, состоящего в том, что книга поставлена в шкаф, равно восьми: 1, 2, 3, 4, 5, 6, 7 и 8.

Метод поиска, на каждом шаге которого отбрасывается половина вариантов, называется методом половинного деления. Этот метод широко используется в компьютерных науках.

1) обойтись минимальным количеством вопросов;

1) Да — Да — Да — Да;

2) Нет — Нет — Нет — Нет;

3) Да — Нет — Да — Нет.

При N, равном целой степени двойки (2, 4, 8, 16, 32 и т. д.), это уравнение легко решается в уме. Решать такие уравнения при других N вы научитесь чуть позже, в курсе математики 11 класса.

2.2. Алфавитный подход к измерению информации

Однако при хранении и передаче информации с помощью технических устройств целесообразно отвлечься от её содержания и рассматривать информацию как последовательность символов (букв, цифр, кодов цвета точек изображения и т. д.) некоторого алфавита.

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

Минимальная мощность алфавита (количество входящих в него символов), пригодного для кодирования информации, равна 2. Такой алфавит называется двоичным. Один символ двоичного алфавита несёт 1 бит информации.

Андрей Николаевич Колмогоров (1903-1987) — один из крупнейших математиков XX века. Им получены основополагающие результаты в математической логике, теории сложности алгоритмов, теории информации, теории множеств и ряде других областей математики и её приложений.

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

Из курса информатики основной школы вы знаете, что двоичные коды бывают равномерные и неравномерные. Равномерные коды в кодовых комбинациях содержат одинаковое число символов, неравномерные — разное.

Первый равномерный двоичный код был изобретён французом Жаном Морисом Бодо в 1870 году. В коде Бодо используются сигналы двух видов, имеющие одинаковую длительность и абсолютную величину, но разную полярность. Длина кодов всех символов алфавита равна пяти (рис. 1.7).

Рис. 1.7. Фрагмент кодовой таблицы кода Бодо

Всего с помощью кода Бодо можно составить 2 5 = 32 комбинации.

Пример 5. Слово WORD, закодированное с помощью кода Бодо, будет выглядеть так:

Пример 6. Для двоичного представления текстов в компьютере чаще всего используется равномерный восьмиразрядный код. С его помощью можно закодировать алфавит из 256 символов (2 8 = 256). Фрагмент кодовой таблицы ASCII представлен на рисунке 1.8.

Рис. 1.8. Фрагмент кодовой таблицы ASCII

Слово WORD, закодированное с помощью таблицы ASCII:

Из курса информатики основной школы вам известно, что с помощью i-разрядного двоичного кода можно закодировать алфавит, мощность N которого определяется из соотношения:

2 i = N.

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

Соотношение для определения информационного веса символа алфавита можно получить и из следующих соображений.

1) определить мощность используемого алфавита N;

2) из соотношения 2 i = N определить i — информационный вес символа алфавита в битах (длину двоичного кода символа из используемого алфавита мощности N);

I = К * i,

где I — информационный вес символа в битах, связанный с мощностью используемого алфавита N соотношением:

2 i = N.

Пример 7. Для регистрации на некотором сайте пользователю надо придумать пароль, состоящий из 10 символов. В качестве символов можно использовать десятичные цифры и шесть первых букв латинского алфавита, причём буквы используются только заглавные. Пароли кодируются посимвольно. Все символы кодируются одинаковым и минимально возможным количеством бит. Для хранения сведений о каждом пользователе в системе отведено одинаковое и минимально возможное целое число байт.

Необходимо выяснить, какой объём памяти потребуется для хранения 100 паролей.

2.3. Единицы измерения информации

Итак, в двоичном коде один двоичный разряд несёт 1 бит информации. 8 бит образуют один байт. Помимо бита и байта, для измерения информации используются более крупные единицы:

1 Кбайт (килобайт) = 2 10 байт;

1 Мбайт (мегабайт) = 2 10 Кбайт = 2 20 байт;

1 Гбайт (гигабайт) = 2 10 Мбайт = 2 20 Кбайт = 2 30 байт;

1 Тбайт (терабайт) = 2 10 Гбайт = 2 20 Мбайт = 2 30 Кбайт = 2 40 байт;

1 Пбайт (петабайт) = 2 10 Тбайт = 2 20 Гбайт = 2 30 Мбайт = 2 40 Кбайт = 2 50 байт.

Это произошло потому, что 2 10 = 1024 ? 1000 = 10 3 . Поэтому 1024 байта и стали называть килобайтом, 2 10 килобайта стали называть мегабайтом и т. д.

Чтобы избежать путаницы с различным использованием одних и тех же приставок, в 1999 г. Международная электротехническая комиссия ввела новый стандарт наименования двоичных приставок. Согласно этому стандарту, 1 килобайт равняется 1000 байт, а величина 1024 байта получила новое название — 1 кибибайт (Кибайт).

Пример 8. При регистрации в компьютерной системе каждому пользователю выдаётся пароль длиной в 12 символов, образованный из десятичных цифр и первых шести букв английского алфавита, причём буквы могут использоваться как строчные, так и прописные — соответствующие символы считаются разными. Пароли кодируются посимвольно. Все символы кодируются одинаковым и минимально возможным количеством бит. Для хранения сведений о каждом пользователе в системе отведено одинаковое и минимально возможное целое число байт.

Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения, для которых отведено 12 байт. На какое максимальное количество пользователей рассчитана система, если для хранения сведений о пользователях в ней отведено 200 Кбайт?

Прежде всего, выясним мощность алфавита, используемого для записи паролей: N — 6 (буквы прописные) + 6 (буквы строчные) + 10 (десятичные цифры) = 22 символа.

Для кодирования одного из 22 символов требуется 5 бит памяти (4 бита позволят закодировать всего 2 4 = 16 символов, 5 бит позволят закодировать уже 2 5 = 32 символа); 5 — минимально возможное количество бит для кодирования 22 разных символов алфавита, используемого для записи паролей.

Для хранения всех 12 символов пароля требуется 12 • 5 = 60 бит. Из условия следует, что пароль должен занимать целое число байт; т. к. 60 не кратно восьми, возьмём ближайшее большее значение, которое кратно восьми: 64 = 8 • 8. Таким образом, один пароль занимает 8 байт.

Информация о пользователе занимает 20 байт, т. к. содержит не только пароль (8 байт), но и дополнительные сведения (12 байт).

САМОЕ ГЛАВНОЕ

I = K * i, где i — информационный вес символа в битах, связанный с мощностью используемого алфавита N соотношением 2 i = N. Единицы измерения информации:

1 Кбайт (килобайт) = 2 10 байт;

1 Мбайт (мегабайт) = 2 10 Кбайт = 2 20 байт;

1 Гбайт (гигабайт) = 2 10 Мбайт = 2 20 Кбайт = 2 30 байт;

1 Тбайт (терабайт) = 2 10 Гбайт = 2 20 Мбайт = 2 30 Кбайт = 2 40 байт;

1 Пбайт (петабайт) = 2 10 Тбайт = 2 20 Гбайт = 2 30 Мбайт = 2 40 Кбайт = 2 50 байт.

Вопросы и задания

1. Что такое неопределённость знания о результате какого-либо события? Приведите пример.

2. В чём состоит суть содержательного подхода к определению количества информации? Что такое бит с точки зрения содержательного подхода?

3. Паролем для приложения служит трёхзначное число в шестнадцатеричной системе счисления. Возможные варианты пароля:

Ответ на какой вопрос (см. ниже) содержит 1 бит информации?

1) Это число записано в двоичной системе счисления?

2) Это число записано в четверичной системе счисления?

3) Это число может быть записано в восьмеричной системе счисления?

4) Это число может быть записано в десятичной системе счисления?

5) Это число может быть записано в шестнадцатеричной системе счисления?

4. При угадывании целого числа в некотором диапазоне было получено 5 бит информации. Каковы наибольшее и наименьшее числа этого диапазона?

5. Какое максимальное количество вопросов достаточно задать вашему собеседнику, чтобы точно определить день и месяц его рождения?

6. В чём состоит суть алфавитного подхода к измерению информации? Что такое бит с точки зрения алфавитного подхода?

8. Какие единицы используются для измерения объёма информации, хранящейся на компьютере?

13. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 6 символов и содержащий только символы из шестибуквенного набора А, В, С, D, Е, F. Для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей и все символы кодируются одинаковым и минимально возможным количеством бит. Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения, занимающие 15 байт. Определите объём памяти в байтах, необходимый для хранения сведений о 120 пользователях.

Вяткин В.Б.

ЗАДАЧА ОЦЕНКИ НЕГЭНТРОПИИ ОТРАЖЕНИЯ СИСТЕМНЫХ ОБЪЕКТОВ
И ТРАДИЦИОННЫЕ ПОДХОДЫ К КОЛИЧЕСТВЕННОМУ
ОПРЕДЕЛЕНИЮ ИНФОРМАЦИИ

Алгоритмический подход к количественному
определению информации

Отличный от взглядов Хартли, Шеннона, Винера и Бриллюэна подход к определению понятия "количество информации", был предложен в 1965 году академиком А.Н. Колмогоровым, который он назвал алгоритмическим.

Исходя из того, что "по существу наиболее содержательным является представление о количестве информации "в чем-либо" (Х) и "о чем-либо" (Y)" [12, с. 218], А.Н. Колмогоров для оценки информации в одном конечном объекте относительно другого конечного объекта предложил использовать теорию алгоритмов. За количество информации при этом, принимается значение некоторой функции от сложности каждого из объектов и длины программы (алгоритма) преобразования одного объекта в другой.

Решение задачи определения количества информации в алгоритмическом подходе имеет общий вид и схематично выглядит следующим образом.

"Относительной сложностью" объекта Y при заданном Х будем считать минимальную длину "программы" Р получения Y из Х. Сформулированное так определение зависит от "метода программирования". Метод программирования есть не что иное, как функция , ставящая в соответствие программе Р и объекту Х объект Y" [12, с. 220].

Так как каждый из объектов может быть бесконечно сложным, то доказывается теорема, согласно которой относительной сложности объекта Y, при заданном методе программирования, может быть поставлена в соответствие иная относительная сложность, полученная при другом методе программирования , такая, что выполняется неравенство:

где - некоторая постоянная программирования, не зависящая от X и Y.

Учитывая, что при любых Х и Y относительная сложность является конечной величиной, а можно считать просто сложностью объекта Y, А.Н. Колмогоров для оценки алгоритмического количества информации в объекте X относительно объекта Y предложил использовать формулу:

причем и, соответственно, .

Алгоритмическая информация (22) может принимать как положительные, так и отрицательные значения. В связи с этим А.Н. Колмогоров делает два замечания. Во-первых, " не меньше некоторой отрицательной константы C, зависящей лишь от условностей избранного метода программирования" [12, с. 221]. Во-вторых, "вся теория рассчитана на применение к большим количествам информации, по сравнению с которыми будет пренебрежимо мал" [12, с. 221].

Алгоритмический подход к измерению количества информации, в силу ряда объективных причин, не нашел широкого практического применения. Во-первых, как писал сам А.Н. Колмогоров, "на пути его формализации встает очевидная трудность: то, что просто описывается на одном языке, может не иметь простого описания на другом, и непонятно, какой способ описания выбрать" [12, с. 253]. То есть алгоритмическая оценка информации зависит от выбранного метода программирования, а такой выбор, в свою очередь, по сути дела всегда имеет субъективный характер. Во-вторых, практическое использование формулы (22) возможно лишь применительно к весьма простым объектам, имеющим математическое описание, в то время как отсутствие последнего является характерной и обязательной чертой сложных объектов [14]. Кроме того, понятие "сложность" само по себе является относительным и зависит от уровня рассмотрения объектов. И, наконец, в-третьих, в соответствии с теоремой Геделя о неполноте формальных систем, нельзя доказать, что минимальная длина программы преобразования X в Y, составленная на каком-либо языке программирования, действительно является объективно минимальной [6].

В своих комментариях относительно алгоритмического подхода А.Н. Колмогоров писал, что он "основан на применении теории алгоритмов для определения понятия энтропии, или сложности, конечного объекта и понятия информации в одном конечном объекте о другом" [12, с. 253]. В соответствии с этим, переходя к рассмотрению алгоритмического подхода с позиций количественного определения негэнтропии отражения, предварительно отметим следующее. – В рассматриваемой нами ситуации (рис. 1) каждый из объектов может быть закодирован с помощью двоичного языка, символами которого являются "0" и "1". Кодируя каждый элемент символом "1", мы получим для отражаемого и отражающего объектов соответствующий код длины и . Естественно, что сложность К каждого из объектов является функцией длины такого кода, которая, в свою очередь, для энтропийной сложности представляет собой логарифм числа элементов конечного множества [14], то есть:

Также очевидно, что алгоритм получения одного объекта из другого в рассматриваемой ситуации сводится к добавлению или обнулению (ликвидации) определенного числа единиц в соответствующем коде. То есть длина "программы" получения одного объекта из другого равна двоичных единиц и соответственно относительная сложность каждого из объектов имеет вид:

Подставляя выражения (23) и (24) в формулу (22), получаем, что алгоритмическое количество информации, которое содержит отражающий объект B относительно отражаемого объекта A, равно:

Алгоритмическая информация (25) наиболее близка к определению негэнтропии отражения системных объектов в сравнении с ранее рассмотренными информационными мерами и даже, на принципиальном уровне суждений (в рамках изложенного материала), может быть принята за ее количественную характеристику. Но, этим ее положительные свойства в негэнтропийном отношении ограничиваются, так как она не применима к открытым системным объектам. Дело в том, что, когда отражаемый объект является открытым, мы опять будем иметь отрицательные значения (при ), негативизм которых, помимо отмеченного выше, может быть дополнен тем, что, как нетрудно видеть, возможны ситуации, когда аддитивная негэнтропия отражения совокупности отражающих объектов будет равна нулю. То есть, например, проведя наблюдения и выявив совокупность объектов, имеющих непосредственную взаимосвязь с отражаемым (исследуемым) объектом, в итоге мы будем иметь, что общее количество информации, полученное нами в процессе исследований равно нулю, а это уже нонсенс. Таким образом, мы видим, что алгоритмический подход, также как комбинаторный и вероятностный, не позволяет получить расчетную формулу для негэнтропии отражения системных объектов .

Впрочем, я не хочу входить здесь в детали этой специальной задачи. Мне важно лишь показать, что математическая проблематика, возникающая на почве чисто комбинаторного подхода к измерению количества информации, не ограничивается тривиальностями.

Естественно определить условную энтропию равенством

(где N(Y_x) - число элементов в множестве Y_x), а информацию в x относительно y−формулой

Например, в случае, изображенном в таблице имеем

2 Вероятностный подход

По-прежнему H_W(y|x) и I_W(x:y) являются функциями от x. Имеют место неравенства

переходящие в равенства при равномерности соответсвующих распределений (на X и Y_x). Величины I_W(x:y) и I(x:y) не связаны неравенством определенного знака. Как и в §1,

Но отличие заключается в том, что можно образовать математические ожидания MH_W(y|x), MI_W(x:y), а величина

что понимается в том смысле, что I_A(x:y) не меньше некоторой отрицательной константы C, зависящей лишь от условностей избранного метода программирования. Как уже говорилось, вся теория рассчитана на применение к большим количествам информации, по сравнению с которым |C| будет пренебрежимо мал.

4 Заключительные замечания

Отличный от взглядов Хартли, Шеннона, Винера и Бриллюэна подход к определению понятия - количество информации -, был предложен в 1965 году академиком А. Н. Колмогоровым, который он назвал алгоритмическим.
Исходя из того, что - по существу наиболее содержательным является представление о количестве информации - в чем-либо - (Х) и - о чем-либо - (Y) -, А. Н. Колмогоров для оценки информации в одном конечном объекте относительно другого конечного объекта предложил использовать теорию алгоритмов. За количество информации при этом, принимается значение некоторой функции от сложности каждого из объектов и длины программы (алгоритма) преобразования одного объекта в другой.

Березюк Н.Г. Кодирование информации (двоичные коды)

формат djvu
размер 6.11 МБ
добавлен 05 декабря 2010 г.

Березюк Н. Т., Андрущенко А. Г., Мощицкий С. С. и др. Кодирование информации (двоичные коды). Харьков, издательское обьединение "Вища школа", 1978, 252 с. В справочнике рассматриваются вопросы кодирование двоичной информации. Приводятся основные понятия из теории информации и вычислительной техники. Подробно описываются различные двоичные коды, применяемые в дискретных устройствах переработки информации, принципы их построения, даны их классифика.

Колмогоров А.Н. Теория информации и теория алгоритмов

формат djvu
размер 4.58 МБ
добавлен 26 октября 2009 г.

Москва.: Наука, 1987. -304с В настоящую работу включены работы по теории информации и теории алгоритмов и их приложениям к различным областям знания. комментарии специалистов дают представление о развитии работ А. Н. Колмогорова и современном состоянии рассматриваемых в них проблем. О понятии алгоритма К общему определению количества информации Теория передачи информации Энтропия и ёмкость множеств в функциональных пространствах Подходы к оценк.

Лекции - Теория информации

формат doc
размер 1.19 МБ
добавлен 12 ноября 2011 г.

Автор неизвестен. Тамбовский государственный технический университет. г. Тамбов, 2010 год. - 50 страниц. Понятие видов информации. Основные понятия комбинаторики. Случайные модели в теории информации. Основные понятия теории информации. Меры информации. Классификация мер информации. Энтропия вероятностной схемы. Основные свойства энтропии. Аксиомы Хинчена и Фадеева. Источники информации и их энтропия. Дискретные источники без памяти и с памятью.

Лекции по информатике

формат doc
размер 93.54 КБ
добавлен 11 апреля 2005 г.

Информационная мера Шеннона. Количество информации и избыточность. Пример. Задачи. Условная энтропия и взаимная информация. Дискретные системы передачи информации. Характеристики системы передачи информации. Каналы передачи информации. Техническиме характеристики канала связи. Кодирование информации. rn

Лекция №4

формат doc
размер 94.74 КБ
добавлен 21 мая 2004 г.

Лидовский В.В. Теория информации

формат pdf
размер 831.16 КБ
добавлен 06 октября 2007 г.

В учебном пособии излагаются основные понятия и факты теории информации. Рассмотрены способы измерения, передачи и обработки информации. Значительное внимание уделено свойствам меры информации, характеристикам канала связи, помехозащитному, уплотняющему и криптографическому кодированию. Кроме того, рассмотрены вопросы формализации информации, в частности, в документах Internet. Изложение сопровождается большим количеством примеров и упражнений. Д.

Презентация - Информация

формат ppt
размер 525.29 КБ
добавлен 17 июня 2009 г.

Понятие количества информации. Подходы к определению количества информации: алфавитный и вероятностный. Единицы измерения .

Тест - Информация. Информационные процессы

формат doc
размер 85.5 КБ
добавлен 14 ноября 2009 г.

Объем 2 стр. Информация, информационные процессы, свойства информации, количество информации, представление информации.

Цымбал В.П. Задачник по теории информации и кодированию

формат djvu
размер 3.93 МБ
добавлен 17 января 2011 г.

Цымбал В.П. Задачник по теории информации и кодированию

формат pdf
размер 7.63 МБ
добавлен 17 января 2011 г.

Читайте также: