 |
Алфавитный подход к измерению количества информации
|
|
|
|
Пример задания:
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы Ш, К, О, Л, А (таким образом, используется 5 различных символов). Каждый такой пароль в компьютерной системе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Укажите объём памяти в байтах, отводимый этой системой для записи 30 паролей. В ответе запишите только число, слово «байт» писать не нужно.
Решение:
1) согласно условию, в пароле можно использовать 5 символов
2) для кодирования номера одного из 5 символов нужно выделить 3 бита памяти (они позволяют закодировать 23 = 8 вариантов)
3) для хранения всех 15 символов пароля нужно 15 × 3 = 45 бит
4) поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 48 = 6 × 8; то есть один пароль занимает 6 байт
5) тогда 30 паролей занимают 6 × 30 = 180 байт
6) ответ: 180.
Ещё пример задания:
Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 11 символов. В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и заглавные (регистр буквы имеет значение!). Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объём памяти в байтах, который занимает хранение 60 паролей.
|
|
|
Решение:
7) согласно условию, в пароле можно использовать 10 цифр (0..9) + 12 заглавных букв местного алфавита + 12 строчных букв, всего 10 + 12 + 12 = 34 символа
8) для кодирования номера одного из 34 символов нужно выделить 6 бит памяти (5 бит не хватает, они позволяют закодировать только 25 = 32 варианта)
9) для хранения всех 11 символов пароля нужно 11 × 6 = 66 бит
10) поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 72 = 9 × 8; то есть один пароль занимает 9 байт
11) тогда 60 паролей занимают 9 × 60 = 540 байт
12) ответ: 540.
| Возможные ловушки: · часто забывают, что пароль должен занимать ЦЕЛОЕ число байт |
Ещё пример задания:
В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем в битах сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?
Решение:
13) велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов
14) по таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно закодировать 128 вариантов, то есть, еще есть запас); итак, 7 бит на один отсчет
15) когда 70 велосипедистов прошли промежуточный финиш, в память устройства записано 70 отсчетов
16) поэтому в сообщении 70*7 = 490 бит информации.
| Возможные ловушки: · дано число, которое есть в условии (неверные ответы 70 бит, 70 байт, 119 байт), чтобы сбить случайное угадывание · указано правильное число, но другие единицы измерения (мог быть вариант 490 байт) · расчет на невнимательное чтение условия: можно не заметить, что требуется определить объем только 70 отсчетов, а не всех 119 (мог быть вариант 119*7=833 бита) |
Еще пример задания:
|
|
|
В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным целым количеством байт. Определите объем памяти, необходимый для хранения 20 автомобильных номеров.
Решение:
1) всего используется 26 букв + 10 цифр = 36 символов
2) для кодирования 36 вариантов необходимо использовать 6 бит, так как 
, т.е. пяти бит не хватит (они позволяют кодировать только 32 варианта), а шести уже достаточно
3) таким образом, на каждый символ нужно 6 бит (минимально возможное количество бит)
4) полный номер содержит 7 символов, каждый по 6 бит, поэтому на номер требуется 
бита
5) по условию каждый номер кодируется целым числом байт (в каждом байте – 8 бит), поэтому требуется 6 байт на номер (
), пяти байтов не хватает, а шесть – минимально возможное количество
6) на 20 номеров нужно выделить 
байт
7) ответ – 120.
Возможные ловушки:
· если не обратить внимание на то, что каждый номер кодируется целым числом БАЙТ, получаем неверный ответ 2 ( бит = 105 байт)
· если по невнимательности считать, что каждый СИМВОЛ кодируется целым числом байт, получаем 7 байт на символ и всего 140 байт (неверный ответ 4)
· если «забыть» про цифры, получим всего 26 символов, 5 бит на символ, 35 бит (5 полных байт) на каждый номер и неверный ответ 100 байт (на 20 номеров)
|
|
|
|
