Ручное решение
Алфавитный подход к измерению информации
2i = N
i – вес символа
N – мощность алфавита
Алгоритм решения заданий на алфавитный подход к измерению информации:
1. Определяем мощность алфавита
2. Определяем вес одного символа по формуле 2i=N
3. Вычисляем количество битов на одно сообщение
4. Учитываем дополнительное условие (если оно есть) - округление до минимально возможного целого числа байтов
5. Вычисляем количество информации по количеству сообщений
Количество байт на пароль + Количество байт на дополнительные сведения = Количество байт на одного пользователя
Вероятностный подход к информации
Вероятность = количество нужных событий
количество всех возможных событий
Вероятность события изменяется:
0 ≤ вероятность ≤ 1
`2^i=1/p`
i – количество информации
P – вероятность события
Подчеркивайте все условия и единицы измерения, эти задания больше на внимательность, чем на знания.
Прототипы с ЕГЭ
Задача №1 При регистрации в компьютерной системе каждому пользователю выдается идентификатор из 101 символа, каждый из которых может быть десятичной цифрой или одним из 4090 символов из специального набора. Каждый символ кодируется с помощью одинакового и минимального количества бит. Идентификатор же записывается в памяти с помощью минимально возможного целого количества байт.
Сколько килобайт потребуется для хранения идентификаторов 2048 пользователей?
Решение:
Сначала определим, сколько уникальных символов есть для идентификатора: 10 десятичных цифр (0-9) и 4090 специальных символов ⇒ общее количество уникальных символов 10 + 4090 = 4100
Определим минимальное количество бит на символ:
N=4100=2i ⇒
i=log₂(4100) = считаем на калькуляторе как log(4100)/log(2) ≈ 12,002... ⇒ (округляем в большую сторону, так как количество бит должно быть целым числом, а объем не ограничен) i=13
Каждый символ идентификатора будет занимать 13 бит. Поскольку идентификатор состоит из 101 символа, общее количество бит для одного идентификатора будет
101 × 13 = 1313 бит
Переведем это количество бит в байты. Поскольку в одном байте 8 бит, количество байт на один идентификатор будет
1313 / 8 = 164,125 байт
Поскольку мы не можем хранить дробные байты, округляем до целого в бОльшую сторону - 165 байт
Теперь вычислим, сколько байт потребуется для хранения идентификаторов 2048 пользователей:
2048 × 165 = 337920 байт
в одном килобайте 1024 байта
337920 байт = 337920 / 1024 = 330 КБ
Ответ: 330
Задача №2 При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используются прописные и строчные буквы латинского алфавита, т.е. всего 52 различных символа. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование паролей, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайтах), необходимый для хранения данных о 65 536 пользователях. В ответе запишите только целое число — количество Кбайт.
Решение:
Чтобы закодировать каждый из этих 52 символов, нужно определить минимальное количество бит, необходимое для их представления:
52=2i
log₂(52) = log(52)/log(2) ≈ 5,7 округляем вверх, так как объем у нас не ограничен, получаем i = 6 бит
Каждый символ пароля будет занимать 6 бит. Поскольку пароль состоит из 10 символов, общее количество бит для одного пароля будет:
10 × 6 = 60 бит
Переведем это количество бит в байты. Поскольку в одном байте 8 бит, количество байт на один пароль будет:
60 / 8 = 7,5 байт
Мы не можем хранить дробные байты, округляем до целого числа: 8 байт
Вычислим, сколько байт потребуется для хранения паролей 65 536 пользователей:
65536 × 8 = 524288 байт
Переведем это количество байт в килобайты, зная, что в одном килобайте 1024 байта:
524 288 / 1024 = 512 КБ
Таким образом, для хранения данных о 65 536 пользователях потребуется 512 Кбайт.
Ответ: 512
Задача №3 При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 25 символов и содержащий только символы из 26-символьного латинского алфавита от A до Z без учёта регистра. В базе данных для хранения сведений о каждом идентификаторе отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в байтах), необходимый для хранения сведений о 35 объектах. В ответе запишите только целое число — количество байт.
Решение:
26=2i
log₂(26) = log(26)/log(2) ≈ 4,66... округляем вверх, i = 5 бит на символ
5*25=125 бит на 1 идентификатор
125:8=15,625 байт округляем вверх до 16 байт на 1 идентификатор
16*35=560 байт на всё
Ответ: 560
Задача №4 При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 105 символов и содержащий только десятичные цифры и символы из 1500-символьного специального алфавита. В базе данных для хранения сведений о каждом идентификаторе отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайт), необходимый для хранения сведений о 16 384 объектах. В ответе запишите только целое число – количество Кбайт.
Решение:
Кол-во символов 10 + 1500 = 1510
1510=2i
log₂(1510) = log(1510)/log(2) ≈ 10,5... округляем вверх, i = 11 бит на символ
105 * 11= 1155 бит на 1 идентификатор, переводим в байты:
1155 : 8 = 144,375 байт округляем вверх = 145 байт
16384*145=2 375 680 байт на все объекты, но надо в Кбайтах:
2 375 680/ 1024= 2320 Кбайт
Ответ: 2320
Задания уровня ЕГЭ
Задача №1 Метеостанция принимает сигналы от метеозондов, собирающих данные по одному из показателей. Известно, что значение измеряемого показателя находится в диапазоне чисел от 10 до 3000 с шагом 0.1. Для сокращения количества передаваемых сигналов показания записываются в пакеты по 10 штук. Каждое показание кодируют одинаковым и минимально возможным количеством бит. При этом каждый пакет показаний сохраняется с помощью целого и минимально возможного количества байт, после чего передается на метеостанцию.
Сколько Кбайт будет принято метеостанцией, если от метеозондов будет получено 8192 пакета? В ответе запишите только целое число – количество Кбайт.
Решение:
Определим количество возможных значений
10 до 3000 с шагом 0,1
Количество значений = `(3000-10)/(0,1) + 1 = 2990/(0,1) + 1 = 29900 + 1 = 29901` значений
Определим минимальное количество бит для кодирования значений
2i ≥ 29901
2¹⁴ = 16384 (меньше 29901)
2¹⁵ = 32768 (больше 29901) ⇒ i = 15 бит
В пакете 15*10 = 150 бит
каждый пакет показаний сохраняется с помощью целого и минимально возможного количества байт
Определим количество байт для пакета
150 бит = 150 : 8 байт = 18,75 округляем в верх = 19 байт
8192 * 19 = 155648 байт = 155648 : 1024 = 152 Кбайт
Ответ: 152
Задача №2 При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 200 символов и содержащий только десятичные цифры и символы из 2040 символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайт), необходимый для хранения 98304 идентификаторов. В ответе запишите только целое число – количество Кбайт.
Решение:
Определяем количества символов
10 цифр + 2040 = 2050
Определяем минимальное количество бит для кодирования одного символа
2i ≥ 2050
2¹¹ = 2048 (меньше 2050)
212 = 4096 (больше 2050) ⇒ i=12 бит
Общее количество бит для одного идентификатора
Биты на один идентификатор = 200 × 11 = 2400 бит
2400 бит = 2400:8=300 байт
98304 * 275 = 29 491 200 байт на все идентификаторы = 29 491 200 : 1024 = 28800 Кбайт
Ответ: 28800
Задача №3 При регистрации в компьютерной системе каждому объекту присваивается идентификатор содержащий только десятичные цифры и символы из 1234-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Известно, что для хранения 65 536 идентификаторов понадобилось не более 2050 КБайт.
Укажите максимально допустимую длину идентификатора пользователя.
Решение:
Определяем количества символов (десятичные цифры и символы из 1234-символьного алфавита)
10 (цифры) + 1234 = 1244
Определяем, сколько бит на 1 символ
2i ≥ 1244
210 = 1024 (меньше 1244)
211 = 2048 (больше 1244) ⇒ i=11 бит
Пусть х символов в идентификаторе
11х бит в идентификаторе
11х/8 байт в идентификаторе
для хранения 65 536 идентификаторов понадобилось не более 2050 КБайт
2050*1024=2 099 200 байт на все идентификаторы
2 099 200 : 65 536 = 32,03125 байт на 1 идентификатор, но нужно целое, округляем вниз (так как вписаться нужно в размер не более 2050 КБайт), берем 32 байт
(11x)/8 = 32
11x=8*32
x=23,(27) округляем вниз, так как опять же нам надо вписаться в отведенный объем, 23 символа максимум влезет в идентификатор
Ответ: 23
Задача №4 При регистрации в компьютерной системе для каждого пользователя заводится учетная запись. В учетной записи 3 поля – номер пользователя (число от 1 до 10000), ФИО (строка длиной 80 символов из строчных и заглавных букв русского алфавита, пробелов и дефисов) и пароль длиной 20 символов. В качестве символов в пароле могут быть 26 строчных латинских букв и спецсимволы из набора $%^&*#@. Пароль и ФИО кодируются отдельно, для кодирования каждого из этих полей используется посимвольное равномерное кодирование – каждый символ кодируется одинаковым и минимально возможным количеством бит. Каждое поле в учетной записи представлено минимально возможным целым количеством байт.
Сколько байтов понадобится для хранения информации о 25 пользователях?
Решение:
Чтобы определить, сколько байтов понадобится для хранения информации о 25 пользователях, нужно рассчитать объем памяти, необходимый для каждого из трех полей учетной записи: номер пользователя, ФИО и пароль.
Номер пользователя — это число от 1 до 10000, то есть 10000 символов
2¹³ = 8192 (меньше 10000)
2¹⁴ = 16384 (больше 10000) ⇒ i=14 бит
Значит, для кодирования номера пользователя нужно 14 бит.
Переводим в биты каждую строку, так как это самостоятельные блоки информации и округлять нужно каждый в отдельности, если придется это делать.
Байты на номер пользователя = 14 / 8 = 1,75 байт округляем вверх (поскольку мы не можем хранить часть байта, а в меньший объем он просто не влезет)
= 2 байта
ФИО из строчных и заглавных букв русского алфавита, пробелов и дефисов. Итого 33 заглавных + 33 строчных + 1 пробел + 1 дефис = 68
i=7 бит (округлили вверх)
80 *7 = 560 бит на ФИО
560/8=70 байт
Пароль 26 + 7 = 33
i=6 бит (округлили вверх)
20*6=120 бит = 15 байт
2 + 70 + 15 =87 байт на 3 строки для одного пользователя
А для 25 пользователей 87 * 25 = 2175 байт
Ответ: 2175
Задача №5 Датчик считывает значения интенсивности поступающего света. Известно, что при считывании значение округляется до одного из 2000 возможных. Каждое считанное значение кодируется одинаковым минимально возможным количеством бит. Также известно, что значения считываются сериями по 50 измерений. Каждая такая серия сохраняется на жесткий диск, на котором занимает целое количество байт. Если последняя переданная серия меньше 50 значений, переданные в ней значения также сохраняются в файле с помощью минимального целого количества байт. За время своей работы датчик считал 12312 значений.
Найдите минимальное целое количество килобайт, которого хватит для хранения считанных значений. В качестве ответа запишите одно число – найденное количество килобайт.
Решение:
2000 значений
2i ≥ 2000
i=11 бит на символ
11*50=550 бит серия
550/8=68,75 байт, округляем вверх = 69 байт серия
12312 значений, в серии 50 измерений - это 246 серий (12300 значений) + 12 значений
246 * 69 = 16974 байт на 246 серий
12*11:8=16,5 = 17 байт на оставшиеся 12 значений
16 991 : 1024 = 16,5 но мы не можем хранить часть килобайта, округляем вверх до 17
Ответ: 17
