Занятие №1. По дисциплине Теория информации



Скачать 110.88 Kb.
Дата03.07.2014
Размер110.88 Kb.
ТипЗанятие
КАФЕДРА

ПРИКЛАДНОЙ ИНФОРМАТИКИ

Практическое занятие №1.


По дисциплине

Теория информации









Тема № 2

Информационные модели сигналов систем





полное наименование темы


Занятие № 4

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




полное наименование занятия


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


Изучаемые вопросы:
1. Определение количества информации при равновероятных событиях.

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


  1. Определение количества информации при равновероятных событиях.


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

(1)

Неопределенность, приходящаяся на символ первичного (кодируемого) алфавита, составленного из равновероятных и взаимно зависимых символов,

(2)

Основание логарифма влияет лишь на удобство вычисления. В случае оценки энтропии:

а) в двоичных единицах бит/символ;

б) в десятичных единицах бит/символ, где , 1 бит 0,3 бит;

в) в натуральных единицах нат/символ, где , 1 бит 0,69нат.


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

бит. (3)

Для случаев равновероятных и взаимонезависимых символов первичного алфавита количество информации в k сообщениях алфавита m равно: бит.

Для неравновероятных алфавитов энтропия на символ алфавита:

бит/символ, (4)

а количество информации в сообщении, составленном из неравноверновероятных символов,

бит. (5)

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

Количество информации определяется исключительно характеристиками первичного алфавита, объем – характеристиками вторичного алфавита. Объем информации

, (6)

где - средняя длина кодовых слов вторичного алфавита.

Для равномерных кодов (все комбинации кода содержат одинаковое количество разрядов) ,

где n – длина кода (число элементарных посылок в коде). Согласно (3), объём равен количеству информации, если , т.е. в случае максимальной информационной нагрузки на символ сообщения. Во всех случаях I<Q.

Например, если кодировать в коде Бодо (см. приложение 3) некоторый равновероятный алфавит, состоящий из 32 символов, то бит;

.

Если кодировать в коде Бодо русский 32-буквенный алфавит, то без учета корреляции между буквами количество информации

бит; ,

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

где N – количество возможных событий; I – количество информации.

,

где - вероятность i-го события.

.

Задача 1. Два ящика, в каждом из которых по 12 шаров. В первом – 3 белых, 3 черных и 6 красных; во втором – каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей исходов этих опытов?

Согласно (2.4) находим энтропии обоих опытов:

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

Будем считать опытом А извлечение первого шара. Он имеет два исхода: A1 – вынут белый шар; его вероятность p(A1) = 2/6 = 1/3; исход A2 – вынут черный шар; его вероятность p(A2)=1 – p(A1) = 2/3. Эти данные позволяют с помощью (2.4) сразу найти H(А):
H(А)= – p(A1)log2 p(A1) – p(A2)log2 p(A2) = –1/3 log21/3 – 2/3 log22/3 = 0,918 бит
Опыт В– извлечение второго шара также имеет два исхода: B1 – вынут белый шар; B2 – вынут черный шар, однако их вероятности будут зависеть от того, каким был исход опыта В. В частности:


С
I=
ледовательно, энтропия, связанная со вторым опытом, является условной и, согласно (2.8) и (2.9), равна:

Наконец, из (2.10): H = 0,918 + 0,888 = 1,806 бит
2. Определение количества информации при различных вероятностях событий.
Задача 3. Имеется три тела с одинаковыми внешними размерами, но с разными массами x1, x2 и x3. Необходимо определить энтропию, связанную с нахождением наиболее тяжелого из них, если сравнивать веса тел можно только попарно.

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

Пусть опыт А состоит в сравнении веса двух тел, например, 1-го и 2-го. Этот опыт, очевидно, может иметь два исхода: A1x1 > x2; его вероятность p(A1) = 1/2; исход A2x1  <  x2; также его вероятность p(A2)=1/2.
H(А) = –1/2 log21/2 – 1/2 log21/2 = 1 бит

Опыт В– сравнение весов тела, выбранного в опыте А, и 3-го –имеет четыре исхода: B1x1> x3, B2x1< x3, B3x2> x3, B4x2< x3; вероятности исходов зависят от реализовавшегося исхода А– для удобства представим их в виде таблицы:
Таблица 1




B1

B2

B3

B4

A1

1/2

1/2

0

0

A2

0

0

1/2

1/2


Вновь, воспользовавшись формулами (2.8) и (2.9) и с учетом свойства (1) п.2.1.2, находим:


Следовательно, энтропия сложного опыта, т.е. всей процедуры испытаний:


Задача 4. Какое количество информации требуется, чтобы узнать исход броска монеты?

В данном случае n=2 и события равновероятны, т.е. p1=p2=0,5. Согласно (2.14):
I = – 0,5• log2 0,5 – 0,5• log2 0,5 = 1 бит




Задача 5. Игра «Угадай-ка–4». Некто задумал целое число в интервале от 0 до 3. Наш опыт состоит в угадывании этого числа. На наши вопросы Некто может отвечать лишь «Да» или «Нет». Какое количество информации мы должны получить, чтобы узнать задуманное число, т.е. полностью снять начальную неопределенность? Как правильно построить процесс угадывания?

Исходами в данном случае являются: A1 – «задуман 0», A2 – «задумана 1», A3 – «задумана 2», A4 – «задумана 3». Конечно, предполагается, что вероятности быть задуманными у всех чисел одинаковы. Поскольку n = 4, следовательно, p(Ai)=1/4, log2 p(Ai)= –2 и I = 2 бит. Таким образом, для полного снятия неопределенности опыта (угадывания задуманного числа) нам необходимо 2 бит информации.

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

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

Для данной ситуации n = 25, значит, k = 5 и, следовательно, I = 5 бит. Последовательность вопросов придумайте самостоятельно.




Задача 7. В некоторой местности имеются две близкорасположенные деревни: A или B. Известно, что жители A всегда говорят правду, а жители B – всегда лгут. Известно также, что жители обеих деревень любят ходить друг к другу в гости, поэтому в каждой из деревень можно встретить жителя соседней деревни. Путешественник, сбившись ночью с пути оказался в одной из двух деревень и, заговорив с первым встречным, захотел выяснить, в какой деревне он находится и откуда его собеседник. Какое минимальное количество вопросов с бинарными ответами требуется задать путешественнику?

Количество возможных комбинаций, очевидно, равно 4 (путешественник в A, собеседник из A; путешественник в A, собеседник из B; и т.д.), т.е. n = 22 и, следовательно значит, k = 2. Последовательность вопросов придумайте самостоятельно.




Контрольные задачи

1.Указать наименьшее количество вопросов, позволяющих всегда угадать день рождения любого человека при ответах: «Да», «Нет».

2. Составить равномерный двоичный код для передачи слов некоторого условного языка, алфавит которого состоит из 20 букв. Чему равен объём информации при передаче семибуквенного слова в этом алфавите?

3. Чему равно количество информации о неисправности n транзисторов после температурных испытаний партии транзисторов из N штук, выпущенной в один и тот же день, одним и тем же заводом?

4. Чему равна энтропия украинского алфавита, если вероятности появления букв в украинских текстах соответствуют табл. 3 приложения 5?

5. Определить энтропию физической системы B, в которой может находиться в одном из 10 состояний. Вероятности состояний системы B:

.

6. Определить объём и количество информации в принятом тексте:

«Товарищ, верь: взойдёт она,

Звезда пленительного счастья,

Россия вспрянет ото сна…»

7. Определить объём и количество информации при следующих исходных условиях: а)алфавит ,, …, равновероятный, символы вторичного алфавита комбинируются в равномерные коды, число качественных признаков, из которых комбинируются вторичные сообщения, б) первичный алфавит содержит 8 букв, вероятности появления букв первичного алфавита на выходе источника сообщений соответственно равны: коды вторичного алфавита равномерные, в) первичный алфавит состоит из 5 букв, которые встречаются в текстах с равными вероятностями, вторичные сообщения составлены из равномерных кодов с числом качественных признаков г) первичный алфавит равновероятный, а вторичный алфавит построен из кодов, способных обнаруживать одиночную ошибку, коды вторичного алфавита – равной длины.

  1. Длина кода во вторичном алфавите равна 10 символам. Количество информации на символ первичного алфавита равно 2,5 бит/символ. Какое количество информации мы получим, если примем: а) 7 символов вторичного алфавита? Б) 17 символов вторичного алфавита?

  2. Определить энтропию симметричной трехуровневой иерархической системы, основание которой равно 2, если: а) на первом уровне один элемент системы с равной вероятностью может находиться в двух состояниях, другой – с равной вероятностью может находиться в трёх состояниях; б) на втором уровне каждый элемент системы может находиться в двух состояниях с вероятностями соответственно: I- 0.2 и 0,8; II - 0,3 и 0,7; III – 0,4 и 0,6; IV – 0,38 и 0,62; в) на третьем иерархическом уровне системы четыре элемента системы с равной вероятностью могут находиться в трех состояниях, два элемента – в двух и два элемента в четырёх состояниях. Зависит ли общая энтропия системы от того, какие именно (первые или последние) элементы третьего уровня могут с равной вероятностью находиться в четырёх состояниях?



Таблица 1.1

Буква

пробел

о

е, ё

а

и

т

н

с

Относи-
тельная
частота


0,175

0,090

0,072

0,062

0,062

0,053

0,053

0,045

Буква

р

в

л

к

м

д

п

у

Относи-
тельная
частота


0,040

0,038

0,035

0,028

0,026

0,025

0,023

0,021

Буква

я

ы

з

ь, ъ

б

г

ч

й

Относи-
тельная
частота


0,018

0,016

0,016

0,014

0,014

0,013

0,012

0,010

Буква

х

ж

ю

ш

ц

щ

э

ф

Относи-
тельная
частота


0,009

0,007

0,006

0,006

0,004

0,003

0,003

0,002

Похожие:

Занятие №1. По дисциплине Теория информации iconЗанятие №3 По дисциплине Теория информации
Цель занятия: Закрепить теоретические знания по определению энтропии объединения информации при различных вероятностях событий
Занятие №1. По дисциплине Теория информации iconЗанятие №2 По дисциплине Теория информации
Цель занятия: Закрепить теоретические знания по определению условной энтропии информации при различных вероятностях событий
Занятие №1. По дисциплине Теория информации iconЛекция №5 По дисциплине Теория информации
Согласование пропускной способности канала передачи информации с потоком информации от источника
Занятие №1. По дисциплине Теория информации iconТеория информации. Мера количества информации лобач Г. С., Саттаров И. Д
Теория информации – комплексная, в основном математическая теория, включающая в себя описание и оценки методов извлечения, передачи,...
Занятие №1. По дисциплине Теория информации iconЛекция №8 По дисциплине Теория информации Тема №4 Помехоустойчивость и эффективность информационных систем полное наименование темы Занятие №12
Цель занятия: дать систематизированные основы научных знаний по различным методам кодированию данных с помощью кодов с памятью и...
Занятие №1. По дисциплине Теория информации iconРабочая программа по дисциплине "Теория информации" для студентов специальности 090106
Учебный план набора 2006 года и последующих лет, квалификация специалист по защите информации
Занятие №1. По дисциплине Теория информации iconЛекция №1 По дисциплине Теория информации
Цель занятия: дать систематизированные основы научных знаний по структуре дисциплины, предмету, методам, задачам; основным понятиям...
Занятие №1. По дисциплине Теория информации iconУчебная программа Дисциплины б5 «Теория информации и кодирования»
Дисциплины «Теория информации и кодирования» направлено на ознакомление студентов с основными количественными характеристиками источников...
Занятие №1. По дисциплине Теория информации iconЗанятие № Случайные события. Мера их неопределенности. Формула Хартли 8 Занятие № Энтропия по Шеннону. Свойства энтропии 16 Занятие № Условная энтропия. Решение задач на условную энтропию 21 Занятие № Количество информации
Очевидно, что для качественного преподавания данного курса в основной и средней школе необходима соответствующая специальная подготовка...
Занятие №1. По дисциплине Теория информации iconТеория информации и искусствознание
В сб.: "Теория информации и искусствознание", 2008. Вып. Ин-т искусствознания под эгидой Межд. Акад информатики
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org