§29. Количество информации при совершении события
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

02.10.2017 С наступающим Днём Учителя, дорогие наши учителя!

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


§29. Количество информации при совершении события


Найти репетитора

§29. Количество информации при совершении события

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

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

Количество информации, получаемое при реализации события из одного и того же набора, при условии, что все возможные события этого набора равновероятны, можно вычислить, пользуясь ранее показанной (в §25) формулой Хартли, только выглядит она немного по-другому — см. (29.1):

(29.1)
(29.1)

Здесь Nk — количество возможных событий k-го набора, s по-прежнему показывает количество состояний, в которых может оказаться выбранная единица информации.

Если количество измеряемой информации должно выражаться в битах, то запись формулы (29.1) становится несколько проще — как (29.2):

(29.2)
(29.2)

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

(29.3)
(29.3)
  • 2

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


      Решение. Особенность формул (29.1) и (29.2) состоит в том, что количество информации не точно равно логарифму, но значение логарифма требуется округлять до целого с избытком. Поэтому в данном случае дать ответ, выраженный единственным числом, невозможно. Так что рассмотрим "пограничные" ситуации.

      1. Найдём минимальную вероятность pi min (и, одновременно, наибольшее количество возможных событий Nmax, которые могут быть в наборе). Для этого положим ⌈log2 N⌉ = log2 Nmax = 5, откуда следует, что Nmax = 32, значит, pi min = 1 / 32 = 0,03125.

      2. Найдём максимальную вероятность pi max (и, одновременно, наименьшее количество возможных событий Nmin, которые могут быть в наборе). Для этого положим ⌈log2 N⌉ – 1 = log2 ( Nmin – 1 ) = 4, значит, Nmin = 17 и pi max = 1 / 17 ≈ 0,05882.

      Обратите внимание, что ( Nmin – 1 ) — это максимальное целое число, с которым логарифм по основанию 2 равен 4, а Nmin — это минимальное целое число, при котором тот же логарифм больше 4, т. е. его значение округляется с избытком до 5.

      Ответ. 0,03125 ≤ pi ≲ 0,05882.

Сравните формулу (29.3) с формулой (28.7) из предыдущего параграфа! Из-за того, что, как показано в (29.3), применительно к равновероятным событиям имеется обратная пропорциональность между количеством возможных событий в наборе и их вероятностью, формулу Хартли можно представить в одном из видов (29.4):

(29.4)
Формула Хартли
(29.4)

Часто наблюдаются ситуации, при которых равновероятные события распределены в несколько наборов, а выбор между наборами также представляется равновероятным. При этом наборы могут содержать разное количество возможных событий. Тогда и получаемая от совершения события из одного набора информация с количественной точки зрения может существенно отличаться от той, которая могла быть получена, если бы совершилось событие из другого набора. Ведь, как показывает формула (29.4), количество информации зависит от условной вероятности события в наборе! В любом случае общее количество информации выражается формулой (28.8) (см. предыдущий параграф). А вот при определении количества информации, передаваемой в момент обращения к набору, нужно руководствоваться лишь определением набора, ведь обращение к нему — это тоже событие. Так что формулы настоящего параграфа справедливы и для оценки количества информации при реализации набора. Решение подобной задачи можно увидеть в Примере 3.

Неравновероятные события при своей реализации образуют разное количество информации. В идеале такое количество информации можно определить, построив дерево Хаффмана (см. §26), используя в нём в качестве символов идентификаторы событий, а вместо количества символов — вероятности событий. Но подобные ситуации мы рассматривать не будем, поскольку, как было отмечено в начале параграфа, для решения задач нами используется только принцип равномерного кодирования. Разберёмся с более простыми случаями, когда равномерное кодирование действительно можно применить к анализу неравновероятных событий. Для этого в Примерах 4 — 8 тексты задач будем дополнять условиями, при которых допустимо использование равномерного кодирования (которое, кстати, требуется применять при решении заданий ЕГЭ по информатике как достаточное средство определения правильного ответа).

В задачах может встретиться неопределённость в количестве событий одного или нескольких наборов. Тогда задача может иметь множество решений, как это было продемонстрировано в Примере 2. В Примерах 4 — 6 нам тоже придётся наблюдать это явление, и решение будет приведено, как и в Примере 2, в общем виде. При этом в Примере 6 показан случай единственного решения, связанного с нахождением значения максимальной информационной ёмкости. Надо понимать, что если к задаче прилагаются варианты ответов, как в контрольных измерительных материалах ЕГЭ по информатике, то правильный будет лежать во множестве, показанном общим решением.

Встречаются неопределённости, связанные и с количеством наборов. Решение задач, при котором выявляются такие неопределённости, в общем виде может содержать весьма обширный ответ, предполагающий разные условия. Но если к подобной задаче приложены варианты ответов, то подходящий (не скажем правильный, ведь правильный не единственный и зависит от разных условий) придётся искать согласно общему решению. Некоторые общие решения можно увидеть из Примеров 7 и 8.

  • 7

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


      Решение. Обозначим общее количество возможных событий буквой Q: Q = 15. Информационная ёмкость сообщения описывается формулой (28.8), где k ∈ {1, 2, … M}, а i ∈ {1, 2, … Q – M + 1} (попробуйте объяснить, почему это так; для этого полезно проанализировать Примеры 5 и 6). В нашем случае информационная ёмкость сообщения, которая может быть максимальной, будет определяться как Iсообщения = ⌈log2 M⌉ + ⌈log2 ( 16 – M )⌉.

      Максимальное количество наборов Mmax = Q (тогда каждое событие будет содержаться в собственном наборе и, кстати, его совершение не будет приносить никакой информации; сообщение будет касаться лишь набора). Значение Mmax нужно знать только для того, чтобы увидеть, каких максимальных значений может достигать первое слагаемое в формуле нахождения информационной ёмкости. При Q = 15 ⌈log2 Mmax⌉ = 4, т. е. Iнабор max = 4. Рассмотрим, при каких значениях M первое слагаемое ⌈log2 M⌉ = Iнабор max, и оказывается, что при 9 ≤ M ≤ Q, т. е. при 9 ≤ M ≤ 15.

      Для полученных значений M узнаем, сколько событий может быть в наборах, чтобы информационная ёмкость сообщения оказалась максимальной. Для этого рассмотрим, при каких условиях второе слагаемое может получить максимальные значения при известных M. Положим, что во всех наборах, кроме M-го, содержится по одному возможному событию. Тогда в M-ом наборе будет Q – M + 1 возможных событий (при Q = 15 в M-ом наборе содержится 16 – M событий). Величина 16 – M получает наибольшее значение при M = 9, так что второе слагаемое имеет максимальное значение Iсоб max = ⌈log2 ( 16 – M )⌉ = 3. Но второе слагаемое имеет максимальное значение и при M = 10, и при M = 11, а это означает, что мы нашли решение задачи: при M ∈ {9, 10, 11} Iсообщения max = 4 + 3 = 7 (бит).

      Это ещё не всё. Слагаемые, составляющие 7 бит, разные по смыслу, и, следовательно, их числовые значения можно поменять местами. Но от этого изменится множество значений M, при которых информационная ёмкость по-прежнему максимальна!

      Положим второе слагаемое формулы Iсоб max = ⌈log2 ( 16 – M )⌉ = 4 (т. к. при Q = 15 большего значения у него быть не может). Тогда 1 ≤ M ≤ 7, и теперь определимся, при каких из полученных значений M первое слагаемое максимально. Подставляя возможные значения в ⌈log2 M⌉, убеждаемся, что M ∈ {5, 6, 7}, т. е. теперь Iсообщения max = 3 + 4 = 7 (бит). Столько же, естественно, но значения M другие!

      Ответ. M ∈ {5, 6, 7, 9, 10, 11}.

  • 8

    • Задача. В лотке перемешаны 28 шаров, среди которых имеется хотя бы один красный. Истинное сообщение, содержащее информацию об извлечении конкретного шара конкретного цвета, не совпадающего с красным, несёт в себе 3 бита информации. Сколько красных шаров в лотке? Считать возможности извлечения шаров различных цветов равновероятными.


      Решение. Согласно формуле (28.8), информационная ёмкость сообщения включает информацию о цвете (наборе) и о самом шаре, поэтому в предложенные 3 бита должна входить и та, и другая информация. Обозначим возможное количество цветов M (M > 1).

      Пусть M = 2. Тогда информации о цвете выделяется 1 бит, а два бита — информации о самом шаре. Получаем, что количество не-красных шаров — 3 или 4, значит, красных — 24 или 25: Nкрас ∈ {24, 25}.

      Пусть M ∈ {3, 4}. Тогда информации о цвете выделяется 2 бита, а один бит — информации о самом шаре. Получаем, что количество шаров одного любого цвета, кроме красного, — 2, значит, красных шаров — 20 или 22: Nкрас ∈ {20, 22}.

      Пусть M ∈ {5, 6, 7}. Тогда информации о цвете выделяется 3 бита, а информация о самом шаре отсутствует. Получаем, что количество шаров одного любого цвета, кроме красного, может быть только 1, значит, красных шаров — от 21 до 23: Nкрас ∈ {21, 22, 23}.

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

      Ответ. Nкрас min = 20, Nкрас max = 25.

      А вот если бы вопрос этой задачи был сформулирован по-другому, например, "может ли в лотке быть 23 красных шара", то на него следовало бы (заметьте, однозначно!) ответить утвердительно.



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика