§28. Вероятностный подход к кодированию информации
ИнфоКонсалтинг
Образовательный сервис


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

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

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

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

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

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

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

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

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

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

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

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


§28. Вероятностный подход к кодированию информации




§28. Вероятностный подход к кодированию информации

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

Теперь же мы опишем ситуации, в которых (если говорить о строках и символах) не будем точно знать, сколько и каких конкретно символов содержится в строке, в каком порядке они в ней следуют, какое количество информации в себе несут. Учитывая, что любой символ в его графической интерпретации — всего лишь "образ" для некоторого события, перефразируем: в этом параграфе, а также в §29 и §30 мы рассмотрим, как количество передаваемой информации зависит от реализации различных событий из некоторого их набора. Тем самым мы осуществим вероятностный подход к оценке количества информации, возможностям её кодирования.

Поясним, что такое вероятность.

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

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

неотрицательность;

нормированность.

Далее покажем, в чём заключён смысл этих свойств.

Свойство неотрицательности декларирует, что значение вероятности всегда лежит на отрезке [0;1].

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

Это свойство можно выразить формулой. Пусть p — это суммарная вероятность всех событий, pi — вероятность реализации i-го события в отдельности, N — общее количество событий. Тогда справедливо равенство (28.1).

(28.1)
Свойство нормированности вероятности
(28.1)

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

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

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

Если имеется M наборов возможных событий, то применительно к вероятностям выбора наборов (короче: вероятностям наборов) по-прежнему актуальны свойства вероятности. В частности, выделим свойство нормированности, по которому сумма вероятностей всех наборов, где k-му набору соответствует вероятность pk, равна единице, — см. (28.2):

(28.2)
Сумма вероятностей наборов событий равна 1 — свойство нормированности вероятности
(28.2)

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

Обозначим условную вероятность через p' (в общем виде). Тогда условная вероятность p'k для k-го набора (того, который оказался выбранным) равна единице, поскольку, как мы видим из (28.3), она составлена из условных вероятностей p'ki входящих в него возможных событий (Nk — количество всех возможных событий k-го набора):

(28.3)
Сумма условных вероятностей событий одного набора равна 1
(28.3)

Общая же вероятность i-го возможного события pki, принадлежащего k-му набору, может быть вычислена по формуле (28.4):

(28.4)
Вероятность возможного события есть произведение вероятности набора и условной вероятности события
(28.4)

Можно также сказать, что вероятность k-го набора pk представляется суммой общих вероятностей входящих в него событий, как это показано в формуле (28.5), однако вероятности событий набора чаще всего (но не всегда) определяются вероятностью набора, ведь сначала выбирают набор!

(28.5)
Вероятность набора событий складывается из вероятностей возможных событий, входящих в набор
(28.5)

Тогда совершенно естественной представляется и формула (28.6):

(28.6)
Сумма вероятностей всех событий из всех наборов равна 1
(28.6)

На следующих ниже примерах можно проследить эти закономерности (см. Примеры 2 — 5).

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

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

  • 5

    • Задача. Игральная кость, на грани которой нанесены обозначения чисел от 1 до 6, бросается два раза. Какова вероятность p того, что сумма выпавших в процессе обоих бросаний чисел составит не менее 9?


      Решение. События выпадения числа в процессе бросания можно считать равновероятными. Положим, что имеется шесть наборов событий по шесть событий в каждом. Первый набор назовём "выпадение 1 при первом бросании", второй — "выпадение 2 при первом бросании", и т. д. События наборов называются "выпадение 1 при втором бросании", "выпадение 2 при втором бросании", и т. д.

      Заметим, что вероятность каждого набора pk = 1/6, условная вероятность каждого события в любом наборе p'ki = 1/6.

      Очевидно, что если выпадает первый или второй набор, то сумма чисел за два бросания составит не более 8, следовательно, эти наборы можно не рассматривать. Достаточно выявить события наборов, для которых k + i ≥ 9.

      Если выпадает третий набор, то возможен вариант, при котором сумма будет равна 9, но только в том случае, если в процессе второго бросания выпадет число 6. Согласно (28.4), вероятность этого события p36 = 1/6 × 1/6 = 1/36.

      По аналогии покажем вероятности интересующих нас событий для четвёртого набора: p45 = p46 = 1/6 × 1/6 = 1/36.

      Для пятого набора: p54 = p55 = p56 = 1/6 × 1/6 = 1/36.

      И для последнего набора: p63 = p64 = p65 = p66 = 1/6 × 1/6 = 1/36.

      Мы обратили внимание на 10 интересующих нас событий, каждое из которых обладает вероятностью 1/36. Поскольку имеется формула (28.6), позволяющая складывать вероятности возможных событий, то и мы сложим вероятности выделенных нами событий.

      Ответ. p = 5/18 ≈ 0,28, или около 28%.

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

Закон, который в общем случае иллюстрирует зависимость количества получаемой информации Iki при совершении конкретного i-го события из k-го набора от условной вероятности реализации p'ki именно этого события и общего количества событий Nk набора, можно описать системой (28.7):

(28.7)
Количество информации при совершении события прямо пропорционально количеству возможных событий и обратно пропорционально условной вероятности совершения именно этого события
(28.7)

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

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

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

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



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


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

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

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



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