Кодирование вариантов и мощность алфавита: задания с разбором — ЕГЭ по информатике

ЕГЭ Информатика

ЕГЭ по информатике, тема «Кодирование вариантов и мощность алфавита»: Код Фано, Объём памяти для идентификаторов. Формулы темы. Ответ проверяется на странице, разбор открывается сразу.

Пример 1

Что больше: 2¹³ бит или 1 Кбайт?

Варианты ответа

Ответ и разбор

Ответ: они равны

Два в тринадцатой — восемь тысяч сто девяносто два бита. Килобайт — тысяча двадцать четыре байта по восемь бит — тоже восемь тысяч сто девяносто два бита. Равны.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-encoding-adv-09

Ещё задания — ниже. Открыть тренажёр

ZIP-архив может хранить файл вообще без сжатия: в спецификации для этого предусмотрен отдельный режим. Архив всё равно удобен как упаковка нескольких файлов и папок. Поэтому слово «архив» не гарантирует, что данные внутри обязательно стали меньше.

Формулы темы

Число вариантов и биты

Сколько бит нужно, чтобы закодировать 30 учеников класса?

N = 2i

N
количество различных вариантов, штук
i
количество бит на один вариант, бит

Каждый бит удваивает число вариантов. Для 30 человек 4 бита мало (16), а 5 бит хватает (32). Берут наименьшее i, при котором 2i не меньше нужного числа.

Округлять надо ВВЕРХ: 4,9 бита не бывает, нужен целый пятый.

Все карточки предмета — в разделе «Формулы»

Ещё задания

Пример 2

По каналу связи передаются сообщения, составленные только из букв А, В, Д, Л, Н. Буквы кодируются двоичным кодом, удовлетворяющим условию Фано: ни одно кодовое слово не является началом другого кодового слова. Для некоторых букв кодовые слова уже выбраны: Н — 001. Для остальных букв (А, В, Д, Л) кодовые слова ещё не выбраны, но каждая буква набора должна получить своё кодовое слово. Какое наименьшее количество двоичных знаков может занять код слова ЛАВАНДА?

Ответ и разбор

Ответ: 15

По условию Фано новое кодовое слово не может совпадать с известным (001), быть его началом или начинаться с него.
Заняты сами известные слова и их начала (0, 00), поэтому новые слова можно начинать только со свободных ветвей кодового дерева: 000, 01, 1.
Кодовые слова нужны ещё 4 буквам (А, В, Д, Л), а свободных ветвей 3 — одну ветвь придётся разделить: ветвь x делится на x0 и x1, и её слова становятся на знак длиннее.
В слове ЛАВАНДА: буква А — 3 раза, буквы В, Д, Л — по одному разу. Короткие слова выгодно отдавать частым буквам.
Наборы слов, которые могут дать наименьшую длину (любой другой набор по каждой длине не короче одного из них):

  • 1, 000, 010, 011 (длины 1, 3, 3, 3): А — 1, В — 000, Д — 010, Л — 011; длина кода 3 · 1 + 3 + 3 + 3 = 12;
  • 1, 01, 0000, 0001 (длины 1, 2, 4, 4): А — 1, В — 01, Д — 0000, Л — 0001; длина кода 3 · 1 + 2 + 4 + 4 = 13;
  • 01, 10, 11, 000 (длины 2, 2, 2, 3): А — 01, В — 10, Д — 11, Л — 000; длина кода 3 · 2 + 2 + 2 + 3 = 13.

Наименьшая длина кода букв А, В, Д, Л — 12.
Буквы с известным кодом: Н (001, 3 знака) встречается 1 раз — 3.
Итого: 12 + 3 = 15.

Ответ: 15.

Нашли ошибку? Напишите нам, код задания: ege-informatics-kod-fano-dlina-slova-1bw96mw

Пример 3

Каждому объекту в информационной системе присваивают идентификатор длиной 17 символов, составленный только из заглавных букв русского алфавита (33 буквы) и символов специального набора из 366 символов. Символы кодируются посимвольно одинаковым и наименьшим возможным числом бит, а под каждый идентификатор отводится одинаковое и наименьшее возможное целое число байт. Сколько байт памяти нужно для хранения сведений о 1024 объектах?

Ответ и разбор

Ответ: 20480

Решение

  1. В наборе 33 + 366 = 399 символов. 2⁸ = 256 < 399 < 512 = 2⁹, поэтому на символ нужно 9 бит.
  2. Идентификатор: 17 · 9 = 153 бита. Целых байт нужно 20: 19 байт — это только 152 бита.
  3. На 1024 объекта: 20 · 1024 = 20480 байт.

Ответ: 20480.

Нашли ошибку? Напишите нам, код задания: ege-informatics-obyom-identifikatorov-18ogjin

Пример 4

Сообщение из 100 символов закодировано равномерным двоичным кодом и занимает 600 бит. Какова наибольшая возможная мощность алфавита?

Варианты ответа

Ответ и разбор

Ответ: 64

Правильный ответ — шестьдесят четыре. На символ приходится шестьсот на сто — шесть бит. Шестью битами можно закодировать не больше чем два в шестой — шестьдесят четыре разных символа, поэтому наибольшая возможная мощность алфавита — шестьдесят четыре.

Почему так

Алфавиты из сорока восьми и шестидесяти символов тоже кодируются шестью битами, но это не наибольшая мощность. Для тридцати двух символов хватило бы пяти бит (два в пятой — тридцать два), и сообщение весило бы пятьсот бит.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-encoding-adv-10

Пример 5

Текст объёмом 2 Кбайт записан алфавитом из 16 символов. Сколько в нём символов?

Варианты ответа

Ответ и разбор

Ответ: 4096

Шестнадцать символов — четыре бита на символ. Два килобайта — две тысячи сорок восемь байт — шестнадцать тысяч триста восемьдесят четыре бита. Делим на четыре: четыре тысячи девяносто шесть символов.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-encoding-adv-02

Пример 6

Алфавит 128 символов, страница — 30 строк по 60 символов. Сколько байт весит страница?

Ответ и разбор

Ответ: 1575

Мощность алфавита N = 128 = 2⁷, значит на один символ уходит i = 7 бит. Символов на странице: 30 · 60 = 1800. Объём в битах: 1800 · 7 = 12 600, переводим в байты делением на 8: 12 600 : 8 = 1575.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-encoding-adv-04

Пример 7

В алфавите 33 буквы. Сколько бит отводится на букву и сколько байт займёт слово из 20 букв? Ответ — байты.

Ответ и разбор

Ответ: 15

Пять бит кодируют 2⁵ = 32 знака, а букв 33, поэтому пяти бит не хватает и на букву берут 6 бит (2⁶ = 64 ≥ 33). Слово из 20 букв весит 20 · 6 = 120 бит. Переводим в байты: 120 : 8 = 15, делится нацело — ровно 15 байт.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-encoding-adv-07

Пример 8

Пароль — 10 символов из алфавита в 32 символа. На пароль отводится целое число байт. Сколько байт нужно на пароли для 100 пользователей?

Ответ и разбор

Ответ: 700

В алфавите 32 = 2⁵ символа, значит на символ уходит 5 бит, а весь пароль весит 10 · 5 = 50 бит.

Почему так

В байте 8 бит, 50 : 8 = 6,25, но по условию на пароль отводится целое число байт, поэтому берём 7 байт (56 бит) — округление только вверх, шести байт (48 бит) не хватит. Для 100 пользователей: 100 · 7 = 700 байт.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-encoding-adv-05

Пример 9

Текст из 4096 символов перекодировали: был алфавит 256 символов, стал 16-символьный. На сколько байт уменьшился объём?

Ответ и разбор

Ответ: 2048

Считаем оба объёма. Было: 4096 символов на восемь бит — 32768 бит — 4096 байт. Стало: на четыре бита — 16384 бита — 2048 байт. Экономия: 4096 минус 2048 — 2048 байт.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-encoding-adv-03

Пример 10

Алфавит 64 символа, в сообщении 120 символов. Сколько байт занимает сообщение?

Варианты ответа

Ответ и разбор

Ответ: 90

Шестьдесят четыре — это два в шестой: шесть бит на символ. Всего шесть умножить на сто двадцать — семьсот двадцать бит, делим на восемь — девяносто байт.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-encoding-adv-01

Виды заданий темы

Рядом

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.