Навигация по странице
О задании
Задание 11 ЕГЭ по информатике нацелено на проверку умений учащихся подсчитывать информационный объём сообщения. Это задание, в целом, очень похоже на рассмотренное ранее задание 7, где требовалось подсчитать вес изображения, звукового или видеофайла.
Но в случае с 11 заданиями, мы будем работать только с текстовой информацией. Это во многом упрощает решение задания 11, однако, в нём присутствует ряд моментов, на которые стоит обратить внимание, чтобы не случайно не допустить ошибку в ответе.
О всех тонкостях и не самых очевидных моментах мы и поговорим в этой статье. Но для начала, давайте узнаем, как в компьютере хранится информация и как правильно определять её объем.
Хранение информации в компьютере
В современном мире информационные технологии стали неотъемлемой частью нашей жизни. Компьютеры, смартфоны и другие устройства стали нашими верными помощниками в работе, учёбе и развлечениях. Но как именно хранится информация в этих устройствах?
Любой современный компьютер — это цифровое устройство. В прошлой статье, посвящённой заданию 7 ЕГЭ по информатике, мы уже выяснили, чем отличаются аналоговые сигналы, от цифровых. Аналогично дело обстоит и с устройствами. Цифровые устройства могут работать только с цифровыми сигналами. А значит, что любая информация — текстовая, звуковая, графическая — может храниться только в виде определённого набора цифр. Но каких цифр?
Таких цифр, с помощью которых можно хранить любую информацию, всего две — 0 и 1. По правде говоря, если немного углубиться в устройство процессора и любой цифровой электроники, то это даже не цифры. Это лишь логические значения, которые указывают, что напряжение электрического сигнала в момент измерение преодолело заданный порог.
Аналогично, можно вместо 0 и 1 использовать слова («Да» и «Нет», «Истина» и «Ложь», «Высокий» и «Низкий») или попросту включение и выключение лампочки. Суть будет одна и та же — мы просто указываем на одно из двух возможных состояний системы. Но именно использование цифр 0 и 1 открывает нам дорогу к возможностям кодирования информации.
Представим такую ситуацию: у нас есть пятибалльная шкала оценивания работы учащихся. И все оценки необходимо как-то хранить в компьютере — в цифровом виде. При этом, мы не можем просто так записать в память компьютера цифру 5. Наши микросхемы памяти просто не поймут, что это такое. У них ведь есть только 2 значения: нет напряжения (логический 0) и напряжение выше порогового (логическая 1).
Здесь и вступает в игру кодирование. Каждый символ нашей шкалы оценивания мы можем закодировать несколькими значениями из двух: нуля и единицы.
Например, для значения «1» все просто — используем одну единицу. Со значением «2» уже посложнее. Можем записать её как одну единицу и один ноль, следующие друг за другом — «10». Тогда числу «3» у нас будет соответствовать значение «11», 4 — «100», а «5» — «101». Да, мы с вами только что заново придумали двоичную систему счисления.
Но в этой статье мы поговорим немного о другом. Вот есть у нас оценки, закодировали мы их. А сколько памяти выделять под 1 оценку? А под 10?
Минимальной базовой единицей измерения информации в компьютерных системах является бит. Каждый бит может принимать одно из двух значений: 0 или 1. Соответсвтенно, если мы хотим вычислить объём памяти под одну оценку, нам необходимо понять, сколько бит требуется, чтобы максимальное закодировать значение этой оценки.
Если значение «1» мы можем закодировать одним битом, «2» и «3» — двумя, а «4» и «5» (максимальное) — тремя, то это означает, что под любую оценку нам необходимо выделять память под 3 бита. Иначе у нас просто может не поместиться какая-либо оценка. Например значения «4» и «5» не поместятся, если у нас будет выделено под оценку всего 2 бита.
Можно представить выделяемую под оценки память как некие ячейки, в которых мы храним значение каждого числа. Если ячеек будет меньше, то и число не поместится. А если нам требуется всего 1 ячейка (как для значения «1»), то оставшиеся ячейки слева заполним незначащими нулями.
Как видите, на изображении выше у нас есть еще некое число «N» — максимально возможное для нашей трёхбитной системы памяти. Давайте определим, сколько различных чисел можем закодировать с помощью трёх битов.
Для этого воспользуемся формулой Хартли:
Здесь:
- N — количество различных вариантов кодирования
- i — используемое количество бит
По данной формуле имеем количество вариантов кодирования 23, то есть всего 8 вариаций. Таким образом можем закодировать, например, все числа от 0 до 7. Также говорят, что в таком случае мы имеем алфавит из 8 символов или мощность алфавита равна 8.
Естественно, под алфавитом здесь подразумевается на буквы «абв» и так далее, а некий набор символов. Он может включать в себя как цифры, так и буквы или специальные символы. Мощность же алфавита означает количество символов, которое содержится в алфавите.
Для вычисления числа бит i, которое потребуется для кодирования N символов воспользуемся следующей формулой:
Вычислим логарифм числа 5 по основанию 2. Получим приближённое значение 2,322. Это у нас дробное число, но количество ячеек (бит) всегда должно быть целым, мы же не можем разделить и без того минимальную единицу измерения информации.
Встаёт вопрос, как из числа 2,322 получить целое. У нас есть два пути округления: в большую или меньшую сторону. Именно в этом и кроется тонкость решения задания 11 ЕГЭ.
Но давайте рассуждать логически. Мы уже видели, что число 5 имеет значение «101», то есть тут нужно 3 бита. Тогда, если мы округлим 2,322 до 2, то все наши значения не поместятся.
Отсюда следует вывод: применяя формулу Хартли для поиска количества бит всегда округляем результат в большую сторону!
И сразу отметим следующее: хоть бит и является минимальной единицей измерения информации, но в современных компьютерах минимальной адресуемой единицей хранения информации является 1 байт.
То есть самая маленькая область памяти, куда можем записать значение, будет равняться одному байту. На подавляющем большинстве современных компьютеров 1 байт состоит из 8 бит.
Поэтому, если требуется определить объем памяти, необходимый для хранения какой-либо информации, то в результате всегда будут байты.
Для перевода значений из байтов в биты и наоборот лучше всего будет запомнить следующие равенства:
1 байт = 8 бит = 23 бит
1 Кбайт = 210 байт = 210 · 23 бит = 213 бит
1 Мбайт = 210 Кбайт = 210 · 23 байт = 220 · 23 бит = 223 бит
1 Гбайт = 210 Мбайт = 210 · 23 Кбайт = 220 · 23 байт = 230 · 23 бит = 233 бит
Немного про терминологию. Сокращение Кбайт (или КБ) означает «килобайт». Один килобайт равен 1024 байт, хотя традиционно десятичная приставка «Кило-» означает умножение на 1000, а не 1024.
В англоязычной литературе можете встретить иной термин: Кибибайт (KiB), который будет означать 1024 байт, когда Килобайт (KB) — 1000 байт. Далее аналогично Мебибайт = 1024 Кибибайт, Гибибайт = 1024 Мебибайт и так далее. То есть здесь используются двоичные приставки, а не десятичные.
От этого порой могут страдать потребители, которые покупают флеш-накопитель. На таком изделии может быть указана ёмкость в 1 Гигабайт, что равняется 1 000 000 000 байт. А покупатель же предполагает, что ёмкость указана в привычных ему единицах (Гибибайт) и составляет 1 073 741 824 байт.
Но в нашей стране все же принято, что 1 Килобайт это 1024 байт, 1 Мегабайт это 1024 Килобайт и так далее.
Еще одно непонимание у пользователя может возникнуть при определении скорости передачи данных. Например, вы видите скорость в 100 Мб в секунду. Но файл, который весит 900 Мегабайт почему-то скачивается не за 9 секунд.
Тут опять же дело в том, что сокращение «Мб» означает «Мегабит» (на английском будет понятней — «Mbit»), а не «Мегабайт» (обратите внимание на букву «б», при обозначении битов она строчная). И как раз скорость передачи данных принято обозначать в битах, Килобитах, Мегабитах и так далее.
Возвращаясь же к заданию 11 ЕГЭ по информатике, помните, что если вы работаете с объёмом памяти сообщения, то он должен быть выражен в байтах. Тогда как вес символа должен быть представлен в битах. При подставлении объёма сообщения и веса символа в одну формулу, например для вычисления длины сообщения, не забывайте приводить все значения к одной размерности!
Объём текстовой информации
Итак, мы уже разобрались с тем, как хранится информация на компьютере и как найти вес одного символа, зная мощность алфавита. Но одного символа нам явно не хватит, чтобы закодировать нужное нам сообщение. Этим сообщением, например, может быть как любая текстовая информация, так и пароль или серийный номер изделия.
Что мы знаем точно, так это то, что у этого сообщения должна быть определённая длина — количество символов, из которых состоит каждое сообщение. Тогда, зная вес одного символа (i) и длину сообщения (L), можем вычислить и объём всего сообщения:
Если же требуется определить максимально возможную длину одного сообщения, то из формулы выше выразим значение L:
При этом, результат формулы может оказаться дробным. Здесь вспоминаем случай с вычислением веса символа и действуем наоборот: если получилась длина сообщения «2,322», то вместить 3 символа мы никак не сможем. И округлять здесь нужно в меньшую сторону!
Алгоритм решения 11 задания
У нас на руках есть все формулы, необходимые для решения этого задания:
,
Все, то от нас требуется — правильно произвести расчеты, не ошибиться в округлении и перевести результат в нужную размерность.
Формулировка 1
Нам дана мощность алфавита N. Также сказано, что для хранения K сообщений отведено не более / не менее X байт. То есть это вес одного сообщения, умноженный на какое-то число K. Здесь требуется найти максимально возможную длину сообщения — значение L из формулы выше.
Для решения будем использовать следующую формулу:
Сначала найдем вес одного символа. Для этого вычислим логарифм по основания 2 от мощности алфавита.
Затем определяем вес одного сообщения: делим указанный объем X на количество сообщений K. Здесь обратите внимание на формулировку. Если в условии указано, что «для хранения K сообщений отведено не более X байт», то округляем полученное значение в меньшую сторону. Если указано обратное — «не менее X байт», то округляем в большую сторону.
Далее подставляем все значения в формулу. Не забываем учесть все размерности. Результат обычно получается дробным числом, а в ответ просят записать только целую часть этого числа.
Формулировка 2
Здесь нам также даётся мощность алфавита N, длина сообщения L, а нам необходимо найти объем памяти I для хранения K сообщений.
Для решения будем использовать следующую формулу:
Сначала определим, сколько бит занимает один символ. Это будет логарифм по основанию 2 от числа N. Не забываем округлять в большую сторону.
Далее вычисляем вес одного сообщения в байтах, умножая вес одного символа на длину сообщения. Получаем значения в битах, которое переводим в байты — делим результат на 8 и не забываем про округление.
Потом определяем, сколько будет весить все K сообщений. И приводим к необходимой по условию размерности. Так, как мы получили число в байтах, то для перевода в Килобайты — делим на 210, в Мегабайты — 220.
Как видите, в любой формулировке достаточно подставить имеющиеся значения в формулу и правильно перевести результат в требуемую размерность. Рассмотрим несколько примеров для закрепления.
Пример 1
На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы (с учётом регистра) и символы из 963-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 2000 серийных номеров отведено не более 693 Кбайт памяти. Определите максимально возможную длину серийного номера. В ответе запишите только целое число.
Давайте выпишем значения, которые нам даны по условию:
- Мощность алфавита N: 10 цифр + 52 латинские буквы + 963 символа = 1025 символов
- Вес 2000 сообщений I: 693 Кбайта.
Требуется найти длину сообщения L.
Вспоминаем формулу:
Давайте подробно разберем её по частям. Начнем с веса символа. Логарифм по основанию 2 от числа 1025 будет немного больше 10 (ведь 210 — это 1024). Следовательно, вес символа должен быть 11 бит/символ (округляем в большую сторону)
Далее определим вес одного сообщения. Для этого переводим 693 Кбайт в байты и делим на 2000: 693 · 210 / 2000 = 354 байт, здесь округляем в меньшую сторону (отведено не более 693 Кбайт)
Теперь делим вес одного сообщения на вес символа и не забываем перевести байты в биты: 354 (байт) · 8 / 11 (бит/символ) = 257, 45 (символ).
В ответе записываем только целое число 257.
Пример 2
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 317 символов и содержащий только десятичные цифры и символы из 4090-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Определите объём памяти (в Мбайт), необходимый для хранения 262 144 идентификаторов.
В ответе запишите только целое число – количество Мбайт.
Давайте выпишем значения, которые нам даны по условию:
- Мощность алфавита N: 10 цифр + 4090 символа = 5000 символов
- Длина сообщения L: 317 символов.
- Количество сообщений K: 262 144
Требуется найти вес I, необходимый для хранения всех сообщений.
Будем использовать следующую формулу:
Как обычно, начинаем с веса символа. Логарифм по основанию 2 от 5000 это число, чуть большее 12. Округляем в большую сторону и получаем вес символа в 13 бит/символ.
Далее вычисляем вес одного сообщения в байтах. Умножаем вес одного символа на длину сообщения: 13 бит/символ · 317 символов / 8 = 516 байт (округляем в большую сторону, иначе все символы не вместятся).
В конце умножаем получившееся число байт на количество сообщений и переводим в Мбайты: 516(байт) · 262 144 / 220 = 129 Мбайт.