Задание 11. Равномерное кодирование
Решение задач
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 108 символов и содержащий только десятичные цифры и символы из 60-символьного специального алфавита.
В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайт), необходимый для хранения 25 600 идентификаторов.
В ответе запишите только целое число - количество Кбайт.
2375
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 60 символов и содержащий только десятичные цифры и символы из 250-символьного специального алфавита.
В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайт), необходимый для хранения 65 536 идентификаторов.
В ответе запишите только целое число - количество Кбайт.
4352
На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы (с учётом регистра) и символы из 963-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 2000 серийных номеров отведено не более 693 Кбайт памяти.
Определите максимально возможную длину серийного номера. В ответе запишите только целое число.
Мощность алфавита: N = 10 + 52 + 963 = 1025
Информационный вес символа: N = 1025 <= 2**i, i = 11 бит
Игформационный объем серийного номера: k = 693 *1024 / 2000 = 354, 818 байт, k = 354 байт, округляем с недостатком, чтобы все серийные номера можно было сохранить
Определяем количество символов в серийном номере: m = 354 * 8 / 11 = 257, (45), округляем с недостатком, чобы все серийные номера поместились в заданный объем 693 Кбайт, m = 257 символов
Проверка : возмем m = 258 и вычислим объем памяти для хранения 2000 серийных номеров:
для хранения обного серийного номера 258 * 11 / 8 = 354, 45 байт, округляем 355 байт, чтобы сохранить все сивмволы номера, тогда
355 * 2000 / 1024 = 693,35 Кбайт
Ответ: 257
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 261 символов. Для его хранения отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 252 500 серийных номеров отведено более 31 Мбайт памяти. Определите минимально возможную мощность алфавита, из которого составляются серийные номера. В ответе запишите только число.
Решение:
Мощность алфавита - это то количество символов, которые претендуют в одну ячейку серийного номера.
Обозначим за x сразу вес одного символа серийного номера в битах. Тогда вес всего номера будет равен 261 * x.
Узнаем, сколько памяти выделили на один серийный номер:
31 Мб / 252500 = 31*1024*1024 / 252500 ≈ 128,74 ≈ 129 байт
Здесь мы округлили в большую сторону, т.к. в задачке сказано, что выделено более 31 Мб.
Найдём x. Переведём значение 261 * x в байты.
261*x / 8 = 129
261*x = 1032
x = 1032 / 261 ≈ 3,9 ≈ 4 бит
Мы округлили в большую сторону, иначе опять бы нарушилось условие, что выделено более 31 Мб на все номера.
Получается 4 бита выделено на один символ серийного номера.
Минимальная возможная мощность алфавита при 4 битах будет равна 9.
N = 2**4 > 9
Но ещё меньше взять нельзя, т.к. если мощность алфавита будет равна 8, то для этого достаточно 3 бита, а нам нужно, чтобы 1 символ весил 4 бита.
Ответ: 9
Домашнее задание
№ 10 Демоверсия 2021 (Уровень: Базовый)
При регистрации в компьютерной системе каждому объекту сопоставляется идентификатор, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байта на один объект.
Определите объём памяти (в байтах), необходимый для хранения сведений о 20 объектах. В ответе запишите только целое число – количество байт.
Ответ: 600
№ 128 (Уровень: Базовый)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, К, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 12 байт на одного пользователя. Определите объём памяти (в байтах), необходимый для хранения сведений о 50 пользователях. В ответе запишите только целое число – количество байт.
Ответ: 1000
№ 133 (Уровень: Средний)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 7 символов. В качестве символов используют прописные и строчные буквы латинского алфавита (в нём 26 символов). В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено 12 байт на одного пользователя. В компьютерной системе выделено 2 Кб для хранения сведений о пользователях. О каком наибольшем количестве пользователей может быть сохранена информация в системе? В ответе запишите только целое число – количество пользователей.
Ответ: 113
№ 135 (Уровень: Базовый)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 12 символов и содержащий символы латинского алфавита (заглавные и строчные), десятичные цифры, а также символы из набора $, #, @, ^. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения. Для хранения сведений о 40 пользователях выделили 1080 байт. Сколько байт можно использовать для хранения дополнительных сведений о каждом пользователе?
Ответ: 16
№ 138 (Уровень: Средний)
Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, код подразделения и некоторая дополнительная информация. Личный код состоит из 11 символов, каждый из которых может быть заглавной латинской буквой (используется 15 различных букв) или одной из цифр от 0 до 9. Для записи кода на пропуске отведено минимально возможное целое число байт. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Код подразделения состоит из 8 символов: в каждой из пяти первых позиций стоит одна из 26 латинских букв, затем – три десятичных цифры. Код подразделения записан на пропуске как двоичное число (используется посимвольное кодирование) и занимает минимально возможное целое число байт. Всего на пропуске хранится 30 байт данных. Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число – количество байт.
Ответ: 18
№ 1194 Апробация 27.04 (Уровень: Базовый)
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 86 символов и содержащий только символы из 250-символьного алфавита. В базе данных для хранения сведений о каждом идентификаторе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит.
Определите объём памяти (в байтах), необходимый для хранения 256 идентификаторов.
В ответе запишите только целое число — количество байт.
Ответ: 22016
№ 1412 (Уровень: Базовый)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 20 символов и содержащий только арабские цифры 0, 1 и буквы A, B, C, D, E, F, G. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранится IP-адрес пользователя (4 байта) и дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 192 пользователях потребовалось 6 Кбайт.
Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число - количество байт.
Ответ: 18
№ 1855 Основная волна 2021 (Уровень: Базовый)
При регистрации в компьютерной системе каждому пользователю выдается идентификатор из 101 символа, каждый из которых может быть десятичной цифрой или одним из 4090 символов из специального набора. Каждый символ кодируется с помощью одинакового и минимального количества бит. Идентификатор же записывается в памяти с помощью минимально возможного целого количества байт.
Сколько килобайт потребуется для хранения идентификаторов 2048 пользователей?
Ответ: 330
№ 17524 Основная волна 07.06.24 (Уровень: Средний)
На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы (с учётом регистра) и символы из 458-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 862 серийных номеров отведено не более 276 Кбайт памяти. Определите максимально возможную длину серийного номера. В ответе запишите только целое число.
Ответ: 261
№ 17630 Основная волна 19.06.24 (Уровень: Средний)
На предприятии каждой изготовленной детали присваивается серийный номер, содержащий десятичные цифры, 26 латинских букв (без учёта регистра) и символы из 450-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 708 серийных номеров отведено более 213 Кбайт памяти. Определите минимально возможную длину серийного номера.
В ответе запишите только целое число.
Ответ: 274
№ 1366 Джобс 16.05.2021 (Уровень: Базовый)
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 80 символов. В базе данных для хранения сведений о каждом идентификаторе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит.
Определите максимальное количество символов, которое может быть использовано для формирования идентификатора (мощность алфавита), если известно, что информация о 1200 идентификаторах занимает не более 150 Кбайт.
Ответ: 4096
№ 17552 Основная волна 08.06.24 (Уровень: Сложный)
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 261 символов. Для его хранения отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 252 500 серийных номеров отведено более 31 Мбайт памяти. Определите минимально возможную мощность алфавита, из которого составляются серийные номера.
В ответе запишите только число.
Ответ: 9
№ 17934 (Уровень: Средний)
(А. Ярмухаметов) При регистрации в компьютерной системе каждому пользователю присваивается идентификатор и дополнительные сведения. Идентификатор, состоящий из 99 символов, содержащий десятичные цифры и символы из 510-символьного набора. Для его хранения отведено одинаковое и минимально возможное число байт. Идентификатор кодируются посимвольно, то есть каждый символ представляется с помощью минимального и одинакового для всех символов количества бит. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. Для хранения сведений о 4322 пользователях потребовалось более 543 Кбайт.
Определите минимальный объём памяти (в байт), необходимый для хранения дополнительных сведений для одного пользователя. В ответе запишите только целое число - количество байт.
Ответ: 5
№ 17935 (Уровень: Средний)
(А. Ярмухаметов) При регистрации в компьютерной системе каждому пользователю присваивается идентификатор и дополнительные сведения. Идентификатор, состоящий из 745 символов, содержит десятичные цифры и символы из 999-символьного набора. Для его хранения отведено одинаковое и минимально возможное число байт. Идентификатор кодируются посимвольно, то есть каждый символ представляется с помощью минимального и одинакового для всех символов количества бит. В базе данных для хранения сведений о каждом пользователе отведено одинаковое целое число байт. Для хранения сведений о 312 пользователях потребовалось не более 311 Кбайт.
Определите максимальный объём памяти (в байт), необходимый для хранения дополнительных сведений всех пользователей. В ответе запишите только целое число - количество байт.
Ответ: 27456