Форум » Вычисление количества информации » задание 11 (№85) » Ответить

задание 11 (№85)

mousoh01: "Автомобильный номер состоит из одиннадцати букв русского алфавита A, B, C, E, H, K, M, O, P, T, X и десятичных цифр от 0 до 9. Каждый номер состоит из двух букв, затем идет 3 цифры и еще одна буква. Например, АВ901С. В системе каждый такой номер кодируется посимвольно, при этом каждая буква и каждая цифра кодируются одинаковым минимально возможным количеством бит. Укажите, сколько бит на один номер можно сэкономить, если кодировать с помощью одинакового минимально возможного количества бит каждую из трех групп – первые две буквы, три цифры и последняя буква." Не совсем понимаю вопрос задачи. N=11, i=4бита (информационный вес 1 буквы) N=10, i=4бита (информационный вес 1 цифры) V=2*4+3*4+1*4=24 бита вес 1 номера. Дальше не понимаю что делать, т.к. не понимаю вопроса. Помоги, пж!

Ответов - 30, стр: 1 2 All

petrgrishin: Так если посчитать не группами, то N = 21 i = 5 бит k = 6 I = 5 * 6 = 30 бит И тогда экономия 30 - 24 = 6

check8386: Официальный ответ на это задание 3.

s11kai: s11kai пишет: Следовательно при групповом кодировании экономим 3 бита ... В первой группе 22, во второй - 30, а в третьей - 11 различных символов, то для их кодирования достаточно выделить по 4 бита.


s11kai: Спасибо, Константин Юрьевич! Одна ошибка найдена, при кодировании первой и второй группы вместо умножения использовал сложение. Но от этого не стало легче, поскольку условие вводит ограничения, количество бит в каждой группе должно быть одинаковым и минимально возможным. В данном случае это 10, в пересчете на три группы получаем 30, против 24. 24 - 30 = -6. Какая же это экономия? На такой ответ мы уже выходили, правда там получалось +6, что уже подавало надежду, но соответствовало ответу petrgrishin пишет: Так если посчитать не группами, то N = 21 i = 5 бит k = 6 I = 5 * 6 = 30 бит И тогда экономия 30 - 24 = 6

mousoh01: Спасибо, теперь хоть как - то стало понятнее! Ну уж больно замороченное условие задачи, надеюсь на экзамене такого не будет!

s11kai: Увы, скорее всего будут сюрпризы и покруче!

check8386: s11kai Объясните, пожалуйста, как можно группу из 3 цифр (от 0 до 9) или группу из двух букв (при мощности алфавита 11) закодировать четырьмя битами.

s11kai: check8386 пишет: s11kai Объясните, пожалуйста, как можно группу из 3 цифр (от 0 до 9) Хороший вопрос, отсюда встречный, как вы думаете, часто ли у нас будет максимальный код: XX999X Подумаем, что можно будет сделать, если нужно закодировать именно его. Начнем с конца! Допустим, что букву "X" мы сопоставили с числом 11. Посмотрим сколько бит нам для этого понадобиться в двоичном коде: 1011, а кто нам запретит его закодировать например так, чтоб "враг" не догадался: 1110 или наоборот 0111. Если взять пять бит, то можно закодировать 32 числа, а цифры от 0 до 9 дают 10 чисел, тогда группа из трех чисел в сумме дает число 30. Например группу из трех цифр 9 + 9 + 9 = 27 можно закодировать в двоичном коде так: 11011, а если соотнести, например 9-ке число 10, то можно будет закодировать и так 11110, все зависит от того, как договорятся тот кто кодирует и кому нужно будет декодировать. Заметим, что даже при максимальных значениях у нас остается, как минимум по 1-му нулевому биту, в каждой группе. А что нам может помешать закодировать 27, в троичном коде оно = 1000.

check8386: *PRIVAT*

EugeneJobs: Уффф, уважаемые, в первую очередь необходимо разобраться с темой кодирование информации. И принять тот факт, что не всегда кодируются отдельные буквы/цифры/символы. Например, если мы знаем, что какая-то СТРОКА принимает условные 6 состояний: "ABC", "ACB", "BAC", "BCA","CAB", "CBA". То мы можем закодировать КАЖДУЮ такую последовательность числами от 0 до 5 или 3 битами при условии равномерного кодирования. После принятия данного факта решение задачи становится весьма простым.

check8386: EugeneJobs s11kai пишет: да и в строке на каждом месте может находится не три символа, как в вашем примере, а 10 или 11. Вдобавок, буквы и цифры могут повторяться, условие это не запрещает. кодировать с помощью одинакового минимально возможного количества бит каждую из трех групп – первые две буквы, три цифры и последняя буква Раз все три группы нужно кодировать одинаковым количеством бит, то нужно найти количество бит для самой большой группы (из трех цифр) и умножить на 3? Будем благодарны за подробное объяснение.

s11kai: EugeneJobs пишет: не всегда кодируются отдельные буквы/цифры/символы Это понятно, но условие задания, как раз предлагает, кодировать посимвольно mousoh01 пишет:каждый такой номер кодируется посимвольно , да и в строке на каждом месте может находится не три символа, как в вашем примере, а 10 или 11. EugeneJobs, поясните пожалуйста подробнее, если можно, не то мы уже которые сутки бьемся в поисках этой самой экономии в три бита и ее целесообразности. Заранее, огромная вам благодарность

Поляков: s11kai пишет: условие задания, как раз предлагает, кодировать посимвольно В условии задачи как раз и спрашивается, сколько бит можно выиграть, если использовать групповое кодирование вместо посимвольного. два символа -> 11*11 = 121 сочетание - хватит 7 битов число 000-999 -> 1000 вариантов - 10 битов последняя буква -> 11 вариантов - 4 бита. Всего 21 бит против 24 при посимвольном кодировании.

check8386: Поляков Большое спасибо, Константин Юрьевич! mousoh01 пишет: сколько бит на один номер можно сэкономить, если кодировать с помощью ОДИНАКОВОГО минимально возможного количества бит каждую из трех групп Непонятно, зачем здесь слово "одинакового"? Вводит в заблуждение.

EugeneJobs: если долго бьетесь над моими задачами, есть смысл найти либо мой канал, либо группу вк. Там разборы всех моих заданий из сборника Константина Юрьевича есть.



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