Коды букв и кодовые слова: задания с разбором — ОГЭ по информатике

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

ОГЭ по информатике, тема «Коды букв и кодовые слова»: Расшифровки с буквой, Число слов из алфавита. Формулы темы. Ответ проверяется на странице, разбор открывается сразу.

Пример 1

Сколько бит нужно на букву в равномерном коде из 4 букв?

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

Ответ: 2

Четыре комбинации покрываются двумя битами: 00, 01, 10, 11 — по одной на букву.

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

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

Ячейка памяти DRAM хранит бит с помощью электрического заряда в крошечном конденсаторе. Заряд постепенно утекает, поэтому память регулярно обновляют. Даже когда программа ничего не меняет, оборудование продолжает поддерживать записанные данные.

Формулы темы

Префиксный код: чтение и сокращение

Как декодировать префиксный код и проверить сокращение кодового слова?

p — не начало q

p
непустое двоичное кодовое слово одного символа, последовательность битов
q
любое другое кодовое слово; коды всех символов различны, последовательность битов

Условие Фано здесь означает: ни одно кодовое слово не является началом другого. Такой код можно читать слева направо: как только набран код символа, записывай символ и начинай следующий.
Пример: А = 0, Б = 11, В = 101, Г = 1000, Д = 1001. Это полный список кодов. Декодируем строку 10010101111000: 1001 / 0 / 101 / 11 / 1000 → Д / А / В / Б / Г.
Ответ: ДАВБГ; все биты использованы.
Можно ли сделать код Г короче, сохранив остальные коды и условие Фано? Однобитный 0 уже занят; 1 был бы началом кодов Б, В и Д. Из двухбитных 00 и 01 начинаются с кода А; 10 является началом кодов В = 101 и Д = 1001; 11 занят кодом Б. Из трёхбитных слова на 0 начинаются с кода А, 110 и 111 — с кода Б; 100 является началом кода Д = 1001; 101 занят кодом В. Подходящего слова длины 1, 2 или 3 нет. Значит, нынешняя длина кода Г — 4 бита — минимальна при неизменных кодах А, Б, В и Д.

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

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

Ещё задания

Пример 2

Выберите вариант, который правильно заполняет пропуск:

Двоичных слов длины 4 существует ровно ___.

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

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

Ответ: 16

Каждый из 4 разрядов принимает 2 значения, всего 2⁴.

Остальные — длина слова, число слов длины 3 и число слов длины 5.

Нашли ошибку? Напишите нам, код задания: inf-oge-informatics-kodirovanie-035

Пример 3

Буквы А, Б, В, Г и Д закодированы двоичным кодом: А — 100, Б — 0, В — 1, Г — 000, Д — 11. Получена цепочка 110011. Сколько существует различных сообщений из этих букв, которые кодируются этой цепочкой и содержат хотя бы одну букву Б?

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

Ответ: 4

Условие Фано не выполнено: код Г (000) начинается с кода Б (0), код А (100) начинается с кода В (1), код Д (11) начинается с кода В (1). Поэтому цепочку 110011 можно разрезать на коды букв по-разному.
Переберём все способы слева направо, как ветви дерева вариантов:

1) 1 · 100 · 1 · 1 — ВАВВ;

2) 1 · 100 · 11 — ВАД;

3) 1 · 1 · 0 · 0 · 1 · 1 — ВВББВВ (есть Б);

4) 1 · 1 · 0 · 0 · 11 — ВВББД (есть Б);

5) 11 · 0 · 0 · 1 · 1 — ДББВВ (есть Б);

6) 11 · 0 · 0 · 11 — ДББД (есть Б).

Буква Б есть в 4 сообщениях из 6: ВВББВВ, ВВББД, ДББВВ, ДББД.

Проверка: всего 6 сообщений, без буквы Б — 2; 6 − 2 = 4. Ответ 6 получился бы, если забыть про букву Б, а 2 — если сосчитать сообщения без неё.

Ответ: 4.

Нашли ошибку? Напишите нам, код задания: oge-informatics-rasshifrovki-s-bukvoy-uars7j

Пример 4

Выберите вариант, который правильно заполняет пропуск:

Даны коды А = 0, Б = 10, В = 110, Г = 1110, Д = 1111. Сообщение «ГАД» занимает ___ бит.

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

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

Ответ: 9

Складываем длины кодов: 4 + 1 + 4.

Остальные — расчёт по равномерному коду из 4 бит, по 2 бита и число букв.

Нашли ошибку? Напишите нам, код задания: inf-oge-informatics-kodirovanie-078

Пример 5

Буквы кодируются так: А = 0, Б = 10, В = 11. Сколько бит в коде слова БАВ?

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

Ответ: 5

Длина кода — сумма длин букв: Б = 10 (2 бита), А = 0 (1 бит), В = 11 (2 бита). Итого 5 бит.

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

Пример 6

Алфавит содержит 2 буквы. Сколько различных паролей длины 4 можно составить, если буквы могут повторяться?

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

Ответ: 16

Каждую из 4 позиций можно заполнить 2 способами.
Всего: 2⁴ = 16.

Нашли ошибку? Напишите нам, код задания: oge-informatics-word-count-3mh76f

Пример 7

Выберите вариант, который правильно заполняет пропуск:

Для букв использован набор А = 0, Б = 01, В = 11, Г = 1, не удовлетворяющий условию Фано. Цепочку 011 можно раскодировать ___ способами.

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

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

Ответ: 3

Перебираем разбиения: 0|1|1 = АГГ, 0|11 = АВ, 01|1 = БГ.

Остальные пропускают одно из разбиений или добавляют невозможное.

Нашли ошибку? Напишите нам, код задания: inf-oge-informatics-kodirovanie-121

Пример 8

Буквы кодируются так: А = 1, Б = 0. Какое слово закодировано последовательностью 1010?

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

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

Ответ: АБАБ

Разбиваем на коды: 1 = А, 0 = Б, 1 = А, 0 = Б. Получается слово АБАБ.

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

Пример 9

Выберите вариант, который правильно заполняет пропуск:

Для пяти букв построен код А = 1, Б = 01, В = 001, Г = 0001, Д = 0000. Если все буквы встречаются одинаково часто, средняя длина кода буквы равна ___ бита.

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

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

Ответ: 2,8

Складываем длины кодов (1 + 2 + 3 + 4 + 4 = 14) и делим на число букв.

Остальные — округление, полусумма крайних длин и сумма длин без деления.

Нашли ошибку? Напишите нам, код задания: inf-oge-informatics-kodirovanie-117

Пример 10

Выберите вариант, который правильно заполняет пропуск:

Для букв А, Б, В выбраны коды 1, 01 и 001. Кратчайший код буквы Г, сохраняющий условие Фано, — ___.

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

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

Ответ: 000

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

Варианты 00 и 0 служат началом кода 001, а 0011 начинается с уже занятого кода 001.

Нашли ошибку? Напишите нам, код задания: inf-oge-informatics-kodirovanie-017

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

Рядом

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

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

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

Родителю

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