Отправлено: 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.
С уважением, Лариса

 Отправлено: 25.04.12 12:14. Заголовок: Larisa пишет: тогда ..

Larisa пишет:

цитата:

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

Ну, поехали по новому кругу.
Для этой задачи правильный ответ - 1. Для набора
А–0, Б–1, В–20, Г–21, Д–22
выполняется условие Фано.

 Отправлено: 09.05.12 18:01. Заголовок: И вновь о А9

Простите, что опять "по новому кругу" спрашиваю, но прочла все записи в форуме и свой пример не могу понять!!!!!!
А -110
Б-100
В-01
Г-11
Как закодировать Д(наимен, однозн): 1)10, 2) 0, 3) 00, 4)010?
У меня получается 2) 00. В ответе 4) 010?
Рассуждаю так: 1) 10 - не подходит, начало Б; 2)0 -начало В; 3) и 4) подходят, выбираем меньшее- 3)00
Второй вопрос: можно ли считать, что В (01) является началом кодового слова Д (010), т.е предлагаемого ответа? Тогда ответ точно-3)00

 Отправлено: 09.05.12 18:10. Заголовок: mortg пишет:А -110 Б..

mortg пишет:

цитата:

А -110 Б-100 В-01 Г-11 Как закодировать Д(наимен, однозн): 1)10, 2) 0, 3) 00, 4)010?

"По новому кругу" означает, что нужно проверять условия Фано (прямое и обратное) для всех букв, в том числе и для тех, коды которых не изменяются. В вашем примере для букв А и Г "прямое" условие Фано не выполняется, а обратное выполняется, поэтому имеет смысл рассматривать только такие коды буквы Д, для которых выполняется обратное условие Фано. Очевидно, что для Д=00 оно не выполняется.

 Отправлено: 11.05.12 02:36. Заголовок: Выполнение условий Ф..

Выполнение условий Фано: Прямое условие "или" обратное. Я так понимаю - достаточно, чтобы выполнялось одно из условий. А в этом примере проверяем выполнение прямого "И" обратного условия.
И опять же, на одной из веточек форума Вы пишете, что нужно проверять условие и между переменными-словами, а если Д=010, то "кодовое слово В является началом кодового слова Д". Я что-то совсем запуталась!

 Отправлено: 11.05.12 05:22. Заголовок: mortg пишет: Я так п..

mortg пишет:

цитата:

Я так понимаю - достаточно, чтобы выполнялось одно из условий.

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

цитата:

А в этом примере проверяем выполнение прямого "И" обратного условия.

В примере мы сначала смотрим на "неизменяемую" часть, чтобы определить, какое из двух условий реально выполнить, выбрав соответствующий код буквы Д. Видим, что "прямое" условие Фано выполнить все равно не удастся (мешает пара А-Г), поэтому ищем способ выбрать код буквы Д так, чтобы выполнялось обратное условие.

 Отправлено: 11.05.12 16:52. Заголовок: Условие Фано в неизменяемой части

То есть получается, что внутри" неизменяемой части" допускается нарушение условия Фано: пара А-Г и получившаяся пара В-Д? Сколько всевозможных условий и ограничений!!!!!!!!!!!!! Мне жаль детей.
А Вам Константин большое спасибо. Я уже как-то писала Вам письмо с благодарностью, честно говоря во многих заданиях я разобралась только благодаря Вам!

 Отправлено: 11.05.12 16:57. Заголовок: mortg пишет: Сколько..

mortg пишет:

цитата:

Сколько всевозможных условий и ограничений!

Такова жизнь.

 Отправлено: 12.05.12 19:19. Заголовок: опять А9

Простите меня за назойливость, но мне нужно до конца разобраться с задачами типа А9.
Задача
А-1
Б-001
В-000
Г-010
Кодовое слово Д: 1) 011, 2) 11, 3) 10, 4) 01 (длина д.б.наименьшая, однозначное декодирование)
В паре А-Б нарушается обратное условие Фано, проверяю прямое условие - подходит 10. А ответ 011! Что опять не так?

 Отправлено: 12.05.12 21:22. Заголовок: Уважаемый mortg, про..

Уважаемый mortg,
проверьте для вариантов 2) 11, 3) 10, 4) 01 оба условия Фано

 Отправлено: 13.05.12 08:31. Заголовок: mortg пишет: Что оп..

mortg пишет:

цитата:

Что опять не так

Если принять ответ 10, то не будет выполняться прямое условие между буквами А(1) и Д(10)

 Отправлено: 12.05.12 21:17. Заголовок: Здравствуйте, Конста..

Здравствуйте, Константин!
Задача из тренировочной работы 23 марта
Дано:
А-011
Б-010
В-000
Г-001
Какой последовательностью можно закодировать букву Д?
1) 00
2) 01
3) 10
4) 111
Вариант 1 не подходит по В
2 не подходит по А
3 не подходит по Б (обратное условие)
Выходит, что правильный ответ - 4?

 Отправлено: 13.05.12 08:38. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

3 не подходит по Б (обратное условие)

Но подходит по прямому условию...

 Отправлено: 12.05.12 21:22. Заголовок: А в ответах к этому ..

А в ответах к этому варианту - 3 (т.е. 10)!

 Отправлено: 12.05.12 21:26. Заголовок: Гость, вы мне? Откуд..

Гость, вы мне? Откуда Вы ответы достали? В сети рядом с этими заданиями выложены ответы к февральской работе

 Отправлено: 13.05.12 09:28. Заголовок: mortg, 1ро4ка_двадва..

mortg, 1ро4ка_двадва88 попробуйте разобраться с построением дерева для проверки условия Фано, второй способ решения для первого примера в разборе задач здесь
1ро4ка_двадва88 пишет:

цитата:

Гость, вы мне? Откуда Вы ответы достали? В сети рядом с этими заданиями выложены ответы к февральской работе

ответ действительно 10

 Отправлено: 13.05.12 18:52. Заголовок: Решайте А9 деревом

oval пишет:
[quote]`

Класс!!!!!!!!!! Спасибо oval! Действительно "деревом" легче разобраться в А9. Я на пробу решила 10 подобных заданий - ни одной ошибки. Кому еще не понятно задание А9- решайте деревом.

 Отправлено: 13.05.12 17:39. Заголовок: Гость, вы мне? Откуд..

цитата:

Гость, вы мне? Откуда Вы ответы достали?

Да, у меня есть ответы к тренировочной № 3 :)

Но не в этом дело. Мне тоже непонятно, почему в некоторых заданиях правильный ответ выбирается по прямому условию Фано, а в некоторых - по обратному. В заданиях никакого намека на это нет. Как быть, уважаемые участники форума?

 Отправлено: 13.05.12 18:37. Заголовок: Гость пишет: почему..

Гость пишет:

цитата:

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

Проверка условия (и прямого, и обратного) предполагает, что сопоставляется предложенный вариант с кодом каждой данной буквы И код каждой данной буквы с предложенным вариантом И коды букв между собой...
Если выполняется хотя бы одно (любое) условие Фано то декодирование ВОЗМОЖНО. Если проверили сначала прямое условие, потом обратное, и оба не выполняются, значит декодирование НЕВОЗМОЖНО.
Если надо выбрать из нескольких возможных вариантов самый короткий (самый длинный), то пользуясь прямым условием, выбираем возможные варианты, затем применяя обратное условие, выбираем возможные варианты, И ИЗ НИХ ВСЕХ выбираем самый короткий (длинный).

 Отправлено: 13.05.12 20:13. Заголовок: А тут как действоват..

А тут как действовать?
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы
1) 101
2) 10
3) 11
4) 01
Четвертый вариант проходит и прямую проверку и обратную

 Отправлено: 13.05.12 20:20. Заголовок: Ответ 4 и будет...

Ответ 4 и будет.

 Отправлено: 13.05.12 20:23. Заголовок: Это задание номер 41..

Это задание номер 41 из конспекта Полякова. Там ответ 1 указан

 Отправлено: 13.05.12 20:33. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

Это задание номер 41 из конспекта Полякова. Там ответ 1 указан

Правильный ответ - 1. При выборе варианта 4 получаем:
A=0, Б=100, В=110, Г=01.
Не выполняется ни прямое условие Фано (мешает пара А-Г), ни обратное (мешают пары А-Б и А-В).

 Отправлено: 13.05.12 20:43. Заголовок: Поляков пишет: меша..

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

цитата:

мешают пары А-Б и А-В

Пара АБ:
0100 - причем тут обратное условие?
вообще, мы тут же сравниваем не отдельные зашифрованные буквы, а защифрованные ряды букв. Условие Фано это и предпологает? Т.е. это тот же самый перебор вариантов в уме?

 Отправлено: 13.05.12 21:38. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

Пара АБ: 0100 - причем тут обратное условие?

Если раскодировать с конца (обратное условие проверяем), то коды букв А(0) и Б (100) невозможно однозначно определить. Например, 01000: ГААА, АБА.
1ро4ка_двадва88 пишет:

цитата:

мы тут же сравниваем не отдельные зашифрованные буквы, а защифрованные ряды букв.

Нет, мы сравниваем отдельные зашифрованные буквы. Проверка условия прямого: совпадает ли начало предложенного варианта с началом кода каждой данной буквы ИЛИ начало кода каждой данной буквы с началом предложенного варианта ИЛИ начала кодов букв между собой... Если совпадает, то декодирование по ЭТОМУ правилу не проходит.
Для проверки обратного - то же самое, только замените везде в предложении слово "начало" на слово "конец".

 Отправлено: 14.05.12 18:22. Заголовок: tavabar пишет: ИЛИ ..

tavabar пишет:

цитата:

ИЛИ начала кодов букв между собой

вот это самый сложный момент этого задания. Чтобы автоматизировать работу с перебором вариантов, можно использовать такую схему. Нам дано 4 буквы, и надо сравнить начала кодов между собой. Перебор очень длинный, и в уме можно пропустить какую-либо последовательность. Поэтому правильнее делать так: сравниваем А и Б
АБ
БА
сравниваем А и В
АВ
ВА
ВБ
БВ.
В данном случае проверка условия Фано будет ли означать, что "new Г" не должно встречаться в ряду, или не должно встречаться двоякого раскодирования рядов цифр? (что опять заставляет нас перебирать коды букв в уме)

 Отправлено: 14.05.12 20:51. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

правильнее делать так: сравниваем А и Б АБ БА сравниваем А и В АВ ВА ВБ БВ.

Нет. Так неправильно. Выбираем, например, проверку прямого правила Фано. Тогда надо сравнить код А с началом кодов Б и В. Затем сравним код Б с началом кодов А и В, и код В с началом кодов А и Б. Если все нормально, т. е. совпадений с началами кодов нет, то начинаем рассматривать варианты кодов для буквы Г.

 Отправлено: 14.05.12 21:12. Заголовок: Правильно ли я поним..

Правильно ли я понимаю, сравнивать коды А с Б и В значит:
перейдем к конкретной задаче
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы
1) 101
2) 10
3) 11
4) 01

Действуем по прямому условию Фано: проверяем А для Б и В
А (0) и Б (100). Б не начинается на 0, значит проверка пройдена.
Проверяем А (0) и В(110). Аналогично.
Так это выглядит? А зачем уже заданные проверять? Ведь с ошибками в условии не будут давать.

 Отправлено: 14.05.12 21:19. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

Так это выглядит?

Да. Так.1ро4ка_двадва88 пишет:

цитата:

А зачем уже заданные проверять?

Для заданных может сразу не выполняться прямое условие Фано, но, возможно, для них выполняется обратное условие. Или наоборот.

 Отправлено: 14.05.12 21:21. Заголовок: tavabar пишет: возм..

tavabar пишет:

цитата:

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

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

 Отправлено: 14.05.12 21:25. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

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

Конечно. Зачем тратить время на проверку выполнения прямого правила, если уже ясно, что даже среди ДАННЫХ кодов букв оно не выполняется.

 Отправлено: 13.05.12 21:40. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

Пара АБ: 0100 - причем тут обратное условие? вообще, мы тут же сравниваем не отдельные зашифрованные буквы, а защифрованные ряды букв. Условие Фано это и предпологает? Т.е. это тот же самый перебор вариантов в уме?

Перечитайте формулировку условия Фано. Например, здесь.

 Отправлено: 13.05.12 20:30. Заголовок: Понять, почему ответ..

Понять, почему ответ 1 можно легко: если бы мы задали код новой букве 01, то возникла бы двусмысленность в записи 0100. Ее можно было бы расшифровать как АБ или ГАА. Но как связать эти рассуждения с условием фано?

 Отправлено: 14.05.12 08:08. Заголовок: Для передачи по кана..

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код:
A=0, Б=10, В=110.
Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
1) 1 2) 1110 3) 111 4) 11
Правильный ответ: 3
Вопрос:а почему для букв, данных в условии задачи не выполняется условие Фано (код А совпадает с концом кода Б и В, А код Б совпадает с концом кода В). Или в условии это неважно?

 Отправлено: 14.05.12 08:17. Заголовок: Иришка пишет: не вып..

Иришка пишет:

цитата:

не выполняется условие Фано (код А совпадает с концом кода Б и В, А код Б совпадает с концом кода В)

Не выполняется обратное условие Фано, это верно. Но выполняется "прямое" - ни один код не совпадает с началом другого кода. Поэтому нуно выбрать код оставшейся буквы так, чтобы это условие сохранилось.

 Отправлено: 15.05.12 02:17. Заголовок: Достаточность услович Фано

Уважаемый, Константин Юрьевич. Хотелось бы немного обсудить с Вами достаточность условия Фано и его применимость.

цитата:

Отправлено: 19.03.12 10:19. oval пишет: Имелось в виду, что мы проверили сначала прямое условие, потом обратное, и оба не выполняются, значит однозначный ответ "декодировать нельзя" Поляков : Да.

Не могу с Вами согласиться. Контрпример. Код: А - 0, Б - 111, В - 010, Г - 101, Д - 110 не является ни префиксным, ни постфиксным, в то же время является однозначно декодируемым.

На основе лекций [1] и других материалов предлагаю решение задачи A9: (.pdf) http://dl.dropbox.com/u/17135806/Sol_%D0%909_LN.pdf
____
[1] Кочетов Ю. А. Дискретная математика. (Лекция 10) http://www.math.nsc.ru/LBRT/k5/dm.html

PS. Ваш сайт - замечательный. Для ребят очень много полезного и хорошо изложенного материала. Хорошо, что Вы находите на это время.

 Отправлено: 15.05.12 10:40. Заголовок: Евич Людмила пишет: ..

Евич Людмила пишет:

цитата:

Хотелось бы немного обсудить с Вами достаточность условия Фано и его применимость.

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

 Отправлено: 15.05.12 20:06. Заголовок: Евич Людмила пишет: ..

Евич Людмила пишет:

цитата:

Контрпример. Код: А - 0, Б - 111, В - 010, Г - 101, Д - 110 не является ни префиксным, ни постфиксным, в то же время является однозначно декодируемым.

Я думаю, что Вы ошибаетесь. Цепочка 0101010 декодируется как
010.101.0 = ВГА или как
0.101.010 = АГВ.
Это подтверждается графом.

Вот простой пример кода, который "не является ни префиксным, ни постфиксным, в то же время является однозначно декодируемым":
А - 0, Б - 010, В - 11.

 Отправлено: 15.05.12 13:51. Заголовок: Достаточность условия Фано

цитата:

Можно ли привести предложенный Вами способ решения со ссылкой на Вас?

Конечно. Может кто-нибудь предложит более оптимальный вариант решения.

 Отправлено: 15.05.12 16:15. Заголовок: Вопрос:В демо-вариан..

Вопрос:

цитата:

В демо-варианте задачи 9 решение основано на использовании свойств префиксных кодов. Значит ли это, что для решения боевых вариантов ЕГЭ этого будет достаточно?

Ответ М.А. Ройтберга:

цитата:

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

 Отправлено: 18.05.12 17:27. Заголовок: Для кодирования неко..

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

Ответ 2?

 Отправлено: 18.05.12 18:04. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

Ответ 2?

да

 Отправлено: 18.05.12 18:32. Заголовок: спс..

спс

 Отправлено: 02.07.12 14:02. Заголовок: Задача 42 выглядит о..

Задача 42 выглядит очень странной. Дело в том, что, хотя ответ 3, в принципе, верен, я не могу доказать, что ответ 2 неверен. Для ответа 2 не выполняется условие Фано, но оно ведь не является необходимым. И я что-то не могу найти ни одного примера, показывающего, где может возникнуть неоднозначность. Видимо, играет свою роль чётное количество нулей и единиц для кодов остальных букв - и если пытаться подобрать контрпример, эта чётность-нечётность сразу рушит его.

 Отправлено: 02.07.12 14:13. Заголовок: А, стоп, чего ж я то..

А, стоп, чего ж я торможу? В задаче 42 для ответа 2 запросто выполняется обратное условие Фано (для ответа 3 - и прямое, и обратное). Значит, оба ответа правильные? Или тут играет свою роль условие "для передачи по каналу связи сообщения...", то есть как бы намекается на невозможность докодирования с конца сообщения? И всё равно - даже если не брать в расчёт обратное условие Фано - контрпримеров для варианта 2 придумать не могу.

 Отправлено: 02.07.12 15:51. Заголовок: Ion пишет: я не мог..

Ion пишет:

цитата:

я не могу доказать, что ответ 2 неверен.

Он (10) неверен, т. к. является началом кода буквы В (100)/
Ion пишет:

цитата:

В задаче 42 для ответа 2 запросто выполняется обратное условие Фано

Обратное условие вообще нельзя использовать, т.к. тогда код буквы А(00) совпадает с концом кода буквы В(100)

 Отправлено: 05.07.12 10:04. Заголовок: Вы, меня, наверное, ..

Вы, меня, наверное, не совсем поняли.

tavabar пишет:

цитата:

Он (10) неверен, т. к. является началом кода буквы В (100)

Из этого следует только то, что не выполняется условие Фано. А оно не является необходимым для однозначного декодирования. В задаче ведь спрашивают про второе ("чтобы ... допускалось однозначное разбиение кодированного сообщения на буквы"), а не про то, выполняется ли тут условие Фано. Я о том и говорю. Условие Фано НЕ выполняется, я это прекрасно вижу. Но придумать такие примеры, которые бы допускали неоднозначности, я никак не смог. А Вы можете? :)

 Отправлено: 05.07.12 10:37. Заголовок: Ion пишет: Я о том и..

Ion пишет:

цитата:

Я о том и говорю. Условие Фано НЕ выполняется, я это прекрасно вижу. Но придумать такие примеры, которые бы допускали неоднозначности, я никак не смог. А Вы можете? :)

Уточним код:

цитата:

А = 00, Б = 11, В = 100, Г = 10

Для него невозможно придумать цепочку, которая неоднозначно раскодируется. Это можно доказать с помощью графов.

А можно "по-простому":
1) Две единицы рядом могут появиться только от буквы Б, поэтому удаляем все комбинации 11.
2) Далее, если в начале цепочки стоят нули, их обязательно должно быть четное количество, это буквы А.
3) В конце цепочки обязательно стоят нули, если их четное число, то это буква В и за ней (возможно) буквы А. Если в конце цепочки нечетное число нулей, то это буква Г и за ней (возможно) буквы А.

Таким образом дальше просто раскодировать, хоть с начала, хоть с конца. Причём однозначно.

Итак, в условии задачи неточность. Сейчас на сайте исправлено. Спасибо!

Успеха на экзамене! Вы должны сдать очень хорошо. :-)

 Отправлено: 05.07.12 19:56. Заголовок: Поляков пишет: Это ..

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

цитата:

Это можно доказать с помощью графов.

А у Вас не осталось решение с помощью графов? Ссылочка Евич Людмила

цитата:

решение задачи A9: (.pdf) http://dl.dropbox.com/u/17135806/Sol_%D0%909_LN.pdf

не работает

 Отправлено: 03.10.12 21:41. Заголовок: oval пишет: А у Вас..

oval пишет:

цитата:

А у Вас не осталось решение с помощью графов?

К сожалению, не смог найти файл, присланный Л. Евич. В моем изложении это выглядит так: decode_graph.doc.

 Отправлено: 04.10.12 08:05. Заголовок: спасибо..

спасибо

 Отправлено: 12.10.12 20:11. Заголовок: oval пишет: А у Вас ..

oval пишет:

цитата:

А у Вас не осталось решение с помощью графов?

Вот и оригинал, который присылала Л. Евич.

 Отправлено: 23.10.12 19:42. Заголовок: Поскольку поток вопр..

Поскольку поток вопросов по задаче А9 не прекращается, я сделал подробный анализ со всеми ньюансами, даже выходящими за рамки самого ЕГЭ: kpolyakov.blogspot.com/2012/10/blog-post.html.

 Отправлено: 05.07.12 11:41. Заголовок: Да-да, Константин Юр..

Да-да, Константин Юрьевич, я примерно это и имел в виду, когда говорил про "чётность-нечётность". Просто времени сейчас в обрез, так что детально разбираться с этим заданием - трата времени для меня сейчас.

 Отправлено: 05.07.12 13:22. Заголовок: Поляков пишет: Успе..

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

цитата:

Успеха на экзамене! Вы должны сдать очень хорошо. :-)

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

 Отправлено: 31.01.13 11:36. Заголовок: Спасибо за ссылку &#..

Спасибо за ссылку "мысли вслух" - помогло разобраться с заданием А6 КЕГЭ

 Отправлено: 15.03.13 15:44. Заголовок: а9

Здравствуйте, Константин Юрьевич!
С данной задачей я так и не разобралась. Помогите, пожалуйста, я прочитала всю теорию у Вас на сайте, такого примера нет.
Для передачи помехоустойчивых сообщений в алфавите, который содержит 16 различных символов, используется равномерный двоичный код. Этот код удовлетворяет следующему свойству: в любом кодовом слове содержится четное количество единиц (возможно, ни одной). Какую наименьшую длину может иметь кодовое слово?

 Отправлено: 15.03.13 17:35. Заголовок: Власова пишет: Для п..

Власова пишет:

цитата:

Для передачи помехоустойчивых сообщений в алфавите, который содержит 16 различных символов, используется равномерный двоичный код. Этот код удовлетворяет следующему свойству: в любом кодовом слове содержится четное количество единиц (возможно, ни одной). Какую наименьшую длину может иметь кодовое слово?

Посмотрите пояснения к ответу, который есть на Яндексе. Там 4 рабочих бита (2⁴ = 16) и 5-ый - бит четности, который и обеспечивает четное число единиц.