Условие Фано
 

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

Содержание:

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

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

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

На дому
у ученика
На дому
у преподавателя
На нейтральной
территории
Дистанционно
по 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. Хочу заметить, что это далеко не единственный способ решения такой задачи. Существует очень эффективный и наглядный способ решения подобных задач с использованием специального двоичного дерева.

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

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

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

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

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

Сычев
Владимир

 
Понравилось заниматься, т к я научился более серьезно понимать программные конструкции, понял наконец-то что такое "указатель" и уже не так сильно боюсь программирования. Главное, больше практиковаться и решать простые...

Догаев
Самир

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

Белкин
Юрий

 
Круто, что я сдал на 5 свой экзамен, было оооооочень сложно, но у меня получилось. Кстати, Александр Георгиевич кроме языка СИ еще приводил сравнения с языком С++, очень круто на самом деле. Заниматься понравилось и...

Александров
Михаил

 
В школе никогда не было нормальной информатики, поэтому на первом курсе я столкнулся с большой проблемой. Надо было научится программировать на языке "чистый" СИ. А я даже не знал азы и не представлял что такое...

Арсеньев
Михаил

 
Еще учась в 9-ом классе, я для себя определил, что хочу продолжить обучение в одном из лучших ВУЗов страны и задолго до экзамена начал подготовку. Очень долго выбирал репетитора, но когда встретил Александра...

Малышев
Евгений

 
В школе никогда не было нормальной информатики, поэтому на первом курсе я столкнулся с большой проблемой. Надо было научится программировать на языке Паскаль. А я даже не знал азы и не представлял что такое...

Станислав
Блок

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

Самуйлов
Кирилл

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

Фрунзе
Яна

 
На самом деле я очень счастлива, что получила четыре на экзамене. Я так боялась того, что меня отчислят из-за этого предмета, но мои страхи были напрасными. Благодаря профессионализму Александра Георгиевича, его...

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

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

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

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

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

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

Владимир
Дятлов

 
Спасибо вам за помощь) Я хотел сначала тупо все заказать на стороне, но стало интересно разобраться самостоятельно и у меня получилось благодаря вашему наставничеству. Если не сдам экзамен, то опять обращусь к вам за...

Мельник
Игорь

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

Каховская
Оксана

 
Хочу всем сказать, что я по своему духу лингвист. Паскаль - это формальный язык написания текстов. Благодаря репетитору я уверенно себя стала чувствовать при написании программ. Мне досконально понятны все базовые...

Фомин
Глеб

 
Уф, зачет сдан, я очень рад! А все благодаря этому репетитору. Мне понравилось заниматься с Александром, т к на его уроках нет никакой "воды", все четко по делу, серьезно, дисциплинированно. Также мне понравился стиль...

Прохоров
Дмитрий

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