Задача 1

Скачать 53 Kb.

Название	Задача 1
Дата публикации	17.07.2013
Размер	53 Kb.
Тип	Задача

100-bal.ru > Информатика > Задача

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

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

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

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

Упражнения

Сколько различных последовательностей длиной в 7 символов можно составить из цифр 0 и 1?
Сколько различных комбинаций можно построить, используя четыре двоичных разряда?
Сколько существует различных последовательностей из символов «а» и «б», длиной ровно в 10 символов?
Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?
Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код Морзе длиной не менее пяти и не более шести сигналов (точек и тире)?
Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код Морзе длиной не менее трех и не более пяти сигналов (точек и тире)?
Один мальчик, чтобы безошибочно определять, кто звонит в дверь, предложил своим друзьям использовать сочетания из длинных и коротких звонков по 3. Он раздал всем друзьям индивидуальные комбинации, и у него осталось еще 2 комбинации для родителей. Сколько друзей у мальчика?
Для передачи сигналов во флоте используются специальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи двух сигнальных флагов, если на корабле имеются флаги шести различных видов (флагов каждого вида неограниченное количество).

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

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

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

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

Упражнения

Сколько двоичных знаков необходимо и достаточно для того, чтобы закодировать одну школьную оценку? оценку в вузе?
Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях («включено» или «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 200 различных сигналов?
В зрительном зале две прямоугольные области зрительских кресел: одна – из 15 рядов по 12 кресел в каждом, а другая – 5 рядов по 9 кресел. Какое минимальное количество бит потребуется для кодирования каждого места в автоматизированной системе?
В зрительном зале две прямоугольные области зрительских кресел: одна – 10 на 12, а другая – 17 на 8. Какое минимальное количество бит потребуется для кодирования каждого места в автоматизированной системе?
Сколько бит информации несет сообщение о том, что тетраэдр, у которого все грани окрашены в разные цвета, после подбрасывания упал на синюю грань?
В корзине лежат 8 шаров. Все шары разного цвета. Сколько бит информации несет в себе сообщение о том, что из корзины выкатился синий шар?
В некоторой стране автомобильный номер длиной 7 символов составляют из заглавных букв (используются только 22 различные буквы) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объем памяти, отводимый этой программой для записи 50 номеров.
Обычный дорожный светофор без дополнительных секций подает шесть видов сигналов (непрерывные красный, желтый и зеленый, мигающие желтый и зеленый, красный и желтый одновременно). Электронное устройство управления светофором последовательно воспроизводит записанные сигналы. Подряд записано 100 сигналов светофора. Сколько составляет данный информационный объем в байтах?
Метеорологическая станция ведет наблюдение за направлением ветра. Результатом одного измерения является одно из восьми возможных направлений, которое записывается при помощи минимально возможного количества бит. Станция сделала 160 измерений. Определите информационный объем результатов наблюдений.
Метеорологическая станция ведет наблюдение за атмосферным давлением. Результатом одного измерения является целое число, принимающее значение от 720 до 780 мм ртутного столба, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.
В велокроссе участвуют 779 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 280 велосипедистов?
В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 80 велосипедистов?
Для компьютерной карточной игры используется 36 карт (4 масти по 9 карт). Двоичный код каждой карты состоит из двух частей: кода масти и кода карты. По сколько бит должно быть выделено на кодировку карты (код масти + код карты данной масти)?
Шахматная доска состоит из 64 полей: 8 столбцов на 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?
Для общения в языке племени мумбо-юмбо используется 12 основных понятий и 5 связок, позволяющие соединять эти понятия. Для передачи сообщений племя использует двоичный код: сочетание звонких и глухих звуков барабана. Сообщения передаются порциями – понятие + связка. Сколько ударов потребуется для кодирования каждой порции сообщения?
Для общения в языке племени мумбо-юмбо используется 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

Добавить документ в свой блог или на сайт

Похожие:

	Задача 1 22 Вариант 3 22 Задача 1 22 Вариант 4 23 Задача 1 23 Задача... «Менеджмент». Дисциплина реализуется кафедрой экономики и управления. Дисциплина нацелена на формирование общекультурных компетенций...		Доктор фаустус Иными словами, посильна ли человеку моего склада эта задача, задача, на выполнение которой меня подвигло скорее сердце, нежели право...
	Задача обучения математики До недавнего времени считалось, что главная задача школы состоит в том, чтобы дать каждому школьнику общей среднее образование в...		Урока: комбинированный. Задача урока Задача урока: показать глубину трагедии русского народа, ввергнутого в братоубийственную войну, определить возможности выхода из...
	Задача Лагранжа. Безусловный и условный экстремумы Задача Лагранжа с одним ограничением Модель II. Модель Уилсона с ограничениями на складские помещения		По Физике Механика от Аристотеля до Ньютона 2000-01 уч год. Основная часть По мере накопления знаний о мире задача их систематизации становилась всё более насущной. Эта задача была выполнена одним из величайших...
	Тема урока «Подобие треугольников. Решение практических задач» Дидактическая задача Дидактическая задача: Формирование универсальный учебных действий в условии решения практических задач		Урок литературного чтения Тема: Н. Н. Носов. «Федина задача» Н. Н. Носова «Федина задача», исследовать творчество Н. Н. Носова, совершенствовать навыки выразительного чтения; формировать умение...
	Реферат Задача иммунной системы состоит в том, чтобы поддержать наследственно... Стресс-индуцированное подавление клеточных иммунных реакций. Роль нейроэндокринного контроля иммунной системы		Программа по формированию навыков безопасного поведения на дорогах... Для учителя: мультимедийный комплекс, презентация к уроку, карточки с числами, ребус со словом «Задача», таблица «Задача. Составные...
	Приветствуют учителя, отвечают на организационные вопросы. С целью Учебная задача: развитие речевых умений на основе творческого применения усвоенного ранее лексико-грамматического материала в новых...		Программа по формированию навыков безопасного поведения на дорогах... И задача духовно- нравственного воспитания заключается в формировании такой личности. Поэтому задача учителя сверхсложная: он должен...
	§ "Король логических парадоксов" В науке, — писал английский химик Ф. Содди, — задача, надлежащим образом поставленная, более чем наполовину решена. Процесс умственной...		Обобщенная теорема Фалеса В этом учебном году на школьной олимпиаде по математике была предложена геометрическая задача, которая нам показалась очень сложной....
	Обобщенная теорема Фалеса В этом учебном году на школьной олимпиаде по математике была предложена геометрическая задача, которая нам показалась очень сложной....		4. технология научных исследований Важное значение имеет задача обеспечения научных исследований удобной для восприятия информацией о важнейших научных достижениях,...

Школьные материалы