Задача №13. Расчет информационного объема сообщения. Автомобильные номера, пароли, вычисление количества вариантов. Подсчет промежуточного количества информации.

   Время чтения 4 минуты

Если нам нужно закодировать сообщение, написанное в алфавите мощностью M, при помощи компьютерных кодов, т.е. в алфавите мощностью 2, то для кодирования всех символов исходного алфавита нам нужно под каждый символ выделить такое количество бит K, что M <= 2K.

Тогда информационный объем сообщения I, содержащего N символов, будет равен: I = K * N

I = log2M * N   (формула Хартли).

Если log2M не является целым числом, округляем значение в большую сторону.

Пример 1.

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

1) 21 байт

2) 140 бит

3) 28 бит

4) 28 байт

Решение:

По формуле Хартли объем сообщения I, написанного в исходном алфавите мощности M, содержащего N символов, будет равен: I = log2M * N.

Если log2M не является целым числом, округляем значение в большую сторону.

В нашем случае мощность алфавита (все символы, подлежащие кодированию) M = 28. N тоже = 28, т.к. все спортсмены прошли финиш.

Тогда I = log228 * 28 ≈ 5 * 28 = 140 бит.

Ответ: 2

Пример 2.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 400 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Решение:

Раз для хранения сведений о 20 пользователях потребовалось 400 байт, то для хранения сведений об 1 пользователе нужно 20 байт.

Для хранения пароля, по формуле Хартли, необходимо  log2M * N = log212 * 15 ≈ 4 * 15 = 60 бит. Но под пароль отведено минимально возможное целое количество байт, значит под пароль отведено  60/8  ≈ 8 байт (округляем в большую сторону, иначе не получится записать пароль). Значит, для хранения дополнительных сведений остается 20 – 8 = 12 байт.

Ответ: 12

Пример 3.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся иден­ти­фи­ка­тор, со­сто­я­щий из 8 сим­во­лов, пер­вый и по­след­ний из ко­то­рых — одна из 18 букв, а осталь­ные — цифры (до­пус­ка­ет­ся ис­поль­зо­ва­ние 10 де­ся­тич­ных цифр). Каж­дый такой иден­ти­фи­ка­тор в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством байт (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние; все цифры ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит, все буквы также ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит).

Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 500 па­ро­лей.

1) 1500 байт

2) 2000 байт

3) 2500 байт

4) 3000 байт

Решение:

Рас­смот­рим от­дель­но бук­вен­ную и циф­ро­вую часть иден­ти­фи­ка­то­ра.

Для записи каждой из 18 букв необходимо log218 ≈ 5 бит.

Для записи каждой из 10 цифр необходимо log210 ≈ 4 бит.

Для хра­не­ния всех 8 сим­во­лов иден­ти­фи­ка­то­ра нужно 5·2 + 4·6 = 34 бита, а т. к. для за­пи­си ис­поль­зу­ет­ся целое число байт, то 34/8 округляем в большую сторону. Получаем 5 байт.

Тогда для 500 па­ро­лей отводится 5·500 = 2500 байт.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

Ответ:3

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

три × три =