Основы теории информации

Реферат Основы теории информации Содержание Введение

1. Мера количества информации

2. Энтропия и ее свойства Литература Введение Строгое понятие информации, точнее количества информации, получило права гражданства только в 50-х годах нашего столетия, хотя само слово — латинское informatio — разъяснение, изложение — известно очень давно и широко использовалось и используется для обозначения сведений и процесса их передачи и получения.

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

Официальной датой рождения этой научной дисциплины считается 1948 год — год, когда были опубликованы «Математическая теория связи» Клода Шеннона и «Кибернетика» Норберта Винера. Нисколько не умаляя заслуг этих двух выдающихся американских ученых, следует отметить, что в разных областях науки еще задолго до выхода в свет этих работ появлялись идеи, на базе которых и сформировалась современная теория информации.

Впервые идею о связи между вероятностью и информацией высказал известный английский статистик Рональд Фишер. С другой стороны ряд результатов, сыгравших значительную роль в формировании теории информации, был сформулирован в физике еще в прошлом веке. Так, например, на базе фундаментальных работ, выполненных Л. Больцманом, стало возможным связать понятия вероятности с мерой необратимости (неопределенности) тепловых процессов, получившей название термодинамической энтропии. Впоследствии понятие энтропии, но уже применительно к процессам передачи сигналов стало, наряду с понятием количества информации, основным в теории информации.

Значительный вклад в становление теории информации внесли такие крупнейшие отечественные специалисты в области теории вероятностей и математической статистики как А. Н. Колмогоров, С. А. Бернштейн, А. Я. Хинчин и ряд других. Так как основные положения теории информации построены на понятиях и методах теории вероятностей и математической статистики, то в определенном смысле теория информации может считаться, хотя и самостоятельной, но ветвью этих математических дисциплин.

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

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

Итак, мера количества информации должна отвечать следующим интуитивно понятным свойствам:

1. Количество получаемой информации больше в том испытании, в котором больше число возможных исходов, т. е.

если >. (1)

Здесь I — количество информации, k и r — число исходов.

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

. (2)

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

(3)

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

(4)

В этом выражении предполагается, что все исходы равновероятны, т. е. p=1/n, так что оно может быть переписано в виде Основание логарифмов a и постоянная c могут быть выбраны произвольно в силу известного тождества. Отсюда следует, что переход от одной системы логарифмов к другой сводится к умножению на постоянный множитель, т. е. эквивалентен простому изменению масштаба. Для удобства принимают с=1 и а=2, тогда

(5)

Единица измерения количества информации при основании логарифмов а=2 носит название двоичной единицы — бита (англ. binary digit) и соответствует количеству информации, получаемому в результате испытания с двумя равновероятными исходами.

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

. (6)

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

Для иллюстрации свойств количества информации рассмотрим несколько задач.

Задача. Пусть в некотором университете студенты-естественники составляют 25% от общего числа студентов, 50% из них (естественников) юноши, а всего в университете 35% юношей. Вопрос состоит в том, какое количество информации содержится в сообщении, что встреченный юноша — студент-естественник?

Решение этой задачи можно получить двумя способами. По первому из них, события: «встречен юноша» и «встречен студент-естественник» обозначим через и соответственно. Тогда вероятность совместного наступления событий и по теореме умножения вероятностей равна

откуда .

Из условий задачи имеем:. Следовательно

=.

Откуда (бит).

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

.

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

бит Естественно, что независимо от подхода к решению, ответ остается одним и тем же.

Задача. Известно, что среди 12 драгоценных монет одинакового достоинства, одна монета фальшивая (имеет меньший вес). Какое наименьшее число взвешиваний на рычажных весах без гирь надо произвести, чтобы обнаружить фальшивую монету?

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

.

информация количество энтропия вероятность Как же должно быть организовано взвешивание, позволяющее выделить информацию, «имеющуюся» у фальшивой монеты? В данном случае процедура должна быть организована так, чтобы всякий раз в результате взвешивания получать 1,58 бита информации. Для этого разбивают 12 монет на три равные подгруппы по 4 монеты, взвешивают и сравнивают веса любых двух групп, более легкую из них снова разбивают на три подгруппы (1,1,2), сравнивают веса первых двух подгрупп (по одной монете) и, если чашки остались в равновесии, сравнивают веса двух оставшихся монет, что и позволит однозначно определить фальшивую монету.

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

Точные количества информации, получаемые в результате реализации каждого из исходов равны соответственно:(бита); (бит); (бита).

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

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

2. Энтропия и ее свойства Формула (6) определяет среднее количество информации, которое содержится в произвольном исходе, при условии, что после проведения испытания неопределенность отсутствует. В тех же случаях, когда после испытания остается некоторая неопределенность, в рассмотрение вводится новое понятие — энтропия.

Определение. Энтропией называется среднее количество неопределенности того или иного исхода до проведения испытания.

Формула для вычисления энтропии такая же как и для количества информации, так как Рассмотрим основные свойства энтропии

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

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

2. При заданном n энтропия максимальна и равна, когда все исходы, получаемые в ходе проведения испытания, равновероятны.

Доказательство. Необходимо найти максимум функции при очевидном условии, что .

Этот максимум можно отыскать, используя множители Лагранжа. Составим функцию

где — множитель Лагранжа, и приравняем к нулю частные производные этой функции:

. (7)

Подставляя в это равенство значение энтропии и выполняя дифференцирование, получим

откуда

Используя дополнительное условие, получим:

откуда .

Таким образом, показано, что энтропия достигает экстремального значения при равновероятных исходах испытания. Если теперь найти вторую производную в (7), то

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

что и требовалось доказать.

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

.

В данном случае речь идет о сложном испытании (XY), включающем в себя два более простых испытания (X) и (Y) со следующими вероятностями различных исходов:

.

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

4. Это свойство следует из того, что .

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

Доказательство. Пусть и произвольные положительные числа такие, что

=1=1. Покажем, что в этом случае

. (8)

Очевидно, что равенство в этом соотношении выполняется, когда =.

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

подставляя в них значения F.

Выполнив дифференцирование, получим. Если теперь просуммировать обе части этого равенства по k, то

.

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

Из свойств вероятности известно, что

.

Если теперь энтропиии умножить на единицы соответствующего вида, получим:

; (9)

(10)

После сложения (9) и (10) имеем

.

Пусть теперь .

Тогда

.

Из сравнения этих равенств с (8) следует

что и требовалось доказать.

.

Доказательство. Определим условную энтропию опыта Y как

. (11)

Эта величина дает среднюю неопределенность исхода любого из событий при любом известном исходе .

Имеем Положительность условной энтропии очевидна, также как и для энтропии вообще, а равенство нулю возможно только в тех случаях, когда события и статистически полностью зависимы. В этом случае, если известен исход любого i-го события x, то с вероятностью 1 известен и исход связанного с ним j-го события y.

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

Если события и статистически зависимы, то всегда. Это неравенство становится очевидным, если рассмотреть свойства 5 и 6.

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

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

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

.

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

.

Если учесть, что неопределенность передачи некоторого сигнала до начала передачи, а после получения сигнала, то количество информации, имеющееся в принятом сигнале относительно переданного, равно

. (12)

Используя свойства энтропии 4 и 6, имеем

.

Подставляя это выражение в (12), получим

.

Несложные преобразования, предлагаемые в качестве самостоятельного упражнения, переводят (12) в следующее выражение:

. (13)

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

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

причем знак равенства имеет место тогда, когда объекты и независимы. Это свойство вытекает из свойства 9 энтропии и из того факта, что если объекты и независимы, то по теореме умножения вероятностей и под знаком логарифма в (13) будет стоять единица во всех слагаемых, так что правая часть этой формулы будет равна нулю.

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

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

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

Обозначим через случайное число студентов, сдававших экзамен, а через число студентов с разной степенью подготовки (тоже случайное). Пусть — случайное число студентов, соответственно сдавших и не сдавших зачет, — случайное число студентов соответственно подготовленных и неподготовленных к зачету. Как следует из условий примера

.

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

Если в эти формулы подставить приведенные выше совместные вероятности, то получим

и соответственно

.

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

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

1. Elaine Marmel Microsoft Office Project 2003 Bible; Наука — Москва, 2009. — 534 c.

2. Krippendorff K. Information Theory. Structural Models for Qualitative Data; СПб. [и др.]: Питер — Москва, 1986. — 606 c.

3. Новости информационных технологий / IT News, № 3, 2013; ИТ Медиа — Москва, 2013. — 492 c.

4. Новости информационных технологий / IT News, № 4, 2013; ИТ Медиа — Москва, 2013. — 344 c.

5. Алферов, А.П. и др. Основы криптографии: Учебное пособие; Гелиос АРВ; Издание 2-е, испр. и доп. — Москва, 2002. — 480 c.

6. Галицкий, А.В.; Рябко, С.Д.; Шаньгин, В. Ф. Защита информации в сети — анализ технологий и синтез решений; ДМК Пресс — Москва, 2004. — 615 c.

7. Гасанов Э. Э., Кудрявцев В. Б. Теория хранения и поиска информации; ИЛ — Москва, 2002. — 152 c.

8. Гоппа В. Д.

Введение

в алгебраическую теорию информации; Гостехиздат — Москва, 1995. — 535 c.

9. Губич Л. В., Ковалев М. Я., Паткевич Н. И. Внедрение на промышленных предприятиях информационных технологий поддержки жизненного цикла продукции; Машиностроение —, 2013. — 190 c.

10. ЛеБо Чарльз, Дэвид В. Лукас Компьютерный анализ фьючерсных рынков; Альпина Паблишер — Москва, 2011. — 304 c.

11. Леонтьев, Борис Крэкинг без секретов; Познавательная книга плюс — Москва, 2001. — 576 c.

12. Мартин Н., Ингленд Дж. Математическая теория энтропии; Машиностроение — Москва, 1988. — 848 c.

13. Партыка, Т.Л.; Попов, И. И. Информационная безопасность; Инфра-М — Москва, 2002. — 368 c.

14. Рудометов, Е.А.; Рудометов, В. Е. Электронные средства коммерческой разведки; СПб: Полигон — Москва, 2000. — 224 c.

15. Харкевич А. А. (ред.) Теория информации и ее приложения; Высшая школа — Москва, 2002. — 496 c.