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

Задание 2 ОГЭ по информатике

Что проверяет линия, сколько она стоит, на чём теряют баллы и как решать — по нашим конспектам. В банке 50 заданий этой линии с разбором.

Аналитика ОГЭ: №2 (кодирование, префиксный код, условие Фано)

Баллы: 1 первичный балл
Частота: в каждом варианте

Частые ловушки

Разбивают цепочку наугад, а не слева направо по кодовым словам
Не проверяют, что код префиксный (иначе разбиение неоднозначно)
Теряют или добавляют один бит при переписывании последовательности

Совет. Читай биты слева направо: как только накопленные цифры совпали с кодом буквы — выписывай букву и продолжай

Разборы

Разбор примера

Задание 2: декодировать последовательность

По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для кодирования используется двоичный префиксный код: А — 0, Б — 10, В — 110, Г — 1110, Д — 1111. Расшифруйте последовательность 1110011010 01111, зная, что в ней шесть букв. Пробелы поставлены для удобства чтения.

Показать решение по шагам

1. Склеиваем поток без пробелов: 111001101001111. Читаем слева направо по одному биту.
2. 1 — нет такой буквы; 11 — нет; 111 — нет; 1110 = Г. Остаток: 01101001111.
3. 0 = А. Остаток: 1101001111. Далее 1 — нет; 11 — нет; 110 = В. Остаток: 1001111.
4. 10 = Б. Остаток: 01111. 0 = А. Остаток: 1111 = Д.
5. Получилось ГАВБАД — ровно шесть букв, как обещано в условии. Совпадение числа букв — главная проверка: если букв вышло больше или меньше, где-то отрезан не тот кусок.

Ответ: ГАВБАД

Разбор примера

Задание 2: достроить код так, чтобы условие Фано выполнялось

Для кодирования букв А, Б, В, Г используется неравномерный двоичный код. Известно: А — 0, Б — 10, В — 110. Какое из кодовых слов можно взять для буквы Г, чтобы код остался префиксным: 1) 11; 2) 1100; 3) 111; 4) 0110?

Показать решение по шагам

1. Проверяем каждый вариант на условие Фано: кодовое слово не должно быть началом другого и другие не должны быть его началом.
2. 1) 11 — является началом слова В (110). Нельзя.
3. 2) 1100 — начинается со 110, то есть В является его началом. Нельзя.
4. 3) 111 — сравниваем с 0, 10, 110: ни одно из них не начинается с 111, и 111 не начинается ни с одного из них (после 1 идёт 1, а у Б после 1 идёт 0; у В третий бит 0, а здесь 1). Подходит.
5. 4) 0110 — начинается с 0, а это код буквы А. Нельзя.
6. Ответ 3. Приём: проверяй пары в обе стороны, иначе легко пропустить случай, где новое слово длиннее старого.

Ответ: 3

Разбор примера

Задание 2: сколько битов нужно на сообщение

Буквы кодируются префиксным кодом: А — 0, Б — 10, В — 110, Г — 111. Сколько битов займёт закодированное сообщение БАГАВ?

Показать решение по шагам

1. Выписываем код каждой буквы по порядку: Б = 10, А = 0, Г = 111, А = 0, В = 110.
2. Склеиваем: 10 + 0 + 111 + 0 + 110 = 1001110110.
3. Считаем длину: 2 + 1 + 3 + 1 + 3 = 10 бит.
4. Смысл неравномерного кода: при равномерном кодировании четырёх букв нужно по 2 бита на каждую, то есть 10 бит на пять букв — столько же. Выигрыш появляется, когда частые буквы получают короткие коды: в тексте, где А встречается вдвое чаще остальных, такой код будет экономнее равномерного.

Ответ: 10

Разбор примера

Файл-ответ decode.py (формат задания 16): программа, которая декодирует сама

Соберите программу, которая по таблице префиксного кода расшифровывает двоичную последовательность. Файл сохраняется как decode.py — в задании 16 сдают именно файл с текстом программы, язык любой.

Показать решение по шагам

1. Замысел: идём по потоку слева направо, копим биты в буфер; как только буфер совпал с каким-то кодовым словом, выводим букву и очищаем буфер. Так работает свойство префиксного кода — возвращаться назад не нужно.
2. Код целиком (Python): code = {'0': 'А', '10': 'Б', '110': 'В', '1110': 'Г', '1111': 'Д'} / s = input() / buf = '' / res = '' / for bit in s: / buf = buf + bit / if buf in code: / res = res + code[buf] / buf = '' / print(res).
3. Трассировка на входе 111001101001111: buf растёт 1 → 11 → 111 → 1110 (совпало, res = «Г», buf пуст) → 0 (совпало, res = «ГА») → 1 → 11 → 110 (совпало, «ГАВ») → 1 → 10 (совпало, «ГАВБ») → 0 (совпало, «ГАВБА») → 1 → 11 → 111 → 1111 (совпало, «ГАВБАД»).
4. Что проверить перед сдачей: после цикла буфер обязан оказаться пустым. Если в нём что-то осталось, поток декодирован не до конца — значит, либо в последовательности ошибка, либо таблица кода неполная. Полезно добавить строку if buf: print('остаток:', buf) для себя, но в сдаваемом файле оставить один итоговый вывод, как требует задание 16.
5. Как сохранять: обычный текстовый файл с расширением .py; эксперт читает текст программы, а не запускает её, поэтому важнее всего, чтобы алгоритм читался однозначно.

Ответ: decode.py: буфер битов, сверка со словарём кода, вывод одной строки

Разбор примера

Задание 2: декодирование по кодовой таблице

Для кодирования букв используется префиксный код: М — 00, А — 01, Ш — 100, И — 101, Н — 11. Расшифруйте последовательность 0001100101 и определите, сколько битов заняла бы эта же надпись при равномерном коде по 5 битов на букву.

Показать решение по шагам

1. Читаем слева направо по одному биту, каждый раз сверяясь с таблицей.
2. 0 — такого кода нет; 00 = М. Остаток: 01100101.
3. 0 — нет; 01 = А. Остаток: 100101. Далее 1 — нет; 10 — нет; 100 = Ш. Остаток: 101 = И.
4. Получилось МАШИ. Проверка: 2 + 2 + 3 + 3 = 10 бит, ровно столько, сколько в потоке. Если сумма длин кодовых слов не совпала с длиной потока, где-то отрезан не тот кусок — это главный способ самопроверки.
5. Равномерный код по 5 битов на букву: 4 буквы · 5 бит = 20 бит, то есть вдвое больше. Так и виден выигрыш неравномерного кода.

Ответ: МАШИ; равномерный код занял бы 20 бит

Уроки по этой линии

Задание 2: префиксный код и условие Фано
Информация, информационные процессы и двоичное кодирование — открыт бесплатно

Потренируй задание 2

Задания этой линии с проверкой и разбором решения — после бесплатной регистрации. Ошибки сами попадут в план повторения.

Начать бесплатно

Аналитика ОГЭ: №2 (кодирование, префиксный код, условие Фано)

Баллы

1 первичный балл

Частота

в каждом варианте

Частые ловушки

Разбивают цепочку наугад, а не слева направо по кодовым словам

Не проверяют, что код префиксный (иначе разбиение неоднозначно)

Теряют или добавляют один бит при переписывании последовательности

Разборы

Разбор примера

Задание 2: декодировать последовательность

Показать решение по шагам

1. Склеиваем поток без пробелов: 111001101001111. Читаем слева направо по одному биту.
2. 1 — нет такой буквы; 11 — нет; 111 — нет; 1110 = Г. Остаток: 01101001111.
3. 0 = А. Остаток: 1101001111. Далее 1 — нет; 11 — нет; 110 = В. Остаток: 1001111.
4. 10 = Б. Остаток: 01111. 0 = А. Остаток: 1111 = Д.
5. Получилось ГАВБАД — ровно шесть букв, как обещано в условии. Совпадение числа букв — главная проверка: если букв вышло больше или меньше, где-то отрезан не тот кусок.

Ответ: ГАВБАД

Разбор примера

Задание 2: достроить код так, чтобы условие Фано выполнялось

Показать решение по шагам

1. Проверяем каждый вариант на условие Фано: кодовое слово не должно быть началом другого и другие не должны быть его началом.
2. 1) 11 — является началом слова В (110). Нельзя.
3. 2) 1100 — начинается со 110, то есть В является его началом. Нельзя.
4. 3) 111 — сравниваем с 0, 10, 110: ни одно из них не начинается с 111, и 111 не начинается ни с одного из них (после 1 идёт 1, а у Б после 1 идёт 0; у В третий бит 0, а здесь 1). Подходит.
5. 4) 0110 — начинается с 0, а это код буквы А. Нельзя.
6. Ответ 3. Приём: проверяй пары в обе стороны, иначе легко пропустить случай, где новое слово длиннее старого.

Ответ: 3

Разбор примера

Задание 2: сколько битов нужно на сообщение

Показать решение по шагам

1. Выписываем код каждой буквы по порядку: Б = 10, А = 0, Г = 111, А = 0, В = 110.
2. Склеиваем: 10 + 0 + 111 + 0 + 110 = 1001110110.
3. Считаем длину: 2 + 1 + 3 + 1 + 3 = 10 бит.
4. Смысл неравномерного кода: при равномерном кодировании четырёх букв нужно по 2 бита на каждую, то есть 10 бит на пять букв — столько же. Выигрыш появляется, когда частые буквы получают короткие коды: в тексте, где А встречается вдвое чаще остальных, такой код будет экономнее равномерного.

Ответ: 10

Разбор примера

Файл-ответ decode.py (формат задания 16): программа, которая декодирует сама

Показать решение по шагам

1. Замысел: идём по потоку слева направо, копим биты в буфер; как только буфер совпал с каким-то кодовым словом, выводим букву и очищаем буфер. Так работает свойство префиксного кода — возвращаться назад не нужно.
2. Код целиком (Python): code = {'0': 'А', '10': 'Б', '110': 'В', '1110': 'Г', '1111': 'Д'} / s = input() / buf = '' / res = '' / for bit in s: / buf = buf + bit / if buf in code: / res = res + code[buf] / buf = '' / print(res).
3. Трассировка на входе 111001101001111: buf растёт 1 → 11 → 111 → 1110 (совпало, res = «Г», buf пуст) → 0 (совпало, res = «ГА») → 1 → 11 → 110 (совпало, «ГАВ») → 1 → 10 (совпало, «ГАВБ») → 0 (совпало, «ГАВБА») → 1 → 11 → 111 → 1111 (совпало, «ГАВБАД»).
4. Что проверить перед сдачей: после цикла буфер обязан оказаться пустым. Если в нём что-то осталось, поток декодирован не до конца — значит, либо в последовательности ошибка, либо таблица кода неполная. Полезно добавить строку if buf: print('остаток:', buf) для себя, но в сдаваемом файле оставить один итоговый вывод, как требует задание 16.
5. Как сохранять: обычный текстовый файл с расширением .py; эксперт читает текст программы, а не запускает её, поэтому важнее всего, чтобы алгоритм читался однозначно.

Ответ: decode.py: буфер битов, сверка со словарём кода, вывод одной строки

Разбор примера

Задание 2: декодирование по кодовой таблице

Показать решение по шагам

1. Читаем слева направо по одному биту, каждый раз сверяясь с таблицей.
2. 0 — такого кода нет; 00 = М. Остаток: 01100101.
3. 0 — нет; 01 = А. Остаток: 100101. Далее 1 — нет; 10 — нет; 100 = Ш. Остаток: 101 = И.
4. Получилось МАШИ. Проверка: 2 + 2 + 3 + 3 = 10 бит, ровно столько, сколько в потоке. Если сумма длин кодовых слов не совпала с длиной потока, где-то отрезан не тот кусок — это главный способ самопроверки.
5. Равномерный код по 5 битов на букву: 4 буквы · 5 бит = 20 бит, то есть вдвое больше. Так и виден выигрыш неравномерного кода.

Ответ: МАШИ; равномерный код занял бы 20 бит