Введение
В этой статье разберём посимвольное и не посимвольное кодирование для нахождения информационного объёма в задании №11 ЕГЭ по информатике.
Термины, которые будем использовать:
Информационный объём, посимвольное кодирование, не посимвольное кодирование, информационный вес символа, мощность алфавита.
При подсчёте информационного объёма сообщения используются единицы измерения информации, они наверняка встречались тебе в школе:
- Бит — наименьшая единица измерения информации.
- Байт = 8 или 2³ бит.
- Килобайт = 2¹⁰ байт = 2¹³ бит.
- Мегабайт = 2¹⁰ Кбайт = 2²⁰ байт = 2²³ бит.
- Гигабайт = 2¹⁰ Мбайт = 2²⁰ Кбайт = 2³⁰ байт = 2³³ бит.
Потренируйся:
- Сколько бит в 35 байтах?
- Сколько Кбайт в 8192 бит?
- Сколько Мбайт в 5 Гбайт?
- 280
- 1
- 5120
Для измерения информационного объёма нужно знать:
- Длину сообщения, то есть количество символов.
- Информационный вес одного символа в битах.
Посимвольное кодирование
Главный принцип:
Каждый символ кодируется одинаковым и минимально возможным количеством бит.
Запоминаем основную формулу:
$ N = 2ⁱ $, где
- N — мощность алфавита, т.е. количество символов алфавита.
- i — минимальное количество бит, необходимое для кодирования любого символа.
При этом N ≤ 2ⁱ. Например, если мощность алфавита равна 32, то есть 2⁵, тогда i = 5, но если N не является степенью двойки и равно 15, то наименьшее возможное количество бит для кодирования будет 4, потому что 15 ≤ 2⁴.
Для решения №11 ЕГЭ по информатике принцип кодирования расширяется до ещё одного условия:
Каждое слово кодируется одинаковым, целым и минимально возможным количеством байт.
Например, тебе необходимо составить пароль из 13 символов, при этом ты можешь использовать 33-символьный алфавит.
Сначала определим мощность: N = 33. Далее найдём количество бит для кодирования символов: 33 ≤ 2ⁱ, минимальное i = 6, значит, на каждый символ достаточно 6 бит, а на пароль целиком — 6 * 13 = 78 бит. Но пароль нужно закодировать в байтах, тогда 78 / 8 = 9.75 байт. Чтобы понять, в какую сторону округлить, представь память компьютера, разделённую на ячейки, каждая из которых вмещает в себя 1 байт. Может ли наш пароль поместится в 9 таких ячеек, если для него нужно минимум 9.75? Нет, значит придётся взять 10 и закодировать десятью байтами.
Попрактикуйся:
Найди информационный объём документа в Кбайт, состоящего из 20 страниц, на каждой из которых записано по 600 символов, если мощность используемого алфавита составляет 100 символов. В ответе укажи только целую часть числа.
10
Примеры заданий
А теперь отточим знания на реальных задачах.
Задание 1
В популярной онлайн-школе каждому сотруднику присваивается идентификатор, состоящий из 15 символов и содержащий только символы Ш, К, О, Л, А (таким образом, используется 5 различных символов). Каждый такой идентификатор в компьютерной системе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование, все символы кодируются одинаковым и минимально возможным количеством бит). Укажите объём памяти в байтах, отводимый этой системой для записи 30 идентификаторов. В ответе запишите только число, слово «байт» писать не нужно.
Наш алфавит состоит из 5 символов (Ш,К,О,Л,А). Воспользуемся формулой N = 2ⁱ. Тогда i = 3 бит (если i будет равняться 2, то мы не сможем закодировать все 5 симв. алфавита, поэтому берём в большую сторону).
Пароль состоит из 15 симв., каждый символ кодируется 3 битами.
Тогда весь пароль кодируется 3 * 15 = 45 битами. Переведём в байты: 45 / 8 = 5,625, округлим в большую сторону = 6 (иначе не поместится в памяти). Для 30 паролей потребуется 30 * 6 = 180 байт.
Ответ: 180
Задание 2
В популярной онлайн-школе каждому сотруднику присваивается идентификатор, состоящий из 6 символов и содержащий только символы из 6-буквенного набора Л, Е, Г, И, О, Н. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора для каждого сотрудника в системе хранятся дополнительные сведения, для чего отведено 10 байт. Определите объём памяти в байтах, необходимый для хранения сведений о 100 сотрудниках.
Наш алфавит состоит из 6 символов (Л, Е, Г, И, О, Н). Воспользуемся формулой N = 2ⁱ. Тогда i = 3 бит (если i будет равняться 2, то мы не сможем закодировать все 6 симв. алфавита, поэтому берём в большую сторону).
Пароль состоит из 6 симв., каждый символ кодируется 3 битами.
Тогда весь пароль кодируется 3 * 6 = 18 битами. Переведём в байты: 18 / 8 = 2,25, округляем в большую сторону = 3 (иначе не поместится в памяти). Тогда для одного человека потребуется 3 + 10 = 13 байт (информация о пароле и дополнительные сведения). Для 100 человек потребуется 100 * 13 = 1300 байт.
Ответ: 1300
Задание 3
В крупной IT-компании каждому сотруднику в электронной почте компании выделяется «почтовый ящик», которому присваивается код сотрудника, состоящий из 8 символов, первый и последний из которых — одна из 20 букв, а остальные — цифры (допускается использование 10 десятичных цифр). Каждый такой код в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит; все буквы кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти в байтах, отводимый IT-компанией для записи 500 кодов.
Наш алфавит состоит из 20 букв для первого и последнего символов пароля и из 10 цифр для всех остальных символов пароля. Воспользуемся формулой N = 2ⁱ. Тогда i = 5 бит для первого и последнего символов пароля (если i будет равняться 4, то мы не сможем закодировать 20 симв. алфавита, поэтому берём в большую сторону), i = 4 бит для всех остальных символов пароля (если i будет равняться 3, то мы не сможем закодировать 10 симв. алфавита, поэтому берём в большую сторону).
Пароль состоит из 8 симв., первый и последний символы кодируются 5 битами, остальные 4.
Тогда весь пароль кодируется 5 * 2 + 4 * 6 = 34 битами. Переведём в байты: 34 / 8 = 4,25, округляем в большую сторону = 5 (иначе не поместится в памяти). Для 500 человек потребуется 500 * 5 = 2500 байт.
Ответ: 2500
Не посимвольное кодирование
Главный принцип: определение информационного веса уникальных символов с помощью все той же формулы N = 2ⁱ.
Например, номер месяца можно выразить с помощью числа от 1 до 12, всего уникальных символов 12, тогда для кодирования любого из них потребуется 4 бита или 1 байт.
Проверь себя:
В велогонке участвуют всего 25 спортсменов, камера фиксирует результаты завершения гонки каждым спортсменом и сохраняет их порядковый номер (число от 1 до 25) в базе. Какой информационный объём в байтах будет храниться в базе после завершения гонки последним участником?
Каждый номер можно закодировать 5 битами, значит информационный объём для 25 номеров в базе будет равен 5*25 = 125 бит или 125 / 8 = 16 байт.
Ответ: 16
Примеры заданий
Задание 1
В крупной IT-компании каждому сотруднику в электронной почте компании выделяется «почтовый ящик», которому присваивается «имя» и «номер отдела» пользователя, а также дополнительная информация. «Имя» пользователя содержит 17 символов и может включать латинские буквы (заглавные и строчные буквы различаются), десятичные цифры и специальные знаки из набора @#$%^&*(). Для хранения «имени» используется посимвольное кодирование, все символы кодируются одинаковым минимально возможным количеством битов, для записи «имени» отводится минимально возможное целое число байтов. «Номер отдела» пользователя (целое число от 1 до 1200) кодируется отдельно и занимает минимально возможное целое число байтов. Известно, что для каждого сотрудника выделено всего 48 байт данных. Сколько байт выделено для хранения дополнительной информации об одном сотруднике? В ответе запишите только целое число — количество байт.
Для начала найдём, сколько памяти необходимо для личного кода. Наш алфавит состоит из 71 символа (26 прописных букв + 26 строчных букв + 10 цифр + 9 специальных симв.). Воспользуемся формулой N = 2ⁱ. Тогда i = 7 бит (если i будет равняться 6, то мы не сможем закодировать все 71 симв. алфавита, поэтому берём в большую сторону).
Пароль состоит из 17 симв., каждый символ кодируется 7 битами.
Тогда весь личный код кодируется 17 * 7 = 119 битами. Переведём в байты: 119 / 8 = 14,875, округляем в большую сторону = 15 (иначе не поместится в памяти).
Теперь найдём, сколько памяти необходимо для номера подразделения. Он кодируется не посимвольно, значит, нам надо просто определить глубину кодирования уникальных символов (их всего 1200). Воспользуемся формулой N = 2ⁱ. Тогда i = 11 бит (если i будет равняться 10, то мы не сможем закодировать все 1200 симв., поэтому берём в большую сторону). Переведём в байты: 11 / 8 = 1,375, округляем в большую сторону = 2 (иначе не поместится в памяти).
Мы знаем, что личный код + номер подразделения + дополнительные данные = весь объём информации. Найдём дополнительные сведения: 48—15—2 = 31 байт.
Ответ: 31
Умение определять информационный объём точно поможет тебе в решении задания №11 ЕГЭ по информатике.
Автор:
Быкова Оксана, методист «100балльного репетитора» по информатике ЕГЭ
