Отправлено: 14.03.12 08:00. Заголовок: [A9] Условие Фано

Здравсвуйте, Константин.
В первом разоранном примере из задания А9 проверятся как прямое, так и обратное условие Фано. Во втором же, мне показалось, что проверяется только прямое. Можно ли как-то поподробное разъянить, когда исп. прямое условие Фано,а когда и обратное тоже
(впервые познакомился с ним в ваших материалах).
Спасибо.

 Отправлено: 14.03.12 10:19. Заголовок: PavelG пишет: когда ..

PavelG пишет:

цитата:

когда исп. прямое условие Фано,а когда и обратное тоже

Для однозначного декодирования достаточно, чтобы выполнялось одно (любое) из условий Фано: прямое позволяет однозначно декодировать цепочку с начала, обратное - с конца. Сначала проверяем для всех указанных в задании вариантов прямое условие Фано, если какой-то из них подошел, это и есть ответ. Если ни для какого варианта не выполняется прямое условие Фано, проверяем обратное.

 Отправлено: 17.03.12 21:40. Заголовок: Поляков пишет: Для ..

я бы уточнил, что проверять надо и имеющиеся коды, и предложенные, именно в этом делают ошибки, например, в задании
43) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=000, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
1) 00 2) 01 3) 11 4) 010

проверяют предложенные варианты, 2 и 3 удовлетворяют первому условию Фано, и ответ 3 подходит, но не проверяют коды букв А,Б,В на соответствие варианту.

 Отправлено: 23.03.12 07:28. Заголовок: кот Бегемот пишет: ..

кот Бегемот пишет:

цитата:

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

Если применить прямое условие Фано, то получаем ответ 2.
Допустим, я начну проверку с обратного условия Фано. Рассматриваю предложенные варианты. Не подходит только первый вариант: остальные не совпадают с концом ни одного кода. Теперь проверяю коды букв: отпадают вариант 3 (из-за А) и вариант 2 (из-за В). Итак, ответ 4.
Так, правильный ответ 2 или 4?
Или надо начинать проверку ТОЛЬКО с прямого условия Фано?

 Отправлено: 23.03.12 07:35. Заголовок: tavabar пишет: Так, ..

tavabar пишет:

цитата:

Так, правильный ответ 2 или 4? Или надо начинать проверку ТОЛЬКО с прямого условия Фано?

В задаче требуется найти самый короткий код из предложенных. Поэтому ответ - 2.

 Отправлено: 19.03.12 08:32. Заголовок: Поляков пишет: Для..

Поляков пишет:

цитата:

Для однозначного декодирования достаточно, чтобы выполнялось одно (любое) из условий Фано: прямое позволяет однозначно декодировать цепочку с начала, обратное - с конца. Сначала проверяем для всех указанных в задании вариантов прямое условие Фано, если какой-то из них подошел, это и есть ответ. Если ни для какого варианта не выполняется прямое условие Фано, проверяем обратное.

Если выполняется обратное условие Фано, то декодируем с конца, а если не выполняется, то однозначно декодировать нельзя.
Или все таки можно?

цитата:

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

"достаточное, но не необходимое" можно пояснить

 Отправлено: 19.03.12 09:04. Заголовок: oval пишет: Если вып..

oval пишет:

цитата:

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

Неверно. Можно, если выполняется "прямое" условие Фано.

цитата:

"достаточное, но не необходимое" можно пояснить

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

 Отправлено: 19.03.12 09:09. Заголовок: Сначала проверяем дл..

цитата:

Сначала проверяем для всех указанных в задании вариантов прямое условие Фано, если какой-то из них подошел, это и есть ответ. Если ни для какого варианта не выполняется прямое условие Фано, проверяем обратное.Если выполняется обратное условие Фано, то декодируем с конца, а если не выполняется, то однозначно декодировать нельзя. Или все таки можно?

Имелось в виду, что мы проверили сначала прямое условие, потом обратное, и оба не выполняются, значит однозначный ответ "декодировать нельзя"
так?

 Отправлено: 19.03.12 09:19. Заголовок: oval пишет: Имелось ..

oval пишет:

цитата:

Имелось в виду, что мы проверили сначала прямое условие, потом обратное, и оба не выполняются, значит однозначный ответ "декодировать нельзя"

Не обязательно. См. далее сообщение Людмилы Евич и ссылки в нем. Но пока все известные задачи ЕГЭ этого типа решаются с помощью условия Фано.

 Отправлено: 17.04.12 18:20. Заголовок: А9 - 45

45)Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–11, Б–10, В–011, Г–000, Д–001. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Г – 00 2) это невозможно
3) для буквы В – 01 4) для буквы Б – 1

Для Г(= 00) подходит обратное условие Фано, в то же время для В(= 01) подходит прямое условие Фано. Получается, здесь два правильных ответа? Заранее спасибо за ответ.

 Отправлено: 17.04.12 18:22. Заголовок: Гришина пишет: Для Г..

Гришина пишет:

цитата:

Для Г(= 00) подходит обратное условие Фано, в то же время для В(= 01) подходит прямое условие Фано. Получается, здесь два правильных ответа?

Читаем форум, перед тем как задать вопрос.

 Отправлено: 24.04.12 11:47. Заголовок: Константин Юрьевич, ..

Константин Юрьевич, объясните, пожалуйста №50.
почему именно 1 ответ, а не 4?
возможно, потому что 1(Б=1) являтся концом одной буквы, а Д=2 -двух, или правильнее, что 1<2?

 Отправлено: 24.04.12 11:51. Заголовок: Larisa пишет: почему..

Larisa пишет:

цитата:

почему именно 1 ответ, а не 4?

Давайте посмотрим, что будет при варианте 4:
А–0, Б–11, В–20, Г–21, Д–2.
Не выполняется ни прямое условие Фано (код Д совпадает с началом кода В), ни обратное (код А совпадает с окончанием кода В). Однозначно раскодировать в общем случае нельзя.

 Отправлено: 24.04.12 20:08. Заголовок: Поляков пишет: Одно..

Поляков пишет:

цитата:

Однозначно раскодировать в общем случае нельзя.

Вывод: проверка условия (и прямого, и обратного) предполагает, что сопоставляется не только предложенный вариант с кодом каждой данной буквы И код каждой данной буквы с предложенным вариантом, но И коды букв между собой...

 Отправлено: 24.04.12 20:27. Заголовок: коды букв между собо..

цитата:

коды букв между собой

да, и глядя на коды букв можно сразу определить имеет ли смысл проверять прямое или обратное условие

 Отправлено: 25.04.12 11:21. Заголовок: Константин Юрьевич, ..

Константин Юрьевич, тогда для 50 номера, правильный ответ 2, а не 1. Поэтому и возник вопрос.
Ответ "невозможно " стоит под цифрой 2.
С уважением, Лариса