Форум » Кодирование и декодирование информации » [A9] Условие Фано » Ответить

[A9] Условие Фано

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

Ответов - 72, стр: 1 2 3 4 5 All

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

Поляков: Larisa пишет: тогда для 50 номера, правильный ответ 2, а не 1. Поэтому и возник вопрос. Ответ "невозможно " стоит под цифрой 2. Ну, поехали по новому кругу. Для этой задачи правильный ответ - 1. Для набора А–0, Б–1, В–20, Г–21, Д–22 выполняется условие Фано.

mortg: Простите, что опять "по новому кругу" спрашиваю, но прочла все записи в форуме и свой пример не могу понять!!!!!! А -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

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

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

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

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

Поляков: mortg пишет: Сколько всевозможных условий и ограничений! Такова жизнь.

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

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

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

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

tavabar: 1ро4ка_двадва88 пишет: 3 не подходит по Б (обратное условие) Но подходит по прямому условию...

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

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

oval: mortg, 1ро4ка_двадва88 попробуйте разобраться с построением дерева для проверки условия Фано, второй способ решения для первого примера в разборе задач здесь 1ро4ка_двадва88 пишет: Гость, вы мне? Откуда Вы ответы достали? В сети рядом с этими заданиями выложены ответы к февральской работе ответ действительно 10

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

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

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

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

Гость: Ответ 4 и будет.

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

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

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

tavabar: 1ро4ка_двадва88 пишет: Пара АБ: 0100 - причем тут обратное условие? Если раскодировать с конца (обратное условие проверяем), то коды букв А(0) и Б (100) невозможно однозначно определить. Например, 01000: ГААА, АБА. 1ро4ка_двадва88 пишет: мы тут же сравниваем не отдельные зашифрованные буквы, а защифрованные ряды букв. Нет, мы сравниваем отдельные зашифрованные буквы. Проверка условия прямого: совпадает ли начало предложенного варианта с началом кода каждой данной буквы ИЛИ начало кода каждой данной буквы с началом предложенного варианта ИЛИ начала кодов букв между собой... Если совпадает, то декодирование по ЭТОМУ правилу не проходит. Для проверки обратного - то же самое, только замените везде в предложении слово "начало" на слово "конец".

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

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

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

tavabar: 1ро4ка_двадва88 пишет: Так это выглядит? Да. Так.1ро4ка_двадва88 пишет: А зачем уже заданные проверять? Для заданных может сразу не выполняться прямое условие Фано, но, возможно, для них выполняется обратное условие. Или наоборот.

1ро4ка_двадва88: tavabar пишет: возможно, для них выполняется обратное условие. это будет значить, что нужно сразу начинать с проверки обратного условия?

tavabar: 1ро4ка_двадва88 пишет: это будет значить, что нужно сразу начинать с проверки обратного условия Конечно. Зачем тратить время на проверку выполнения прямого правила, если уже ясно, что даже среди ДАННЫХ кодов букв оно не выполняется.

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

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

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

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

Евич Людмила: Уважаемый, Константин Юрьевич. Хотелось бы немного обсудить с Вами достаточность условия Фано и его применимость. Отправлено: 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. Ваш сайт - замечательный. Для ребят очень много полезного и хорошо изложенного материала. Хорошо, что Вы находите на это время.

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

Поляков: Евич Людмила пишет: Контрпример. Код: А - 0, Б - 111, В - 010, Г - 101, Д - 110 не является ни префиксным, ни постфиксным, в то же время является однозначно декодируемым. Я думаю, что Вы ошибаетесь. Цепочка 0101010 декодируется как 010.101.0 = ВГА или как 0.101.010 = АГВ. Это подтверждается графом. Вот простой пример кода, который "не является ни префиксным, ни постфиксным, в то же время является однозначно декодируемым": А - 0, Б - 010, В - 11.

Евич Людмила: Можно ли привести предложенный Вами способ решения со ссылкой на Вас? Конечно. Может кто-нибудь предложит более оптимальный вариант решения.

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

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

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

1ро4ка_двадва88: спс

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

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

tavabar: Ion пишет: я не могу доказать, что ответ 2 неверен. Он (10) неверен, т. к. является началом кода буквы В (100)/ Ion пишет: В задаче 42 для ответа 2 запросто выполняется обратное условие Фано Обратное условие вообще нельзя использовать, т.к. тогда код буквы А(00) совпадает с концом кода буквы В(100)

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

Поляков: Ion пишет: Я о том и говорю. Условие Фано НЕ выполняется, я это прекрасно вижу. Но придумать такие примеры, которые бы допускали неоднозначности, я никак не смог. А Вы можете? :) Уточним код: А = 00, Б = 11, В = 100, Г = 10 Для него невозможно придумать цепочку, которая неоднозначно раскодируется. Это можно доказать с помощью графов. А можно "по-простому": 1) Две единицы рядом могут появиться только от буквы Б, поэтому удаляем все комбинации 11. 2) Далее, если в начале цепочки стоят нули, их обязательно должно быть четное количество, это буквы А. 3) В конце цепочки обязательно стоят нули, если их четное число, то это буква В и за ней (возможно) буквы А. Если в конце цепочки нечетное число нулей, то это буква Г и за ней (возможно) буквы А. Таким образом дальше просто раскодировать, хоть с начала, хоть с конца. Причём однозначно. Итак, в условии задачи неточность. Сейчас на сайте исправлено. Спасибо! Успеха на экзамене! Вы должны сдать очень хорошо. :-)

oval: Поляков пишет: Это можно доказать с помощью графов. А у Вас не осталось решение с помощью графов? Ссылочка Евич Людмила решение задачи A9: (.pdf) http://dl.dropbox.com/u/17135806/Sol_%D0%909_LN.pdf не работает

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

oval: спасибо

Поляков: oval пишет: А у Вас не осталось решение с помощью графов? Вот и оригинал, который присылала Л. Евич.

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

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

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

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

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

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



полная версия страницы