← На главную ОГЭ 🎮 К заданию

📚 Теория: Задание 2 ОГЭ — Расшифровка сообщения

🔐 Что такое кодирование?

Кодирование — это представление информации в виде последовательности символов (сигналов). В компьютерах информация кодируется с помощью двоичного кода — последовательности нулей и единиц.

Каждому символу (букве, цифре, знаку) ставится в соответствие уникальный код — последовательность из 0 и 1.

📋 Пример таблицы кодировки

Буква А Б В Г
Код 00 01 10 11

Слово ВАГА будет закодировано как 10 00 11 00 или 10001100.

📊 Равномерное и неравномерное кодирование

📏 Равномерное кодирование

При равномерном кодировании все символы кодируются кодами одинаковой длины.

Буква А Б В Г
Код 000 001 010 011

Все коды имеют длину 3. Расшифровка однозначна: разбиваем сообщение на группы по 3 символа.

📐 Неравномерное кодирование

При неравномерном кодировании разные символы могут кодироваться кодами разной длины. Часто встречающиеся символы кодируются короткими кодами, редкие — длинными.

Буква А Б В Г
Код 0 10 110 111

Коды имеют разную длину: от 1 до 3 символов. Но как понять, где заканчивается один код и начинается другой?

🎯 Условие Фано

✅ Прямое условие Фано

Ни одно кодовое слово не является началом другого кодового слова.

Это гарантирует, что сообщение можно расшифровать однозначно, читая его слева направо.

Пример: коды удовлетворяют прямому условию Фано

Буква А Б В Г
Код 0 10 110 111

✓ Код 0 не является началом кодов 10, 110, 111

✓ Код 10 не является началом кодов 110, 111

✓ Код 110 не является началом кода 111

❌ Пример: коды НЕ удовлетворяют условию Фано

Буква А Б В
Код 0 01 10

✗ Код 0 является началом кода 01 — условие Фано нарушено!

Сообщение 01 можно расшифровать как АБ или как В — неоднозначно!

🔄 Обратное условие Фано

Ни одно кодовое слово не является окончанием другого кодового слова.

Это гарантирует, что сообщение можно расшифровать однозначно, читая его справа налево.

Пример: коды удовлетворяют обратному условию Фано

Буква А Б В Г
Код 0 01 011 111

✓ Код 0 не является окончанием кодов 01, 011, 111

✓ Код 01 не является окончанием кодов 011, 111

✓ Код 011 не является окончанием кода 111

🌳 Дерево кодов (для проверки условия Фано)

Условие Фано можно проверить с помощью двоичного дерева. Если все кодовые слова находятся в листьях дерева (на концах веток), то условие Фано выполняется.

Корень

↙ ↘
А (0)
1

        ↙ ↘
        
Б (10)
11

            ↙ ↘
            
В (110)
Г (111)

Все буквы находятся в листьях — условие Фано выполняется. Если бы какая-то буква была во внутренней вершине, условие было бы нарушено.

📝 Алгоритм расшифровки

При прямом условии Фано (слева направо)

  1. Смотрим на начало закодированного сообщения
  2. Ищем кодовое слово, которое совпадает с началом сообщения
  3. Записываем соответствующую букву
  4. Отсекаем использованный код от сообщения
  5. Повторяем, пока сообщение не закончится

При обратном условии Фано (справа налево)

  1. Смотрим на конец закодированного сообщения
  2. Ищем кодовое слово, которое совпадает с концом сообщения
  3. Записываем соответствующую букву
  4. Отсекаем использованный код от сообщения
  5. Повторяем, пока сообщение не закончится
  6. Результат переворачиваем (так как читали справа налево)

✏️ Примеры решения задач

Пример 1: Прямое условие Фано

Условие: От разведчика было получено сообщение:

001100011110110100

Таблица кодов:

Буква А Б В З К У Я
Код 00 01 1011 1100 1101 1110 1111
Решение (слева направо):

00 → А Осталось: 1100011110110100
1100 → З Осталось: 011110110100
01 → Б Осталось: 11110110100
1111 → Я Осталось: 0110100
01 → Б Осталось: 10100
1011 → В Нет! Пробуем 10... нет такого кода
1101 → К Осталось: 00
00 → А Готово!

Ответ: АЗЯУБКА

Пример 2: Равномерный код

Условие: Расшифруйте сообщение 01100101000110111

Буква А Е И Н С Т Ц
Код 11 000 001 010 011 100 101
Решение:

011 → С
001 → И
010 → Н
001 → И
101 → Ц
11 → А
Н → 010
А → 11

Ответ: СИНЦИАНА

⚠️ Частые ошибки

🎯 План решения задачи

  1. 📝 Внимательно прочитайте условие и таблицу кодов
  2. 🔍 Определите, выполняется ли прямое или обратное условие Фано
  3. ➡️ Выберите направление расшифровки (слева направо или справа налево)
  4. 🔄 Последовательно находите кодовые слова и записывайте буквы
  5. ✅ Проверьте, что всё сообщение расшифровано
  6. 📝 Запишите ответ

💡 Полезные советы

Как быстро определить условие Фано

  • Прямое: посмотрите на все коды — если ни один не является началом другого, условие выполняется
  • Обратное: посмотрите на все коды — если ни один не является окончанием другого, условие выполняется
  • Код может удовлетворять обоим условиям одновременно (например, равномерный код)

Как выбирать код для расшифровки

  • Начинайте с самых коротких кодов и проверяйте их первыми
  • Если сообщение начинается с 0, ищите коды, начинающиеся с 0
  • Если сообщение начинается с 1, ищите коды, начинающиеся с 1