50_000337

Практика 1-2 – комбинаторика, количество информации

2.3Элементарная комбинаторика

2.3.1Комбинаторные формулы-задачи с решениями

Пример 9. Сколькими способами возможно расставить на полке 5 книг?

Решение. Искомое количество способов равно числу перестановок из 5 элементов (книг):

P5 = 5! = 1 2 3 4 5 = 120:

Пример 10. Сколько "слов"по две буквы возможно составить из букв a,b,c,d,e таким образом, чтобы буквы в этих "словах"не повторялись?

Решение. Так как каждое "слово"должно содержать две буквы, то итоговое количество способов равно числу размещений из 5 элементов (букв) по две, т.е.:

Пример 11. Сколькими способами возможно выбрать 1 красную гвоздику и 2 розовых из вазы, в которой стоят 10 красных и 4 розовых гвоздики?

31

Решение. Так как порядок выбора цветов не имеет значения, то красную гвоздику можно выбрать

способами. Выбрать две розовые гвоздики из имеющихся четырех воз-

можно

C42 = 2!4!2! = 41 32 = 6

способами. Поэтому букет из одной красной и двух розовых гвоздик можно составить по правилу умножения C101 C42 = 10 6 = 60 способами.

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

Решение. Благоприятствующий исход здесь один - правильный выбор последних цифр (m = 1). Всех возможных исходов n здесь столько же, сколько существует комбинаций из 3-х цифр, порядок которых имеет значение. Таким образом,

n= A103 = 720

ивероятность целевого события A (того, что номер набран правильно):

P (A) = mn = 7201 :

Пример 13. Среди 100 колес 5 нестандартных. Для контроля выбирается 7 колес. Найти вероятность того, что среди них будет ровно 3 нестандартных.

Решение. Число всех возможных исходов равно количеству комбинаций из 100 колес по 7 штук, т.к. порядок значения не имеет, то n = C1007. Благоприятствующий исход состоит в выборе ровно 3 нестандартных колес из 5 и совместном выборе (7-3) стандартных колес из (100-5), при этом порядок значения не имеет. По правилу произведения

m = C53 C954

32

. Следовательно, вероятность того, что среди взятых для контроля колес будет ровно 3 нестандартных (целевое событие A):

2.3.2Комбинаторные формулы-задачи

1 Сколько четных положительных чисел можно составить из цифр числа 13754, если каждую цифру можно использовать в записи не более 1 раза?

2 Сколькими способами можно составить трехцветный флаг, если имеется материал пяти различных цветов?

3Необходимо доставить рекламные проспекты в 6 различных фирм. Сколькими способами это могут сделать трое курьеров?

4В коробке 48 шариковых ручек и 3 гелевых. Наудачу извлекают одну ручку и, не возвращая ее обратно, извлекают еще одну. Какова вероятность того, что последняя рука шариковая, если первая извлеченная ручка - гелевая?

5В группе 25 студентов, среди них 5 отличников. Выбирают по списку 10 студентов. Найти вероятность того, что среди них окажется 3 отличника.

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

2.4.1Количество информации-задачи с решениями

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

33

Решение. Вероятность того, что монетка упала гербом, равна p = 12. Поэтому проведение данного испытания дало нам:

I = log p = log 12 = log 2 = 1bit;

т.е. один бит информации.

Пример 15. В ящике 10 гранат, из которых 8 без взрывателя. Из ящика наудачу выбираются 3 гранаты. Какое количество информации содержится в сообщении о том, что все выбранные гранаты оказались без взрывателя?

Решение. Определим вероятность выбора из ящика 3-х гранат без взры-

вателя:

p = 108 79 68 = 157 = 0:467:

Количество информации в данном сообщении определяется по формуле:

I = log p = log 157 = 1:1bit

.

Пример 16. В группе 20 курсантов, среди которых 4 отличника, 6 хорошистов, 7 троечников, остальные двоечники. По списку наудачу отбираются 5 курсантов. Какое количество информации содержится в сообщении о том, что среди отобранных курсантов 3 отличника, 1 хорошист и 1 троечник?

Решение. Используем понятие т.н. обобщенной гипергеометрической вероятности, используемое, когда интересующие объекты не возвращаюся в выборку. Достаточно очевидно, что общее количество исходов определяется, как CNM = C205, в то же время, число благоприятных исходов по комбинаторному правилу произведения определяется, как:

Cnm11 Cnm22 Cnm33 Cnm44 = C43 C61 C71 C30:

34

Итоговое значение вероятности совпадает с формулой гипергеометрического распределения и равно:

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

I= log P = log 0:011 = 6:528bit:

2.4.2Количество информации-задачи

1В отделе работают 6 мужчин и 4 женщины. По табельным номерам наудачу отобраны 7 человек. Какое количество информации содержится в сообщении о том, что среди отобранных лиц окажутся 3 женщины?

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

3Имеются изделия четырех сортов, причем число изделий каждого

сорта равно n1 = 2; n2 = 3; n3 = 1; n4 = 3. Для контроля наудачу берутся 5 изделий. Какое количество информации содержится в

сообщении о том, что среди них m1 = 2 - первосортных; m2 = 1 - второго, m3 = 0 - третьего и m4 = 2 - четвертого сорта?

4Таможенный контроль проходят 3 таджика, 4 грузина и 6 азербайджанцев. На досмотр наудачу вызывают трех человек. Какое количество информации содержится в сообщении о том, что все три вызванных являются грузинами?

35

Лекция 3

Свойства энтропии. Взаимная информация. Непрерывные случайные величины

3.1Энтропия

3.1.1Свойства дискретной энтропии

Энтропия - это важнейшее понятие в теории информации. Рассмотрим далее свойства энтропии и доказательства их корректности:

Свойство 1. Энтропия – вещественная и неотрицательная величина:

H(U) 0.

Доказательство.

По определению, энтропия H(U) сообщения U определяется по формуле

m

X

H = Pi log Pi:

i=1

Каждое слагаемое в данной сумме является неотрицательным. Действительно:

1.8i 1 i Npi 2 [0; 1]:

2.Для указанных значений p log p 0 ) pi log pi > 0, что и требо-

валось доказать.

3. H(U) = 0 тогда и только тогда, когда какой-то k-й из исходов является достоверным (pk = 1, соответственно 8pi; i 6= k). Данное утверждение доказывается от противного – 8pi; 0 < pi < 1 все pi log pi > 0, что и требовалось доказать.

36

Свойство 2. Для произвольного источника информации значение энтропии удовлетворяет неравенству H(U) log N, где N - объем алфавита источника, при этом max H(U) = log N для случая n равновероятных исходов: pi = n1 ; i = 1 : : : n.

Доказательство.

1. Рассмотрим разность H(U) log N:

что и требовалось доказать. Из этого же равенства, а также из 3.2 следует,

Для рассмотрения следующего свойства энтропии введем понятие объединения источников сообщений (без ограничения общности - для случая двух источников сообщений):

Объединением источников сообщений U и Z c объемами алфавита

N и M соответственно понимают обобщенный источник сообщений U; Z, характеризующийся совместными вероятностями P (U; Zj) всех возможных комбинаций, выбираемых из алфавита размерностью N M

37

Свойство 3. Свойство аддитивности энтропии:

Энтропия объединения нескольких независимых источников сообщений равна сумме их исходных значений энтропии:

K

X

H(U1; U2; : : : ; UK) = H(Uk):

k=1

Доказательство.

1. Не теряя общности, ограничимся рассмотрением объединения двух источников U и Z с объемами алфавита, соответственно, N и M. Энтропия такого объединенного источника определяется по формуле:

=1 j=1

2. Для случая статистической независимости U и Z P (U; Zj), тогда:

3.1.2Условная энтропия и взаимная информация

Часто необходимо определить энтропию сложного опыта U; Z для случая, когда U и Z не являются независимыми - т.е. если на исход источника U влияет результат опыта Z. Элементарным примером является случай с нахождением в некотором ящике всего двух разноцветных шаров, когда результат U состоит в извлечении первого шара, а Z - второго. Для этого случая H(U; Z) = H(U), а не H(U) + H(Z) согласно озвученному выше правилу аддитивности.

Итак, пусть источники U и Z являются зависимыми. Тогда, согласно

2.15:

38

P (U; Z) = P (U) P (ZjU); log P (U; Z) = log P (U) + log P (ZjU): (3.6)

Используя 3.4, получаем следующий вывод для энтропии описанного сложного опыта:

NM

XX

H(U; Z) = P (Ui; Zj) log P (Ui; Zj) =

i=1 j=1

NM

N M

XX

@P (Ui) P (ZjjUi) log P (ZjjUi)A

i=1 j=1

полная условная энтропия или просто условная энтропия источника

Z по отношению к источника U.

39

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

при этом HU (Z) = 0, когда по сообщению источника U возможно точно определить сообщение источника Z1 и HU (Z) = H(Z), когда источники U и Z независимы и знание реализации U ничего не говорит о реализации

Z.

Итак, в общем случае HU (Z) < H(Z) и знание реализации U снижает первоначальную неопределенность Z. На основании сделанного вывода возможно ввести специальную информационную характеристику двух зависимых источников U и Z - так называемую взаимную информацию.

Взаимная информация - количество информации, содержащееся в U относительно Z и равна:

Взаимная информация определяется в тех же единицах, что и энтропия2. Величина I(Z; U) показыает, сколько в среднем бит информации о реализации сообщения источника Z дает наблюдение о реализации сообщения источника U.

Определим I(Z; U) с использованием выражений 3.7, 3.9 и 3.11, а

1Такой случай идентичен каналу связи без помех, когда Z - сообщение, переданное по каналу связи, а U - сообщение, принятое на приемной стороне

2В битах, детах и натах, см. лекцию 1.

40