Введение. Измерение информации

Информация и сообщение. Формы представления информации. Дискретный источник информации, информационная неопределенность. Равновероятные и неравновероятные состояния источника. Обоснование формул Хартли и Шеннона-Фано.

Введение. Информатика появилась как отдельная дисциплина в университетах в 70-е годы. Основными компонентами содержания в области информатики традиционно считаются: информация и информационные процессы, алгоритмические языки и программирование, компьютер и организация вычислительных процессов, основы формализации и моделирования, информационные технологии. Изучить все аспекты информатики в рамках одного учебного курса невозможно, особенно это касается специальностей информационного цикла, где требуется основательная подготовка по всем перечисленным научным направлениям. Преподавание информатики в этом случае ведется в рамках многих дисциплин, таких как "Языки программирования", "Информационные технологии", "Аппаратные средства вычислительной техники", «Теория информации» и многие другие. Целью данного курса является изучение теоретических основ информатики.

За основу примем следующее определение информатики.

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

Слово информатика происходит от французского слова Informatique, образованного в результате объединения терминов Informacion (информация) и Automatique (автоматика), что выражает её суть как науки об автоматической обработке информации. Кроме Франции термин информатика используется в ряде стран Восточной Европы. В то же время, в большинстве стран Западной Европы и США используется другой термин – Computer Science (наука о средствах вычислительной техники).

В качестве источников информатики обычно называют две науки – документалистику и кибернетику. Документалистика сформировалась в конце XIX века в связи с бурным развитием производственных отношений. Её расцвет пришёлся на 20 – 30-е годы XX века, а основным предметом стало изучение рациональных средств и методов повышения эффективности документооборота. Основы близкой к информатике науки кибернетики были заложены трудами американского математика Норберта Винера, опубликованными в 1948 году, а само название происходит от греческого слова kiberneticos (искусный в управлении). Впервые термин кибернетика ввёл французский физик Андре Мари Ампер в первой половине XIX века, обозначив этим термином науку об управлении, которая по его мнению должна была существовать.

Структура информатики как науки может быть изображена с помощью следующей упрощенной схемы.

Сосредоточимся на первой составляющей.

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

– совокупность данных, знаний о некотором объекте, процессе, явлении;

– сообщение о состоянии и свойствах объекта, процесса, явления;

– мера определенности в сообщении.

Эти три определения не являются исчерпывающими каждое по отдельности, они, как мы далее увидим, дополняют друг друга, отражая разные стороны информации. Более того, каждое из них может быть подвергнуто критике. Так, первое не учитывает динамический характер информации: информация возникает в процессе взаимодействия данных с методами. В виде данных информация существует в состоянии покоя. Кроме того, термин «знания» является антропометрическим, и его применения по отношению к автоматизированным системам обработки и хранения информации является не вполне корректным. Второе определение связывает информацию с понятием сообщения. Но всегда ли сообщение несет информацию? Сообщение содержит информацию, если в нем говорится о чем-то ранее неизвестном, если оно содержит элемент непредсказуемости. Третье определение, как мы увидим, ближе других к процессу измерения информации, т.к. связывает получение информации со снятием неопределенности.

Отметим, что термин «сообщение» используется дважды, потому рассмотрим его подробнее.

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

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

В процессе передачи информации принято выделять следующие составляющие: источник информации, получатель информации, носитель информации, канал связи. Функция источника информации состоит в генерировании сообщений, а получателя – в приеме этих сообщений. Носителем информации является физическая или энергетическая субстанция, материализующая данное сообщение. Канал связи включает в себя физическую среду и совокупность технических средств, обеспечивающих его продвижение от источника к получателю. В качестве примера можно рассмотреть работу пожарной сигнализации. Источником здесь является датчик, фиксирующий задымление и передающий соответствующий электрический сигнал (носитель информации) по проводам (канал связи) на пульт охраны (получатель).

Формы представления информации. Информация очень разнообразна по своей природе, как разнообразны и органы чувств, её воспринимающие. Однако можно выделить лишь две принципиально разные формы ее представления – дискретную и непрерывную. Говорят, что информация задана в непрерывной форме, если она выражается величиной, которая может принимать любое значение на некотором интервале числовой оси. Дискретная форма представления характеризуется тем, что соответствующая величина имеет конечное или счетное множество значений. В качестве примера можно привести процесс измерения температуры. Если сведения о температуре сообщать, демонстрируя высоту столба окрашенной жидкости, то перед нами будет пример информации в непрерывной форме, так как жидкость может остановиться в любом месте капилляра. Если мы отградуируем термометр и будем сообщать о температуре, считывая показания с его шкалы, то тем самым перейдем к дискретной форме представления той же информации.

Алфавитный способ представления информации также является дискретным. Это книги, речь на различных языках, в том числе и технических, таких как азбука Морзе. Известно, что в боль шинстве современных приборов – телевизор, фотокамеры, музыкальные центры и т.д. – информация представлена в оцифрованном виде. Слово "цифровой" указывает на дискретный характер воспроизводимой информации. Современные методы преобразования позволяют с высокой точностью переходить от аналоговой формы представления информации к цифровой и наоборот.

Теория информации. Часто по своим свойствам информацию сравнивают с энергией. То же многообразие видов и возможность субъективного оценивания. Однако любые виды энергии измеряются в джоулях, что позволяет делать сравнения и количественные оценки. Поскольку информация является основой для принятия решений, возникает вопрос ее измерения и количественного описания. В конце 40-х годов XX в. эта проблема получает бурное развитие. В 1948 г. Клод Шеннон опубликовал фундаментальную работу "Математическая теория связи", в которой обобщил имевшиеся к тому времени научные результаты и заложил основы новой науки – теории информации. Важнейшие свойства информации были отражены в формальной модели, разработанной Шенноном. Он предложил метод, позволяющий измерять информацию в математическом смысле, независимо от смыслового значения сообщений, ввел единицу ее измерения – 1 бит. Рассмотрим подробнее основные принципы измерения информации.

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

Энтропия источника. Основной характеристикой источника информации является его энтропия, равная среднему количеству информации, приходящейся на одно состояние источника. Это значит, что, узнав о реализации (наступлении) какого-либо из состояний источника, мы получаем информацию, равную по количеству энтропии этого источника. Вопрос о нахождении энтропии сводится к математической задаче измерения информации. Здесь принципиально различимыми являются два случая: 1) когда состояния источника информации являются равновероятными, 2) когда не являются равновероятными. Приступим к их рассмотрению.

Измерение информации. Равновероятные исходы. Подход к измерению информации основан на постулате Шеннона: получение информации есть устранение или уменьшение информационной неопределенности об интересующем объекте, явлении. Сам же процесс измерения сводится к выбору одного из нескольких возможных состояний источника информации. Если состояний всего два и они равновозможны, то количество информации в сообщении о наступлении одного из исходов содержит 1 бит информации. Такое количество информации было взято за единицу ее измерения.

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

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

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

1 бит – это количество информации, уменьшающее информационную неопределенность вдвое.

Пользуясь этим определением, можно измерить количество информации для случаев, когда информационная неопределенность N больше двух (для простоты возьмем N = 2 ^k , где k = 2, 3, 4,…), а все исходы равновероятны. С целью измерения будем последовательно задавать вопросы, ответ на которые уменьшит исходную информационную неопределенность вдвое (и тем самым даст 1 бит информации), пока не получим окончательный ответ.

Пример 1.1. Сколько бит информации содержится в сообщении о том, какое из 4-х мест в купе Ваше?

Вопрос	Ответ	Количество информации
На верхней полке?	Нет	1 бит
Нижнее справа?	Да	1 бит

Итак, сообщение содержит 2 бита информации.

Нетрудно привести пример, где событие имеет 8 равновероятных исходов. Строя интересующий нас ответ как последовательность однобитовых сообщений, получим 3 бита информации. Случай с 16 исходами даст 4 бита информации. Рассмотрим подробно еще один пример с N = 32.

Пример 1.2. Пусть имеется колода из 32 игральных карт (без шестерок). Загадали одну карту. Сколько бит информации несет сообщение о том, какая именно карта загадана?

Будем строить последовательность однобитовых сообщений-ответов.

Вопрос	Ответ	Количество информации
Карта черной масти?	Нет	1 бит
Карта бубновой масти?	Да	1 бит
Карта-картинка?	Нет	1 бит
Число нечетное?	Да	1 бит
Семерка бубновая?	Да	1 бит

Чтобы выяснить, какая карта задумана, пришлось задать 5 вопросов, ответ на каждый из них содержал 1 бит информации. Следовательно, в сообщении о любой из задуманных карт будет содержаться 5 бит информации.

Обобщим результаты рассмотрения примеров в виде таблицы.

N (исходов)
Н (бит)

Заметим, что количество информации равно 0, если исход события предопределен, т.е. когда информационная неопределенность N равна единице.

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

,

(1.1)

где N – информационная неопределенность источника информации;

H – энтропия источника.

По этой же формуле рассчитывается количество информации и в случае, когда N не является степенью двойки. Например, если источник имеет 3 равновероятных состояния, то его энтропия .

Неравновероятные исходы. Определим вероятность p_i как величину, характеризующую относительную частоту реализации i -го исхода в достаточно длинной последовательности экспериментов и удовлетворяющую условиям

(1.2)

(1.3)

где N – общее число исходов в исследуемой ситуации;

p_i – вероятность i -го исхода.

Рассмотрим несколько примеров, поясняющих смысл введенного понятия.

Пример 1.3. В коробке находятся два шарика – черный и белый. Достаем наугад один из них. Исходов два – "вынут черный" или "вынут белый". Если шарики неотличимы на ощупь, исход будет являться случайным. В такой ситуации вероятность каждого исхода считается равной 1/2. Следует отметить, что при повторении этого испытания небольшое число раз (после каждого испытания мы возвращаем вынутый шарик в коробку) не исключено, что в большинстве случаев будет вынут шарик одного цвета. Но в достаточно большой серии испытаний (порядка тысячи) процент вынутых белых и черных шариков будет примерно одинаков.

Пример 1.4. В коробке находятся 2 белых и 1 черный шарик. Ясно, что белый шарик будет в среднем попадается в 2 раза чаще, чем черный. Поэтому возможным исходам ставят в соответствие вероятности 2/3 и 1/3.

Пример 1.5. В коробке находится N шариков пяти разных цветов, из них k ₁ шариков 1-го цвета, k ₂ шариков 2-го цвета и т. д. В сумме Тогда вероятность появления шариков соответствующего цвета находится как их относительное количество:

Полученные вероятности p_i удовлетворяют условиям (1.2) и (1.3):

и

Вернемся к вопросу оценки количества информации. Для источника с N равновероятными состояниями количество информации находится по формуле (1.1). При этом вероятность любого из состояний равна

Запишем формулу Хартли с учетом понятия вероятности:

где p – вероятность любого из N состояний.

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

Пусть дан алфавит состоящий из N символов, с вероятностями появления этих символов в тексте соответственно. В символах этого алфавита составлен текст длиной М символов (M >> N). После прочтения этого текста буква встретится нам раз. Рассмотрим отдельно подпоследовательность букв . В ней все буквы одинаковы и, следовательно, равновероятны. Поэтому для подсчета количества информации, которое несет появление одной буквы , мы можем использовать формулу Хартли (1.1). Это дает бит информации. Вся подпоследовательность из букв несет бит информации.

Просуммировав полученную величину по всем буквам алфавита, получим общее количество информации, содержащееся в прочитанном тексте

Поделив полученную величину на число букв в тексте, найдем среднее количество информации, приходящееся на одну букву:

(1.4)

Полученная формула называется формулой Шеннона, по имени основателя теории информации. Она позволяет найти энтропию источника в случае неравновероятных состояний.

Пример 1.6. Дан алфавит из трех букв { a, b, c }. Вероятности появления букв в тексте равны Найти энтропию этого алфавита.

Дата добавления: 2014-01-20