Задача Вычисление количества последовательностей значений из заданного набора - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Порядок вычисления значений хэш-функции для файлов с помощью программного... 1 29.04kb.
Вопросы к экзамену по дисциплине «Прикладной функциональный анализ» 1 36.69kb.
Задачи на вычисление количества информации Что нужно знать 1 88.68kb.
Дискретное программирование 1 49.85kb.
Химия 9 класс. Задания с развернутым ответом 1 32.84kb.
Задача №1 По данным таблицы определите среднюю выработку на одного... 1 39.96kb.
Программа государственного экзаменА по специальности 230201. 1 52.42kb.
Генераторы реальных случайных последовательностей 1 108.06kb.
65. Вычисление некоторых пределов 1 24.12kb.
Программа предназначена для выполнения несложных газодинамических... 1 30.64kb.
Задача о классе качества вод: прогноз отклика по многомерным эмпирическим... 10 2034.49kb.
Обобщить и систематизировать материал по указанной теме 1 71.51kb.
Направления изучения представлений о справедливости 1 202.17kb.

Задача Вычисление количества последовательностей значений из заданного набора - страница №1/1

Задача 1. Вычисление количества последовательностей значений из заданного набора

Пусть составляются последовательности из N символов, каждый из которых может принимать одно из k значений. Определить количество различных последовательностей, составленных из этих символов.



Утверждение 1. Количество последовательностей длины N, составленных из символов, каждый из которых может принимать одно из k значений, равно k   N.

Совет. Вместо того, чтобы заучивать формулы, гораздо лучше запомнить алгоритм перечисления последовательностей, из которого они получаются.

Упражнения

    1. Сколько различных последовательностей длиной в 7 символов можно составить из цифр 0 и 1?

    2. Сколько различных комбинаций можно построить, исполь­зуя четыре двоичных разряда?

    3. Сколько существует различных последовательностей из символов «а» и «б», длиной ровно в 10 символов?

    4. Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?

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

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

    7. Один мальчик, чтобы безошибочно определять, кто звонит в дверь, предложил своим друзьям использовать сочетания из длинных и коротких звонков по 3. Он раздал всем друзьям ин­дивидуальные комбинации, и у него осталось еще 2 комбинации для родителей. Сколько друзей у мальчика?

    8. Для передачи сигналов во флоте используются специальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи двух сигнальных флагов, если на корабле имеются флаги шести различных видов (флагов каждого вида неограниченное количество).


Задача 2. Вычисление минимальной длины последовательностей, необходимых для кодирования указанного числа различных объектов

Пусть сначала кодирование осуществляется битовыми последовательностями, т. е. символы из последовательности могут принимать лишь два значения: 0 и 1. Пусть имеется X различных объектов, требуется определить минимальное число N, такое, что каждому из этих X объектов можно сопоставить свою уникальную последовательность длины N.



Утверждение 2. Число N удовлетворяет двойному неравенству 2N1  X  2N. Число N равно наименьшему целому числу, не меньшему log2  X (то есть логарифм нужно округлить вверх до ближайшего целого).

Совет. Лучше запомнить не формулы, а способ их получения. В частности, длину битовых последовательностей можно искать подбором, основываясь на неравенстве 2N1  X  2N.

Упражнения

    1. Сколько двоичных знаков необходимо и достаточно для того, чтобы закодировать одну школьную оценку? оценку в вузе?

    2. Световое табло состоит из лампочек, каждая из которых может находиться в двух со­стояниях («включено» или «выключено»). Какое наименьшее количество лампочек долж­но находиться на табло, чтобы с его помощью можно было передать 200 различных сиг­налов?

    3. В зрительном зале две прямоугольные области зрительских кресел: одна – из 15 рядов по 12 кресел в каждом, а другая – 5 рядов по 9 кресел. Какое минимальное количество бит потребуется для кодирования каждого места в автоматизированной системе?

    4. В зрительном зале две прямоугольные области зрительских кресел: одна – 10 на 12, а другая – 17 на 8. Какое минимальное количество бит потребуется для кодирования каждого места в автоматизированной системе?

    5. Сколько бит информации несет сообщение о том, что тетраэдр, у которого все грани окрашены в разные цвета, после подбрасывания упал на синюю грань?

    6. В корзине лежат 8 шаров. Все шары разного цвета. Сколько бит информации несет в себе сообщение о том, что из корзины выкатился синий шар?

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

    8. Обычный дорожный светофор без дополнительных секций подает шесть видов сигна­лов (непрерывные красный, желтый и зеленый, мигающие желтый и зеленый, красный и желтый одновременно). Электронное устройство управления светофором последователь­но воспроизводит записанные сигналы. Подряд записано 100 сигналов светофора. Сколько составляет данный информационный объем в бай­тах?

    9. Метеорологическая станция ведет наблюдение за направлением ветра. Результа­том одного измерения является одно из восьми возможных направлений, которое записывается при помощи минимально возможного количества бит. Станция сделала 160 измерений. Определите информационный объем результатов на­блюдений.

    10. Метеорологическая станция ведет наблюдение за атмосферным давлением. Результа­том одного измерения является целое число, принимающее значение от 720 до 780 мм ртутного столба, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов на­блюдений.

    11. В велокроссе участвуют 779 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с ис­пользованием минимально возможного количества бит, одинакового для каждого спорт­смена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 280 велосипедистов?

    12. В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с ис­пользованием минимально возможного количества бит, одинакового для каждого спорт­смена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 80 велосипедистов?

    13. Для компьютерной карточной игры используется 36 карт (4 масти по 9 карт). Двоичный код каждой карты состоит из двух частей: кода масти и кода карты. По сколько бит должно быть выделено на кодировку карты (код масти + код карты данной масти)?

    14. Шахматная доска состоит из 64 полей: 8 столбцов на 8 строк. Какое минимальное ко­личество бит потребуется для кодирования координат одного шахматного поля?

    15. Для общения в языке племени мумбо-юмбо используется 12 основных понятий и 5 связок, позволяющие соединять эти понятия. Для передачи сообщений племя использует двоичный код: сочетание звонких и глухих звуков барабана. Сообщения передаются порциями – понятие + связка. Сколь­ко ударов по­требуется для кодирования каждой порции сообщения?

    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.9 (2.11), 2.13, 2.15

2.2, 2.4, 2.6, 2.8, 2.10, 2.12, 2.14, 2.16







Ничто так не способствует развитию демократии, как ее отсутствие. Михаил Генин
ещё >>