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

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

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

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

Задача 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

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

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

Тема «Информация и её кодирование» очень значима в ЕГЭ по информатике. Проверке знаний и умений по разделу «Информация и её кодирование» содержания курса информатики посвящены задания: №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 велосипедистов?

1. 70 бит
2. 70 байт
3. 490 бит
4. 119 байт

Решение:

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

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

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

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

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

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

1. 240 байт
2. 300 байт
3. 360 байт
4. 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. При этом информационное сообщение уменьшилось на

1. 320 бит
2. 20 бит
3. 160 байт
4. 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. Через канал связи передается сообщение: ГБВАВГ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричную систему счисления. Какой вид будет иметь это сообщение?

1. 71013
2. DBCACD
3. 7A13
4. 31A7

Решение:

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

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

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

1. 44 Мбайт
2. 87 Мбайт
3. 125 Мбайт
4. 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.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1. для буквы Д – 11
2. это невозможно
3. для буквы Г – 10
4. для буквы Д – 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 номеров.

1. 100 байт
2. 150 байт
3. 200 байт
4. 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. Через канал связи передается сообщение: ВАГБГВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид.

1. AD34
2. 43DA
3. 101334
4. CADBCD

Решение:

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

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

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

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

1. BACD
2. 1023

Решение:

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

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

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

0100 1011 2 = 4 B 16 .

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

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

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

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

1. 540 байт
2. 600 байт
3. 660 байт
4. 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-модели следующим образом:

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

1. серый
2. белый
3. фиолетовый
4. черный

Решение:

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

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

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

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

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

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

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

1. белый
2. зеленый
3. красный
4. синий

Решение:

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

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

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

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

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

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

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

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

1. белый
2. зеленый
3. красный
4. синий

Решение:

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

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

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

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

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

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

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

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

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

1. 350 байт
2. 300 байт
3. 250 байт
4. 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 различных символов .




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

Информация и её кодирование. Разбор заданий А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. Но обязательным будет предварительный разбор заданий, что вами получены на этом занятии. Выполняя задания, обязательно прикладывайте решения. Следуйте тому формату решения, что мною представлен в сценарии урока.

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

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

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