Условие Фано
 

Другие статьи из рубрики «Информатика»

Содержание:

Давайте знакомиться! Меня зовут Александр. Готовлю школьников к успешной сдаче ОГЭ и ЕГЭ по информатике

Здравствуйте! Меня зовут Александр Георгиевич и я являюсь московским профессиональным репетитором по информатике и программированию. Вам попалась задача, связанная с кодированием и декодированием информации, и вы запутались в алгоритме ее решения?

Вам срочно нужно познакомиться с условием Фано, а также записаться ко мне на индивидуальные уроки. На своих уроках я акцентирую внимание на решении тематических простых и сложных упражнений.

На дому
у ученика
На дому
у преподавателя
На нейтральной
территории
Дистанционно
по Skype
Рекомендую воспользоваться форматом дистанционного обучения. Это выгодно, удобно и крайне эффективно.

В чем смысл прямого условия Фано?

Условие Фано названо в честь его создателя, итальянско-американского ученого Роберта Фано. Условие является необходимым в теории кодирования при построении самотерминирующегося кода. Учитывая другую терминологию, такой код называется префиксным.

Сформулировать данное условие можно следующим образом: «ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова».

С математической точки зрения условие можно сформулировать следующим образом: «если код содержит слово 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$

Очевидно, что здесь имеет место быть нарушение обратного условия Фано. Внимательный читатель заметит, что нарушение происходит даже не один раз. wink

Давайте рассмотрим пару элементов множества: ${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$ не совпадает с окончанием кода всех остальных символов. По этой причине, вариант является подходящим. cool

После проверки вариантов решения задачи на соответствие прямому и обратному условию Фано, было установлено, что правильным является вариант $4$.

Ответ: $4$

P.S. Хочу заметить, что это далеко не единственный способ решения такой задачи. Существует очень эффективный и наглядный способ решения подобных задач с использованием специального двоичного дерева.

А сейчас я вам предлагаю ознакомиться с мультимедийным решением задачи, которая была предложена в демонстрационном варианте ЕГЭ по информатике и ИКТ. Кстати, данная задача относится к типу задач, решаемых с использованием условия Фано.

Остались вопросы

Если после прочтения данной публикации у вас все равно остались какие-то вопросы, непонимания или вы хотите закрепить пройденный материал практическими решениями, то звоните и записывайтесь ко мне на частные уроки по информатике и ИКТ.

Я практик! Это означает, что на своих индивидуальных уроках я показываю своим подопечным самые лучшие методики решения заданий, ориентированных на условие Фано.

Отзывы
моих учеников

Коряков
Михаил

 
Когда я начал заниматься с Александром Георгиевичем, у меня уже была довольно сильная база, но мы ее упрочили невероятно сильно дополнительными методиками. Я научился решать наиболее оптимально огромное количество задач...

Иванов
Денис

 
Очень много нового узнал о ДС, Александр Георгиевич показал несколько способов построения бинарного дерева, а также реализацию функций повышенного уровня сложности. Когда шел на экзамен, то абсолютно не волновался, так...

Воробьев
Станислав

 
Я очень рад, что оказался в учениках у Александра Георгиевича. У меня были огромные пробелы в знаниях, связанных со строками, подпрограммами, рекурсией. Думал, что провалю экзамен и буду отчислен, но сдал экзамен на...

Лебедев
Валерий

 
С большим удовольствием занимался с учителем, т к начал понимать программирование на более углубленном уровне. Очень много изучали такую тему как "указатели" и я их понял наконец-таки очень хорошо. Понимание указателей...

Догаев
Самир

 
Когда я поступил в ВУЗ, то я совсем не умел программировать на С++ и нам сразу стали давать сложные лабораторные, которые мне физически были не под силу. Решил найти репетитора и обратился к Александру Георгиевичу (он...

Соколов
Дмитрий

 
Я научился тому, о чем мечтал с 15 лет. Александр Георгиевич, оказывается, очень хорошо знает веб-программирование, хотя его основной профиль (по его словам) - подготовка к ОГЭ/ЕГЭ по информатике и ИКТ. Скажу честно,...

Уфимцев
Сергей

 
Хочется подчеркнуть высокую дисциплину на протяжении всех уроков, понятность объяснения и помощь даже во внеурочное время. Спасибо большое! Буду рекомендовать вас своим знакомым и друзьям))

Богдан
Игнатьев

 
Теперь я чувствую себя уверенно при программировании графических примитивов. Я еще раз убедился, что хороший учитель очень важен для хорошего обучения. В следующем учебном году у нас будет дисциплина "Мультипликация и...

Калиновский
Илья

 
Как только поступил в ВУЗ, думал, что буду отчислен из-за дисциплины программирования, т к оказалось очень сложной и у меня ничего не получалось. Потом нашел репетитора и вместе с ним научился средне программировать и...

Сема
Катерина

 
Я очень рада, что нашла такого толкового репетитора-практика, который не только хорошо знает теоретическую часть языка программирования С, но и имеет шикарную базу для реализации различных курсовых работ для таких...

Шамшуров
Денис

 
Спасибо вам большое Александр Георгиевич! Вы практически сделали невозможное - натаскали меня к экзамену по программированию, которое я очень плохо понимал до того, как обратился к вам. Хочу отдельно отметить, что урок...

Волков
Антон

 
Было очень сложно и, оказалось, что я совсем не знал ни Excel, ни C#. Александр Георгиевич подтянул мои знания и вывел их на новый квалитативный уровень. Спасибо вам и успехов!

Потапова
Ирина

 
Спасибо большое вам за помощь. Без вашей поддержки я бы не получила 5-ку на экзамене. Хочу особенно отметить, что на ваших уроках вы даете очень много полезной сопутствующей информации, в том числе и разного рода...

Ланцев
Дмитрий

 
Я был очень круто подготовлен. Александр Георгиевич натаскивал меня по полной программе, мы прорерашли более 200 задач по программированию, научились строить выйгрышные стратегии. Я сам виноват, что не повторил...

Орлов
Максим

 
Спасибо большое вам Александр Георгиевич. Было очень интересно и увлекательно решать с вами данные лабораторные. Они оказались не такими сложными, какими они казались изначально. Оказывается процесс программирования...

Миронов
Сергей

 
Очень рад, что поступил в заветный ВУЗ, так как считаю, что именно в этом ВУЗе можно научиться отлично программировать, а репетитор помог мне очень сильно. Было интересно заниматься и сложно. Особенно я целыми часами...

Волков
Павел

 
Спасибо вам большое. Да, курсовая была непростой, но я сдал ее на 5-ку. Хочу отметить атмосферу проводимых уроков: во-первых, мы занимались в чистой и опрятной комнате, во-вторых, на уроке стоит здоровая учебная...
Смотреть все отзывы
 
 
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?
Занятия по информатике