Условие Фано
 

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

Содержание:

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

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

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

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

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

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

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

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

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

Леонов
Никос

 
Полученный бал, превзошел все мои ожидания, так как я максимум рассчитывал на 90 баллов тестовых. Думаю, получением столь высокой оценки я обязан репетитору Александру Георгиевичу. Но мой личный вклад тоже не мал!

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

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

Потанин
Михаил

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

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

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

Булычев
Владимир

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

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

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

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

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

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

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

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

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

Камю
Константин

 
Я сдал курсовой проект на отлично благодаря помощи репетитора Александра. Он очень доступно дает незнакомый и сложный материал. Понравилось еще то, что он старается все свои объяснения подкреплять визуальными...

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

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

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

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

Ахматова
Юлия

 
В нашем вузе я должна была сдавать экзамену по C#. Билеты были очень сложные. Один вопрос теоретический, практическая задача в консоли и лабораторная, связанная с базами данных. Знания у меня были тусклые в этих...

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

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

Фомин
Глеб

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

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

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

Даниил
Сафонов

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