Подводные камни измерения информации

Тема: Кодирование текстовой информации. Кодировка ASCII. Основные кодировки кириллицы Что нужно знать: все символы кодируются одинаковым числом бит (алфавитный подход) чаще всего используют кодировки, в которых на символ отводится 8 бит (8-битные) или 16 бит (16-битные) при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 кбайт) – 1024 байта, в мегабайте (1Мбайт) – 1024 кбайта после знака препинания внутри (не в конце!) текста ставится пробел чтобы найти информационный объем текста I, нужно умножить количество символов N на число бит на символ K: I = N * K две строчки текста не могут занимать 100 кбайт в памяти

Примерные задания Пример задания: Определите информационный объем текста Бамбарбия! Кергуду! 1) 38 бит 2) 144 бита 3) 152 бита 4) 19 бит Решение: в этом тексте 19 символов (обязательно считать пробелы и знаки препинания) если нет дополнительной информации, считаем, что используется 8- битная кодировка (чаще всего явно указано, что кодировка 8- или 16- битная) поэтому в сообщении 19*8 = 152 бита информации (ответ 3).

Возможные ловушки: указано правильное число, но другие единицы измерения (объем текста 19 байт, а один из неверных ответов – 19 бит) расчет на то, что «забудут» пробел, в этом случае получается 18*8 = 144 бита (ответ 2, неверный) в 16-битной кодировке объем текста – 38 байт, а один из неверных ответов – 38 бит.

Примерные задания Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах? 1) 30 2) 60 3) 120 4) 480 Решение: обозначим количество символов через N при 16-битной кодировке объем сообщения – 16*N бит когда его перекодировали в 8-битный код, его объем стал равен– 8*N бит таким образом, сообщение уменьшилось на 16*N – 8*N = 8*N = 480 бит отсюда находим N = 480/8 = 60 символов (ответ 2).

Тема: Вычисление информационного объема сообщения Что нужно знать: с помощью K бит можно закодировать Q = 2 K различных вариантов (чисел) таблица степеней двойки, она же показывает, сколько вариантов Q можно закодировать с помощью K бит: при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 кбайт) – 1024 байта, в мегабайте (1Мбайт) – 1024 кбайта чтобы найти информационный объем сообщения (текста) I, нужно умножить количество символов (отсчетов) N на число бит на символ (отсчет) K: I = N * K две строчки текста не могут занимать 100 кбайт в памяти мощность алфавита – это количество символов в этом алфавите Чаще всего килобайт обозначают «Кб», а мегабайт – «Мб», но в демо- тестах ЕГЭ разработчики привели именно такие обозначения.

Примерные задания В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов? 1) 70 бит 2) 70 байт 3) 490 бит 4) 119 байт Решение: велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов по таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно закодировать 128 вариантов, то есть, еще есть запас); итак, 7 бит на один отсчет когда 70 велосипедистов прошли промежуточный финиш, в память устройства записано 70 отсчетов поэтому в сообщении 70*7 = 490 бит информации (ответ 3).

Возможные ловушки: дано число, которое есть в условии (неверные ответы 70 бит, 70 байт, 119 байт), чтобы сбить случайное угадывание указано правильное число, но другие единицы измерения (мог быть вариант 490 байт) расчет на невнимательное чтение условия: можно не заметить, что требуется определить объем только 70 отсчетов, а не всех 119 (мог быть вариант 119*7=833 бита)

Примерные задания В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян – альбинос (вся белая). Сообщение «Обезьяна-альбинос живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б? 1) 42) 16 3) 28 4) 30 Решение (вариант 1): информация в 4 бита соответствует выбору одного из 16 вариантов, … … поэтому в вольере А живет 1/16 часть всех обезьян (это самый важный момент!) всего обезьян – 32, поэтому в вольере А живет 32/16 = 2 обезьяны поэтому в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян правильный ответ – 4.

Примерные задания В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян – альбинос (вся белая). Сообщение «Обезьяна-альбинос живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б? 1) 42) 16 3) 28 4) 30 Решение (вариант 2):

Возможные ловушки: неверный ответ 1 (4 обезьяны) сбивает случайное угадывание «в лоб», по исходным данным можно сделать неверный вывод о том, что в вольере А живет 4 обезьяны (столько же, сколько бит информации мы получили), следовательно, в вольере Б живут оставшиеся 28 обезьян (неверный ответ 3) после п. 1 можно сделать (неверный) вывод о том, что в вольере А живет 16 обезьян, следовательно, в вольере Б – тоже 16 (неверный ответ 2)

Примерные задания В некоторой стране автомобильный номер длиной 7 символов составляют из заглавных букв (используются только 22 различные буквы) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объем памяти, отводимый этой программой для записи 50 номеров. 1) 350 байт 2) 300 байт 3) 250 байт 4) 200 байт Решение: На каждом из 7 мест может стоять один из 32 символов (22 буквы + 10 цифр). Значит на один символ компьютерная программа должна отводить минимум 5 бит (2 5 =32) Номер состоит из 7 знаков, значит на него отводится 5 бит * 7 = 35 бит (т.к. отводятся байты, значит программа выделяет на один номер 6 байт) Таких номеров 50. Значит для записи 50 номеров отводится 50 * 6 байт = 300 байт памяти.

Тема: расчет количества возможных вариантов (комбинаторика) Что нужно знать: если на каждом шаге известно количество возможных вариантов выбора, то для вычисления общего количества вариантов нужно все эти числа перемножить; например, в двузначном числе мы можем выбрать первую цифру 9 способами (она не может быть нулем), а вторую – 10 способами, поэтому всего есть 9·10=90 двузначных чисел если мы разбили все нужные нам комбинации на несколько групп (не имеющих общих элементов!) и подсчитали количество вариантов в каждой группе, то для вычисления общего количества вариантов нужно все эти числа сложить; например, есть 9·10=90 трехзначных чисел, оканчивающихся на 5, и 9·10=90 трехзначных чисел, оканчивающихся на 2, поэтому 90+90=180 трехзначных чисел оканчиваются на 2 или на 5 если в предыдущем случае группы имеют общие элементы, их количество нужно вычесть из полученной суммы; например, есть 9·10=90 трехзначных чисел, оканчивающихся на 5, и 10·10=100 трехзначных чисел, начинающихся на 5; в обе группы входят числа, которые начинаются и заканчиваются на 5, их всего 10 штук, поэтому количество чисел, которые начинаются или заканчиваются на 5, равно =180.

Примерные задания Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи четырех сигнальных флагов, если на корабле имеются флаги трех различных видов (флагов каждого вида неограниченное количество)? Решение: Рассмотрим формулу Шеннона подробнее: 2 i = N, где 2 – количество символов для кодирования (0,1); i – количество мест; N – количество вариантов. На каждом из 4 мест может висеть один из 3 флагов. В данном случае количество символов для кодирования равно ТРЕМ. Количество мест равно ЧЕТЫРЕМ. Значит формула для вычисления примет вид: 3 4 = N=81

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

Задание 2 В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар? 1) 2 бита 2) 4 бита 3)8 бит 4)24 бита

Задание 3 В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке? 1) 4 2) 8 3) 16 4) 32

Спасибо за внимание