Образовательный портал Павла Добряка

Тема «кодирование» близка к задачам на системы счисления и является их логичным продолжением. Я включил в неё задачи, которые можно решить с помощью систем счисления, комбинаторные задачи (которые когда-то давно изучали в школе, потом их убрали из школьной программы, и потом они вновь «всплыли» уже на ЕГЭ по информатике) и задачи на передачу информации (строго говоря, к кодированию не относятся, но «по жизни» с кодированием связанные).

Задача 2.1.1. Для ко­ди­ро­ва­ния букв О, К, Г, Д, Р ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). За­ко­ди­руй­те по­сле­до­ва­тель­ность букв ГО­РО­ДОК таким спо­со­бом и ре­зуль­тат за­пи­ши­те вось­ме­рич­ным кодом.

Задача 2.1.2. Для ко­ди­ро­ва­ния букв А, В, С, D ис­поль­зу­ют­ся трех­раз­ряд­ные по­сле­до­ва­тель­ные дво­ич­ные числа, на­чи­на­ю­щи­е­ся с 1 (от 100 до 111 со­от­вет­ствен­но). За­ко­ди­руй­те таким об­ра­зом по­сле­до­ва­тель­ность сим­во­лов CDAB и за­пи­ши­те ре­зуль­тат в шест­на­дца­те­рич­ном коде.

Задача 2.1.3. Все 5-буквенные слова, со­став­лен­ные из букв А, Н, П, за­пи­са­ны в ал­фа­вит­ном порядке. Вот на­ча­ло списка:

Задача 2.1.4. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Укажите номер первого слова, которое начинается с буквы У.

Задача 2.2.1. Сколько можно составить пятибуквенных слов, если используются только буквы A, B, C (каждая буква может повторяться несколько раз или не встречаться в слове вовсе).

Задача 2.2.2. Есть четыре флага разных цветов и четыре мачты. Сколько можно передать сообщений, если флаги вывешивать на мачты в разном порядке (на каждой мачте обязательно должен висеть один из флагов).

Задача 2.2.3. В магазине продается 7 видов фруктов. Мы можем купить только три вида фруктов, чтобы сделать из них салат. Сколько различных видов салатов мы могли бы приготовить из имеющегося в магазине ассортимента?

Задача 2.2.4. Сколько шестибуквенных слов можно составить из букв A,B,C,D, если буква A встречается в каждом слове ровно три раза, а остальные буквы могут присутствовать в любых количествах или не быть вообще.

Задача 2.2.5. В соревновании принимали участие 20 спортсменов. Какой объем памяти (бит) нужен, чтобы запомнить номера трех победителей?

Задача 2.2.6. Петя и Вася живут напротив друг друга и решили обмениваться сообщениями с помощью табло из лампочек. Каждая лампочка может быть выключенной, включенной или мигать. Сколько лампочек нужно, чтобы закодировать 33 буквы русского алфавита?

Задача 2.2.7. В детскую игрушку «Набор юного шпиона» входят два одинаковых комплекта из четырех флажков различных цветов. Сколько различных тайных сообщений можно передать этими флажками, условившись менять выставленный флажок каждые пять минут и наблюдая за процессом 15 минут? Наблюдатель видит вынос первого флажка и две перемены флажка. При этом возможна смена флажка на флажок того же цвета.

Задача 2.2.8. Команды для некоторого устройства задаются тремя одинаковыми тумблерами. Сколько положений должно быть в тумблере, чтобы можно было закодировать 120 различных команд?

Задача 2.2.9. Метеостанция измеряет температуру в диапазоне от -8 до 8 с точностью 0,5 градусов. Сколько бит нужно, чтобы сохранить результаты одного измерения?

Задача 2.2.10. Какой объем памяти в байтах нужен, чтобы сохранить картинку размером 8X8 пикселей, при использовании палитры из 32   цветов?

Задача 2.2.11. Производится двухканальная звукозапись с частотой дискретизации 100 Гц. При записи использовались 256 уровней дискретизации. Запись длится 5 минут. Сколько байт требуется для сохранения звукозаписи?

Задача 2.2.12.  Производится од­но­ка­наль­ная (моно) зву­ко­за­пись с ча­сто­той дискретизации 48 кГц и глу­би­ной кодирования 16 бит. За­пись длится 2 минуты, ее ре­зуль­та­ты записываются в файл, сжа­тие данных не производится. Какое из при­ве­ден­ных ниже чисел наи­бо­лее близко к раз­ме­ру полученного файла, вы­ра­жен­но­му в мегабайтах?

Задача 2.2.13. B не­ко­то­рой стра­не ав­то­мо­биль­ный номер дли­ной 7 сим­во­лов со­став­ля­ют из за­глав­ных букв (ис­поль­зу­ют­ся толь­ко 33 раз­лич­ных буквы) и де­ся­тич­ных цифр в любом по­ряд­ке. Каж­дый такой номер в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством бай­тов (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов). Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 125 но­ме­ров.

Задача 2.2.14. Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?

Задача 2.2.15. Герасим составляет 7-буквенные коды из букв Г, Е, Р, А, С, И, М. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Герасим?

Задача 2.2.16. Левий составляет 5-буквенные коды из букв Л, Е, В, И, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ЕИ. Сколько различных кодов может составить Левий?

Задача 2.3.1. Для пе­ре­да­чи чисел по ка­на­лу с по­ме­ха­ми ис­поль­зу­ет­ся код про­вер­ки чет­но­сти. Каж­дая его цифра за­пи­сы­ва­ет­ся в дво­ич­ном пред­став­ле­нии, с до­бав­ле­ни­ем незначащих нулей до длины 4, и к по­лу­чив­шей­ся по­сле­до­ва­тель­но­сти до­пи­сы­ва­ет­ся сумма её эле­мен­тов по мо­ду­лю 2 (на­при­мер, если пе­ре­даём 23, то по­лу­чим по­сле­до­ва­тель­ность 0010100110). Опре­де­ли­те, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100000100110. Если фрагмент декодировать невозможно, обозначьте его буквой X.

Задача 2.3.2. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы — П, О, Р, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова:

Задача 2.4.1. Какой объем информации в битах мы получим, кидая монетку два раза, если оба раза выпадет «орёл»?

Задача 2.4.2. На правильный тетраэдр (пирамиду из четырех правильных треугольников) нанесли числа 0, 1, 2, 3. Какой объем информации нужен, чтобы сохранить результат  одного кидания тетраэдра (грани, на которую он приземлится)?

Задача 2.4.3. Двое играют в «крестики-нолики» на поле 4 на 4 клетки. Какое количество информации (в битах) получил второй игрок, узнав ход первого игрока?

Задача 2.4.4. В кор­зи­не лежат чер­ные и белые шары. Среди них 18 чер­ных шаров. Со­об­ще­ние о том, что до­ста­ли белый шар, несет 2 бита информации. Сколь­ко всего шаров в корзине?

Задача 2.4.5. За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации. Сколько четверок получил Василий за четверть?

Задача 2.4.6. В закрытом ящике находятся 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?

Задача 2.5.1. Азбука Морзе поз­во­ля­ет кодировать сим­во­лы для со­об­ще­ний по радиосвязи, за­да­вая комбинацию точек и тире. Сколь­ко различных сим­во­лов (цифр, букв, зна­ков пунктуации и т. д.) можно закодировать, ис­поль­зуя код аз­бу­ки Морзе дли­ной не менее трёх и не более пяти сиг­на­лов (точек и тире)?

Задача 2.5.2.  Для 5 букв русского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех): К – 000, М – 10, А – 111, Р – 01, И – 101 . Из четырех сообщений в этом коде только одно прошло без ошибки и может быть корректно декодировано. Найдите его.

Задача 2.5.3.  Некоторые буквы русского алфавита закодировали неравномерным кодом (по две и три двоичные цифры): А – 010, Б – 111, В – 10, Г – 01, Д – 00. Напишите без пробелов букву, в которой для корректного декодирования нужно добавить третью цифру, и букву, в которой третья цифра избыточна для корректного декодирования.

Задача 2.5.4.  По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко пять букв: A, B, С, D, E. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, до­пус­ка­ю­щий од­но­знач­ное де­ко­ди­ро­ва­ние. Для букв A, B, C ис­поль­зу­ют­ся такие ко­до­вые слова:

A – 1, B – 010, C – 000.

Ука­жи­те крат­чай­шее ко­до­вое слово для буквы E, при ко­то­ром код будет до­пус­кать од­но­знач­ное де­ко­ди­ро­ва­ние. Если таких кодов не­сколь­ко, ука­жи­те код с наи­мень­шим чис­ло­вым зна­че­ни­ем.

Задача 2.5.5. По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г – 110, И – 01, Т – 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАРАБАН? 

Задача 2.6.1. Документ объемом 5 Мбайт можно передать с одного компьютера на другой двумя способами:

А) Сжать архиватором, передать архив по каналу связи, распаковать.

Б) Передать по каналу связи без использования архиватора.

Какой способ быстрее и насколько, если

– средняя скорость передачи данных по каналу связи составляет 2¹⁸ бит в секунду,

– объем сжатого архиватором документа равен 80% от исходного,

– время, требуемое на сжатие документа – 35 секунд, на распаковку – 3 секунды?

Задача 2.6.2. У Толи есть доступ к сети Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 2¹⁹ бит в секунду. У Миши нет скоростного доступа в Интернет, но есть возможность получать информацию от Толи по низкоскоростному телефонному каналу со средней скоростью 2¹⁵ бит в секунду. Миша договорился с Толей, что тот будет скачивать для него данные объемом 5 Мбайт по высокоскоростному каналу и ретранслировать их Мише по низкоскоростному каналу.

Компьютер Толи может начать ретрансляцию данных не раньше, чем им будут получены первые 512 Кбайт этих данных. Каков минимальный возможный промежуток времени (в секундах) с момента начала скачивания Толей данных до полного их получения Мишей?

В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Задача 2.6.3.  Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 15 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 2 раза выше, чем канала связи с городом А. Сколько секунд длилась передача файла в город Б? В ответе запишите только целое число, единицу измерения писать не нужно.