Задача 1. Вычисление количества последовательностей значений из заданного набора
Пусть составляются последовательности из N символов, каждый из которых может принимать одно из k значений. Определить количество различных последовательностей, составленных из этих символов.
Утверждение 1. Количество последовательностей длины N, составленных из символов, каждый из которых может принимать одно из k значений, равно k N.
Совет. Вместо того, чтобы заучивать формулы, гораздо лучше запомнить алгоритм перечисления последовательностей, из которого они получаются.
Упражнения
1.1. Сколько различных последовательностей длиной в 7 символов можно составить из цифр 0 и 1?
1.2. Сколько различных комбинаций можно построить, используя четыре двоичных разряда?
1.3. Сколько существует различных последовательностей из символов «а» и «б», длиной ровно в 10 символов?
1.4. Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?
1.5. Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код Морзе длиной не менее пяти и не более шести сигналов (точек и тире)?
1.6. Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код Морзе длиной не менее трех и не более пяти сигналов (точек и тире)?
1.7. Один мальчик, чтобы безошибочно определять, кто звонит в дверь, предложил своим друзьям использовать сочетания из длинных и коротких звонков по 3. Он раздал всем друзьям индивидуальные комбинации, и у него осталось еще 2 комбинации для родителей. Сколько друзей у мальчика?
1.8. Для передачи сигналов во флоте используются специальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи двух сигнальных флагов, если на корабле имеются флаги шести различных видов (флагов каждого вида неограниченное количество).
Задача 2. Вычисление минимальной длины последовательностей, необходимых для кодирования указанного числа различных объектов
Пусть сначала кодирование осуществляется битовыми последовательностями, т. е. символы из последовательности могут принимать лишь два значения: 0 и 1. Пусть имеется X различных объектов, требуется определить минимальное число N, такое, что каждому из этих X объектов можно сопоставить свою уникальную последовательность длины N.
Утверждение 2. Число N удовлетворяет двойному неравенству 2N-1 < X £ 2N. Число N равно наименьшему целому числу, не меньшему log2 X (то есть логарифм нужно округлить вверх до ближайшего целого).
Совет. Лучше запомнить не формулы, а способ их получения. В частности, длину битовых последовательностей можно искать подбором, основываясь на неравенстве 2N-1 < X £ 2N.
Упражнения
2.1. Сколько двоичных знаков необходимо и достаточно для того, чтобы закодировать одну школьную оценку? оценку в вузе?
2.2. Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях («включено» или «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 200 различных сигналов?
2.3. В зрительном зале две прямоугольные области зрительских кресел: одна – из 15 рядов по 12 кресел в каждом, а другая – 5 рядов по 9 кресел. Какое минимальное количество бит потребуется для кодирования каждого места в автоматизированной системе?
2.4. В зрительном зале две прямоугольные области зрительских кресел: одна – 10 на 12, а другая – 17 на 8. Какое минимальное количество бит потребуется для кодирования каждого места в автоматизированной системе?
2.5. Сколько бит информации несет сообщение о том, что тетраэдр, у которого все грани окрашены в разные цвета, после подбрасывания упал на синюю грань?
2.6. В корзине лежат 8 шаров. Все шары разного цвета. Сколько бит информации несет в себе сообщение о том, что из корзины выкатился синий шар?
2.7. В некоторой стране автомобильный номер длиной 7 символов составляют из заглавных букв (используются только 22 различные буквы) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объем памяти, отводимый этой программой для записи 50 номеров.
2.8. Обычный дорожный светофор без дополнительных секций подает шесть видов сигналов (непрерывные красный, желтый и зеленый, мигающие желтый и зеленый, красный и желтый одновременно). Электронное устройство управления светофором последовательно воспроизводит записанные сигналы. Подряд записано 100 сигналов светофора. Сколько составляет данный информационный объем в байтах?
2.9. Метеорологическая станция ведет наблюдение за направлением ветра. Результатом одного измерения является одно из восьми возможных направлений, которое записывается при помощи минимально возможного количества бит. Станция сделала 160 измерений. Определите информационный объем результатов наблюдений.
2.10. Метеорологическая станция ведет наблюдение за атмосферным давлением. Результатом одного измерения является целое число, принимающее значение от 720 до 780 мм ртутного столба, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.
2.11. В велокроссе участвуют 779 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 280 велосипедистов?
2.12. В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 80 велосипедистов?
2.13. Для компьютерной карточной игры используется 36 карт (4 масти по 9 карт). Двоичный код каждой карты состоит из двух частей: кода масти и кода карты. По сколько бит должно быть выделено на кодировку карты (код масти + код карты данной масти)?
2.14. Шахматная доска состоит из 64 полей: 8 столбцов на 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?
2.15. Для общения в языке племени мумбо-юмбо используется 12 основных понятий и 5 связок, позволяющие соединять эти понятия. Для передачи сообщений племя использует двоичный код: сочетание звонких и глухих звуков барабана. Сообщения передаются порциями – понятие + связка. Сколько ударов потребуется для кодирования каждой порции сообщения?
2.16. Для общения в языке племени мумбо-юмбо используется 13 основных понятий и 4 связки, позволяющие соединять эти понятия. Для передачи сообщений племя использует двоичный код: сочетание звонких и глухих звуков барабана. Сообщения передаются порциями – понятие + связка. Сколько ударов потребуется для кодирования каждой порции сообщения?
Задачи для решения в классе | Домашнее задание |
1.1, 1.3, 1.5, 1.7, 1.8 | 1.2, 1.4, 1.6, 1.8 |
2.1, 2.3, 2.5, 2.7, , 2.13, 2.15 | 2.2, 2.4, 2.6, 2.8, 2.10, 2.12, 2.14, 2.16 |
