Фано информатика

Условие Фано

Фано информатика

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

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

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

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

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

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

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

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

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

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

Источник: http://www.videoege.ru/informatika/uslovie-fano

Задача №5. Кодирование в различных системах счисления, расшифровка сообщений, выбор кода

Фано информатика

Автор материалов — Лада Борисовна Есакова.

Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.

Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.

Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.

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

Равномерное кодирование всегда однозначно декодируемо.

Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:

Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.

Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.

Кодирование в различных системах счисления

Пример 1.

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление

чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится

1) 22162

2) 1020342

3) 2131453

4) 34017

Решение:

Представим коды указанных букв в дво­ич­ном коде, добавив незначащий нуль для одноразрядных чисел:

ОВДПА
01234
00011011100

Закодируем по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010.

Разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём каждую тройку в восьмеричное число.

010 010 001 110 010 — 22162.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

Ответ: 1

Пример 2.

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся по­сим­воль­ное ко­ди­ро­ва­ние: А-10, Б-11, В-110, Г-0. Через канал связи пе­ре­даётся со­об­ще­ние: ВАГ­БА­А­ГВ. За­ко­ди­руй­те со­об­ще­ние дан­ным кодом. По­лу­чен­ное дво­ич­ное число пе­ре­ве­ди­те в шест­на­дца­те­рич­ный вид.

            1) D3A6

2) 62032206

3) 6A3D

4) CADBAADC

Решение:

За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВАГ­БА­А­ГВ — 1101001110100110. Разобьем это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём каждую четверку в шестнадцатеричное число:

1101 0011 1010 01102 = D3A616

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

Ответ: 1

Расшифровка сообщений

Пример 3.

Для 5 букв ла­тин­ско­го ал­фа­ви­та за­да­ны их дво­ич­ные коды (для не­ко­то­рых букв – из двух бит, для не­ко­то­рых – из трех). Эти коды пред­став­ле­ны в таб­ли­це:

abcde
1001100110110

Опре­де­ли­те, какой набор букв за­ко­ди­ро­ван дво­ич­ной стро­кой 1000110110110, если из­вест­но, что все буквы в по­сле­до­ва­тель­но­сти – раз­ные:

1) cbade

2) acdeb

3) acbed

4) bacde

Решение:

Мы видим, что усло­вия Фано и об­рат­ное усло­вие Фано не вы­пол­ня­ют­ся, зна­чит код можно рас­ко­ди­ро­вать не­од­но­знач­но.

Значит, будем перебирать варианты, пока не получим подходящее слово :

1) 100 011 01 10 110

Пер­вая буква опре­де­ля­ет­ся од­но­знач­но, её код 100: a.

Пусть вто­рая буква — с, тогда сле­ду­ю­щая буква — d, потом — e и b.

Такой ва­ри­ант удо­вле­тво­ряет усло­вию, зна­чит, окон­ча­тель­но по­лу­чи­ли ответ: acdeb.

Ответ: 2

Пример 4.

Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми: А — 11010, Б — 10111, В — 01101.

При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях.

По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась. (Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».

) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква Б. (От­ли­чие от ко­до­во­го слова для Б толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.

) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся 'х').

По­лу­че­но со­об­ще­ние 11000 11101 10001 11111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

1) АххБ

2) АВхБ

3) хххх

4) АВББ

Решение:

Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 11000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Вто­рое слово: 11101 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей. Тре­тье слово: 10001 от­ли­ча­ет­ся от любой буквы более чем одной по­зи­ци­ей. Четвёртое слово: 11111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей.

Таким об­ра­зом, ответ: АВхБ.

Ответ: 2

Однозначное кодирование

Пример 5.

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=1, Б=01, В=001. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?

1) 0001

2) 000

3) 11

4) 101

Решение:

Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.

Ответ: 2

Пример 6.

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му остал­ся пре­фикс­ным? Коды осталь­ных букв ме­нять­ся не долж­ны.

Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.

При­ме­ча­ние. Пре­фикс­ный код — это код, в ко­то­ром ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го; такие коды поз­во­ля­ют од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность.

1) ко­до­вое слово для буквы Е можно со­кра­тить до 01

2) ко­до­вое слово для буквы К можно со­кра­тить до 1

3) ко­до­вое слово для буквы Н можно со­кра­тить до 10

4) это не­воз­мож­но

Решение:

Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:

 

Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. ко­до­вое слово для буквы Н можно со­кра­тить до 10.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

Ответ: 3

Источник: https://ege-study.ru/ru/ege/materialy/informatika/zadanie-5/

Информатика ЕГЭ 5 задание разбор и объяснение

Фано информатика

Урок посвящен тому, как решать 5 задание ЕГЭ по информатике

Кодирование информации

5-я тема характеризуется, как задания базового уровня сложности, время выполнения – примерно 2 минуты, максимальный балл — 1

  • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
  • Кодирование бывает равномерным и неравномерным:
  • при равномерном кодировании всем символам соответствуют коды одинаковой длины;
  • при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.

Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:

Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).

Кодирование и расшифровка сообщений

Декодирование (расшифровка) — это восстановление сообщения из последовательности кодов.

Для решения задач с декодированием, необходимо знать условие Фано:

Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)

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

  • если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:
  • Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового словаПостфиксный код — это код, в котором ни одно кодовое слово не совпадает с концом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно и только с конца.

  • условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Однозначное декодирование обеспечивается:

Однозначное декодирование

Декодирование

Егифка ©:

Решение 5 заданий ЕГЭ

ЕГЭ 5.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

✍ Решение:

  • Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
  • О -> 0 -> 00 В -> 1 -> 01 Д -> 2 -> 10 П -> 3 -> 11 А -> 4 -> 100

  • Теперь закодируем последовательность букв из слова ВОДОПАД:
  • 010010001110010

  • Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:
  • 010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2

Результат: 22162

Решение ЕГЭ данного задания по информатике, видео:

Рассмотрим еще разбор 5 задания ЕГЭ:

ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

abcde
0001100100110

Какой набор букв закодирован двоичной строкой 1100000100110?

✍ Решение:

  • Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.
  •  ✎ 1 вариант решения:

  • Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:
  • 110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ b a c d e

Результат: b a c d e.

✎ 2 вариант решения:

    Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.
  • Сделаем дерево, согласно кодам в таблице:
  • Сопоставим закодированное сообщение с кодами в дереве:
  • 110 000 01 001 10

Результат: b a c d e.

Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Решим следующее 5 задание:

ЕГЭ 5.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110).

Определите, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100100100110.

✍ Решение:

  • Рассмотрим пример из условия задачи:
  • Было 2310 Стало 00101001102

  • Где сами цифры исходного числа (выделим их красным цветом):
  • 0010100110 (0010 — 2, 0011 — 3)

  • Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011, значит — четное).
  • Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:
  • разбиваем по 5:
  • 01100 01010 01001 00110

  • отбрасываем из каждой группы последний символ:
  • 0110 0101 0100 0011

  • Результат переводим в десятичную систему:
  • 0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3

Ответ: 6 5 4 3

Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10.

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Подобные задания для тренировки

✍ Решение:

✎ 1 вариант решения основан на логических умозаключениях:

  • Найдём самые короткие возможные кодовые слова для всех букв.
  • Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
  • Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
  • Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
  • Суммарная длина всех четырёх кодовых слов равна:
  • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

✎ 2 вариант решения:

  • Будем использовать дерево. Влево откладываем 0, вправо — 1:
  • Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
  • (Н) -> 0 -> 1 символ (К) -> 10 -> 2 символа (Л) -> 110 -> 3 символа (М) -> 111 -> 3 символа

  • Суммарная длина всех четырёх кодовых слов равна:
  • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

Ответ: 9

5.5: ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова:

А: 101010, Б: 011011, В: 01000

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Подобные задания для тренировки

✍ Решение:

  • Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
  • Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

Результат: 00

5.6: ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 16 (под редакцией Крылова С.С., Чуркиной Т.Е.):

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код:

А — 01 Б — 00 В — 11 Г — 100

Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

  • Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:
  • Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:
  • Перепишем сверху вниз получившееся кодовое слово для Д: 101

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

5.7: 5 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

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

Похожие задания для тренировки

✍ Решение:

  • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
  • При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:

Результат: 1100

Подробное решение данного 5 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

5.8: Задание 5_9. Типовые экзаменационные варианты 2017. Вариант 4 (Крылов С.С., Чуркина Т.Е.):

По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова:

А: 00011 Б: 111 В: 1010

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

  • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
  • Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).
  • Дерево по условию Фано (однозначно декодируется с начала):

  • Получившееся числовое значение кодового слова для буквы Г01.
  • Дерево по обратному условию Фано (однозначно декодируется с конца):

  • Получившееся числовое значение кодового слова для буквы Г00.
  • После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.

Результат: 00

5.9: Тренировочный вариант №3 от 01.10.2018 (ФИПИ):

По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

Е – 000 Д – 10 К – 111

Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.

✍ Решение:

  • С помощью дерева отобразим известные коды для букв:
  • В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:
  • Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
  • Д Е Д М А К А Р 10 000 10 001 01 111 01 110

  • Посчитаем количество цифр в итоговом коде и получим 20.

Результат: 20

Смотрите виде решения задания:

Источник: https://labs-org.ru/ege-5/

Фано информатика

Фано информатика

Замечание 1

Фано информатика это — условие Фано в теории кодирования, которое является достаточным условием для построения самоопределяющегося кода (по-другому, префиксного кода).

При кодировании символов, которое всегда выполняется при работе с текстовыми данными на компьютере, как правило, предполагается, что любому символу соответствует одно и то же число разрядов. К примеру, кодирование в ASCII сопоставляет любому знаку информационный байт, который хранит номер символьного знака в данной таблице.

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

Если в текстовом файле задействованы не все знаки, имеющиеся табличной кодировке (например, сообщение состоит только из прописных русских символов), тем не менее, применяется то же самое восьми битное кодирование.

Однако, существует более гибкий и менее объёмный метод кодирования, который называется неравномерным. В таком коде число битов, которые отводятся для кодировки знаков, зависит от числа применяемых в данном конкретном случае разных знаков, иначе говоря, от алфавитной мощности.

При этом кодирование разных знаков, имеет различную длину в двоичном формате. Это кодирование возможно оптимизировать путём учёта частоты повторяемости разных знаков и давать постоянно применяемым символам наиболее маленькие коды.

Основное правило при неравномерном кодировании заключается в обеспечении возможности однозначного и правильного декодирования закодированной таким образом информации. Это декодирование должно выполняться путём поочерёдного выделения и распознавания из непрерывной цепи нулей и единиц кодов отдельного символа.

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

Ничего непонятно?

Попробуй обратиться за помощью к преподавателям

Принцип Фано

Прямое условие Фано формулируется следующим образом: неравномерный код возможно однозначно декодировать, если код любого символа не имеет совпадений с начальными знаками (префиксом) любого другого кода, имеющего больший размер.

Подобный код имеет название «префиксный». Обратное условие Фано формулируется так: неравномерный код возможно однозначно декодировать, при условии, что нет кодов, которые имеют совпадения с окончанием (постфиксом) любого другого кода, имеющего большую длину.

Этот код носит название «постфиксный».

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

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

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

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

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

Проверка условий Фано

Для проверки выполнения прямого условия Фано, необходимо поочерёдно выполнять сравнение всех пар кодов, соблюдая такие условия:

  1. Когда пара кодов, подлежащих сравнению, имеет одинаковый размер, то хватит проверки на совпадение.

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

Для последнего случая проверка кодов может выполняться таким образом. Вначале записывается более длинный код. Далее снизу под ним располагается более короткий код так, чтобы было совпадение по расположению знаков. Причём, если проверяется прямое условие Фано, то по левой позиции знаков, а если обратное условие Фано, то по правой позиции знаков.

Пример проверки

Имеем заданные коды символов: A – 10, B – 11, C – 011. Необходимо проверить выполнение условий Фано для такого кодового набора.

Алгоритм решения можно представить в следующем виде:

  1. Выполняем сравнение кодов символов A и B. По длине коды одинаковые (у обеих длина два бита), но сами коды разные. Отсюда следует вывод, что выполнено и прямое и обратное условие Фано для пары символов A и B.

  2. Выполняем сравнение символов A и C. Они имеют коды различной длины.

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

    C: 0 1 1

    A: 1 0

    Кодирование символа A (оно короче) не совпадает с начальными кодами символа C (который длиннее). Это означает, что для данной пары символов выполнено прямое условие Фано.

    • Выполняем проверку обратного условия Фано:

    C: 0 1 1

    A: 1 0

    Кодирование символа A (оно короче) не совпадает с окончанием кода символа (его код длиннее). Делаем вывод о выполнении обратного условия Фано для этих символов.

  3. Выполняем сравнение кодов символов B и C. По длине их коды так же отличаются.

    • Выполняем проверку на выполнение прямого условия Фано:

    C: 0 1 1

    B: 1 1

    Код символа B (он короче) не совпадает с начальными знаками кода символа C (его код длиннее). Делаем вывод, что прямое условие Фано для этих символов выполнено.

    • Выполняем проверку исполнения обратного условия Фано:

    C: 0 1 1

    B: 1 1

    Код символа B (он короче) совпадает с окончанием кода символа C (его код длиннее). То есть обратное условие Фано для этих символов не выполнено.

  4. Формирование итогов. Прямое условие Фано исполнено для всех пар символов, обратное условие не исполнено для одной пары, то есть не может применяться и для всего набора символов.

Источник: https://spravochnick.ru/informatika/fano_informatika/

Booksm
Добавить комментарий