Кодирование и декодирование информации

Кодирование и декодирование информации

11 класс

Манушкина Е.В., МАОУ «СОШ №1»

Часть 1: Вычисление информационного объема. Анализ последовательностей.

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

• с помощью K бит можно закодировать различных вариантов (чисел)

• таблица степеней двойки, она же показывает, сколько вариантов N можно закодировать с помощью X бит:

К, бит

Q, вар-в

1

2

2

3

4

8

4

16

5

6

32

64

7

8

128

256

9

10

512

1024

• при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 Кбайт) – 1024 байта, в мегабайте (1 Мбайт) – 1024 Кбайта

• чтобы найти информационный объем сообщения (текста) I , нужно умножить количество символов (отсчетов) X на число бит на символ (отсчет) K :

• две строчки текста не могут занимать 100 Кбайт в памяти

мощность алфавита M – это количество символов в этом алфавите

если алфавит имеет мощность M , то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно

для двоичного кодирования (мощность алфавита M – 2 символа) получаем известную формулу:

13 (повышенный уровень, время – 3 мин)

Пример 1:

№ 1

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, К, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 12 байт на одного пользователя. Определите объём памяти (в байтах), необходимый для хранения сведений о 50 пользователях. В ответе запишите только целое число – количество байт.

Задача из варианта КИМ для досрочной сдачи ЕГЭ по информатике 05.05.2015

№ 1

По­яс­не­ние:

На кодирование одного символа из 12-буквенного алфавита требуется 4 бита. Тогда на один пароль необходимо 4*15=60 бит. Минимальное количество байт, вмещающее 60 бит — 8. Итого на одного пользователя необходимо 8 + 12 = 20 байт. А на 50 пользователей нужно 20 * 50 = 1000 байт.

Возможные ловушки :

часто забывают, что пароль должен занимать ЦЕЛОЕ число байт

13 (повышенный уровень, время – 3 мин)

Пример 2:

№ 2

  Автомобильный номер состоит из 6 символов. Допустимыми символами считаются 10 цифр и 5 заглавных букв: A, P, T, E, K. Для хранения каждого из 15 допустимых символов используется одинаковое и наименьшее возможное количество бит. Для хранения каждого номера используется одинаковое и мини­маль­но возможное количество байт. Сколько байт памяти потребуется для хранения 400 автомобильных но­ме­ров? Номера хранятся без разделителей. 

1) 800

2) 1200

3) 1600

4) 2000

По­яс­не­ние:

Согласно условию, в номере могут быть использованы 15 символов. Известно, что с помощью N бит можно закодировать 2 N  различных вариантов. Поскольку 2 3  

Для хранения всех 6 символов номера нужно 4 · 6 = 24 бит = 3 байт. Тогда для записи 400 автомобильных номеров необходимо 3 · 400 = 1200 байт.

Правильный ответ указан под номером 2.

№ 2

13 (повышенный уровень, время – 3 мин)

Пример 3:

№ 3

В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболевшая обезьяна живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б?

Пояснение:

И нформация в 4 бита соответствует выбору одного из 16 вариантов, поэтому в вольере А живет 1/16 часть всех обезьян (это самый важный момент !)

Всего обезьян – 32, поэтому в вольере А живет 32/16 = 2 обезьяны

В вольере Б живут все оставшиеся 32 – 2 = 30 обезьян

ответ – 30.

№ 3

Возможные ловушки :

1) можно сделать неверный вывод о том, что в вольере А живет 4 обезьяны (столько же, сколько бит информации мы получили), следовательно, в вольере Б живут оставшиеся 28 обезьян (неверный ответ 3)

2) после п. 1 можно сделать (неверный) вывод о том, что в вольере А живет 16 обезьян, следовательно, в вольере Б – тоже 16 (неверный ответ 2)

13 (повышенный уровень, время – 3 мин)

Пример 4:

№ 4

Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах? 

1) 30

2) 60

3) 120

4) 480

Пояснение:

1 символ в коде Unicode кодируется 16-ю битами, 1 символ в коде КОИ-8 — 8-ю битами. Количество символов при перекодировке не меняется, поэтому обозначим его за Х .

Составим уравнение:

16*х – 8*х = 480

Решая его найдём 8*х = 480 следовательно, х = 60 .

Пра­виль­ный ответ ука­зан под но­ме­ром 2 .

№ 4

10 (базовый уровень, время – 4 мин)

Пример 5:

№ 5

Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Задача из варианта КИМ для досрочной сдачи ЕГЭ по информатике 05.05.2015

Пояснение :

• буква С может стоять на одном из пяти мест: С****, *С***, **С**, ***С* и ****С, где * обозначает любой из оставшихся трёх символов
• в каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н, поэтому при заданном расположении буквы С имеем 3 4 = 81 вариант
• всего вариантов 5 · 81 = 405.

Ответ: 405 .

№ 5

10 (базовый уровень, время – 4 мин)

Пример 6:

№ 6

Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A?

Пояснение (1 способ):

• рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:

АА*** А*А** А**А* А***А

Здесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов.

• итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 3 3 = 27
• всего 4 шаблона, они дают 4 · 27 = 108 комбинаций
• теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:

*АА** *А*А* *А**А

они дают 3 · 27 = 81 комбинацию

• два шаблона, где первая по счёту буква А стоит на третьей позиции:

**АА* **А*А

они дают 2 · 27 = 54 комбинации

• и один шаблон, где сочетание АА стоит в конце

***АА

они дают 27 комбинаций

• всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций
• ответ: 270 .

№ 6

Пояснение (2 способ):

1) в последовательности из 5 символов нужно использовать ровно две буквы А и три символа, не совпадающих с А, которые обозначим звездочкой

2) сначала найдём количество перестановок из двух букв А и трёх звёздочек

используем формулу для вычисления числа перестановок с повторениями; для двух разных символов она выглядит так:

Здесь – количество букв А, – количество звёздочек и восклицательный знак обозначает факториал натурального числа, то есть произведение всех натуральных чисел от 1 до n :

№ 6

3) в нашем случае и , так что получаем:

4) теперь разберёмся со звёздочками: вместо каждой из них может стоять любой из трёх символов (кроме А), то есть на каждую из 10 перестановок мы имеем 33 = 27 вариантов распределения остальных символов на месте звёздочек

5) таким образом, получаем всего 10 · 27 = 270 вариантов.

ответ: 270 .

10 (базовый уровень, время – 4 мин)

Пример 7:

№ 7

Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Пояснение:

• Дано слово длиной 5 символов типа * ****, где красная звездочка – гласная буква (Е или Э), а черная буква любая из трёх заданных.
• Общая формула количества вариантов:

N = M L , где М – мощность алфавита, а L – длина кода.

• Так как положение одной из букв строго регламентировано (знак умножения в зависимых событиях), то формула всех вариантов примет вид: N = M 1 L 1 ∙ M 2 L2 ,
• Тогда M 1 = 2 (алфавит гласных букв), а L 1 = 1 (только 1 позиция в слове).

M 2 = 3 (алфавит всех букв), а L 2 = 4 (оставшиеся 4 позиции в слове).

• В итоге получаем: N = 2 1 ∙ 3 4 = 2 ∙ 81 = 162.
• ответ: 162 .

№ 7

10 (базовый уровень, время – 4 мин)

Пример 8:

№ 8

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.

Вот начало списка:

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Запишите слово, которое стоит на 240-м месте от начала списка.

Пояснение (способ 1):

• подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв;
• очевидно, что есть всего 3 однобуквенных слова (А, О, У); двух буквенных слов уже 3  3=9 (АА, АО, АУ, ОА, ОО, ОУ, УА, УО и УУ)
• аналогично можно показать, что есть всего 3 5 = 243 слова из 5 букв
• очевидно, что последнее, 243-е слово – это УУУУУ
• далее идём назад: предпоследнее слово УУУУО (242-е), затем идет УУУУА (241-е) и, наконец, УУУОУ (240-е)
• Ответ: УУУОУ .

№ 8

Возможные ловушки и проблемы :

хорошо, что требовалось найти слово, которое стоит близко к концу списка; если бы было нужно, скажем, 123-е слово, работы было бы значительно больше

Пояснение (способ 2):

по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию)

выпишем начало списка, заменив буквы на цифры:

1. 00000

2. 00001

3. 00002

4. 00010

……

это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д.

тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления

переведем 239 в троичную систему: 239 = 22212 3

заменяем обратно цифры на буквы: 22212  УУУОУ

Ответ: УУУОУ .

№ 8

Возможные ловушки и проблемы :

нужно помнить, что нумерация в задаче начинается с 1, а числа в троичной системе – с нуля, поэтому для получения 240-го элемента списка нужно переводить в троичную систему число 240-1 = 239.

10 (базовый уровень, время – 4 мин)

Пример 9:

№ 9

Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.

Вот начало списка:

1. ААААА

2. ААААК

3. ААААЛ

4. ААААО

5. ААААШ

6. АААКА

……

На каком месте от начала списка стоит слово ШКОЛА?

Пояснение:

По аналогии с предыдущей задаче, используя пятеричную систему счисления

Ответ: 2711 .

№ 9

Возможные ловушки и проблемы :

нужно помнить, что список в задании начинается с 1, а числа в троичной системе – с нуля, поэтому для получения N-ой по счёту цепочки нужно переводить в троичную систему число N-1.

10 (базовый уровень, время – 4 мин)

Пример 10:

№ 10

Все 5-буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка:

1. УУУУУ

2. УУУУО

3. УУУУА

4. УУУОУ

……

Запишите слово, которое стоит на 240-м месте от начала списка.

Пояснение:

Ответ: АААОА .

№ 10

10 (базовый уровень, время – 4 мин)

Пример 11:

№ 11

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

Пояснение:

Если в алфавите   N   символов, то количество всех возможных «слов» (сообщений) дли н ой  M   равно              .

Поэтому четырехбуквенных символов слов 16, я пятибуквенных — 32. Всего можно закодировать 48 сообщений.

№ 11

Ответ: 48 .