Кодирование и декодирование информации. ЕГЭ

Урок посвящен тому, как решать 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 (под редакцией Крылова С.С., Чуркиной Т.Е.):

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код: А — 01 , Б — 00 , В — 11 , Г — 100 .

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

✍ Решение:

Результат: 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

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

Подготовка к ЕГЭ.

Информация и её кодирование. Разбор заданий А9, А11.

Доброго времени суток, ученики!

Приглашаю вас к онлайн-уроку по подготовке к ЕГЭ по информатике. Структура урока логична и последовательна. Опираясь на базовые понятия и формулы темы урока, мы приступаем к анализу решения задач, а затем самостоятельному выполнению стандартных и нестандартных задач. Каждый урок будет содержать избыточную информацию, которая в текущем занятии может и не использоваться явно, но важна для последующих.

Сценарий работы:

1. База . Введение базовых понятий и формул

2. На зубок . Сквозная рубрика. Ее материал рекомендован для автоматического безошибочного воспроизведения среди ночи.

3. Из теории . Дополнительный материал из смежных тем других дисциплин в рамках темы занятия.

4. Выполни самостоятельно . Задания для отработки материала из пунктов 1­­ – 3.

5. Разбор заданий . Разбираем разные способы решения заданий ЕГЭ из демонстрационных КИМов прошлых лет и реальных ЕГЭ. Делаем микро выводы (сквозная рубрика NB! ).

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

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

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

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

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

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

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

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

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

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

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

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

На зубок:

i

N=2i

NB ! (Nota Bene, от лат. «обрати внимание»)

1 байт = 23 бит

1 Кбайт = 210байт = 213бит

1Мбайт = 210Кбайт = 220байт = 223бит

1Гбайт = 210Мбайт = 220Кбайт = 230байт = 233бит

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

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

Решение.

1-ый способ (сложный категорически):

https://pandia.ru/text/78/122/images/image003_19.png" width="589" height="184 src=">

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

Из алгебры:

https://pandia.ru/text/78/122/images/image005_15.png" width="91 height=41" height="41">? В ответе укажи степень числа 2.

2) Сколько Мбайт содержится в 4096 байтах? В ответе укажи степень числа 2.

Разбор заданий А9.

Базовый уровень.

Максимальный балл - 1.

Что проверяет задание: Процесс передачи информации, источник и приемник информации. Сигнал, кодирование и декодирование. Искажение информации.

Задание . КИМы по ЕГЭ-2012.

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

Решение .

1. Код символов неравномерный. Но декодирование сообщения должно быть однозначным.

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

· Д - 00. Тогда, например, сообщение ДА (кодможет быть декодировано как символ В (код 001). НЕВЕРНО.

· Д - 01. Тогда, например, сообщение ДА (кодможет быть декодировано как символ г (код 011). НЕВЕРНО.

· Д - 11. Тогда, например, сообщение ДА (кодможет быть декодировано как ААА (код 1) или АД (код 1 и 11). НЕВЕРНО.

ü Д - 010. Единственно верный вариант. Любая последовательность символов приписанная перед или после символа Д будет однозначна декодирована.

NB ! При декодировании неравномерного кода обязательно рассматривайте все возможные варианты.

Задание . Источник КИМы по ЕГЭ-2011.

Для передачи по каналу связи сообщения, состоящего только из символов A, B, C и D, используется неравномерный (по длине) код: А-01, В-1, С-001. Каким кодовым словом нужно закодировать символ D, чтобы длина его была минимальной, а код при этом допускал однозначное разбиение кодированного сообщения на символы.

Решение .

1. Код символов неравномерный. Но декодирование сообщения должно быть однозначным. В отличие от предыдущей задачи здесь стоит условие - длина кода должна быть минимальной . Поэтому при переборе вариантов не останавливаться на первом коде, приводящем к однозначному декодированию. Другой код может выполнять это же условие и быть меньшим по длине.

2. Проанализируем варианты кодов для символа D и выберем тот, при котором сообщение будет однозначно декодирован, а длина кода будет минимальной .

· Очевидно, что код символа должен начинаться с 0, в противном случае будет сообщение будет неоднозначно декодировано. Например, пусть D-101. Тогда сообщение из одного символа D (101) может быть декодировано как сообщение ВАИли пусть D-11. Тогда сообщение из одного символа D (11) может быть декодировано как сообщение ВВ

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

ü D - 000.

3. Мы использовали условие Фано . Его формулировка: для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.

NB ! При решении задач обращайте внимание на все условия задания. В этом задании есть риск того, что анализ может быть проведен неверно, поэтому рекомендовано перебрать все варианты, как способ перепроверки выбранного решения.

Задание . Источник КИМы по ЕГЭ-2011.

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

Решение .

1. В отличие от предыдущих двух заданий здесь необходимо применить знаний по переводу чисел из двоичной системы счисления в шестнадцатеричную (в общем случае в систему счисления с основанием, кратным степени 2 (то есть в систему счисления с основанием q=2n, где n - натуральное число)).

2. Вместо символов сообщения записываем их коды. Получаем двоичный код сообщения:

ГБВАВГ: . Представим двоичный код в алфавите 16-ой сс.

1-ый способ перевода из 2сс в систему счисления с основанием 2 n (несравнимо удобный):

Алфавиту системы счисления с основанием 2n (это символы от 0 до 2n-1) ставится в соответствие уникальный двоичный код длиной в n символов.

На зубок:

4-ая сс (q =22)	2-ая сс	8-ая сс (q =23)	2-ая сс	16-ая сс (q =24)	2-ая сс

2-ой способ перевода из 2сс в систему счисления с основанием 2n (громоздкий и рискованный) :

1 этап. Перевод двоичного кода в 10 сс (используя развернутую формулу записи числа ):

На зубок:

DIV_ADBLOCK154">

4. Верный ответ 3.

Выполни самостоятельно.

Для кодирования букв А, Б, В, Г, Д, Е решили использовать следующий код: А - 101, Б - 1, В - 10, Г - 110, Д - 001, Е - 0. Если таким образом закодировать последовательность символов АЕЕВГДБЕ и записать результат в восьмеричной системе счисления, то получится:

3) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

4) Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код:

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

5) Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

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

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

Разбор заданий А11.

Повышенный уровень.

Максимальный балл - 1.

Что проверяет задание: Дискретное (цифровое) представление текстовой, графической, звуковой информации и видеоинформации. Единицы измерения количества информации.

Задание . КИМы по ЕГЭ-2012.

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

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

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

Решение .

Разворачиваем решение задачи с конца.

Iф - это информационный объем искомого файла.

I ф = I 1 пароля × K , где I1 пароля - информационный объем, требуемый для хранения 1 пароля, К - количество паролей (60).

I 1 пароля = i × L , i - количество бит для кодирования одного символа пароля, L - длина пароля (11).

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

Выполним все операции снизу вверх с учетом условий задания:

1. N = 10 + 12 + 12 = 34 символа (10 цифр, 12 строчных и 12 прописных букв)

2. i = log2N или N = 2i
i = log234 или 34 = 2i
5 бит < i < 6 бит
i = 6 бит.
Мы выполняем условие задачи: используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.

3. I1 пароля = 6 бит × 11 = 66 бит.
Обратимся к условию задачи: под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов. Округляем 66 бит до целого числа байт.
Тогда I1 пароля = 72 бит = 9 байт.

4. Iф = 9 байт × 60 = 540 байт.

NB! В данной задаче количество символов в алфавите некратно степени 2, и мы прибегали к округлению в сторону увеличения до целого числа бит.

Задание . Диагностическая работа по информатике от МИОО. 29 ноября 2010 года.

Программа генерирует N-символьные пароли следующим образом: в качестве символов используются цифры, а также строчные и прописные латинские буквы в любом порядке (в латинском алфавите 26 знаков). Все символы кодируются одним и тем же минимально возможным количеством бит и записываются на диск. Программа сгенерировала 128 паролей и записала их в файл подряд, без дополнительных символов. Размер полученного файла составил 1,5 Кбайта.

Какова длина пароля (N)?

Решение .

NB! Это и предыдущее задание отличаются тем, что искомое предыдущего задания есть данное текущего и наоборот.

1. M - это количество символов, которое можно использовать для составления пароля.
M = 10 + 26 + 26 = 56 символов (10 цифр, 26 строчных и прописных букв).
Обратимся к условию задачи: Все символы кодируются одним и тем же минимально возможным количеством бит и записываются на диск.
i = log2М или М = 2i
i = log256 или 56 = 2i, 7 бит < i < 8 бит
Так как «Все символы кодируются одним и тем же минимально возможным количеством бит», то i = 8 бит.

2. Iф = I1 пароля×K, где Iф - это информационный объем искомого файла (1,5 Кбайта), I1 пароля - информационный объем, требуемый для хранения 1 пароля, К - количество паролей (128).
I1 пароля = i × N, i - количество бит для кодирования одного символа пароля, N - длина пароля (неизвестное).
Iф = i × N × K
N =

NB! Обратите внимание на удобство расчетов в степенях 2. Этот навык отрабатывайте непрестанно. В начале лекции у вас было 2 задания на эту тему.
Уверена, что вы заметили на важную формулировку в задании: «Программа сгенерировала 128 паролей и записала их в файл подряд, без дополнительных символов». Если было бы указано количество дополнительных символов между паролями, используемых при записи, то это необходимо было бы учитывать. Важно внимательно читать условие задания.

Выполни самостоятельно.

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

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

8) Каждая клетка поля 8×8 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток. Каков объем информации после 11 сделанных ходов? (Запись решения начинается с начальной позиции коня).

Мы рассмотрели с вами первое занятие из 14. Начинаем собирать мозаику заданий ЕГЭ и знаний за все курсы информатики и математики.

Следующее занятие будет посвящено продолжению изучения темы и разбору заданий В1, В4, В10. Но обязательным будет предварительный разбор заданий, что вами получены на этом занятии. Выполняя задания, обязательно прикладывайте решения. Следуйте тому формату решения, что мною представлен в сценарии урока.

Дорогу осилит идущий.

С уважением, Екатерина Вадимовна.

ГБПОУ города Москвы «Спортивно-педагогический колледж»

Департамент спорта и туризма города Москвы

Преподаватель информатики и ИКТ: Макеева Е.С.

Задачи ЕГЭ. Кодирование текстовой информации

Задача 1

Считая, что каждый символ кодируется одним байтом, оцените объем следующего предложения (в битах) в кодировке ASCII : http :// www . fipi . ru

Задача 2

В кодировке КОИ-8 каждый символ кодируется 8 битами. Определите информационный объем (в байтах) следующего предложения: Mail . ru - почтовый сервер. В ответе укажите только число.

Задача 3

Каждый символ в Unicode закодирован двухбайтовым словом. Определите информационный объем (в битах) следующей фразы А.П. Чехова в этой кодировке: Что непонятно, то и чудо. В ответе укажите только число.

Задача 4

В текстовом редакторе включена кодировка текста КОИ-8 (1 байт на 1 символ). Мальчик набрал несколько слов. Сколько символов набрано в редакторе, если общий объем информации, набранный мальчиком, составил 592 бита?

Задача 5

Информационный объем предложения Кашу маслом не испортишь. составляет 50 байт. Определите, сколькими битами кодируется один символ. В ответе укажите только число.

Задача 6

Во сколько раз уменьшится информационный объем страницы текста (текст не содержит управляющих символов форматирования) при его преобразовании из кодировки Unicode (таблица кодировки содержит 65 536 символов) в кодировку Windows (таблица кодировки содержит 256 символов)? В ответе укажите только число.

Задача 7

Используется кодовая таблица CP1251 (Windows Cyrillic). Сколько килобайт будет занимать файл в простом текстовом формате (plain text), если в тексте 200 страниц, на странице 32 строки, а в строке в среднем 48 символов? В ответе укажите только число.

Задача 8

Система оптического распознавания символов позволяет преобразовывать отсканированные изображения страниц документа в текстовый формат со скоростью 4 страницы в минуту и использует алфавит мощностью 65 536 символов. Какое количество информации (в килобайтах) будет нести текстовый документ, каждая страница которого содержит 40 строк по 50 символов, после 10 минут работы приложения? В ответе укажите только число.

Задача 9

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

Задача 10

Автоматическое устройство осуществило автоматическую перекодировку информационного сообщения на русском языке из 16-битного представления Unicode в 8-битную кодировку КОИ-8. До перекодировки информационный объем сообщения составлял 30 байт. Определите информационный объем сообщения (в битах) после перекодировки. В ответе укажите только число.

Задачи ЕГЭ. Кодирование текстовой информации.

Задача 1

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

Задача 2

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

Задача 3

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

Задача 4

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

Задача 5

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

Задача 6

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

Задача 7

Текстовый документ, состоящий из 10240 символов, хранился в 8-битной кодировке КОИ-8. Этот документ был преобразован в 16-битную кодировку Unicode. Укажите, какое дополнительное количество Кбайт потребуется для хранения документа. В ответе запишите только число.

Задача 8

Текстовый документ, состоящий из 11264 символов, хранился в 8-битной кодировке КОИ-8. Этот документ был преобразован в 16-битную кодировку Unicode. Укажите, какое дополнительное количество Кбайт потребуется для хранения документа. В ответе запишите только число.

Задача 9

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

Задача 10

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

Задачи ЕГЭ. Кодирование графической информации

Задача 1

Черно-белое (без градаций серого цвета) растровое графическое изображение имеет размер 10х10 точек. Какой объем памяти в битах займет это изображение? В ответе запишите только число.

Задача 2

Черно-белое (без градаций серого цвета) растровое графическое изображение имеет размер 20х20 точек. Какой объем памяти в байтах займет это изображение? В ответе запишите только число.

Задача 3

Цветное (с палитрой из 256 цветов) растровое графическое изображение имеет размер 10х10 точек. Какой объем памяти в битах займет это изображение? В ответе запишите только число.

Задача 4

В процессе преобразования растрового графического изображения количество цветов уменьшилось с 65 536 до 16. Во сколько раз уменьшился информационный объем графического файла?

Задача 5

В процессе преобразования растрового графического файла количество цветов уменьшилось с 1024 до 32. Во сколько раз уменьшился информационный объем файла?

Задача 6

Для хранения растрового изображения размером 32×32 пикселя отвели 512 байтов памяти. Каково максимально возможное число цветов в палитре изображения? В ответе запишите только число.

Задача 7

Для хранения растрового изображения размером 64×64 пикселя отвели 3 килобайта памяти. Каково максимально возможное количество цветов в палитре изображения? В ответе запишите только число.

Задача 8

Какой объем памяти в килобайтах необходимо выделить под хранение растрового изображения размером 240×192 пикселей, если в палитре изображения 65 тысяч цветов? В ответе запишите только число.

Задача 9

Разрешение экрана монитора 1024х768 точек, глубина цвета - 16 бит. Каков необходимый объем видеопамяти (в мегабайтах) для данного графического режима? В ответе запишите только число.

Задача 10

Какой объем памяти в килобайтах необходимо выделить под хранение растрового изображения размером 640×480 пикселей, если в палитре изображения 16 миллионов цветов? В ответе запишите только число.

Задачи ЕГЭ. Кодирование звуковой информации.

Задача 1

Аналоговый звуковой сигнал был дискретизирован сначала с использованием 65 536 уровней интенсивности сигнала (качество звучания аудио-CD), а затем - с использованием 256 уровней интенсивности сигнала (качество звучания радиотрансляции). Во сколько раз различаются информационные объемы оцифрованных звуковых сигналов? В ответе запишите только число.

Задача 2

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

Задача 3

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

Задача 4

Двухканальная (стерео) звукозапись с частотой дискретизации 32 кГц и 24-битным разрешением велась в течение 5 минут. Сжатие данных не производилось. Какая из приведенных ниже величин наиболее близка к размеру полученного файла?

Задача 5

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

Задача 6

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

Задача 7

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

Задача 8

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

Задача 9

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

Задача 10

Цифровой аудиофайл (моно) имеет продолжительность звучания 1 минута. При этом он занимает 2,52 Мбайт. С какой частотой дискретизации записан звук, если разрядность звуковой платы 8 бит?

Контрольная работа. Вариант 1

Задача 1

Фразу на русском языке закодировали 16-битным кодом Unicode :

«Не стыдно чего-нибудь не знать, но стыдно не хотеть учиться» (Сократ)

Каков информационный объем этой фразы (взятой в кавычки) в байтах. В ответе запишите только число.

Задача 2

Текстовый документ, состоящий из 20480 символов, хранился в 8-битной кодировке КОИ-8. Этот документ был преобразован в 16-битную кодировку Unicode. Укажите, какое дополнительное количество Кбайт потребуется для хранения документа. В ответе запишите только число.

Задача 3

Какой объем памяти в килобайтах необходимо выделить под хранение растрового изображения размером 128×128 пикселей, если в палитре изображения 64 цвета? В ответе запишите только число.

Задача 4

Для хранения растрового изображения размером 160×128 пикселей отвели 5 килобайт памяти. Каково максимально возможное количество цветов в палитре изображения? В ответе запишите только число.

Задача 5

Цифровой аудиофайл (моно) занимает 2,7 Мбайт памяти, разрешение 16 бит. С какой частотой дискретизации записан звук, если длительность звучания 1 минута?

Контрольная работа. Вариант 2

Задача 1

Каждый символ в Unicode закодирован двухбайтным словом. Оцените информационный объем следующего предложения в байтах.

«Вкладка - раздел (страница) диалогового окна»

В ответе запишите только число.

Задача 2

Некоторое сообщение первоначально было записано в 16-битном коде Unicode. При его перекодировке в 8-битную кодировку КОИ-8 информационное сообщение уменьшилось на 1040 бит. Укажите длину сообщения в символах. В ответе запишите только число.

Задача 3

Какой объем памяти в килобайтах необходимо выделить под хранение растрового изображения размером 128×128 пикселей, если в палитре изображения 256 цветов? В ответе запишите только число.

Задача 4

Для хранения растрового изображения размером 64×64 пикселей отвели 3 килобайта памяти. Каково максимально возможное количество цветов в палитре изображения? В ответе запишите только число.

Задача 5

Объем свободной памяти на диске 10,1 Мбайт, разрядность звуковой платы - 16 бит. Какой может быть продолжительность звучания аудиофайла (стерео), записанного с частотой дискретизации 44,1 кГц?

Ответы к задачам ЕГЭ:

1	144		400				300	156	300	120
2		400	440	800					320	2048
3	100		800						1,5	900
4
Контр. раб. Вариант1	118
Контр. раб. Вариант2		130

Основано на: демонстрационных вариантах ЕГЭ по информатике за 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. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Как это можно сделать?