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

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

 Отправлено: 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 пишет:

цитата:

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

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