Другие статьи из рубрики «Информатика»
- Выбор оптимального способа измерения информации
- Выбор оптимальной циклической конструкции в Паскаль в зависимости от входных данных
- Дискретная форма представления информации
- Задача №1 (найти максимальное количество цветов)
- Задача №2 (объем растрового изображения)
- Задача №3 (изменение глубины цвета)
- Зачем нужен цикл while в Паскаль
- Зачем нужна операция присваивания в языках программирования?
- Знакомы с видеохостинг YouTube? Говорим сегодня о кодировании видеоинформации
- Кодирование графической информации
- Методы измерения информации
- Не понимаете, как правильно инициализировать элементы двумерного массива в Паскаль?
- Не понимаешь базовых действий с массивами? Успеха на ЕГЭ не жди!
- Нет переменных - нет программы!
- Общие сведения о декодировании информации
- Общие сведения о кодировании информации
- Общие сведения об информации
- Основные методики, используемые при построении блок-схем
- Поиск информации в таблице на основе граничных условий
- Понятие о равномерном и неравномерном коде
- Построение блок-схем с репетитором по информатике и программированию
- Роль двоичной системы счисления в ЕГЭ по информатике
- Свойства информации
- Условие Фано
Содержание: |
Давайте знакомиться! Меня зовут Александр. Готовлю школьников к успешной сдаче ОГЭ и ЕГЭ по информатике
Здравствуйте! Меня зовут Александр Георгиевич и я являюсь московским профессиональным репетитором по информатике и программированию. Вам попалась задача, связанная с кодированием и декодированием информации, и вы запутались в алгоритме ее решения?
Вам срочно нужно познакомиться с условием Фано, а также записаться ко мне на индивидуальные уроки. На своих уроках я акцентирую внимание на решении тематических простых и сложных упражнений.
В чем смысл прямого условия Фано?
Условие Фано названо в честь его создателя, итальянско-американского ученого Роберта Фано. Условие является необходимым в теории кодирования при построении самотерминирующегося кода. Учитывая другую терминологию, такой код называется префиксным.
Сформулировать данное условие можно следующим образом: «ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова». |
С математической точки зрения условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова BC не существует в коде».
Давайте рассмотрим примеры, когда прямое условие Фано выполняется и когда происходит его нарушение. Прежде, чем рассматривать эти примеры, рекомендую освежить знания о равномерном и неравномерном коде.
Пример $№1$(прямое условие Фано выполняется корректно). Например, нам известны символы некоторого множества $\{A,\ B,\ C,\ D\}$. Произведем кодирование каждого элемента множества неравномерным кодом, необязательно минимальной длины.
Символ | $A$ | $B$ | $C$ | $D$ |
Код символа | $00$ | $010$ | $1011$ | $110$ |
Проверим код буквы $A = 00$. Как видно, ни один другой символ не начинается на связку битов $00$. Аналогичные умозаключения можно сделать, если провести анализ остальных букв алфавита, т е букв $B$, $C$ и $D$.
Пример $№2$(прямое условие Фано нарушено). Пусть нам дано такое же множество элементов, как и в примере $№1$, то есть работаем с множеством $\{A,\ B,\ C,\ D\}$. Закодируем элементы этого множества неравномерным кодом, опять-таки, необязательно минимальной длины.
Символ | $A$ | $B$ | $C$ | $D$ |
Код символа | $00$ | $01$ | $101$ | $0110$ |
Очевидно, что в данном случае имеется нарушение прямого условия Фано! Давайте рассмотрим пару элементов множества: ${B,\ D}$. Начало кода буквы $D$ на $100\%$ совпадает с полным кодом буквы $B$: $D = \underbrace{01}_{B}10$.
Такие кодовые слова практически невозможно однозначно декодировать.
В чем смысл обратного условия Фано?
Существует также и обратное правило Фано, формулировка которого звучит следующим образом: «ни одно кодовое слово не может выступать в качестве окончания любого другого кодового слова». |
С математической точки зрения обратное условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова CB не существует в коде».
Пример $№3$(обратное условие Фано выполняется корректно). Воспользуемся тем же самым алфавитом, что и в примерах выше: $\{A,\ B,\ C,\ D\}$. Произведем кодирование элементов данного множества неравномерным кодом, причем необязательно минимальной длины.
Символ | $A$ | $B$ | $C$ | $D$ |
Код символа | $100$ | $0101$ | $11$ | $110$ |
Последовательно проверим полный код буквы $A = 100$, не является ли он окончанием какого-либо другого кодового слова. У буквы $B$ последних $3$ бита равны комбинации $101$, что не совпадает с полным кодом буквы $А$.
Полный код буквы $C$ вообще составляет всего $2$ разряда, - проверка как таковая бессмысленна. Код буквы $D$ также состоит из $3$ бит, равных $110$ и они не равны цепочке $100$.
Делаем вывод, что код буквы $A = 100$ не нарушает обратное правило Фано. Аналогично можно рассмотреть оставшиеся кодовые слова и убедиться в том, что ни одно из них не является окончанием другого кодового слова.
Общий вывод: при таких кодовых словах абсолютно четко выполняется обратное условие Фано.
Пример $№4$(обратное условие Фано нарушено). Рассмотрим следущие элементы множества и их кодовые слова.
Символ | $A$ | $B$ | $C$ | $D$ |
Код символа | $0$ | $01$ | $1001$ | $110$ |
Очевидно, что здесь имеет место быть нарушение обратного условия Фано. Внимательный читатель заметит, что нарушение происходит даже не один раз.
Давайте рассмотрим пару элементов множества: ${A,\ D}$. Конец кода буквы $D$ на $100\%$ совпадает с полным кодом буквы $A$: $D = 11\underbrace{0}_{A}$. Налицо нарушение обратного правила Фано.
Рассмотрим еще одну пару элементов множества: ${B,\ C}$. Конец кода буквы $C$ на $100\%$ совпадает с полным кодом буквы $B$: $C = 10\underbrace{01}_{B}$.
Однозначно декодировать подобные кодовые слова не представляется возможным, хотя в редчаших случаях здесь могут быть исключения. Об этом более детально сможем поговорить на моих частных занятиях.
Практическое применение условия Фано
Рассмотрим телефонные номера в традиционной телефонии. Если уже существует номер $«102»$, то номер $«1029876»$ попросту не будет выдан. В случае набора первых трех цифр АТС перестает распознавать и принимать все остальные цифры, соединяя с абонентом по номеру $102$.
Однако это правило не является действительным для операторов мобильной связи. Связано это с тем, что для набора номера необходимо нажатие соответствующей клавиши, которой, в основном, является клавиша с изображением зеленой телефонной трубки. По этой причине, номера $«102»$, $«1020»$ и $«1029876»$ могут существовать и быть закрепленными за разными адресатами.
Связь условия Фано с другими темами информатики
Прямое и обратное условие Фано являются обязательными для изучения и понимания теми, кто планирует успешно сдать экзамен ЕГЭ по информатике. Но на практике вы не столкнетесь с заданиями, которые конкретно ориентированы на эту тему.
Применение условий Фано требуется обычно неявно! То есть в постановке задачи не будет и слова об этом условии. Вы должны сообразить, что в данном случае нужно воспользоваться этим правилом.
Вы могли уже заметить выше, что правило Фано используется тогда, когда приходится анализировать какие-либо кодовые слова, состоящие из цепочки бит, то есть из цепочки $0$ и $1$.
Поэтому, в обязательном порядке, вам нужно прекрасно понимать, как устроена двоичная система счисления, а также знать переводы чисел, как правило натуральных, из $10$-ной СС в $2$-ную СС и обратно.
Практически во всех заданиях ЕГЭ по информатике, где вам потребуется применить условие Фано, упор делается на однозначное кодирование и декодирование какой-либо информации.
Также условие Фано неразрывно связано с неравномерным кодом. Хочу обратить особое внимание на тот факт, что правило Фано практически не распространяется на случаи, когда информация кодируется равномерным кодом.
То есть вы должны понимать, что условие Фано - инструмент, понимание которого позволит вам быстро и эффективно решать задачи, связанные в $1$-ую очередь с кодированием/декодированием информации в двоичном представлении.
Пример задачи, которую можно эффективно решить, при помощи условия Фано
Условие задачи: дана последовательность, которая состоит из букв $A$, $B$, $C$, $D$ и $E$. Для кодирования приведенной последовательности применяется неравномерный двоичный код, при помощи которого можно осуществить однозначное декодирование.
Буква |
$A$ |
$B$ |
$C$ |
$D$ |
$E$ |
Двоичный эквивалент |
$00$ |
$010$ |
$011$ |
$101$ |
$111$ |
Вопрос: есть ли возможность для одного из символов сократить длину кодового слова таким образом, чтобы сохранить возможность однозначного декодирования? При этом коды остальных символов должны остаться неизменными.
Номер варианта |
$1$ |
$2$ |
$3$ |
$4$ |
Ответ |
$B\ –\ 01$ |
Не представляется возможным |
$C\ –\ 01$ |
$D\ –\ 01$ |
Решение: для того, чтобы сохранилась возможность декодирования, достаточным является соблюдение прямого или обратного условия Фано. Проведем последовательную проверку вариантов $1$, $3$ и $4$. В случае если ни один из вариантов не подойдет, правильным ответом будет вариант $2$ (не представляется возможным).
Вариант $1$. Код: $A - 00$, $B - 01$, $C - 011$, $D - 101$, и $E - 111$. Прямое условие Фано не выполняется: код символа $B$ совпадает с началом кода символа $C$, то есть $C = \underbrace{01}_{B}1$.
Обратное правило Фано не выполняется: код символа $B$ совпадает с окончанием кода символа $D$, то есть $D = 1\underbrace{01}_{B}$.
Вариант не является подходящим.
Вариант $3$. Код: $A - 00$, $B - 010$, $C - 01$, $D - 101$, и $E - 111$. Прямое условие Фано не выполняется: код символа $C$ совпадает с началом кода символа $B$, то есть $B = \underbrace{01}_{C}0$.
Обратное условие также не выполняется: код символа $C$ совпадает с окончанием кода символа $D$, то есть $D = 1\underbrace{01}_{C}$.
Вариант не является подходящим.
Вариант $4$. Код: $A - 00$, $B - 010$, $C - 011$, $D - 01$, и $E - 111$. Прямое условие Фано не выполняется: код символа $D$ совпадает с началом кода символов $B$ и $C$, то есть: $B = \underbrace{01}_{B}0$ и $C = \underbrace{01}_{B}1$ соответственно.
Однако наблюдается выполнение обратного правила Фано: код символа $D = 01$ не совпадает с окончанием кода всех остальных символов. По этой причине, вариант является подходящим.
После проверки вариантов решения задачи на соответствие прямому и обратному условию Фано, было установлено, что правильным является вариант $4$.
Ответ: $4$
P.S. Хочу заметить, что это далеко не единственный способ решения такой задачи. Существует очень эффективный и наглядный способ решения подобных задач с использованием специального двоичного дерева.
А сейчас я вам предлагаю ознакомиться с мультимедийным решением задачи, которая была предложена в демонстрационном варианте ЕГЭ по информатике и ИКТ. Кстати, данная задача относится к типу задач, решаемых с использованием условия Фано.
Остались вопросы
Если после прочтения данной публикации у вас все равно остались какие-то вопросы, непонимания или вы хотите закрепить пройденный материал практическими решениями, то звоните и записывайтесь ко мне на частные уроки по информатике и ИКТ.
Я практик! Это означает, что на своих индивидуальных уроках я показываю своим подопечным самые лучшие методики решения заданий, ориентированных на условие Фано.
Отзывы
моих учеников
Коряков
Михаил
Иванов
Денис
Воробьев
Станислав
Лебедев
Валерий
Догаев
Самир
Соколов
Дмитрий
Уфимцев
Сергей
Богдан
Игнатьев
Калиновский
Илья
Сема
Катерина
Шамшуров
Денис
Волков
Антон
Потапова
Ирина
Ланцев
Дмитрий
Орлов
Максим
Миронов
Сергей
Волков
Павел