Question

(ОЧЕНЬ СРОЧНО ПОЖАЛУЙСТА РЕШИТЕ) 1) В велокроссе участвуют 48 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда половина спортсменов пройдут промежуточный финиш. 2) Автомобильный номер состоит из 6 символов. Допустимыми символами считаются 10 цифр и 5 заглавных букв: A, L, T, E, K. Для хранения каждого из 15 допустимых символов используется одинаковое и минимально возможное количество бит. Сколько бит памяти потребуется для хранения 40 автомобильных номеров. (Номера хранятся без пробелов) 3) При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 11 символов и содержащий только символы А, Б, В, Г, Д, Е. Каждый такой пароль в компьютерной программе записывается минимально возможным и одинаковым целым количеством БАЙТ, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством БИТ. Определите, сколько байт необходимо для хранения 20 паролей.

Answer 1

1) Ищем ближайшую сверху к 48 степень двойки - это 2^6 = 64, то есть каждого спортсмена можно закодировать минимум 6 битами. Половина спортсменом это 48/2 = 24, и если на каждого из них надо по 6 бит, то необходимый объем памяти: 24*6 = 144 бита

2) Ближайшая к 15 степень двойки это 2^4 = 16, значит по 4 бита на номер. Для 40 номеров нужно 4*40 = 160 бит

3) Всего в алфавите 5 символов, ближайшая к 5 степень двойки это 2^3 = 8, значит по 3 бита на символ. Каждый пароль кодируется 11*3 = 33 битами. А для хранения 33 бит нужно 33/8 = 4.125 байт, округляем до 5 байт (по условию). Значит на 20 паролей нужно 20*5 = 100 байт.

Answer 2

1. Для того, чтобы записать номера каждого спортсмена, нужно использовать логарифм по основанию 2 от количества возможных номеров, так как каждый номер можно закодировать как последовательность битов длины логарифма. В данном случае у нас 48 спортсменов, то есть возможных номеров 48. Логарифм по основанию 2 от 48 примерно равен 5.58, что означает, что для записи каждого номера требуется около 6 бит. Когда половина спортсменов пройдет промежуточный финиш, то это будет 24 спортсмена, и для их номеров потребуется 24*6=144 бит памяти.

2. Для каждого символа из списка допустимых требуется использовать логарифм по основанию 2 от 15, так как каждый символ можно закодировать как последовательность битов длиной логарифма. Логарифм по основанию 2 от 15 равен 3.91, то есть для каждого символа нужно около 4 бит. Чтобы закодировать 40 номеров, требуется 406=240 номеров. Таким образом, для хранения 40 автомобильных номеров потребуется 2404=960 бит памяти.

3. Если каждый символ требует использования минимального количества бит, то каждый символ можно закодировать как последовательность битов длиной логарифма по основанию 2 от количества возможных символов, то есть от 5. В данном случае у нас 5 возможных символов, поэтому для каждого символа потребуется около 3 бит. Таким образом, чтобы закодировать один пароль, нужно 113=33 бит. Для 20 паролей потребуется 2033=660 бит, что равно 83 байтам.