Егэ кодирование. Кодирование и декодирование информации

21.10.2019

Основано на: демонстрационных вариантах ЕГЭ по информатике за 2015 год, http://wiki.vspu.ru/

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А - 0; Б - 100; В - 1010; Г - 111; Д - 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Как это можно сделать?

Для того чтобы понять что от нас требуют, давайте разберемся с каждым словом в этом задании. Кодирование, последовательность, - это всем нам с вами знакомые и хорошо понятные слова и что они означяают, мы прекрасно понимаем. И вот после перечисления букв мы сталкиваемся с не всем знакомым словосочетанием НЕРАВНОМЕРНЫЙ двоичный код. Неравномерное двоичное кодирование - кодирование при котором символы некоторого первичного алфавита кодируются комбинациями символов двоичного алфавита (т.е. 0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Данная идея двоичного кодирования положена в основу Кода Хаффмана, в котором символ, который встречается в последовательности чаще всего, получает очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код, тем самым позволяя уменьшить объем информации.

Предположим, у нас есть строка «тор тут тёр», для которой, в её текущем виде, на каждый знак тратится по одному байту. Это означает, что вся строка целиком занимает 11*8 = 88 бит памяти. После кодирования строка займёт 27 бит.

Чтобы получить код для каждого символа строки «тор тут тёр», на основе его частотности, нам надо построить дерево (граф), такое, что каждый лист этого дерева будет содержать символ. Дерево будет строиться от листьев к корню, в том смысле, что символы с меньшей частотой будут дальше от корня, чем символы с большей.

Чтобы построить дерево, мы воспользуемся слегка модифицированной очередью с приоритетами — первыми из неё будут извлекаться элементы с наименьшим приоритетом, а не наибольшим. Это нужно, чтобы строить дерево от листьев к корню.

И так, подсчитаем частотность символов Т Р пробел О У Е

Символ	Частотность
Т	4
Р	2
" "	2
У	1
О	1
Е	1

После вычисления частот мы создадим узлы бинарного дерева для каждого знака и добавим их в очередь, используя частоту в качестве приоритета:

Теперь мы достаём два первых элемента из очереди и связываем их, создавая новый узел дерева, в котором они оба будут потомками, а приоритет нового узла будет равен сумме их приоритетов. После этого мы добавим получившийся новый узел обратно в очередь.

Повторим те же шаги и в итоге мы получим:

После связывания веток в одно дерево, мы с вами получим следующие коды для наших символов

Т - 00; Р - 10; пробел -01; О - 1110; У - 110; Е - 1111 более подробно можно прочитать

Задание 1 ЕГЭ:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А - 0; Б - 100; В - 1010; Г - 111; Д - 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Как это можно сделать?

Урок посвящен тому, как решать 5 задание ЕГЭ по информатике

5-я тема характеризуется, как задания базового уровня сложности, время выполнения – примерно 2 минуты, максимальный балл — 1

Кодирование - это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом .
Кодирование бывает равномерным и неравномерным :
при равномерном кодировании всем символам соответствуют коды одинаковой длины;
при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.

Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:

Таким образом, мы получили равномерный код , т.к. длина каждого кодового слова одинакова для всех кодов (2).

Кодирование и расшифровка сообщений

Декодирование (расшифровка) - это восстановление сообщения из последовательности кодов.

Для решения задач с декодированием, необходимо знать условие Фано:

Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)

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

Однозначное декодирование обеспечивается:

Решение 5 заданий ЕГЭ

ЕГЭ 5.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0 , 1 , 2 , 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

✍ Решение:

Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:

О -> 0 -> 00 В -> 1 -> 01 Д -> 2 -> 10 П -> 3 -> 11 А -> 4 -> 100

Теперь закодируем последовательность букв из слова ВОДОПАД:

010010001110010

Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:

010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2

Результат: 22162

Решение ЕГЭ данного задания по информатике, видео:

Рассмотрим еще разбор 5 задания ЕГЭ:

ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице:

a	b	c	d	e
000	110	01	001	10

Какой набор букв закодирован двоичной строкой 1100000100110 ?

✍ Решение:

Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.

✎ 1 вариант решения:

Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:

110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ b a c d e

Результат: b a c d e.

✎ 2 вариант решения:

110 000 01 001 10

Результат: b a c d e.

Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Решим следующее 5 задание:

ЕГЭ 5.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4 , и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23 , то получим последовательность 0010100110).

Определите, какое число передавалось по каналу в виде 01100010100100100110 .

✍ Решение:

Рассмотрим пример из условия задачи:

Было 23 10 Стало 0010100110 2

Где сами цифры исходного числа (выделим их красным цветом):

0010 10011 0 (0010 - 2, 0011 - 3)

Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011 , значит — четное).

Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:

разбиваем по 5:

01100 01010 01001 00110

отбрасываем из каждой группы последний символ:

0110 0101 0100 0011

Результат переводим в десятичную систему:

0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3

Ответ: 6 5 4 3

Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

ЕГЭ 5.4:
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0 , для буквы К - кодовое слово 10 .

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

✍ Решение:

✎ 1 вариант решения основан на логических умозаключениях:

Найдём самые короткие возможные кодовые слова для всех букв.
Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н ).
Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11 . Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111 . Условие Фано соблюдается.

(Н)1 + (К)2 + (Л)3 + (М)3 = 9

✎ 2 вариант решения :

(Н) -> 0 -> 1 символ (К) -> 10 -> 2 символа (Л) -> 110 -> 3 символа (М) -> 111 -> 3 символа

Суммарная длина всех четырёх кодовых слов равна:

(Н)1 + (К)2 + (Л)3 + (М)3 = 9

Ответ: 9

ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова: А: 101010 , Б: 011011 , В: 01000 .

Г, при котором код будет допускать однозначное декодирование. наименьшим числовым значением.

✍ Решение:

Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010 , Б начинается с нуля — 011011 ).
Следующим наименьшим кодом было бы двухбуквенное слово 00 . Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00 .

Результат: 00

ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 16 (под редакцией Крылова С.С., Чуркиной Т.Е.):

Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 17 (Крылов С.С., Чуркина Т.Е.):

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код: А — 0 , Б — 111 , В — 11001 , Г — 11000 , Д — 10 .

Укажите, каким кодовым словом должна быть закодирована буква Е. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

1 - не подходит (все буквы кроме А начинаются с 1) 10 - не подходит (соответствует коду Д) 11 - не подходит (начало кодов Б, В и Г) 100 - не подходит (код Д - 10 - является началом данного кода) 101 - не подходит (код Д - 10 - является началом данного кода) 110 - не подходит (начало кода В и Г) 111 - не подходит (соответствует коду Б) 1000 - не подходит (код Д - 10 - является началом данного кода) 1001 - не подходит (код Д - 10 - является началом данного кода) 1010 - не подходит (код Д - 10 - является началом данного кода) 1011 - не подходит (код Д - 10 - является началом данного кода) 1100 - не подходит (начало кода В и Г) 1101 - подходит

Результат: 1101

Более подробное решение данного задания представлено в видеоуроке:

5 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Укажите кратчайшее кодовое слово для буквы Б , при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

Результат: 1100

Подробное решение данного 5 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

Задание 5_9. Типовые экзаменационные варианты 2017. Вариант 4 (Крылов С.С., Чуркина Т.Е.):

По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А , Б , В используются кодовые слова:

А: 00011 Б: 111 В: 1010

Укажите кратчайшее кодовое слово для буквы Г , при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

✍ Решение:

Результат: 00

Задание 5_10. Тренировочный вариант №3 от 01.10.2018 (ФИПИ):

По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р ; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

Е – 000 Д – 10 К – 111

Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР .
В ответе напишите число – количество бит.

✍ Решение:

Д Е Д М А К А Р 10 000 10 001 01 111 01 110

Посчитаем количество цифр в итоговом коде и получим 20 .

Результат: 20

Смотрите виде решения задания:

Методические материалы для подготовки к ЕГЭ по информатике по теме «Информация и ее кодирование»

Кодирование информации – одна из базовых тем курса информатики и ИКТ, отражающая фундаментальную необходимость представления информации в какой-либо форме.

Тема «Информация и её кодирование» очень значима в ЕГЭ по информатике. Проверке знаний и умений по разделу «Информация и её кодирование» содержания курса информатики посвящены задания: №1, № 16 (системы счисления), № 9, № 13 (оценка количественных характеристик информации), № 5 (однозначность двоичного кода) и № 10 (комбинаторика) из которых пять базового, и одно (№ 13) – повышенного уровня сложности.

Базовые понятия:

Информация - это сведения об объектах и явлениях окружающей среды, их свойствах, уменьшающие неопределенность и/или неполноту знаний.

Бит (Binary digIT) - это единица измерения количества информации, равная количеству информации, содержащемуся в опыте, имеющем два равновероятных исхода.

Кодирование информации - это процесс однозначного преобразования информации с одного языка на другой. Однозначный процесс, значит имеющий правило/систему правил для обратного преобразования информации в первоначальный вид. Неоднозначный процесс, значит не позволяющий вернуться к первоначальному виду информации, искажающий ее.

Декодирование информации - это процесс преобразования информации обратный кодированию.

Равномерное кодирование - это кодирование, при котором все символы кодируются кодами равной длины.

Неравномерное кодирование - это кодирование, при котором разные символы могут кодироваться кодами разной длины.

Алфавит - это совокупность всех различных символов, которая используется для записи сообщения.

Глубина кодирования цвета - это количество бит, необходимых для хранения и представления цвета при кодировании одного пикселя растровой графики.

Базовые формулы:

N = 2 i , где N - это количество различных символов в алфавите, i - это минимальное количество информации (бит), которое требуется для кодирования одного символа в алфавите.

I = K · i, где I - это информационный объем сообщения в битах (байтах, Кбайтах…),

K - это количество символов в сообщении (для текстового сообщения К - это количество всех знаков в сообщении; для графического изображения: К - это количество пикселей в растровом изображении; для звукового файла: в формуле есть дополнительные множители, подробнее в других уроках),

i - это количество бит на кодирование одного символа (в терминологии кодирования графической информации i - глубина кодирования цвета).

Необходимо четко знать:

- значения степеней числа 2;

- правила перевода из различных систем счисления в десятичную и обратно;

- единицы измерения информации

1 байт = 2 3 бит

1 Кбайт = 2 10 байт = 2 13 бит

1Мбайт = 2 10 Кбайт = 2 20 байт = 2 23 бит

1Гбайт = 2 10 Мбайт = 2 20 Кбайт = 2 30 байт = 2 33 бит

Поскольку на экзамене по информатике нельзя пользоваться калькулятором, то учимся вычислять выражения со степенями 2, не прибегая к сложным вычислениям с длинными числами.

Задание. Вычислим, сколько бит содержится в МБайт:

Решение.

1-ый способ:

Любую арифметическую операцию умножения или деления всегда надо проверять. Здесь работаем с большими числами, высока вероятность ошибки.

2-ой способ (более простой):

Во втором способе решения мы только складываем и вычитаем значения степеней 2. Применяем основные формулы для преобразования степеней, которые будут полезны при решении многих заданий ЕГЭ.

При подготовке учащихся к ЕГЭ все задания по теме «Информация и кодирование» целесообразно разбить на 3 блока (на каждый блок отводим одно занятие):

I – системы счисления;

II – равномерное и неравномерное кодирование, правило Фано и комбинаторика;

III – расчет объема текстовой, графической и звуковой информации, скорости передачи данных.

Рассмотрим первый блок заданий ЕГЭ– позиционные системы счисления.

Считаю, что почти все задания ЕГЭ по информатике из года в год имеют тенденцию к усложнению. Это касается и раздела системы счисления. Сравним оба задания этого блока из демоверсий 2016 и 2017 г.

2016: Сколько единиц в двоичной записи шестнадцатеричного числа E1A0 16 ?

2017: Сколько существует натуральных чисел x, для которых выполнено неравенство 11011100 2 16 ? В ответе укажите только количество чисел, сами числа писать не нужно.

Это задание наверно не случайно находится в КИМ-ах на первом месте, так как является наиболее простым. Для решения задания достаточно перевести число из шестнадцатиричной системы в двоичную, заменив каждую цифру ее двоичным 4-х битным представлением (метод быстрого перевода чисел из двоичной системы в шестнадцатеричную ). В 2017 году проверяется также умение сравнивать числа в 2-ичной или 16-тиричной системах.

Более сложным является задание 16.

2016: Сколько единиц содержится в двоичной записи значения выражения: 4 2013 + 2 2012 – 16?

2017: Значение арифметического выражения: 9 18 + 3 54 – 9 – записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Рассмотрим на примерах, как решаются подобные задачи.

Пример1.

Пример 2.

Десятичное число 57 в некоторой системе счисления записывается как 212. Определите основание системы счисления

Решение:

57=2*х 2 +1*х 1 +2*х 0

Решая квадратное уравнение 2х 2 +х-55 =0 получаем х=5.

____________________________________________________________________

Пример 3.

Для решения используем правила перевода в различные системы счисления чисел, равных основанию системы в n -ой степени:

Вернемся к решению примера 3:

Ответ: 4400.

Пример 4.

Пример 5.

Следующий тип задач – это расшифровка сообщений, закодированных с помощью неравномерного двоичного кода, удовлетворяющего условию Фано. К такому типу относится задание №5.

2016: По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 0; Б – 110; В – 100.

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

2017: Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение данного типа задач не требует глубоких знаний и формул, а сводится к построению «битового» дерева, наглядно демонстрирующего различные двоичные цепочки для кодировки букв из сообщения.

Рассмотрим это на примерах.

Пример 1. (К. Поляков)

Решение:

В соответствии с условием Фано, код буквы С не может начинаться на 0. На построенной схеме видно, что существует два варианта ответа: 101 и 110. Исходя из условия задачи выбираем код с наименьшим числовым значением: 101.

Пример 2. (К. Поляков)

Решение.

По условию Фано и на схеме показано, что искомые коды согласных букв не могут начинаться на 1, на 01 и на 001.

Они могут начинаться только с 000. Трехбитный код 000 возможен только для одной буквы, четырехбитный – для двух вариантов букв (0000 и 0001), пятибитный –для четырех букв, а по условию их пять. Значит ответ – 6 бит.

Пример 3.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110.

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Решение.

Построим дерево для заданных кодовых слов А – 0 и Б – 110:

Штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для кодовых слов букв В (10) и Г (111). Получаем суммарную длину кодовых слов

9 символов.

Пример 4.

Решим задание № 5 из демоверсии 2016г.

Решение.

Построив дерево, получаем два варианта ответа, из которых выбираем наименьшее значение кода для буквы Г. Это - 101.

Пример 5.

А – 0; Б – 100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны.

Решение.

Изобразим на дереве цепочки с кодами букв последовательности из условия задачи:

А – 0; Б – 100; В – 1010; Г – 111; Д – 110.

По полученному рисунку делаем вывод, что код буквы В может быть сокращен с четырехбитного варианта, до трехбитового, а именно вместо 1010 можно использовать цепочку битов 101.

Разобрав данные примеры учащиеся уже самостоятельно легко справляются с решением аналогичных задач из открытого банка заданий различных образовательных ресурсов.

Задание № 10 предполагает проверку знаний теоретического материала и умений решать задачи из комбинаторики.

Теория:

Рассмотрим несколько примеров.

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

Решение:

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

В нашем случае N = 5, M = 3. Следовательно, Q = 3 5 = 243.

Ответ : 243

Пример 2.

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

Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение:

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

Ответ: 405.

Пример 3.

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

Решение:

Рассмотрим различные варианты слов из 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.

Пример 4.

Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

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

Решение:

Самый простой вариант решения этой задачи – использование систем счисления; Действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв).

Выполним замену К0, Л1, Р2, Т3; поскольку нумерация слов начинается с единицы, а первое число КККК0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 1002 4

Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.

Ответ: ЛККР.

Последний блок заданий посвящен проверке умений производить количественную оценку информации различного типа.

Задание № 9 из КИМов ЕГЭ проверяет знание способов кодирования растровых изображений и алгоритма нахождения объема графического файла. Решение такого вида заданий не вызывают затруднений у выпускников и достаточно хорошо отработаны ими в процессе обучения в курсе основной школы.

2016: Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 320×640 пикселей при условии, что в изображении могут использоваться 256 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно.

Решение .

По условию К=320*640 пикселей, N =256, значит глубина цвета по формуле Хартли i =8 (т.к. 2 8 =256). Тогда объем файла I =K *I , I = 320*640*8 бит =2 5 *10*2 6 *10*2 3 бит. Переводим в Кбайты и получаем: 100*2 14 /2 13 =50 Кбайт.

Ответ: 50 Кбайт.

2017: Для хранения произвольного растрового изображения размером 1024×1024 пикселей отведено 512 Кбайт памяти, при этом для каждого пикселя хранится двоичное число – код цвета этого пикселя. Для каждого пикселя для хранения кода выделено одинаковое количество бит. Сжатие данных не производится. Какое максимальное количество цветов можно использовать в изображении?

Решение.

По условию К= 2 10 *2 10 пикселей, I =512 Кбайт или 2 9 *2 13 бит. Тогда глубина цвета i =I /K =2 22 /2 20 =2 2 =4 бит. Следовательно, по формуле Хартли получаем N =24=16 цветов.

Ответ: 16 цветов.

В задания КИМов ЕГЭ последних лет не включены задания на определение объема звукового файла и скорости передачи данных по сети. Вероятно, из-за простоты их решения, эти задачи содержатся в ОГЭ для выпускников 9 класса.

Задание № 13 считается заданием повышенного уровня сложности. Решается с использованием алфавитного подхода к измерению количества информации.

Данные задачи также неплохо представлены в школьном курсе обучения информатике, но в более простом варианте, как например в задаче из демоверсий прошлых лет:

Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля - ровно 11 символов. В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и заглавные (регистр буквы имеет значение!).

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

Определите объём памяти, который занимает хранение 60 паролей.

Решение.

1. Определяется мощность используемого алфавита: 10 цифр и 12 букв, каждая из которых может иметь два возможных начертания. Итого 10+12*2=34 знака.

2. Определяется целое количество битов, минимально достаточное для представления одного знака такого алфавита. Поэтому выбирается ближайшее большее число N , равное степени числа 2. В нашем случае это 2 6 =64 (значения 2 5 =32 недостаточно). Значит i =6 бит на один знак алфавита.

3. Длина пароля равна11 символам (К=11). Тогда объем одного пароля I =К*i =11*6=66 битов.

4. Под хранение каждого пароля отводится минимальное целое количество байтов. Значит 66:8=8,259 байтов.

5. Тогда под хранение 60 паролей потребуется 60*9=540 байтов.

Ответ : 540 байтов.

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

2016: При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 9 символов и содержащий только символы из 26-символьного набора прописных латинских букв. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 400 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Решение.

После нахождения мощности алфавита (N =9+26=35 знака), целого количества бит для каждого символа (i =6 бит, т.к.2 6 =64) и длины каждого пароля в байтах (9*6=54 бита или 7 байт), рассчитываем целое количество байт, отводимое для хранения пароля и дополнительных сведений о каждом пользователе: I 1 =400/20=20 байт. Оставшиеся 20-7=13 байт отводятся под хранение дополнительных сведений о каждом пользователе.

Ответ: 13 байт.

2017: При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 9 символов. Из соображений информационной безопасности каждый пароль должен содержать хотя бы 1 десятичную цифру, как прописные, так и строчные латинские буквы, а также не менее 1 символа из 6-символьного набора: «&», «#», «$», «*», «!», «@». В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 500 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Примечание. В латинском алфавите 26 букв.

(Ответ: 17 байт).

Банк заданий для данного блока довольно обширен (см. список ЭОР)

Умение решать задачи по информатике и ИКТ является важным критерием сформированности мыслительных способностей учащихся. Раздел «Информация и её кодирование», при правильной организации учебного процесса позволяет сформировать

у учащихся глубокие навыки решения заданий ЕГЭ по информатике.

Используемые материалы и ЭОР:

Методические рекомендации на сайте Полякова К. Ю. http ://kpolyakov .spb .ru (ПОЛЯКОВ Константин Юрьевич, д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург, [email protected]).

Лещинер В.Р. ЕГЭ 2015. Информатика. Типовые тестовые задания. - М.: Экзамен, 2015.

Крылов С.С., Чуркина Т.Е. ЕГЭ 2015. Информатика и ИКТ. Типовые экзаменационные варианты. - М.: «Национальное образование», 2015.

www .fipi .ru – официалный сайт Федерльного института педгогических исследований

http://ege-go.ru М.А. Ройтберг [email protected]

http://infbu.ru/catalog/1013 - БУ информатик

http://pandia.ru/text/78/122/98265.php

http://down.ctege.info/ege/obshee/inform/praktika/inform-a1-praktika.pdf

http://easyinformatics.ru/

Кодирование символов

V=l*r ,

где l-длина сообщения (количество символов),
r-разрешение.

Разрешение-количество бит, выделенное на кодирование одного символа.

Кодировка Unicod: 1 символ кодируется 2 байтами или 16 битами.Закодированный символ представляется в виде в 16-чном коде с приставкой "U+". Например, код буквы "я" такой: U+044F

Кодировка КОИ-8: 1 символ кодируется 1 байтом или 8 битами.

Кодирование звука

Звук-это колебания воздуха. Аналоговый сигнал-это звук, преобразованный в колебания электрического тока. При кодировании звука аналоговый сигнал преобразуется в оцифрованный сигнал с помощью дискретизации. Непрерывный сигнал преобразуется в набор дискретных значений, каждое из которых представляется двоичным числом. На рисуне показано, как происходит кодирование звука.

Частота дискретизации-количество измерений амплитуды А аналогового сигнала в единицу времени.
Разрешение-сколько бит выделяется на кодирование значений амплитуды.
Чем больше частота дискретизации (меньше шаг дискретизации) и больше разрешение, тем качественнее будет аудиозапись.

V=υ*r*t*a ,

где υ-частота дискретизации,
r-разрешение,
t-время,
a-коэффициент (для монозвука а=1, для стерео а=2).

Кодирование цвета

Как закодировать цвет

Модель RGB (red-green-blue, красный-зеленый-синий)

Различные цвета получаются смешиванием этих 3-х основных цветов. Чтобы определить,какие цвета нужно смешать для получения искомого цвета сделаем следующее:

1)нарисуем радугу в виде колеса, используя такое предложение:

" К аждый О хотник Ж елает З нать Г де С идит Ф азан".

Первые буквы в словах обозначают цвета. К-красный, О-оранжевый, Ж-желтый, З-зеленый, Г-голубой, С-синий, Ф-фиолетовый.

2)выделим из представленных цветов основные красный, зеленый и синий. На рисунке видно, что между красным и зеленым расположены цвета оранжевый и желтый. Их можно получить смешиванием красного и зеленого, а синий цвет должен отсутствовать. Между зеленым и синим расположен голубой. Чтобы получить голубой цвет, нужно смешать синий и зеленый, а красный должен отсутствовать. Между синим и красным цветом расположен фиолетовый. Чтобы получить фиолетовый цвет, нужно смешать синий и красный, зеленый должен отсутствовать. Если смешать все три цвета красный, зеленый и синий, то получим белый цвет. Черный цвет получаем, когда нет ни одного цвета.

В данной модели для кодирования цвета выделено 3 байта, по 1 байту на каждый из трех основных цветов. Поэтому интенсивность цвета может принимать значение от 0 до 255 (2 8 =256 комбинаций). Для примера, пусть цвета нужны яркие, интенсивность максимальна(255). В таблице опишем как будут закодированы цвета:

Искомый цвет	10-чный код	16-чный код
красный	(255,0,0)	FF0000
зеленый	(0,255,0)	00FF00
синий	(0,0,255)	0000FF
желтый,оранжевый	(255,255,0)	FFFF00
голубой	(0,255,255)	00FFFF
фиолетовый	(255,0,255)	FF00FF
белый	(255,255,255)	FFFFFF
черный	(0,0,0)	000000
серый	(128,128,128)	808080

Серый цвет-переход от черного к белому. Три основных цвета имеют одинаковую интенсивность. Если нам нужен темно-серый цвет, то нужно уменьшмить интенсивность основных цветов, т.е сдвинуться к черному. Например, 10-чный код такой:(64,64,64). Если нужен светло-серый, значит, будем двигаться в сторону белого, т.е. увеличим интенсивность базовых цветов: (192,192,192).

Кодирование изображений

Объем изображения

Объем изображения определяется по формуле:

V=S*r ,

где S-площадь изображения,
r-разрешение.

Разрешение-сколько бит выделено на кодирование цветов.

В модели RGB r=3 байта.

Разбор задачи A1 (демо ЕГЭ 2009)

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

Решение:

Объем сообщения определяется по формуле:

V=l*r,

где l-длина сообщения, r-разрешение.

V 1 =l*r 1 ; V 2 =l*r 2 ;

V 1 -V 2 =l*r 1 -l*r 2 =l(r 1 -r 2 ); l=(V 1 -V 2 )\(r 1 -r 2 );

l=480\(16-8)=480\8= 60 символов .

Разбор задачи A2 (демо ЕГЭ 2009)

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

70 бит
70 байт
490 бит
119 байт

Решение:

Необходимо закодивовать: 119 символов

Для кодирования номера 1 велосипедиста необходимо 7 бит, т.к. 64 7 .

Для кодирования номеров 70 велосипедистов нужно: 7*70= 490 бит .

Разбор задачи A2 (демо ЕГЭ 2010)

Уровень сложности-повышенный

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

240 байт
300 байт
360 байт
420 байт

Решение:

Необходимо закодивовать: 10 цифр (от 0 до 9)+18 букв=28 символов.

Для кодирования необходимо 5 бит, т.к. 16 5 .

40\8=5 байт-отводится на 1 автомобильный номер.

Для кодирования 60 номеров нужно: 5*60= 300 байт .

Разбор задачи A2 (демо ЕГЭ 2011)

Время выполнения-1 мин, уровень сложности-базовый

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

320 бит
20 бит
160 байт
20 байт

Решение:

V=l*r,

V 1 =l*r 1 =20*16=320 бит.

V 2 =l*r 2 =20*8=160 бит.

V 1 -V 2 =320-160=160 бит=160\8= 20 байт .

Разбор задачи A5 (демо ЕГЭ 2011)

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ГБВАВГ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричную систему счисления. Какой вид будет иметь это сообщение?

71013
DBCACD
7A13
31A7

Решение:

ГБВАВГ закодируется так: 011 11 010 00 010 011 2 =0111 1010 0001 0011 2 = 7A13 16 .

Разбор задачи A8 (демо ЕГЭ 2013)

Производится одноканальная (моно) цифровая звукозапись. Значение сигнала фиксируется 48 000 раз в секунду, для записи каждого значения используется 32 бит. Запись длится 4 минуты, её результаты записываются в файл, сжатия данных не производится. Какая из приведённых ниже величин наиболее близка к размеру полученного файла?

44 Мбайт
87 Мбайт
125 Мбайт
175 Мбайт

Решение:

Объем звукозаписи (размер аудиофайла) определяют по формуле:

V=υ*r*t*a,

υ=48 000 Гц=48*10 3 Гц

r=32 бита=32\8=4 байта

t=4 мин=4*60=240 сек

a=1-для монозвука

V= 48*10 3 *4* 240 *1= 3*16*(5*2) 3 *4* 3*8*5*2 = 3*2 4 *5 3 *2 3 *2 2 * 3*2 3 *5*2 =3 2 *5 4 *2 13 =9*625*2 13 =5625*2 13 байт

Выбазим в мегабайтах:

1 мегабайт=2 20

2 13 *5625\2 20 =5625\2 7 =5625\128=43,95≈ 44 мегабайта .

Разбор задачи A8 (демо ЕГЭ 2012)

Время выполнения-2 мин, уровень сложности-базовый

Производится одноканальная (моно) звукозапись с частотой дискретизации 16 кГц и 24-битным разрешением. Запись длится 1 минуту, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?

Решение:

Объем звукозаписи (размер аудиофайла) определяют по формуле:

V=υ*r*t*a,

где υ-частота дискретизации, r-разрешение, t-время, a-коэффициент.

υ=16 кГц=16*10 3 Гц

r=24 бита=24\8=3 байта

t=1 мин=60 сек

a=1-для монозвука

V=16*10 3 *3*60*1=16*10 3 *3*6*10 1 =16*18*10 4 =2 4 *2 1 *9*(2*5) 4 =2 9 *9*5 4 =2 9 *5625 байт

Выбазим в мегабайтах:

1 мегабайт=2 20

2 9 *5625\2 20 =5625\2048=2,7≈ 3 мегабайта .

Разбор задачи A9 (демо ЕГЭ 2013)

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

для буквы Д – 11
это невозможно
для буквы Г – 10
для буквы Д – 10

Решение:

Построим графы, образующие используемые коды:

На графе видно, что для букв А, Б, В и Г сократить длину кода нельзя.

Возьмем, к примеру, букву А. Ее код - 00. Сократим на 1 разряд и получим 0 (идем вверх от кода 00 по ветке графа). Тогда буква Б не сможет использоваться. Код буквы Б, 0 1 , будет раскодирован как буква А , и останется нераскодированный код 1 .

Поэтому сократить длину кода можно только для буквы Д. Идем вверх от кода 110 по ветке графа и получаем код 11.

Получили, буква Д с кодом 11 .

Разбор задачи A9 (демо ЕГЭ 2012)

Время выполнения-2 мин, уровень сложности-базовый

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

Решение:

При однозначном декодировании в коде одного символа не должно быть дублирования(повторения) части кода другого символа. Т.к. длина кода должна быть наименьшей, то начнем с длины кода =1.

Возможные коды: 0, 1.

"0"-не подходит, т.к. он является частью кода букв: Б,В,Г

"1"-не подходит,т.к. таким кодом закодирована буква А

Возьмем длину кода =2.

Возможные коды: 00,01,10,11

"00"- не подходит, т.к. он является частью кода букв: Б,В

"01"- не подходит, т.к. он является частью кода буквы Г

"10" и "11"- не подходят, т.к. он начинается с "1", а этим кодом закодирована буква А

Возьмем длину кода =3.

Возможные коды: 000,001,010,011,100,101,110,111.

Сразу отбросим коды,которые начинаются с "1",т.к. этим кодом закодирована буква А.

"000"- не подходит, т.к. таким кодом закодирована буква Б

"001"- не подходит, т.к. таким кодом закодирована буква В

" 010 "- подходит, т.к. таким кодом ничего не закодировано

Разбор задачи A11 (демо ЕГЭ 2013)

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

100 байт
150 байт
200 байт
250 байт

Решение:

Необходимо закодивовать: 30 букв + 10 цифр (от 0 до 9) = 40 символов .

Для кодирования необходимо 6 бит , т.к. 3240 5 6 .

Для кодирования 1 автомобильного номера нужно: 6*5=30 бит.

30 нацело не делится на 8. А нам по условию дано, что 1 номер должен кодироваться целым количеством байтов. Поэтому округляем 30 до 32.

32\8=4 байта-отводится на 1 автомобильный номер.

Для кодирования 50 номеров нужно: 4*50= 200 байт .

Разбор задачи A11 (демо ЕГЭ 2010)

Уровень сложности-базовый

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное кодирование: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ВАГБГВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид.

AD34
43DA
101334
CADBCD

Решение:

ВАГБГВ закодируется так: 010 00 011 11 011 010 2 =0100 0011 1101 1010 2 = 43DA 16 .

Разбор задачи A11 (демо ЕГЭ 2009)

Время выполнения-1 мин, уровень сложности-базовый

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится

BACD
1023

Решение:

00-А, 01-Б, 10-В, 11-Г

БАВГ закодируется так: 01 00 10 11=01001011 2 .

Воспользуемся методом быстрого перевода чисел из двоичной системы в шестнадцатеричную :

0100 1011 2 = 4 B 16 .

Получили, 4B .

Разбор задачи A11 (демо ЕГЭ 2012)

Время выполнения-3 мин, уровень сложности-повышенный

Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 11 символов. В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и заглавные (регистр буквы имеет значение!). Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объём памяти, который занимает хранение 60 паролей.

540 байт
600 байт
660 байт
720 байт

Решение:

Необходимо закодивовать: 10 цифр(от 0 до 9)+24 буквы(12*2)=34 символа

Для кодирования необходимо 6 бит, т.к. 32 6 .

Для кодирования 1 пароля нужно: 6*11=66 бит.

66 нацело не делится на 8. А нам по условию дано,что 1 пароль должен кодироваться целым количеством байтов. Поэтому округдяем 66 до 72.

72\8=9 байт-отводится на 1 пароль

Для кодирования 60 паролей нужно: 9*60= 540 байт .

Разбор задачи A14 (демо ЕГЭ 2011)

Время выполнения-1 мин, уровень сложности-повышенный

Для кодирования цвета фона интернет-страницы используется атрибут bgcolor="#ХХХХХХ", где в кавычках задаются шестнадцатеричные значения интенсивности цветовых компонент в 24-битной RGB-модели следующим образом:

К какому цвету будет близок цвет страницы, заданный тэгом?

серый
белый
фиолетовый
черный

Решение:

Заданный код цвета:747474.

Код белого цвета: FFFFFF-присутствуют все три цвета: красный, зеленый, синий.

Код черного цвета: 000000-отсутствуют все три цвета.

#747474-код цвета между белым и черным. Поэтому искомый цвет: серый .

Разбор задачи A15 (демо ЕГЭ 2010)

Уровень сложности-повышенный

Для кодирования цвета фона web-страницы используется атрибут bgcolor="#ХХХХХХ", где в кавычках задаются шестнадцатеричные значения интенсивности цветовых компонент в 24-битной RGB-модели. Какой цвет будет у страницы, заданной тэгом?

белый
зеленый
красный
синий

Решение:

Заданный код цвета:00FF00.

RGB-red(красный),green(зеленый),blue(синий).

1-й байт-"00"-красный. Поэтому, красной составляющей в цвете нет.

3-й байт-"00"-синий. Поэтому, синей составляющей в цвете нет.

Получаем зеленый цвет .

Разбор задачи A15 (демо ЕГЭ 2009)

Время выполнения-2 мин, уровень сложности-повышенный

Для кодирования цвета фона страницы Интернет используется атрибут bgcolor="#ХХХХХХ", где в кавычках задаются шестнадцатеричные значения интенсивности цветовых компонент в 24-битной RGB-модели. Какой цвет будет у страницы, заданной тэгом?

белый
зеленый
красный
синий

Решение:

Заданный код цвета:FFFFFF.

RGB-red(красный),green(зеленый),blue(синий).

1-й байт-"FF"-красный. Поэтому, есть красный цвет.

2-й байт-"FF"-зеленый. Поэтому,есть зеленый цвет.

1-й байт-"FF"-синий. Поэтому, есть синий цвет.

При смешивании красного, зеленого и синего цвета получаем белый цвет .

Разбор задачи A16 (демо ЕГЭ 2011)

Время выполнения-3 мин, уровень сложности-повышенный

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

350 байт
300 байт
250 байт
200 байт

Решение:

Необходимо закодивовать: 10 цифр(от 0 до 9)+22 буквы=32 символа

Для кодирования необходимо 5 бит, т.к. 32=2 5 .

Для кодирования 1 автомобильного знака нужно: 5*7=35 бит.

35 нацело не делится на 8. А нам по условию дано,что 1 автомобильный номер должен кодироваться целым количеством байтов. Поэтому округляем 35 до 40.

40\8=5 байт-отводится на 1 автомобильный номер

Для кодирования 50 номеров нужно: 5*50= 250 байт .

Разбор задачи B1 (демо ЕГЭ 2012)

Время выполнения-1 мин, уровень сложности-базовый

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

Ответ: 160

Решение:

Объем сообщения (длина в сообщения в битах) определяется по формуле:

V=l*r,

где l-длина сообщения (количество символов),

r-разрешение (бит на 1 символ).

V 1 =l*r 1 =20*2*8=320 бит.

V 2 =l*r 2 =20*8=160 бит.

V 1 -V 2 =320-160= 160 бит .

Разбор задачи B1 (демо ЕГЭ 2011)

Время выполнения-1 мин, уровень сложности-базовый

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

Ответ: 81

Решение:

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

N=X y ,

где X - количество видов флагов,
y - количество флагов.

3 вида флагов, поэтому Х=3

Используется 4 флага, поэтому y=4.

N=3 4 = 81 .

Разбор задачи B1 (демо ЕГЭ 2010)

Уровень сложности-базовый

Некоторое сигнальное устройство за одну секунду передает один из трех сигналов. Сколько различных сообщений длиной в четыре секунды можно передать при помощи этого устройства?

Ответ: 81

Решение:

Количество различных сообщений определяется по формуле:

N=X y .

где X - количество видов сигнала,
y - количество сигналов.

3 вида сигналов, поэтому Х=3

Длина сообщения 4 секунды, поэтому y=4.

N=3 4 = 81 .

Разбор задачи B1 (демо ЕГЭ 2009)

Время выполнения-1 мин, уровень сложности-базовый

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

Ответ: 3

Решение:

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

N=X y ,

где X - количеств состояний лампочки,

y - количество лампочек.

Отсюда y=logxN.

N=18.

3 состояния лампочки: «включено», «выключено» или «мигает», поэтому Х=3.

y=log 3 18=2,63. Округляем до 3 лампочек .

Или по-другому:

18=3 y . 3 2 3 . 9 3 лампочки .

Разбор задачи B4 (демо ЕГЭ 2013)

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

Ответ: 48

Решение:

Количество различных комбинаций из "точек" и "тире" определяется по формуле:

N=X y ,

где X - количество вариантов символов,

y - длина последовательности сигналов.

2 варианта символов: «точка» и «тире» (Х=2).

Длина последовательности 1 - 4 сигнала (y 1 =4).

Длина последовательности 2 - 5 сигналов (y 2 =5).

N 1 =X y 1 =2 4 =16 комбинаций.

N 2 =X y 2 =2 5 =32 комбинации.

N=N 1 +N 2 =16+32=48 комбинаций из "точек" и "тире", т.е. могут быть закодированы 48 различных символов .

не менее четырёх и не более пяти сигналов (точек и тире)?

Решение.

Мы имеем алфавит из двух букв: точка и тире. Из двух букв можно составить 2 4 четырёхбуквенных слова и 2 5 пятибуквенных слов.

Соответственно, количество закодированных символов будет равно количеству различных слов, а их 16 + 32 = 48.

Ответ: 48

Источник: Демонстрационная версия ЕГЭ-2013 по информатике.

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

Решение.

В этой задаче мы можем использовать не менее 3 и не более 4 сигналов, это значит, что количество различных символов N = 2 4 +2 3 = 24.

Правильный ответ: 24.

Ответ: 24

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

Решение.

Информация, получаемая из одного символа азбуки Морзе, равна одному биту, так как символов всего два. Если символов два, то для того, чтобы вычислить количество возможных комбинаций этих символов на n позициях, нужно возвести 2 в степень n.

В этой задаче мы можем использовать не менее 2 и не более 4 сигналов, это значит, что количество различных символов N = 2 4 + 2 3 + 2 2 = 28.

Правильный ответ: 28.

Ответ: 28

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

Решение.

M=2 (точкa и тире), "не менее двух и не более пяти сигналов" означает, что нужно определить количество всех 5-ти, 4-х, 3-х и 2-х буквенных слов в двоичном алфавите.

Ответ: 60

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

Решение.

Из двух символов алфавита (точка и тире) можно составить 2 5 пятибуквенных слов, 2 4 четырехбуквенных слова, 2 3 трехбуквенных слова, 2 2 слов, состоящих из двух букв, и 2 1 отдельных символов. Поэтому количество закодированных символов равно 32 + 16 + 8 + 4 + 2 = 62.

Ответ: 62

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

Решение.

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

Ответ: 48

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

Решение.

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

Нужно определить количество всех трёх-, четырех- и пятибуквенных слов в двоичном алфавите:

Дублирует задание 4988.

Ответ: 56

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

Решение.

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

Нужно определить количество всех пяти-, четырех- и трехбуквенных слов в двоичном алфавите:

Ответ: 56

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

Решение.

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

В данном случае M = 2 (точкa и тире), «пять или шесть сигналов» означает, что нужно определить количество всех пяти- и шестибуквенных слов в двоичном алфавите:

2 5 +2 6 = 32 + 64 = 96.

Ответ: 96

Решение.

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

В данном случае M = 2 (точкa и тире), "не менее четырёх и не более шести" означает, что нужно определить количество всех четырёх, пяти- и шестибуквенных буквенных слов в двоичном алфавите:

2 4 + 2 5 + 2 6 = 16 + 32 + 64 = 112.

Ответ: 112.

Ответ: 112

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

Решение.

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