Что нужно знать:

• мощность алфавита M  – это количество символов в этом алфавите
• если алфавит имеет мощность M, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно  Q=M^N
• для двоичного кодирования (мощность алфавита M  – 2 символа) получаем известную формулу: Q=2^N
• таблица степеней двойки, она же показывает, сколько вариантов Q  можно закодировать с помощью K  бит:

Пример задания:

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

Решение:

1. согласно условию, алфавит содержит только два знака – точку и тире
2. «не менее четырёх и не более пяти сигналов» означает, что нужно определить количество всех 4- и 5-буквенных слов в двоичном алфавите
3. количество 4-буквенных слов равно 2⁴ = 16, а количество 5-буквенных 2⁵ = 32
4. поэтому общее количество 4- и 5-буквенных слов равно 16 + 32 = 48
5. ответ: 48.

Задачи для тренировки:

1. Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?
2. Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?
3. Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?
4. Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60?
5. Двое играют в «крестики-нолики» на поле 4 на 4 клетки.  Какое количество информации (в битах) получил второй игрок, узнав ход первого игрока?
6. В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?
7. В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке?
8. За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации. Сколько четверок получил Василий за четверть?
9. В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?
10. В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?
11. Некоторый алфавит содержит 4 различных символа.  Сколько трехбуквенных слов можно составить из символов этого алфавита, если символы в слове могут повторяться?
12. Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из трех различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из четырех таких элементов (при условии, что все элементы должны гореть)?
13. Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи четырех сигнальных флагов, если на корабле имеются флаги трех различных видов (флагов каждого вида неограниченное количество)?
14. Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи пяти сигнальных флагов, если на корабле имеются флаги четырех различных видов (флагов каждого вида неограниченное количество)?
15. Некоторое сигнальное устройство за одну секунду передает один из трех сигналов. Сколько различных сообщений длиной в пять секунд можно передать при помощи этого устройства?
16. Вася и Петя передают друг другу сообщения, используя синий, красный и зеленый фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении – 3 или 4, между сообщениями – паузы. Сколько различных сообщений могут передавать мальчики?
17. Для кодирования 300 различных сообщений используются 5 последовательных цветовых вспышек. Вспышки одинаковой длительности, для каждой вспышки используется одна лампочка определенного цвета. Лампочки скольких цветов должны использоваться при передаче (укажите минимально возможное количество)?
18. Каждая клетка поля 8×8 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток . Определите объем информации в байтах после 11 сделанных ходов? (Запись решения начинается с начальной позиции коня).
19. Каждая клетка поля 5×5 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток . Определите объем информации в байтах после 15 сделанных ходов? (Запись решения начинается с начальной позиции коня).
20. Учитель, выставляя в журнал четвертные отметки по биологии за третью четверть (3, 4, 5), обратил внимание, что комбинация из трех четвертных отметок по этому предмету у всех учеников различна. Какое может быть максимальное количество учеников в этом классе?
21. Некоторый алфавит содержит четыре различных символа. Сколько слов длиной ровно в 4 символа можно составить из слов данного алфавита (символы в слове могут повторяться)?
22. Квадратное световое табло 2´2 состоит из светящихся элементов, каждый из которых может гореть одним из четырех различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из четырех таких элементов (при условии, что все элементы должны гореть)?
23. Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из восьми различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из трех таких элементов (при условии, что все элементы должны гореть)?
24. Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?
25. Одна ячейка памяти троичного компьютера (один трит) может принимать одно из трех возможных значений: 0, 1 или –1. Для хранения некоторой величины в памяти такого компьютер отвели 4 ячейки. Сколько разных значений может принимать эта величина? 

Назад  В начало