| Автор | Сообщение |
|
Отправлено: 14.03.12 08:00. Заголовок: [A9] Условие Фано
Здравсвуйте, Константин.
В первом разоранном примере из задания А9 проверятся как прямое, так и обратное условие Фано. Во втором же, мне показалось, что проверяется только прямое. Можно ли как-то поподробное разъянить, когда исп. прямое условие Фано,а когда и обратное тоже
(впервые познакомился с ним в ваших материалах).
Спасибо.
|
 |
  
|
|
Ответов - 72
, стр:
1
2
3
4
5
All
[только новые]
|
|
|
|
| Администратор
|
Сообщение: 321
|
|
Отправлено: 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
Вопрос:а почему для букв, данных в условии задачи не выполняется условие Фано (код А совпадает с концом кода Б и В, А код Б совпадает с концом кода В). Или в условии это неважно?
|
|
|
|
|
| Администратор
|
Сообщение: 322
|
|
Отправлено: 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. Ваш сайт - замечательный. Для ребят очень много полезного и хорошо изложенного материала. Хорошо, что Вы находите на это время. |
|
|
|
|
| Администратор
|
Сообщение: 326
|
|
Отправлено: 15.05.12 10:40. Заголовок: Евич Людмила пишет: ..
Евич Людмила пишет: | цитата: | | Хотелось бы немного обсудить с Вами достаточность условия Фано и его применимость. |
|
Спасибо, Вы правы, я ошибся. Действительно, условие Фано - достаточное, но не необходимое. К счастью, пока все известные задачи А9 решались через условие Фано. Можно ли привести предложенный Вами способ решения со ссылкой на Вас? |
|
|
|
|
| Администратор
|
Сообщение: 329
|
|
Отправлено: 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. Заголовок: Достаточность условия Фано
| цитата: | | Можно ли привести предложенный Вами способ решения со ссылкой на Вас? |
|
Конечно. Может кто-нибудь предложит более оптимальный вариант решения. |
|
|
|
|
| Администратор
|
Сообщение: 328
|
|
Отправлено: 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?
|
|
|
|
|
| постоянный участник
|
Сообщение: 72
|
|
Отправлено: 18.05.12 18:04. Заголовок: 1ро4ка_двадва88 пише..
1ро4ка_двадва88 пишет: да |
|
|
|
|
|
Отправлено: 18.05.12 18:32. Заголовок: спс..
спс
|
|
|
|
Отправлено: 02.07.12 14:02. Заголовок: Задача 42 выглядит о..
Задача 42 выглядит очень странной. Дело в том, что, хотя ответ 3, в принципе, верен, я не могу доказать, что ответ 2 неверен. Для ответа 2 не выполняется условие Фано, но оно ведь не является необходимым. И я что-то не могу найти ни одного примера, показывающего, где может возникнуть неоднозначность. Видимо, играет свою роль чётное количество нулей и единиц для кодов остальных букв - и если пытаться подобрать контрпример, эта чётность-нечётность сразу рушит его.
|
|
|
|
Отправлено: 02.07.12 14:13. Заголовок: А, стоп, чего ж я то..
А, стоп, чего ж я торможу? В задаче 42 для ответа 2 запросто выполняется обратное условие Фано (для ответа 3 - и прямое, и обратное). Значит, оба ответа правильные? Или тут играет свою роль условие "для передачи по каналу связи сообщения...", то есть как бы намекается на невозможность докодирования с конца сообщения? И всё равно - даже если не брать в расчёт обратное условие Фано - контрпримеров для варианта 2 придумать не могу.
|
|
|
|
|
| постоянный участник
|
Сообщение: 103
|
|
Отправлено: 02.07.12 15:51. Заголовок: Ion пишет: я не мог..
Ion пишет: | цитата: | | я не могу доказать, что ответ 2 неверен. |
|
Он ( 10) неверен, т. к. является началом кода буквы В ( 100)/ Ion пишет: | цитата: | | В задаче 42 для ответа 2 запросто выполняется обратное условие Фано |
|
Обратное условие вообще нельзя использовать, т.к. тогда код буквы А( 00) совпадает с концом кода буквы В(1 00) |
|
|
|
Ответов - 72
, стр:
1
2
3
4
5
All
[только новые]
|
|
- участник сейчас на форуме
- участник вне форума