§30. Кодирование информации о совершённых событиях
ИнфоКонсалтинг
Образовательный сервис


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

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

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

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

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

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

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

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

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

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

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

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


§30. Кодирование информации о совершённых событиях




§30. Кодирование информации о совершённых событиях

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

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

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

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

В предыдущих примерах, как и подобных им, знанию идентификатора события не сто́ит придавать большое значение. Разные наблюдатели по-разному воспринимают этот идентификатор, если вообще его воспринимают, поэтому во многих случаях совершенно не важно, какое конкретное содержимое несёт в себе идентификатор события, имеющийся в сообщении. Благодаря особенностям наблюдателей содержимое идентификатора события воспринимается по-разному, субъективно. Однако ни в коем случае нельзя говорить о его отсутствии, и причина тому следующая: количество информации (т. е. длина идентификатора, выраженная в некоторых единицах информации) в общем случае определяется только вероятностью возможного события, а, как было описано в §28, чем менее ожидаемо событие, тем больше информации приносит его совершение, и наоборот. Проиллюстрировать это утверждение может Пример 4.

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

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

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

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

Пусть алфавит идентификаторов событий одного и того же набора образован s знаками, соответствующими s возможным состояниям прототипа некоторой единицы информации, и при этом каждый идентификатор имеет длину I знаков. Тогда мы можем, ещё не зная количества возможных событий набора, оценить количество информации, которая будет передана при совершении любого из этих событий. Но лишь при условии, что все события набора равновероятны! Это можно увидеть из Примера 5.

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

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

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

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

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

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

количества разрядов идентификатора события (информационной ёмкости сообщения о совершении события);

особенности организации набора (упорядоченный или неупорядоченный);

способа выбора состояния прототипа единицы информации для заполнения каждого разряда идентификатора события соответствующим состоянию знаком алфавита (с возвращением или без возвращения).

Осталось представить зависимости количества событий в наборах, организованных по-разному, в виде формул. Рассмотрим все возможные случаи.

Пусть имеется упорядоченный набор событий, идентификаторы которых состоят из I знаков предложенного алфавита, и при формировании идентификаторов использование каждого из s возможных знаков осуществлялось на основе выбора с возвращением. Тогда количество возможных событий такого набора описывается формулой (30.1):

(30.1)
(30.1)

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

Действительно, если идентификатор содержит I разрядов, в каждом из которых может находиться один из s знаков, то количество всех возможных сочетаний знаков формула (30.1) и показывает. Если понимать это, то некоторые дополнительные ограничения, накладываемые на формирование идентификаторов или, в общем понимании, чисел, не вызовут сложностей. Такие усложнения можно видеть на Примерах 7 и 8.

  • 7

    • Задача. Сколько существует трёхзначных десятичных чисел, не начинающихся с цифры 5?


      Решение. В данной задаче мы видим упорядоченный набор чисел, которые формируются методом выбора с возвращением (цифры в числах могут повторяться). Поэтому для её решения можно было бы использовать формулу (30.1), ведь надо найти количество чисел! Однако мы видим следующие ограничения: 1) первой цифрой искомых чисел не может быть 5 (по условию) и 2) первой цифрой искомых чисел не может быть 0 (первой цифрой чисел является значащая). Значит, прямое применение формулы (30.1) оказывается невозможным, и требуется подразделить все числа на несколько наборов, которые тоже будут упорядоченными, а сами числа этих наборов также будут формироваться методом выбора с возвращением.

      Заметим, что последние две цифры всех чисел могут быть любыми, а на месте первой может быть одна из восьми (любая, кроме 0 и 5). Тогда все составленные подобным образом числа могут быть распределены в 8 наборов, общим названием которых может стать "первая цифра числа …". Числа этих наборов образованы двумя последними цифрами исходных чисел. Тогда в каждом наборе будет содержаться Ni = 10 2 = 100 чисел. Поскольку всего наборов — 8, то общее количество чисел в 8 раз больше, т. е. 800.

      Ответ. N = 800.

  • 8

    • Задача. Рассматриваются все четырёхзначные десятичные числа, содержащие две цифры 9 в соседних разрядах, в других разрядах цифра 9 отсутствует. Сколько есть таких чисел?


      Решение. Первоначально мы видим три набора, в которые можно сгруппировать такие числа. Первый включает все числа, начинающиеся с двух цифр 9 (условно назовём его 99XX), второй — числа, в которых две цифры 9 находятся в середине (X99X), числа третьего набора оканчиваются двумя цифрами 9 (XX99). По условию задачи других конструкций чисел быть не может.

      Рассмотрим набор 99XX. В его числах есть любые, не содержащие в разряде единиц и разряде десятков цифру 9, значит, числа, составленные двумя последними цифрами исходных чисел, основаны на алфавите, состоящем из девяти знаков (все десятичные цифры, кроме 9), т. е. s = 9. Тогда N99XX = 9 2 = 81.

      Набор X99X придётся разделить ещё на 8 наборов, поскольку первой цифрой чисел с такой структурой может быть одна из восьми (см. Пример 7), а последней — одна из девяти. Таким образом, каждый из восьми наборов, условно называющихся "первая цифра числа …", содержит 9 чисел, и набор X99X включает в себя 72 возможных числа.

      Набор XX99 имеет такую же структуру, как и набор X99X, потому он тоже включает 72 возможных числа.

      Общее количество чисел, соответствующих условию задачи, определяется суммой количества чисел из рассмотренных наборов: N = N99XX + NX99X + NXX99 = 81 + 72 + 72 = 225 (чисел).

      Ответ. N = 225.

Если представлен упорядоченный набор событий, идентификаторы которых, состоящие из I знаков, формировались выбором из s знаков алфавита без возвращения, то количество событий такого набора можно найти, используя формулу (30.2):

(30.2)
(30.2)

В Примере 9 показана ситуация, при которой полезна формула (30.2), а в Примере 10, благодаря введению дополнительного условия, она применяется даже дважды.

  • 10

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


      Решение. Предположим, что нулём может начинаться любое трёхзначное число. Тогда все числа, которые можно составить по правилам условия задачи (I = 3), образуют упорядоченный набор. Поскольку каждая цифра может присутствовать в любом числе только один раз (израсходованная карточка не может быть использована повторно!), то можно заключить, что выбор знаков из алфавита в 5 цифр (s = 5) осуществляется методом без возвращения.

      Подставляя в формулу (30.2) значения s и I, меняя целое i от 0 до 2 (т. е. до значения I – 1), найдём количество трёхзначных чисел N0, которые могут начинаться любой цифрой, в т. ч. и нулём: N0 = 5 × 4 × 3 = 60 (чисел).

      Это решение не является окончательным, т. к. мы предположили, что числа могут начинаться нулём. Теперь из всех чисел нужно исключить такие, первой цифрой которых является нуль. Для этого сгруппируем все возможные числа в два набора, в один из которых войдут имеющие лидирующий 0 (назовём этот набор 0XX), а в другой — все остальные. Количество остальных чисел нам и требуется узнать. Но, если мы уже знаем общее количество чисел и сможем вычислить их количество в наборе 0XX, то легко определим искомую величину вычитанием.

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

      А таких карточек уже 4, так что s = 4 (ведь 0 использовать нельзя). Полагая теперь I = 2, применим формулу (30.2) и получим N0XX = 4 × 3 = 12 (чисел).

      Отвечая на вопрос задачи, находим N = N0 – N0XX = 48 (чисел).

      Ответ. N = 48.

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

(30.3)
(30.3)

Один из случаев, при котором можно наблюдать упорядоченный набор событий с идентификаторами, формируемыми методом выбора без возращения, при I = s, можно увидеть в Примере 11.

  • 11

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


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

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

      Перейдём к вычислениям. В нашей ситуации I = s = 6, так что можно использовать формулу (30.3): N = 6 ! = 1 × 2 × 3 × 4 × 5 × 6 = 720 (способов).

      Ответ. N = 720.

Теперь рассмотрим неупорядоченный набор событий, идентификаторы которых формируются методом выбора с возвращением. По-прежнему длина каждого идентификатора составляет I знаков, а каждый знак выбирается из числа s имеющихся в алфавите. Количество возможных событий такого набора вычисляется с помощью формулы (30.4):

(30.4)
(30.4)

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

  • 12

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


      Решение. Коммутативность умножения предполагает возможность перестановки множителей, от которой, как известно, произведение не меняется. Так, если имеются множители 4 и 7, можно выбирать столбец 4 и строку 7, а можно столбец 7 и строку 4, — в любом случае на их пересечении окажутся результаты умножения одного и того же. Другими словами, идентификаторам '47' и '74' соответствует одно и то же событие, — результат умножения чисел 4 и 7, — что недопустимо для неупорядоченного набора (заметим, что в упорядоченном наборе эти идентификаторы соответствуют разным событиям, потому что организация упорядоченного набора подразумевает чёткое знание о том, что, как в данном случае, является первым множителем, а что вторым). И, конечно, идентификаторы должны составляться так, чтобы набор событий позволял отобразить результат умножения числа на самого себя. Следовательно, формирование идентификаторов происходит с использованием метода выбора с возвращением.

      Учитывая, что нулевой множитель отсутствует, полагаем s = 9. Поскольку умножаются два однозначных числа, I = 2. Подставляя значения в формулу (30.4), получаем: N = 1/2 × ( 9 × 10 ) = 45 (произведений уникальных пар чисел).

      Ответ. N = 45.

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

(30.5)
(30.5)

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



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


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

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

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



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