close

Вход

Забыли?

вход по аккаунту

?

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

код для вставки
711954835.doc
-1-
Количество информации как мера уменьшения неопределенности знаний
Содержательный подход
Количество информации, заключенное в сообщении, определяется объемом знаний,
который несет это сообщение получающему его человеку. Сообщение содержит
информацию для человека, если заключенные в нем сведения являются для этого
человека новыми и понятными, и, следовательно, пополняют его знания.
При содержательном подходе возможна качественная оценка информации:
полезная, безразличная, важная, вредная, … Одну и туже информацию разные
люди могут оценить по разному.
Информацию, которую получает человек, можно считать мерой уменьшения неопределенности
знаний. Если некоторое сообщение приводит к уменьшению неопределенности наших знаний, то
можно говорить, что такое сообщение содержит информацию.
За единицу количества информации принято такое количество информации,
которое мы получаем при уменьшении неопределенности в 2 раза. Такая
единица названа бит.
В компьютере информация представлена в двоичном коде или на машинном языке, алфавит
которого состоит из двух цифр (0 и 1). Эти цифры можно рассматривать как два равновероятных
состояния. При записи одного двоичного разряда реализуется выбор одного из двух возможных
состояний (одной из двух цифр) и, следовательно, один двоичный разряд несет количество
информации в 1 бит. Два двоичных разряда несут информацию 2 бита, три разряда – 3 бита и т.д.
Поставим теперь обратную задачу и определим: «Какое количество различных двоичных чисел N
можно записать с помощью I двоичных разрядов?» С помощью одного двоичного разряда можно
записать 2 различных числа (N=2=21), с помощью двух двоичных разрядов можно записать
четыре двоичных числа (N=4=22), с помощью трех двоичных разрядов можно записать восемь
двоичных чисел (N=8=23) и т.д.
В общем случае количество различных двоичных чисел можно определить по формуле
N=2I,
где
I – количество информации;
N – количество возможных событий (равновероятных)!!!;
В математике существует функция, с помощью которой решается показательное уравнение, эта
функция называется логарифмом. Решение такого уравнения имеет вид:
I  log 2 N .
Если события равновероятны, то количество информации определяется по
данной формуле.
Количество информации для событий с различными вероятностями
определяется по формуле:
N
I   pi log 2 pi ,
i 1
где
I – количество информации;
N – количество возможных событий;
Pi – вероятность отдельных событий.
Формула Шеннона
711954835.doc
-2-
Пример 1. В барабане для розыгрыша лотереи находится 32 шара. Сколько
информации содержит сообщение о первом выпавшем номере (например, выпал
номер 15)?
Поскольку вытаскивание любого из 32 шаров равновероятно, то количество
информации об одном выпавшем номере находится из уравнения: 2I=32.
Но 32=25. Следовательно, I=5 бит. Очевидно, ответ не зависит от того, какой именно выпал номер.
Пример 2. Какое количество вопросов достаточно задать вашему собеседнику,
чтобы наверняка определить месяц, в котором он родился?
Будем рассматривать 12 месяцев как 12 возможных событий. Если спрашивать о конкретном
месяце рождения, то, возможно, придется задать 11 вопросов (если на 11 первых вопросов был
получен отрицательный ответ, то 12-й задавать не обязательно, так как он и будет правильным).
Правильнее задавать «двоичные» вопросы, то есть вопросы, на которые можно ответить только
«да» или «нет». Например, «Вы родились во второй половине года?». Каждый такой вопрос
разбивает множество вариантов на два подмножества: одно соответствует ответу «да», а другое –
ответу «нет».
Правильная стратегия состоит в том, что вопросы нужно задавать так, чтобы количество
возможных вариантов каждый раз уменьшалось вдвое. Тогда количество возможных событий в
каждом из полученных подмножеств будет одинаково и их отгадывание равновероятно. В этом
случае на каждом шаге ответ («да» или «нет») будет нести максимальное количество информации
(1 бит).
По формуле 2 и с помощью калькулятора получаем:
I  log2 12  3,6 бита.
Количество полученных бит информации соответствует количеству заданных вопросов, однако
количество вопросов не может быть нецелым числом. Округляем до большего целого числа и
получаем ответ: при правильной стратегии необходимо задать не более 4 вопросов.
Пример 3. После экзамена по информатике, который сдавали ваши друзья,
объявляются оценки («2», «3», «4» или «5»). Какое количество информации
будет нести сообщение об оценке учащегося А, который выучил лишь половину
билетов, и сообщение об оценке учащегося В, который выучил все билеты.
Опыт показывает, что для учащегося А все четыре оценки (события) равновероятны и тогда
количество информации, которое несет сообщение об оценке, можно вычислить по формуле (1):
I  log 2 4  2 бита.
На основании опыта можно также предположить, что для учащегося В наиболее вероятной
оценкой является «5» (p1=1/2), вероятность оценки «4» в два раза меньше (p2=1/4), а вероятности
оценок «2» и «3» еще в два раза меньше (p3 =p4=1/8). Так как события неравновероятны,
воспользуемся для подсчета количества информации в сообщении формулой 2:
I  (1/ 2  log2 1/ 2 1/ 4  log2 1/ 4 1/ 8  log2 1/ 8 1/ 8  log2 1/ 8)  1,75 бита
Вычисления показали, что при равновероятных событиях мы получаем большее количество
информации, чем при неравновероятных событиях.
Пример 4. В непрозрачном мешочке хранятся 10 белых, 20 красных, 30 синих и
40 зеленых шариков. Какое количество информации будет содержать
зрительное сообщение о цвете вынутого шарика.
Так как количество шариков разного цвета неодинаково, то вероятности зрительных сообщений о
цвете вынутого из мешочка шарика также различаются и равны количеству шариков данного
цвета деленному на общее количество шариков:
Pб=0,1;
Pк=0,2;
Pс=0,3;Pз=0,4.
События неравновероятны, поэтому для определения количества информации, содержащегося в
сообщении о цвете шарика, воспользуемся формулой 2:
I  (0,1 log2 0,1  0,2  log2 0,2  0,3  log2 0,3  0,4  log2 0,4) бит
Для вычисления этого выражения, содержащего логарифмы можно воспользоваться
калькулятором. I1,85 бита.
711954835.doc
-3-
Пример 5. Используя формулу Шеннона, достаточно просто определить, какое
количество бит информации или двоичных разрядов необходимо, чтобы
закодировать 256 различных символов. 256 различных символов можно
рассматривать как 256 различных равновероятных состояний (событий). В
соответствии с вероятностным подходом к измерению количества информации
необходимое количество информации для двоичного кодирования 256 символов
равно:
I=log2256=8 бит=1 байт
Следовательно, для двоичного кодирования 1 символа необходим 1 байт
информации или 8 двоичных разрядов.
Задачи для самостоятельного выполнения:
1. Какое количество информации несет в себе сообщение о том, что нужная вам
программа находится на одной из восьми дискет?
2. Какое количество информации получит второй игрок при игре в крестикинолики на поле 88, после первого хода первого игрока, играющего ноликами?
3. В рулетке общее количество лунок равно 128. Какое количество информации мы
получаем в зрительном сообщении об остановке шарика в одной из лунок?
4. Происходит выбор одной карты из колоды в 32 карты. Какое количество
информации мы получаем в зрительном сообщении о выборе определенной
карты?
5. Какое количество информации будет содержать зрительное сообщение о цвете
вынутого шарика, если в непрозрачном мешочке хранятся:
А) 25 белых, 25 красных, 25 синих и 25 зеленых шариков;
Б) 30 белых, 30 красных, 30 синих и 10 зеленых шариков?
6. Какое количество вопросов достаточно задать вашему собеседнику, чтобы точно
определить день и месяц его рождения?
7. «Вы выходите на следующей остановке?» – спросили человека в автобусе.
«Нет», - ответил он. Сколько информации содержит ответ?
8. Какой
объем
информации
содержит
сообщение,
уменьшающее
неопределенность знаний в 4 раза?
9. Вы подошли к светофору, когда горел желтый свет. После этого загорелся
зеленый. Какое количество информации вы при этом получили?
10.Группа школьников пришла в бассейн, в котором 4 дорожки для плавания.
Тренер сообщил, что группа будет плавать на дорожке номер 3. Сколько
информации получили школьники из этого сообщения?
11.В корзине лежат 8 шаров. Все шары разного цвета. Сколько информации несет
сообщение о том, что из корзины достали красный шар?
12.Была получена телеграмма: «Встречайте, вагон 7». Известно, что в составе
поезда 16 вагонов. Какое количество информации было получено?
13.В школьной библиотеке 16 стеллажей с книгами. На каждом стеллаже 8 полок.
Библиотекарь сообщил Пете, что нужная ему книга находится на пятом стеллаже
на третьей сверху полке. Какое количество информации библиотекарь передал
Пете?
14.При угадывании целого числа в диапазоне от 1 до N было получено 7 бит
информации. Чему равно N?
711954835.doc
-4-
15.При угадывании целого числа в некотором диапазоне было получено 6 бит
информации. Сколько чисел содержит этот диапазон?
16.Сообщение о том, что ваш друг живет на 10 этаже, несет 4 бита информации.
Сколько этажей в доме?
17.Сообщение о том, что Петя живет во втором подъезде, несет 3 бита информации.
Сколько подъездов в доме?
18. В коробке лежат 7 цветных карандашей. Какое количество информации
содержит сообщение, что из коробки достали красный карандаш?
19.Какое количество информации несет сообщение: «Встреча назначена на
сентябрь»?
20. Какое количество информации несет сообщение: «Встреча назначена на 15
число»?
21.Какое количество информации несет сообщение: «Встреча назначена на 23
октября в 15.00»?
22. Какое минимальное количество битов нужно для кодирования 5 цветов
палитры?
23. Для кодирования красного цвета служит код 00011. Сколько цветов содержит
палитра?
24.Сколько информации несет сообщение, что книга стоит на 4-ой полке, если всего
имеется 4 полки?
25.В детской игре «Угадай число» первый участник загадал целое число в
промежутке от 1 до 16. Второй участник задает вопросы: «Загаданное число
больше число _?» Какое максимальное количество вопросов при правильной
стратегии (интервал чисел в каждом вопросе делится пополам) должен задать
второй участник, чтобы отгадать число?
26.Какое количество информации содержит один разряд шестнадцатеричного
числа?
27.Какое количество информации содержит один разряд двоичного числа?
28.Количество информации, которое требуется для двоичного кодирования 256
символов равно …
29.Какое количество информации необходимо для кодирования одной точки
изображения при палитре из 16 цветов?
30.Количество информации, которое требуется для двоичного кодирования
цветного рисунка (256 цветов) размером 10*10 точек, равно …
Автор
boriskova_sch112
Документ
Категория
Образование
Просмотров
251
Размер файла
50 Кб
Теги
задачи
1/--страниц
Пожаловаться на содержимое документа