русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Количественная оценка информации


Дата добавления: 2013-12-23; просмотров: 1631; Нарушение авторских прав


Задачи и постулаты прикладной теории информации

 

К теории информации относят результаты решения ряда фундаментальных теоретических вопросов:

- анализ сигналов как средства передачи сообщений, включающий вопросы оценки переносимого ими «количества информации»;

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

В теории информации исследуются информационные системы при четко сформулированных условиях (постулатах):

1. Источник сообщения осуществляет выбор сообщения из некоторого множества с определенной вероятностью.

2. Сообщения могут передаваться по каналу связи в закодированном виде. Кодированные сообщения образуют множество, являющееся взаимно однозначным отображением множества сообщений. Правило декодирования известно декодеру (записано в его программе).

3. Сообщения следуют друг за другом, причем число сообщений может быть сколь угодно большим.

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

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

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



Пусть алфавит источника сообщений состоит из m знаков, каждый из которых может служить элементом сообщения. Количество N возможных сообщений длины nравно числу перестановок с неограниченными повторениями:

 

N = mn

Если для получателя все N сообщений от источника являются равновероятными, то получение конкретного сообщения равносильно для него случайному выбору одного из N сообщений с вероятностью 1/N.

Ясно, что чем больше N, тем большая степень неопределенности характеризует этот выбор и тем более информативным можно считать сообщение.

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

В качестве меры неопределенности выбора состояния источника с равновероятными состояниями принимают логарифм числа состояний:

I = log N = log mn = n log m.

 

Эта логарифмическая функция характеризует количество информации:

Указанная мера была предложена американским ученым Р.Хартли в 1928 г.

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

 

.

 

В принципе безразлично, какое основание логарифма использовать для определения количества информации и энтропии, т. к. в силу соотношения loga m =loga b logb m переход от одного основания логарифма к другому сводится лишь к изменению единицы измерения.

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

H0 = log2 m.

Тогда единицу количества информации на один элемент сообщения называют двоичной единицей или битом. При этом единица неопределенности (двоичная единица или бит) представляет собой неопределенность выбора из двух равновероятных событий (bit — сокращение от англ. binary digit — двоичная единица)

Так как из log2 m = 1 следует m = 2, то ясно, что 1 бит - это количество информации, которым характеризуется один двоичный элемент при равновероятных состояниях 0 и 1.

Двоичное сообщение длины n содержит n бит информации.

Единица количества информации, равная 8 битам, называется байтом.

Если основание логарифма выбрать равным десяти, то энтропия выражается в десятичных единицах на элемент сообщения - дитах, причем 1 дит = log102 бит = 3,32 бит.

Одно взвешивание способно прояснить неопределенность ансамбля насчитывающего три возможных исхода (левая чаша весов легче, правая чаша весов легче, весы находятся в равновесии).Так как все исходы равновероятны (нельзя заранее отдать предпочтение одному из них), то результат одного взвешивания представляет источник с равновероятными состояниями, а его энтропия составляет: H2= Iog23 бит.

Так как энтропия отвечает требованию аддитивности и при этом Н1=3Н2= 3 1og23, то для определения фальшивой монеты достаточно произвести три взвешивания.

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

Рассмотренная выше оценка информации основана на предположении о равновероятности всех знаков алфавита.

В общем случае каждый из знаков появляется в сообщении с различной вероятностью.

Пусть на основании статистического анализа известно, что в сообщении длиныn знак xi появляется ni раз, т.е. вероятность появления знака:

 

, (i = 1, 2, 3, ... , m).

 

Все знаки алфавита составляют полную систему случайных событий, поэтому:

 

.

 

Число всех возможных сообщений длины n, в которых знак xi входит ni раз, где i = 1, 2, 3 ... ,m, определяется как число перестановок с повторениями из n элементов, спецификация которых {n1, n2, ..., nm}. Поэтому количество возможных сообщений определяют по формуле:

 

.

 

Например, план застройки улицы 10 домами, среди которых 3 дома одного типа, 5 другого и 2 третьего, можно представить

 

.

 

Количество информации можно найти по формуле:

 

I = log N = log n! - (log n1!+log n2!+...+log nm!).

 

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

 

log n! » n(ln n - 1).

 

Воспользовавшись формулой Стирлинга и соотношением , получают:

 

 

 

Переходя к вероятностям и произвольным основаниям логарифмов, получают формулы Шеннона для количества информации и энтропии:

 

 

 



<== предыдущая лекция | следующая лекция ==>
Система передачи информации | Из этого следует, что при равновероятности знаков алфовита энтропия определяется исключительно числом знаков m алфавита и по существу является характеристикой только алфавита.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.