Форум » Кодирование и декодирование информации » [A9] Условие Фано » Ответить
[A9] Условие Фано
PavelG: Здравсвуйте, Константин. В первом разоранном примере из задания А9 проверятся как прямое, так и обратное условие Фано. Во втором же, мне показалось, что проверяется только прямое. Можно ли как-то поподробное разъянить, когда исп. прямое условие Фано,а когда и обратное тоже (впервые познакомился с ним в ваших материалах). Спасибо.
Поляков: PavelG пишет: когда исп. прямое условие Фано,а когда и обратное тоже Для однозначного декодирования достаточно, чтобы выполнялось одно (любое) из условий Фано: прямое позволяет однозначно декодировать цепочку с начала, обратное - с конца. Сначала проверяем для всех указанных в задании вариантов прямое условие Фано, если какой-то из них подошел, это и есть ответ. Если ни для какого варианта не выполняется прямое условие Фано, проверяем обратное.
кот Бегемот: я бы уточнил, что проверять надо и имеющиеся коды, и предложенные, именно в этом делают ошибки, например, в задании 43) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=000, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 1) 00 2) 01 3) 11 4) 010 проверяют предложенные варианты, 2 и 3 удовлетворяют первому условию Фано, и ответ 3 подходит, но не проверяют коды букв А,Б,В на соответствие варианту.
tavabar: кот Бегемот пишет: Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=000, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 1) 00 2) 01 3) 11 4) 010 Если применить прямое условие Фано, то получаем ответ 2. Допустим, я начну проверку с обратного условия Фано. Рассматриваю предложенные варианты. Не подходит только первый вариант: остальные не совпадают с концом ни одного кода. Теперь проверяю коды букв: отпадают вариант 3 (из-за А) и вариант 2 (из-за В). Итак, ответ 4. Так, правильный ответ 2 или 4? Или надо начинать проверку ТОЛЬКО с прямого условия Фано?
Поляков: tavabar пишет: Так, правильный ответ 2 или 4? Или надо начинать проверку ТОЛЬКО с прямого условия Фано? В задаче требуется найти самый короткий код из предложенных. Поэтому ответ - 2.
oval: Поляков пишет: Для однозначного декодирования достаточно, чтобы выполнялось одно (любое) из условий Фано: прямое позволяет однозначно декодировать цепочку с начала, обратное - с конца. Сначала проверяем для всех указанных в задании вариантов прямое условие Фано, если какой-то из них подошел, это и есть ответ. Если ни для какого варианта не выполняется прямое условие Фано, проверяем обратное. Если выполняется обратное условие Фано, то декодируем с конца, а если не выполняется, то однозначно декодировать нельзя. Или все таки можно? условие Фано – это достаточное, но не необходимое условие однозначного декодирования. "достаточное, но не необходимое" можно пояснить
Поляков: oval пишет: Если выполняется обратное условие Фано, то декодируем с конца, а если не выполняется, то однозначно декодировать нельзя. Неверно. Можно, если выполняется "прямое" условие Фано. "достаточное, но не необходимое" можно пояснить Это значит, что если условие выполняется, то декодировать точно можно. Если условие не выполняется, то нельзя утверждать, что однозначно декодировать нельзя - может выполняться другое условие Фано (возможно, удастся декодировать в другом направлении).
oval: Сначала проверяем для всех указанных в задании вариантов прямое условие Фано, если какой-то из них подошел, это и есть ответ. Если ни для какого варианта не выполняется прямое условие Фано, проверяем обратное.Если выполняется обратное условие Фано, то декодируем с конца, а если не выполняется, то однозначно декодировать нельзя. Или все таки можно? Имелось в виду, что мы проверили сначала прямое условие, потом обратное, и оба не выполняются, значит однозначный ответ "декодировать нельзя" так?
Поляков: oval пишет: Имелось в виду, что мы проверили сначала прямое условие, потом обратное, и оба не выполняются, значит однозначный ответ "декодировать нельзя" Не обязательно. См. далее сообщение Людмилы Евич и ссылки в нем. Но пока все известные задачи ЕГЭ этого типа решаются с помощью условия Фано.
Гришина: 45)Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–11, Б–10, В–011, Г–000, Д–001. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа. 1) для буквы Г – 00 2) это невозможно 3) для буквы В – 01 4) для буквы Б – 1 Для Г(= 00) подходит обратное условие Фано, в то же время для В(= 01) подходит прямое условие Фано. Получается, здесь два правильных ответа? Заранее спасибо за ответ.
Поляков: Гришина пишет: Для Г(= 00) подходит обратное условие Фано, в то же время для В(= 01) подходит прямое условие Фано. Получается, здесь два правильных ответа? Читаем форум, перед тем как задать вопрос.
Larisa: Константин Юрьевич, объясните, пожалуйста №50. почему именно 1 ответ, а не 4? возможно, потому что 1(Б=1) являтся концом одной буквы, а Д=2 -двух, или правильнее, что 1<2?
Поляков: Larisa пишет: почему именно 1 ответ, а не 4? Давайте посмотрим, что будет при варианте 4: А–0, Б–11, В–20, Г–21, Д–2. Не выполняется ни прямое условие Фано (код Д совпадает с началом кода В), ни обратное (код А совпадает с окончанием кода В). Однозначно раскодировать в общем случае нельзя.
tavabar: Поляков пишет: Однозначно раскодировать в общем случае нельзя. Вывод: проверка условия (и прямого, и обратного) предполагает, что сопоставляется не только предложенный вариант с кодом каждой данной буквы И код каждой данной буквы с предложенным вариантом, но И коды букв между собой...
oval: коды букв между собойда, и глядя на коды букв можно сразу определить имеет ли смысл проверять прямое или обратное условие
Larisa: Константин Юрьевич, тогда для 50 номера, правильный ответ 2, а не 1. Поэтому и возник вопрос. Ответ "невозможно " стоит под цифрой 2. С уважением, Лариса
полная версия страницы