Здравствуйте! С вами Елена TeachYOU, и сегодня мы разберем задачи 11 из ЕГЭ по информатике. Задачи несложные, но почему-то у многих учеников с ними возникают проблемы.
Что такое равномерное кодирование
Для того, чтобы работать с какими-то объектами с помощью компьютера, необходимо их закодировать. Так как подавляющее большинство современных ЭВМ использует двоичную логику, разумно кодировать объекты с использованием двоичного кодирования.
Двоичное кодирование можно разделить на равномерное (когда кодовые слова, или коды, имеют одинаковую длину), и неравномерное (когда длина кодовых слов разная). Тема неравномерного кодирования поднимается в 4 задании ЕГЭ, можете посмотреть материал по нему в этой статье. Там разобраны примеры с разными вариантами кодирования. Если вам все еще непонятно, чем равномерное кодирование отличается от неравномерного, то перед тем, как читать материал по 11 заданию дальше, советую сначала просмотреть материал по ссылке выше.
Перевод битов в байты и далее
Прежде чем двигаться дальше, напомню правила перевода между единицами измерения информации. Основное:
- 1 байт = 8 бит
- 1 Кбайт = 1024 байт = 2^10 байт = 2^13 бит
- 1 Мбайт = 1024 Кбайт = 2^10 Кбайт = 2^23 бит
Что нужно знать про равномерное двоичное кодирование
Кодирование равномерное => все кодовые слова имеют одинаковую, минимально возможную, длину. Кодирование двоичное => кодовые слова состоят только из 0 и 1.
Сколько объектов можно закодировать, используя кодовые слова имеют длины i ?
Например, буква А может кодироваться кодовым словом 01101. В нем пять знаков (0 или 1). Говорят, что кодовое слово 01101 состоит из пяти бит. Бит - это ячейка, принимающая значение 0 или 1 (тире или точка, вкл или выкл и пр.).
Тогда кодовое слово 0110 состоит из 4 бит, слово 110011 - из 6 бит и т.д.
Посмотрим, сколько разных кодовых слов можно составить, если брать кодовые слова определенной длины (здесь нам поможет теория по теме "Комбинаторика" для 8 номера).
- Кодовые слова длины 1 - это 0 и 1. Их два (каждое занимает 1 бит).
- Кодовые слова длины 2 - это 00, 01, 10 и 11. Их четыре (каждое занимает 2 бит).
- Кодовые слова длины 3 я перечислять не буду. Их количество равно 2*2*2 = 2^3 = 8 (если непонятно, загляните в материал по комбинаторике). Каждое кодовое слово занимает 3 бита.
- ....
- Кодовые слова длины i - их 2^i. Каждое занимает i бит.
Получается, что, если для кодирования мы выберем кодовые слова длины i (i-битные), то сможем закодировать 2^i объектов.
Если в сообщении используется N символов, сколько бит нужно для кодирования каждого символа?
Количество i-битных кодовых слов равно 2^i.
Похоже, что, нужно подобрать такое i, чтобы N = 2^i.
Но на практике не всегда число N является степенью двойки. Поэтому для кодирования N объектов нужно взять такое минимальное i, чтобы выполнялось условие N <= 2^i.
Например:
- N = 14: 14 <= 16 = 2^4. Получается, что при кодировании 14 объектов с использованием равномерного двоичного кодирования на каждый объект будет приходиться 4 бита.
- N = 250: 250 <= 256 = 2^8 => 8 бит на объект.
- N = 2050: 2050 <= 4096 = 2^12 => 12 бит на объект.
Рассмотрим задачи 11 из ЕГЭ
Задача 1 (номер 1964 с компегэ)
При регистрации в компьютерной системе каждому объекту сопоставляется идентификатор, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байта на один объект.
Определите объём памяти (в байтах), необходимый для хранения сведений о 20 объектах. В ответе запишите только целое число – количество байт.
Из задачи следует, что нужно сохранить данные о 20 объектах. Для каждого из них хранится идентификатор (его информационный вес нужно вычислить) и дополнительные сведения (известны, 24 байта на один объект).
Начнем с вычисления количества байт, которое занимает один идентификатор.
Длина идентификатора 15 символов, а мощность алфавита равна восьми. Вспоминаем основную формулу информатики: N = 2^i, где N - количество кодируемых равномерным кодированием объектов, i - количество бит, которое приходится на один объект. N = 8 (нужно закодировать все символы из набора, поэтому N = мощности алфавита). Из 8 = 2^i находим i=3 бита. Каждый символ кодируется 3 битами, а идентификатор состоит из 15 символов. Получается, на один идентификатор приходится 15 * 3 = 45 бит = 5,625 байт.
Обращаем внимание, что в задаче говорится, что для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. Необходимо округлить 5,625 байт до целого значения. Но в большую или меньшую сторону?
Если округлим в меньшую, то получим 5 байт = 40 бит. Но для хранения идентификатора нужно 45 бит! 45 бит не помещаются в "коробочку" из 5 байт. Значит, нужно округлять в большую. Итого, на идентификатор приходится 6 байт.
Для вычисления информационного объема, необходимого для хранения сведений об одном объекте, найдем сумму байт, приходящихся на идентификатор и на дополнительные сведения:
6 + 24 = 30 (байт) - на 1 объект.
Вычислим объем информации для хранения сведений о 20 объектах:
30 (байт) * 20 (объектов) = 600 (байт).
Задача 2 (номер 212 с компегэ)
Для регистрации на сайте необходимо продумать пароль, состоящий из 9 символов. Он может содержать десятичные цифры, строчные или заглавные буквы латинского алфавита (алфавит содержит 26 букв) и символы из перечисленных: «.», «$», «#», «@», «%», «&». В базе данных для хранения сведения о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственного пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт одинаковое для каждого пользователя. Для хранения сведений о двадцати пользователях потребовалось 500 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе. В ответе запишите только целое число – количество байт.
Сайт хранит данные о 20 пользователях. Они занимают 500 байт. Для каждого пользователя хранятся пароль (его информационный объем нужно вычислить) и дополнительные сведения (эту величину нужно найти и взять в качестве ответа).
Начнем с поиска количества байт, приходящихся на одного пользователя:
500 (байт) / 20 (польз.) = 25 (байт на 1 польз.)
Разберемся с паролем. Мощность алфавита символов, которые используются для его записи:
N = 10 (цифр) + 26 (строчных букв) + 26 (заглавных букв) + 6 (символов «.», «$», «#», «@», «%», «&») = 68 (символов).
Сколькими битами можно закодировать каждый из 78 символов при использовании равномерного кодирования?
68 <= 2^i, i = 7 (бит).
Тогда пароль занимает
7 (бит) * 9 (символов) = 63 (бит) = 8 (байт).
Для одного пользователя хранится пароль (8 байт) и доп. сведения. Всего на пользователя приходится 25 байт. Тогда доп. сведения занимают
25 - 8 = 17 (байт).
Задача 3 (номер 463 с компегэ)
Очень люблю эту задачу авторства Евгения Джобса за нацеленность на понимание темы
Автомобильный номер состоит из одиннадцати букв русского алфавита A, B,C, E, H, K, M, O, P, T, X и десятичных цифр от 0 до 9. Каждый номер состоит из двух букв, затем идет 3 цифры и еще одна буква. Например, АВ901С.
В системе каждый такой номер кодируется посимвольно, при этом каждая буква и каждая цифра кодируются одинаковым минимально возможным количеством бит.
Укажите, сколько бит на один номер можно сэкономить, если кодировать с помощью одинакового минимально возможного количества бит каждую из трех групп – первые две буквы, три цифры и последняя буква.
В этой задаче есть "до" и "после".
"До": каждая буква и каждая цифра кодируются отдельно.
"После": кодируются отдельно первые две буквы, три цифры и последняя буква.
Разберемся, сколько бит занимал автомобильный номер при выборе способа кодирования "до".
- Буквы: N = 11 <= 16 = 2^4 => i = 4.
- Цифры: N = 10 <= 16 = 2^4 => i = 4.
- Весь номер состоит их трех цифр и трех букв, это 3 (буквы) * 4 (бита) + 3 (цифры) * 4 (бита) = 24 (бит на один номер)
Как кодируем номер "после"?
- Первые две буквы. Букв 11. Количество пар букв (АА, АВ, ... , ХХ) равно 11*11 = 121. Нашли объекты - это пары букв. Их количество N = 121 <= 128 = 2^7 => i=7 бит. Раньше каждую букву мы кодировали 4 битами и две буквы занимали 8 бит. А теперь 7. Э - экономия!
- Три цифры. Цифр 10. Количество троек цифр (000, 001, ... , 999) равно 10*10*10 = 1000. В этом случае кодируемые объекты - это тройки цифр. N = 1000 <= 1024 = 2^10 => i = 10 бит. "До" каждую цифру кодировали 4 битами, три цифры занимали 12 бит. А сейчас 10. И здесь сэкономили.
- Последняя буква. N = 11 <= 16 = 2^4 => i=4. Тут ничего не изменилось: "до" кодировали объекты-буквы и здесь поступили так же.
- Количество бит на номер "после": 7 + 10 + 4 = 21 (бит).
Итого сэкономили 24 - 21 = 3 (бита).
Какие еще задачи посмотреть, чтобы закрепить материал?
Сайт kompege.ru покорил мое сердце, и теперь я считаю себя его амбассадором)
Если вы только знакомитесь с 11 номерами, решайте любые задачи (на сайте компегэ их можно отсортировать по сложности, начните с простых).
Для более продвинутых настоятельно советую прорешать задачи из списка ниже, так как в каждой есть свои тонкости.
Номера 11: 4468, 4323, 2119, 5433.
