Вопросы и задачи

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

Решение. Вероятность того, что староста группы — девушка, равна Р = 3/24 = 1/8 (считаем, что решение о назначении старосты не зависит от пола студента). По формуле (2.4) количество информации в таком сообщении равно-log₂P = -log₂1/8 = 3 (бита).^{[1][2][3][4][5][6]}

• 7. Нам сказали, что сумма чисел у кости домино равна 4. Какое количество информации нам сообщили?
• 8. Нам сообщили, что у кости домино числа разные. Какое количество информации нам сообщили? Какое количество осталось сообщить, чтобы однозначно определить кость домино?
• 9. Мы сказали продавцу, что хотим купить коньки. Коньки бывают обычные и роликовые, белого, черного и зеленого цветов, есть размеры 38, 39, 41 и 42. Какое количество информации нужно сообщить продавцу?
• 10. Бросаются одновременно две игральные кости. Определить количество информации, содержащееся в сообщении о том, что сумма числа выпавших очков больше 4.
• 11. Сообщение содержит 32 Кбайта информации. Оно состоит из 64 страниц, на каждой странице по 16 строк, разбитых на 4 абзаца, в каждой строке 64 символа. Найти мощность алфавита такого сообщения.
• 12. Два стрелка производят по одному выстрелу в мишень. Вероятности попадания для них равны соответственно 0,8 и 0,7. Какое количество информации содержится в сообщении о том, что мишень поражена?
• 13. Магазин торгует бытовой техникой ценой до 25 тыс. руб. Плотность распределения вероятности покупки в зависимости от цены товара представлена на рисунке.

• 30% посетителей покидают магазин без покупки. На выходе из магазина покупателей опрашивает маркетинговая группа, которая выясняет стоимость покупки и заполняет анкету. В анкете четыре позиции: 1) без покупки; 2) покупка на сумму до 5 тыс. руб.; 3) покупка на сумму от 5 до 10 тыс. руб.; 4) покупка на сумму свыше 10 тыс. руб. Маркетологи опросили 100 посетителей магазина. Какое количество информации они получили?
• 14. Температура t холодильной камеры является случайной и распределена по закону, плотность вероятности которого представлена на рисунке.

Датчик температуры измеряет ее один раз в две минуты и в зависимости от результата измерения передает в систему управления одну из команд: «повысить температуру», если t < 4; «снизить температуру», если t > 6. При иных значениях температуры команда не передается. Какое количество информации поступает в систему управления за 1 ч?

Пример. Имеются два ящика, в каждом из которых по 12 шаров. В первом — 3 белых, 3 черных и 6 красных; во втором — по 4 шара каждого цвета. Опыты состоят в вытаскивании по одному шару из каждого ящика. Каково количество информации, содержащееся в сообщении об исходе опыта?

Решение. Вероятности исходов опыта для первого ящика: р_6ел= 3/12, Рчер =3/12, р_крас = 6/12. Сообщение об исходе опыта содержит один символ, всего в алфавите источника сообщений 3 символа («белый», «черный», «красный»). Вероятности каждого символа равны вероятностям соответствующих исходов опыта. По формуле (2.6):

Вероятности исходов опыта для второго ящика:

• 15. Перед нами пять черных ящиков. В каждом из них находится либо черный, либо белый шарик. Нам говорят, что три шарика белые. Какое количество информации мы получили?
• 16. Перед нами N черных ящиков. В каждом из них находится либо черный, либо белый шарик. Нам говорят, что 60% шариков — белые. Какое количество информации мы получили?

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

Решение. В данном случае п = 2 и события равновероятны, т. е. Согласно (2.6),

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

Решение. Исходами в данном случае являются: А_} — «задуман О», А₂ — «задумана 1», А₃ — «задумана 2», А_а — «задумана 3». Конечно, предполагается, что вероятности быть задуманными у всех чисел одинаковы. Поскольку п = 4, следовательно, р (АЦ = ¼, log₂ р (Л,) = -2 и / = 2 бит. Таким образом, для полного снятия неопределенности опыта (угадывания задуманного числа) нам необходимо 2 бит информации.

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

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

Пример. В Белгороде 340 000 жителей¹. Какое минимальное количество вопросов, требующих ответа «да» или «нет», необходимо, чтобы однозначно найти одного жителя?

Решение. Каждый житель — элемент случайной системы, количество элементов т = 340 000. Ответ на один вопрос дает 1 бит информации, следовательно, количество информации равно количеству вопросов. По формуле Хартли 1 = п • log₂m. /= log₂340 000 = 18,4 (бит). Округляя в большую сторону, получаем ответ — 19 вопросов.

• 17. Коля съел на перерыве шоколадку, яблоко и кекс. Сколько бинарных вопросов надо задать, чтобы узнать, в какой последовательности он их съел?
• 18. Случайным образом вынимается карта из колоды в 32 карты. Какое количество информации требуется, чтобы угадать, что это за карта? Как построить угадывание?
• 19. В университете 12 000 студентов. Какое минимальное количество вопросов, требующих ответа «да» или «нет», необходимо, чтобы однозначно найти одного студента.
• 20. Орудие стреляет по удаленной цели¹. При каждом выстреле она поражается с вероятностью р = 0,1. Разведка может только один раз проверить, поражена ли цель. Через какое количество выстрелов к следует провести проверку, чтобы она дала максимальное количество информации?
• 21. Датчик технологического процесса имеет погрешность 1%. Датчик опрашивается с интенсивностью 5 с. Определить общее количество информации, поступившее от датчика за 2 мин, энтропию и скорость передачи информации датчиком.

Пример. АСУТП посредством АЦП опрашивает потенциометрические датчики Д1 и Д2, имеющие погрешность б, = 0,1% и б₂ = 0,2% соответственно. Датчик Д1 опрашивается с интервалом 0,25 с, датчик Д2 — с интервалом 0,2 с. Определить общее количество информации, поступившее от датчиков за 2 с и скорость передачи информации каждым датчиком.

Решение. Число различных уровней квантования (число символов в алфавитах датчиков):

Количество символов сообщения (отсчетов), поступивших за 2 с:

По формуле (2.5) скорость передачи

Для сравнения: скорость обычной речи — примерно 20 бит/с, муравьи обмениваются информацией со скоростью 0,1 бит/с.

• 22. Символы азбуки Морзе могут появиться в сообщении с вероятностями: для точки — 0,51, для тире — 0,31, для промежутка между буквами—0,12, между словами—0,06. Определить среднее количество информации в сообщении из 500 символов данного алфавита, считая, что связь между последовательными символами отсутствует¹.
• 23. Для передачи сообщений используется алфавит из 32 прописных русских букв² (не используется «Ё»), Все передаваемые слова содержат ровно по 8 букв. Каждое передаваемое слово начинается с одной из четырех букв (К, Л, М, Н). Остальные буквы в каждом слове могут быть любыми из используемого алфавита. Какое количество информации (в битах) несет произвольная фраза из 10 слов, если для ее кодирования использовалось минимальное количество бит в рамках описанных выше правил?
• 24. Имеется 12 монет одного достоинства; 11 из них имеют одинаковый вес, а одна — фальшивая — отличается по весу от остальных (причем неизвестно, легче она или тяжелее настоящих). Каково наименьшее число взвешиваний на чашечных весах без гирь, которое позволяет обнаружить фальшивую монету и выяснить, легче она, чем остальные монеты, или тяжелее?
• 25. Радиотехническое устройство состоит из 5 блоков (А, Б, В, Г, Д). Блок, А в среднем выходит из строя 1 раз в 100 дней, блок Б — 1 раз в 25 дней, В — 1 раз в 5 дней, Г — 1 раз в 4 дня и Д — 1 раз в 2 дня. Контрольный прибор позволяет за одно измерение проверить работоспособность в целом любой комбинации блоков. Как нужно проводить контроль, чтобы затратить на поиски неисправного блока в среднем минимальное количество проверок? Найти это среднее значение.
• 26. Полиция ищет преступника. На допрос вызван его предполагаемый сообщник, которому, чтобы обезопасить себя от уголовного преследования, надо назвать три правдивых приметы разыскиваемого. Какие приметы он должен сообщить полиции, чтобы дать минимальное количество информации? Рассчитайте это количество информации.

Информация к размышлению:

• 1 Автор задачи — проф. Л. А. Луизова.
• 2 Сюжет задачи взят с олимпиады СПбИТМО.

Окончание таблицы

27. Шпион имеет возможность похитить только три документа, содержащих различную информацию. Какие документы он должен похитить, чтобы количество похищенной информации было максимальным. Рассчитайте это количество информации.

Информация к размышлению (размышлять быстро (c)):

28. Служебная таможенная собака различает 50 запахов запрещенных веществ. На обнюхивание одного объекта она затрачивает 1 мин. Какое количество информации поступает собаке за 2-часовую смену?

Пример. Эллочка-Людоедка знает 20 слов. В обычном состоянии она произносит в среднем 50 слов в минуту. Причем слова «мрак», «жуть», «хо-хо» и «парниша» она произносит в четыре раза чаще других слов. Какое количество информации получит от нее Остап Бендер в течение получасового общения?

Решение. Мощность алфавита Эллочки т = 20. Символы алфавита неравновероятны. Найдем вероятности символов. Пусть вероятности слов «мрак», «жуть», «хо-хо» и «парниша» — р, вероятности остальных шестнадцати слов — р₂. По условию задачи р, = 4р₂. По условию нормировки 1р;= 1.

За полчаса Эллочка произнесет 50 • 30 = 1500 слов. То есть длина такого сообщения п = 1500.

По формуле (2.6) количество информации

• 29. Индеец Чуткое Ухо различает голоса 100 видов птиц. Из них 20 видов встречаются часто — составляют 70% птиц, обитающих в прериях, а 80 видов — редкие птицы. Найти среднее количество информации, содержащееся для индейца в птичьем крике.
• 30. Индеец Меткий Глаз видит бизона на расстоянии до 1800 м и может определить расстояние до него с точностью до 20 м. Найти общее количество информации, которое получает Меткий Глаз о расположении стада бизонов, если в нем находится 20 особей.
• 31. На шахматной доске в одной из клеток поставлена фигура. Вероятность нахождения фигуры на любой клетке одинакова. Определить информацию, получаемую от сообщения с координатами фигуры на доске.
• 32. Во время пожара температура вблизи датчика пожарной

сигнализации распределена по закону ).

При нахождении температуры в диапазоне от 280 до 320 градусов датчик срабатывает с вероятностью р_х = 0,8, при температуре выше 320 градусов датчик срабатывает с вероятностью р₂ = 0,95. Найти количество информации, которое поступает на пульт пожарной охраны во время пожара.

Пример. Алфавит источника сообщений состоит из двух элементов: а и Ь. Рассмотрим случаи передачи информации с помощью этих элементов.

1. Элементы независимы и равновероятны. Количество информации, которое несет каждый символ сообщения (см. формулу (2.5)):

aside class="viderzhka__img" itemscope itemtype="http://schema.org/ImageObject">

где т — мощность алфавита.

2. Элементы независимы и неравновероятны. Пусть ,.

а . Тогда количество информации на один символ составит по формуле (2.6):

3. Элементы взаимозависимы и неравновероятны. Пусть, например,.

Пусть:

 — вероятности повторения символов;

 — вероятности чередования символов.

Чтобы применить формулу (2.7), воспользуемся правилом P (X, Y) =

= P (X)-P (YX).

По формуле (2.7):

Пример. Система X имеет восемь равновероятных состояний. Определить энтропию.

Решение. (бит/символ).

Пример. Источник генерирует зна^ с вероятностью 0,8 и z₂ с вероятностью 0,2. Какова энтропия источника?

Решение. (бит/символ).

33. Определить энтропию системы, состояние которой описывается таблицей.

• 34. Алфавит состоит из букв а, Ь, с, d. Даны вероятности: р_а = р_ь = = 0,25; р_с = 0,34. Найти энтропию источника сообщений.
• 35. Найти число значений т случайной величины Y, все значения которой одинаково вероятны¹. При этом необходимо, чтобы энтропия Y

была равна энтропии случайной величины X, вероятности значений которой заданы таблицей:

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

Решение. Будем считать сообщением А — посылку первого задания на выполнение. Ресурс потребуется с вероятностью Р (Л₁)=2/6=1/3. Ресурс не потребуется с вероятностью Р (А₂)=2/3. Энтропия сообщения А равна:

Сообщение В — посылка второго задания на выполнение. Вероятность того, что потребуется ресурс Р (В_}), зависит от того, какое задание было послано первым.

Следовательно, энтропия сообщения В равна.

Обратим внимание, что энтропия сообщения В оказалась меньше, чем сообщения А. Это естественно, так как, получив информацию об исходе А, у нас уменьшилась неопределенность относительно исхода В. Полная совместная энтропия получается по формуле (2.11):

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

Пример. Имеется три тела с одинаковыми внешними размерами, но с разными массами х_}, х₂ и х₃. Необходимо определить энтропию, связанную с нахождением наиболее тяжелого из них, если сравнивать веса тел можно только попарно.

Решение. Последовательность действий достаточно очевидна: сравниваем вес двух любых тел, определяем из них более тяжелое, затем с ним сравниваем вес третьего тела и выбираем наибольший из них. Поскольку внешне тела неразличимы, выбор номеров тел при взвешивании будет случаен, однако общий результат от этого выбора не зависит. Пусть опыт А состоит в сравнении веса двух тел, например, первого и второго. Этот опыт, очевидно, может иметь два исхода: А_]:х_] >х₂, его вероятность p (AJ = ½; исход А₂: х_} < х₂; также его вероятность р (А₂) = ½.

Опыт В, сравнение весов тела, выбранного в опыте А, и третьего, имеет четыре исхода: В_]:х_у >х₃, В₂:х_]<х₃, В₃:х₂>х₃, В_А:х₂<х₃; вероятности исходов зависят от реализовавшегося исхода А — для удобства представим их в виде таблицы:

Вновь воспользовавшись формулами (2.10) и (2.11), находим:

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

^[7][8]

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

• 1) Z1 —оборудование исправно;
• 2) Z2 — требуется регулировка;
• 3) Z3 — требуется замена отдельных деталей;
• 4) Z4 — оборудование непригодно к эксплуатации.

Условные априорные вероятности каждого исхода в зависимости от истинного состояния оборудования сведены в таблицу:

Насколько уменьшилась неопределенность о состоянии оборудования в результате испытаний?

Решение. Необходимо найти общую условную энтропию С при условии получения сообщения Z: H (C|Z).

Найдем вероятность каждого исхода Z/.

Найдем апостериорную вероятность состояний Cj по формуле Байеса Результаты сведем в таблицу.

Наконец, вычислим общую условную энтропию H (C|Z). По формуле.

(2.10):

Видно, что в результате испытаний неопределенность уменьшилась.

Пример. Найти энтропию непрерывной системы X, все состояния которой на участке от а до Ь равновероятны.

Решение. Плотность вероятности состояний системы Хопределяется функцией:

По формуле (2.13).

Приведенная энтропия

37. Найти энтропию непрерывной системы X, вероятности состояний которой подчинены нормальному закону распределения.

Пример. Устройство управления (УУ) ЭВМ вырабатывает 100 команд, которые могут быть разбиты на 2 группы. 80 команд используются редко и составляют 1% от общего числа используемых команд. 20 команд используются часто — в 99% случаев. Определить избыточность, содержащуюся в командах УУ.

Решение. Вероятность появления команды из первой группы — 1/100; вероятность появления конкретной команды из первой группы 1/8000;

аналогично:

Энтропия разных команд:

Оптимальная энтропия (бит на команду);

избыточность

• 38. В студенческой группе зачет по теории информационных процессов и систем до 1 января не сдали 8 человек, среди которых — один студент из Камбоджи и один студент из Таджикистана. Преподаватель перенес зачет на весенний семестр. Во время повторной сдачи зачета преподаватель спросил у одного из студентов: «Вы сегодня отмечаете Новый год?» Какое количество информации содержит ответ студента? Дополнительные сведения к задаче: в Камбодже Новый год отмечается 3 дня — с 14 по 16 февраля; в Таджикистане Новый год (Навруз) отмечается 3 дня — с 21 по 23 марта; весенний семестр длится 120 дней.
• 39. В конкурсе курсовых проектов участвуют четверокурсники, третьекурсники и второкурсники. В жюри попали один четверокурсник Чантхорн, два третьекурсника Тихон и Тимофей, два второкурсника Вася и Витя. Каждый член жюри определяет своего победителя конкурса. С вероятностью 80% члены жюри Вася и Витя выберут второкурсника, а с вероятностью 20% — четверокурсника. Тихон и Тимофей с вероятностью 60% проголосуют за студентов своего курса, а с вероятностью 40% — за четверокурсника. Чантхорн с равной вероятностью выберет второкурсника или четверокурсника. Какое количество информации содержится в сообщении о победителях конкурса?
• 40. В скачках на ипподроме участвуют 4 лошади: жеребцы Гигабайт (18% побед в скачках), Мегабит (29% побед), Сигнал (31% побед) и молодая кобыла Энтропия. Найти количество информации, содержащееся в сообщении о победителе двух забегов.
• 41. Метод обнаружения сетевых атак, на котором основан алгоритм работы интеллектуального агента, состоит в периодическом вычислении энтропии запросов к серверу базы данных. Если в какой-то момент энтропия запросов изменилась более чем на 30% по сравнению с обычной ситуацией, то интеллектуальный агент объявляет тревогу. В некоторой сети запросы к серверу поступают с девяти IP-адресов (обозначим их *.1, *.2,…, *.9). Балансировка информационных потоков такова, что с IP-адреса *.1 поступает 20% всех запросов, а оставшиеся запросы равномерно распределены по остальным восьми адресам. Однажды замеры интеллектуального агента показали, что в течение 1 мс с IP-адреса *.1 поступило 52 запроса, с IP-адреса *.2 поступило 67 запросов, с IP-адреса *.3 — 33 запроса, с остальных адресов — по 8 запросов. Будет ли объявлена тревога в связи с сетевой атакой?
• 42. В ми-ми-мишном Инстаграммчике находятся фоточки, на которых изображены Няши, Нюши и Плюши. Причем фотографий с Нюшами в 2 раза больше, чем фотографий с Няшами, а фотографий с Плюшами на 12 больше, чем с Нюшами. Сообщение о том, что на случайно выбранной фотографии изображена Нюша, содержит 2 бита информации. Найти количество фотографий с Плюшами^[9].
• 43. Какими свойствами обладает логарифмическая мера информации?
• 44. Из каких соображений получена шенноновская мера информации?
• 45. Что называется энтропией?
• 46. Что такое приведенная энтропия?
• 47. Что такое условная энтропия?
• 48. Докажите, что для независимых источников сообщений А и В выполняется Н (В | А) = Н (В).
• 49. Каковы причины появления избыточности в сообщении?

• [1] Известно, что в студенческой группе два отличника, 16 хорошистов, шесть троечников и четыре двоечника. Какое количествоинформации содержится в сообщениях: а) «Коля хорошист»; б) «Коляне двоечник»; в) «Коля учится на 4 и 5»?
• [2] У Коли на втором курсе было восемь предметов и четыре аттестации. Нам сообщили, что у него не было двоек и троек. Какое количество информации нам сообщили?
• [3] В лотерее N билетов, из них к выигрышных. Студент Вася купилМ билетов и после розыгрыша сообщил вам, что выиграл (но, возможно, и не на один билет)1. Какое количество информации вы получили?
• [4] «Граждане встречающие! Поезд 26 прибывает на 7-й путь4-й платформы в 19:35». Какое количество информации содержитсяв этом сообщении? Всего на вокзале шесть платформ, на каждой по двапути, ежедневно прибывает 120 поездов.
• [5] Вася выучил стихотворение, в котором 32 слова. Оцените информацию, которую он запомнил. Считается, что в русском языке 10 000 слов.
• [6] У Васи есть игральная карта. Известно, что это карта трефовоймасти. Какое количество информации нам известно?
• [7] Пример. Установленное на предприятии оборудование в результате эксплуатации может оказаться в одном из трех состояний износа:
• [8] С1 — оборудование работоспособно, но требует небольшогоремонта; 2) С2 — большая часть деталей изношена, требуется серьезныйремонт; 3) СЗ — дальнейшая эксплуатация оборудования невозможна. Предыдущая практика показывает, что вероятность состояния С1 равна 20%, р (С2) = 50%, р (СЗ) = 30%. Найти неопределенность (энтропию) состояния оборудования. Решение. По формуле (2.8)
• [9] Задача взята с Олимпиады по сложным техническим системам Института оценки качества образования.