- •Министерство образования и науки Российской федерации
- •§ 1. Вычисление количества последовательностей значений из заданного набора
- •Упражнения для самостоятельного решения
- •§ 2. Вычисление минимальной длины последовательностей, необходимых для кодирования указанного числа различных объектов
- •Упражнения для самостоятельного решения
- •§ 3. Определение информационного объема и параметров растрового изображения
- •Упражнения для самостоятельного решения
- •§ 4. Определение информационного объема и параметров цифрового звука
- •Упражнения для самостоятельного решения
- •§ 5. Определение информационного объема и параметров текстовой информации
- •Упражнения для самостоятельного решения
- •Содержание
Министерство образования и науки Российской федерации
Ивановский государственный университет
Математический факультет
Кафедра вычислительной и прикладной математики
Е. В. Соколов
Внутреннее представление,
измерение и хранение
информации
Методические указания для абитуриентов, сдающих ЕГЭ по информатике и ИКТ
Иваново
Издательство «Ивановский государственный университет»
2010
УДК 004.6
ББК 32.811
Внутреннее представление, измерение и хранение информации:методические указания для абитуриентов, сдающих ЕГЭ по информатике и ИКТ — Иваново: ИвГУ, 2010. — 26 с.
Составитель:кандидат физ.‑мат. наук, доцент кафедры вычислительной и прикладной математикиЕ. В. Соколов
Пособие посвящено решению задач, связанных с определением информационного объема и других параметров текстовой, графической и звуковой информации. Рассматриваются вопросы кодирования объектов битовыми последовательностями и последовательностями, составленными из символов, принадлежащих некоторому фиксированному алфавиту.
Каждый параграф содержит необходимые теоретические сведения, подборку задач с решениями и упражнения для самостоятельной работы. Решения и ответы к упражнениям собраны в конце издания. Там же приводятся задания для контрольной работы по рассматриваемой теме. Тематика задач соответствует кодификатору и спецификации ЕГЭ по информатике и ИКТ. При подготовке пособия в числе других источников использовались демонстрационные варианты ЕГЭ 2005–2011 гг.
Издание адресуется учащимся 10–11 классов, предполагающим сдавать ЕГЭ по информатике и ИКТ, но может быть полезно также и студентам 1 курса направлений «Математика» и «Математика и компьютерные науки», изучающим дисциплину «Архитектура ЭВМ».
Рецензент:кандидат физ.‑мат. наук, профессор кафедры алгебры и математической логикиН. И. Яцкин
Издается по решению методической комиссии математического факультета Ивановского государственного университета
Е. В. Соколов, 2010
§ 1. Вычисление количества последовательностей значений из заданного набора
Во всех задачах данного параграфа требуется найти количество различных последовательностей, составленных из символов, принимающих некоторый фиксированный набор значений. Посмотрим, как это сделать.
Выпишем все (упорядоченные) последовательности длины 2 из символов 0 и 1:
00, 01, 10, 11.
А теперь то же самое для последовательностей длины 3:
000, 001, 010, 011,
100, 101, 110, 111.
Легко заметить, что процесс выписывания последовательностей можно упорядочить следующим образом.
Положим значение крайнего левого символа равным 0 и будем перебирать все значения второго и третьего символов так, как будто они составляют самостоятельную последовательность длины 2:
0 00, 001, 010, 011,
Затем положим значение крайнего левого символа равным 1 и снова будем перебирать все значения оставшихся символов в том же порядке, что и в первом случае:
1 00, 101, 110, 111.
Аналогичным образом можно поступить и при выписывании последовательностей большей длины: по очереди фиксируем различные значения крайнего левого символа, и для каждого из них выписываем все сочетания значений остальных символов, перебирая тем самым последовательности длины, на единицу меньшей. Вот примеры перечисления последовательностей длин 4 и 5:
0 000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1 000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.
0 0000, 00001, 00010, 00011,, 01100, 01101, 01110, 01111,
1 0000, 10001, 10010, 10011,, 11100, 11101, 11110, 11111,
Как видно из приведенного алгоритма, при увеличении длины последовательности на единицу количество различных последовательностей возрастает в два раза. Отсюда легко получается следующее
Утверждение 1.1.Количество последовательностей длиныN, составленных из символов 0 и 1, равно 2N.
Пусть теперь имеется набор не из 2, а из kразличных значений. Последовательности, составленные из символов, принимающих этиkзначений, выписываются точно так же: по очереди фиксируем всеkзначений крайнего левого символа, и для каждого из них выписываем все сочетания значений остальных символов. Например, для набора значений{x, y, z}имеем:
x x x, x x y, x x z,
x y x, x y y, x y z,
x z x, x z y, x z z,
y x x, y x y, y x z,
y y x, y y y, y y z,
y z x, y z y, y z z,
z x x, z x y, z x z,
z y x, z y y, z y z,
z z x,z z y,z z z.
Ясно, что в общем случае при увеличении длины последовательности на один символ количество последовательностей возрастет в kраз. Тем самым, мы получаем
Утверждение 1.2.Количество последовательностей длиныN, составленных из символов, каждый из которых может принимать одно изkзначений, равноkN.
Совет.Вместо того, чтобы заучивать формулы из приведенных утверждений, гораздо лучше запомнить алгоритм перечисления последовательностей, из которого они получаются. Это избавит от многих ошибок, например, от использования выраженияNkвместоkN.
Теперь перейдем к рассмотрению конкретных задач.
Задача 1.1.Сколько различных последовательностей длиной в 7 символов можно составить из цифр 0 и 1?
Решение.Набор значений в этой задаче состоит из цифр 0 и 1, поэтомуk2. Составляемые последовательности имеют длинуN7. Стало быть, число различных последовательностей равно 27.
Ответ: 27128 последовательностей.
Задача 1.2.Сколько различных комбинаций можно построить, используя четыре двоичных разряда?
Решение.Двоичные разряды, о которых идет речь в данной задаче, — это то же самое, что и биты. Двоичный разряд потому и называетсядвоичным, что он может иметьдваразличных значения, соответствующие числам 0 и 1. Таким образом, в данной задачеk2 и, так как комбинации составляются из четырех разрядов,N4. Поэтому число различных комбинаций равно 24.
Ответ:2416 комбинаций.
Задача 1.3.Сколько существует различных последовательностей из символов «а» и «б», длиной ровно в 10 символов?
Решение.В предыдущих двух задачах последовательности составлялись из цифр 0 и 1. Здесь им на смену приходят символы «а» и «б». Что от этого меняется? Ничего, так как нас интересуют не сами символы, а только их количествоk. Оно же в этой задаче снова оказывается равным двум. Так как рассматриваемые последовательности имеют длинуN10, получаем, что их количество равно 210.
Ответ:2101024 последовательности.
Задача 1.4.Один мальчик, чтобы безошибочно определять, кто звонит в дверь, предложил своим друзьям использовать сочетания из длинных и коротких звонков по 3. Он раздал всем друзьям индивидуальные комбинации, и у него осталось еще 2 комбинации для родителей. Сколько друзей у мальчика?
Решение.Здесь опять используется набор из двух значений, только теперь это — длинный и короткий звонки. Комбинации составляются изN3 звонков, поэтому максимальное число различных комбинаций — 238. Известно, что после того, как мальчик раздал часть из этих 8 комбинаций друзьям, у него осталось еще две для родителей. Стало быть, друзьям он раздал 6 комбинаций и, так как каждый друг получил свою собственную, индивидуальную комбинацию, то и друзей у мальчика шесть.
Ответ:6 друзей.
Задача 1.5.Одна ячейка памяти троичной ЭВМ (компьютера, основанного на троичной системе счисления) может принимать одно из трех возможных состояний. Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?
Решение.А вот, наконец, задача, в которой набор состоит не из двух, а из трех значений: этими значениями являются состояния, которые может принимать ячейка памяти троичной ЭВМ. Таким образом, здесьk3. Далее, для хранения рассматриваемой величины используется последовательность изN4 ячеек. Следовательно, количество различных значений этой величины совпадает с количеством различных последовательностей, составленных из значений всех четырех ячеек, и равно 34.
Ответ:3481 значение.
Задача 1.6.Для передачи сигналов во флоте используются специальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи двух сигнальных флагов, если на корабле имеются флаги шести различных видов (флагов каждого вида неограниченное количество).
Решение.Невнимательно прочитав данную задачу, легко допустить ошибку.
Как указано в условии, сигналы подаются с помощью последовательности флагов. При этом на каждое место в последовательности может быть повешен флаг любого вида (это следует из того, что флагов каждого вида неограниченное количество), а видов этих согласно условию — шесть. Таким образом, в данной задаче набор состоит из k6 значений.
Далее, в условии сказано, что сигналы подаются с помощью двух флагов (каждый из которых может иметь один из шести видов). Следовательно, мы рассматриваем последовательности длины N2 и количество различных сигналов, передаваемых с помощью этих последовательностей, получается равным 62, а не 26, как может показаться на первый взгляд.
Ответ:6236 сигналов.
Задача 1.7.Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код Морзе длиной не менее пяти и не более шести сигналов (точек и тире)?
Решение.Здесь снова используются комбинации изk2 значений: точек и тире. Отличие данной задачи в том, что в ней рассматриваются последовательности различной длины: пять или шесть сигналов. Количество последовательностей необходимо подсчитать отдельно дляN5 и дляN6. В первом случае оно будет равно 25, во втором — 26. Общее количество кодируемых символов будет равно суммарному числу последовательностей обоих видов.
Ответ:252696 символов.