Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.
Проверяемые элементы содержания: Умение подсчитывать информационный объём сообщения
Задание демонстрационного варианта 2021 года ФИПИ
Содержание:
Кодирование сообщений (работа с текстом)
Объем сообщения – 7,5 Кбайт. Известно, что данное сообщение содержит 7680 символов. Какова мощность алфавита?
Типовые задания для тренировки
Ответ: 256
- Воспользуемся формулой:
I - объем сообщения N - количество символов K - количество бит на 1 символ
I = 7,5 Кбайт = 7,5 * 213 бит
\[ K = \frac {7,5 * 2^{13}}{7680} = \frac {7,5 * 2^{13}}{15 * 2^9} = \frac {7,5 * 16}{15} = 8 \]
28 = 256 различных символов
(по формуле Q = 2N)
Мощность алфавита равна 256. Сколько Кбайт памяти потребуется для сохранения 160 страниц текста, содержащего в среднем 192 символа на каждой странице?
Типовые задания для тренировки
Ответ: 30
- Найдем общее количество символов на всех страницах (для удобства будем использовать степени двойки):
160 * 192 = 15 * 211
256 = 2n -> n = 8 бит на 1 символ
\[ I = {15 * 2^{11}} * 2^3 бит = \frac {15 * 2^{14}}{2^{13}} Кбайт = 30 Кбайт \]
I = 30 Кбайт
Два текста содержат одинаковое количество символов. Первый текст составлен в алфавите мощностью 16 символов, а второй текст – в алфавите из 256 символов.
Во сколько раз количество информации во втором тексте больше, чем в первом?
Ответ: 2
- Необходима формула Q = 2n
- Вычислим требуемое количество бит на хранение одного символа для обоих текстов:
1. 16 = 2n -> n = 4 2. 256 = 2n -> n = 8
Работа с различными системами
Кабельная сеть проводит голосование среди зрителей о том, какой из четырех фильмов они хотели бы посмотреть вечером. Кабельной сетью пользуются 2000 человек. В голосовании участвовало 1200 человек.
Каков объем информации (в байтах), записанный автоматизированной системой голосования?
Ответ: 300
- Так как номера четырех фильмов хранятся в компьютерной системе, то можно найти количество бит, необходимое для хранения номера фильма:
Q = 2k -> 4 = 2k -> k = 2 бита
1200 * 2 = 2400 бит = 2400/8 байт = 300 байт
Репетиционный экзамен в школе сдают 105 человек. Каждому из них выделяют специальный номер, идентифицирующий его в автоматической системе проверки ответов. При регистрации участника для записи его номера система использует минимально возможное количество бит, одинаковое для каждого участника.
Каков объем информации в битах, записанный устройством после регистрации 60 участников?
Ответ: 420
В базе данных хранятся записи, содержащие информацию о датах. Каждая запись содержит три поля: год (число от 1 до 2100), номер месяца (число от 1 до 12) и номер дня в месяце (число от 1 до 31). Каждое поле записывается отдельно от других полей с помощью минимально возможного числа бит.
Определите минимальное количество бит, необходимых для кодирования одной записи.
Ответ: 21
- Необходима формула Q = 2n.
- Вычислим требуемое количество бит на хранение каждого пункта всей записи:
1. 2100 вариантов: 2100 ~ 212 -> n = 12 бит 2. 12 вариантов: 12 ~ 24 -> n = 4 бит 3. 31 вариант: 31 ~ 25 -> n = 5 бит
12 + 4 + 5 = 21
Репетиционный экзамен сдают 9 потоков по 100 человек в каждом. Каждому из них выделяют специальный код, состоящий из номера потока и номера в потоке. При кодировании этих номеров участников проверяющая система использует минимально возможное количество бит, одинаковое для каждого участника, отдельно для номера потока и номера в потоке. При этом для записи кода используется минимально возможное и одинаково целое количество байтов.
Каков объем информации в байтах, записанный устройством после регистрации 80 участников?
В ответе укажите только число.
Ответ: 160
- Код состоит из двух составляющих: 1. номер потока (в битах) и 2. номер по порядку (в битах). Найдем количество бит, необходимое для их хранения:
1. N = 2i -> 9 = 2i -> i = 4 бит (23 < 9 < 24) 2. N = 2i -> 100 = 2i -> i = 7 бит (26 < 100 < 27)
11/ 8 ~ 2 байта (одного байта недостаточно, 8 < 11)
2 * 80 = 160 байт
Компьютерные системы и автомобильные номера
Автомобильный номер состоит из нескольких букв (количество букв одинаковое во всех номерах), за которыми следуют три цифры. При этом используются 10 цифр и только 5 букв: Н, О, М, Е и Р. Нужно иметь не менее 100 тысяч различных номеров.
Какое наименьшее количество букв должно быть в автомобильном номере?
Ответ: 3
- Необходима формула Q = mn.
Q - количество вариантов m - мощность алфавита n - длина
5 ... 5 10 10 10 = 5x * 103
100000 <= 5x * 103
x = 3:
53 * 1000 = 125000 (125000 > 100000)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит.
Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях.
В ответе запишите только целое число – количество байт.
Ответ: 350
- Основной формулой для решения данной задачи является:
- Чтобы найти количество бит, необходимое для хранения одного пароля, для начала нужно найти количество бит, необходимых для хранения 1 символа в пароле. По формуле получаем:
где Q - количество вариантов символов, которые можно закодировать с помощью N бит.
26 = 2N -> N ~ 5 бит
10 * 5 = 50 бит всего на пароль
50 бит / 8 ~ 7 байт (берем ближайшее число большее 50 и кратное 8: 56/8 = 7)
7 байт * 50 (пользователей) = 350 байт
В некоторой стране автомобильный номер состоит из 7 символов. Каждый символ может быть одной из 18 различных букв или десятичной цифрой.
Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт, при этом используют посимвольное кодирование и каждый символ кодируется одинаковым и минимально возможным количеством бит.
Определите объем памяти в байтах, отводимый этой программой для записи 50 номеров.
В ответе укажите только число.
Ответ: 250
- Так как в номере может быть использована либо одна буква из 18, либо одна цифра из 10, то всего в качестве одного символа в номере может быть использован один из 28 символов:
18 + 10 = 28
28 = 2i => i = 5
I = 7 * 5 = 35 бит
35 / 8 ~ 5 байт
I = 50 * 5 = 250 байт на хранение 50 номеров
При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 10 символов, первый и последний из которых — одна из 18 букв, а остальные — цифры (допускается использование 10 десятичных цифр). Каждый такой идентификатор в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит, все буквы также кодируются одинаковым и минимально возможным количеством бит).
Определите объём памяти, отводимый этой программой для записи 25 паролей. (Ответ дайте в байтах.)
Ответ: 150
- Идентификатор пароля по заданию состоит из букв и цифр, необходимо рассмотреть отдельно эти составляющие.
- Поскольку в пароле может присутствовать 18 букв, то подсчитаем, сколько бит необходимо для хранения 1-й буквы:
С помощью n бит можно закодировать 2n различных вариантов, Иначе говоря 18 = 2n, -> n = 5 бит (т.к. 4 мало, 24=16, 25 = 32)
10 = 2n, -> n = 4 бита (т.к. 3 мало, 23=8, 24 = 16)
В битах: 5 4 4 4 4 4 4 4 4 5 или: 5 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 5 = 5 * 2 + 4 * 8 = 42 бита
48 = 6·8 бит (6 байт).
6·25 = 150 байт
При регистрации в компьютерной системе каждому пользователю выдается пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора A, B, C, D, E, F, G, H, I, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 12 байт на одного пользователя.
Определите объем памяти (в байтах), необходимый для хранения сведений о 30 пользователях.
В ответе запишите только целое число - количество байт.
Типовые задания для тренировки
Ответ: 600
При регистрации в компьютерной системе каждому пользователю выдается пароль, состоящий из 7 символов и содержащий только символы из 33-символьного алфавита. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственного пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.
Для хранения сведений о 60 пользователях потребовалось 900 байт.
Сколько байт выделено для хранения дополнительных сведений об одном пользователе?
В ответ запишите только целое число - количество байт.
Типовые задания для тренировки
Ответ: 9
- Сначала определимся с паролем. По формуле Q = MN получаем:
33 = 2N -> N = 6 бит на 1 символ
-> 7*6 = 42 бит всего на пароль
48/8 = 6 42 бит ~ 6 байт
900 байт / 60 (пользователей) = 15 байт на каждого пользователя
15 байт (на хранение всей информации) - 6 байт (на хранение пароля) = 9 байт на дополнительные сведения
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 9 символов. В качестве символов используют прописные и строчные буквы латинского алфавита (в нём 26 символов), а также десятичные цифры. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено 18 байт на одного пользователя. В компьютерной системе выделено 1 Кб для хранения сведений о пользователях.
О каком наибольшем количестве пользователей может быть сохранена информация в системе? В ответе запишите только целое число – количество пользователей.
Типовые задания для тренировки
Ответ: 40
- Так как используются как прописные, так и строчные буквы, то получим всего вариантов символов для кодирования:
26 + 26 + 10 = 62
Q = 2n получим количество бит, требуемое для кодирования 1 символа пароля:Q = 2n -> 62 = 2n -> n = 6
6 * 9 = 54
54 / 8 = 7 байт
18 + 7 = 25 байт
1 Кб = 1024 байт
1024 / 25 = 40,96
