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

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

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

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

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

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

Решение.

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

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

Ответ: 48

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

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

Решение.

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

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

Ответ: 24

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

Решение.

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

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

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

Ответ: 28

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

Решение.

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

Ответ: 60

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

Решение.

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

Ответ: 62

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

Решение.

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

Ответ: 48

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

Решение.

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

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

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

Ответ: 56

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

Решение.

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

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

Ответ: 56

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

Решение.

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

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

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

Ответ: 96

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

Решение.

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

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

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

Ответ: 112.

Ответ: 112

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

Решение.

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

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

Различные подходы к определению понятия «информация». Виды информационных процессов. Информационный аспект в деятельности человека

Информация (лат. informatio — разъяснение, изложение, набор сведений) — базовое понятие в информатике, которому нельзя дать строгого определения, а можно только пояснить:

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

Понятие «информация» является общенаучным, т. е. используется в различных науках: физике, биологии, кибернетике, информатике и др. При этом в каждой науке данное понятие связано с различными системами понятий. Так, в физике информация рассматривается как антиэнтропия (мера упорядоченности и сложности системы). В биологии понятие «информация» связывается с целесообразным поведением живых организмов, а также с исследованиями механизмов наследственности. В кибернетике понятие «информация» связано с процессами управления в сложных системах.

Основными социально значимыми свойствами информации являются:

• полезность;
• доступность (понятность);
• актуальность;
• полнота;
• достоверность;
• адекватность.

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

Информационный процесс — это процесс сбора (приема), передачи (обмена), хранения, обработки (преобразования) информации.

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

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

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

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

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

Язык как способ представления и передачи информации

В зависимости от способа восприятия знаки делятся на:

• зрительные (буквы и цифры, математические знаки, музыкальные ноты, дорожные знаки и др.);
• слуховые (устная речь, звонки, сирены, гудки и др.);
• осязательные (азбука Брайля для слепых, жесты-касания и др.);
• обонятельные;
• вкусовые.

Для долговременного хранения знаки записывают на носители информации.

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

По способу связи между формой и значением знаки делятся на:

• иконические — их форма похожа на отображаемый объект (например, значок папки «Мой компьютер» на «Рабочем столе» компьютера);
• символы — связь между их формой и значением устанавливается по общепринятому соглашению (например, буквы, математические символы ∫, ≤, ⊆, ∞; символы химических элементов).

Для представления информации используются знаковые системы, которые называются языками . Основу любого языка составляет алфавит — набор символов, из которых формируется сообщение, и набор правил выполнения операций над символами.

Языки делятся на:

• естественные (разговорные) — русский, английский, немецкий и др.;
• формальные — встречающиеся в специальных областях человеческой деятельности (например, язык алгебры, языки программирования, электрических схем и др.)

Системы счисления также можно рассматривать как формальные языки. Так, десятичная система счисления — это язык, алфавит которого состоит из десяти цифр 0..9, двоичная система счисления — язык, алфавит которого состоит из двух цифр — 0 и 1.

Методы измерения количества информации: вероятностный и алфавитный

Единицей измерения количества информации является бит . 1 бит — это количество информации, содержащейся в сообщении, которое вдвое уменьшает неопределенность знаний о чем-либо.

Связь между количеством возможных событий N и количеством информации I определяется формулой Хартли:

Например, пусть шарик находится в одной из четырех коробок. Таким образом, имеется четыре равновероятных события (N = 4). Тогда по формуле Хартли 4 = 2 I . Отсюда I = 2. То есть сообщение о том, в какой именно коробке находится шарик, содержит 2 бита информации.

Алфавитный подход

При алфавитном подходе к определению количества информации отвлекаются от содержания (смысла) информации и рассматривают ее как последовательность знаков определенной знаковой системы. Набор символов языка (алфавит) можно рассматривать как различные возможные события. Тогда, если считать, что появление символов в сообщении равновероятно, по формуле Хартли можно рассчитать, какое количество информации несет каждый символ:

Например, в русском языке 32 буквы (буква ё обычно не используется), т. е. количество событий будет равно 32. Тогда информационный объем одного символа будет равен:

I = log 2 32 = 5 битов.

Если N не является целой степенью 2, то число log 2 N не является целым числом, и для I надо выполнять округление в большую сторону. При решении задач в таком случае I можно найти как log 2 N", где N′ — ближайшая к N степень двойки — такая, что N′ > N.

Например, в английском языке 26 букв. Информационный объем одного символа можно найти так:

N = 26; N" = 32; I = log 2 N" = log 2 (2 5) = 5 битов.

Если количество символов алфавита равно N, а количество символов в записи сообщения равно М, то информационный объем данного сообщения вычисляется по формуле:

I = M · log 2 N.

Примеры решения задач

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

Решение. С помощью n лампочек, каждая из которых может находиться в одном из двух состояний, можно закодировать 2 n сигналов. 2 5 < 50 < 2 6 , поэтому пяти лампочек недостаточно, а шести хватит.

Ответ: 6.

Пример 2. Метеорологическая станция ведет наблюдения за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100, которое записывается при помощи минимально возможного количества битов. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.

Решение. В данном случае алфавитом является множество целых чисел от 0 до 100. Всего таких значений 101. Поэтому информационный объем результатов одного измерения I = log 2 101. Это значение не будет целочисленным. Заменим число 101 ближайшей к нему степенью двойки, большей 101. Это число 128 = 27. Принимаем для одного измерения I = log 2 128 = 7 битов. Для 80 измерений общий информационный объем равен:

80 · 7 = 560 битов = 70 байтов.

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

Вероятностный подход

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

$I=-∑↙{i=1}↖{N}p_ilog_2p_i$,

где $I$ — количество информации;

$N$ — количество возможных событий;

$p_i$ — вероятность $i$-го события.

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

$p_1={1}/{2}, p_2={1}/{4}, p_3={1}/{8}, p_4={1}/{8}$.

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

$I=-({1}/{2}·log_2{1}/{2}+{1}/{4}·log_2{1}/{4}+{1}/{8}·log_2{1}/{8}+{1}/{8}·log_2{1}/{8})={14}/{8}$ битов $= 1.75 $бита.

Единицы измерения количества информации

Наименьшей единицей информации является бит (англ. binary digit (bit) — двоичная единица информации).

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

В информатике принято рассматривать последовательности длиной 8 битов. Такая последовательность называется байтом.

Производные единицы измерения количества информации:

1 байт = 8 битов

1 килобайт (Кб) = 1024 байта = 2 10 байтов

1 мегабайт (Мб) = 1024 килобайта = 2 20 байтов

1 гигабайт (Гб) = 1024 мегабайта = 2 30 байтов

1 терабайт (Тб) = 1024 гигабайта = 2 40 байтов

Процесс передачи информации. Виды и свойства источников и приемников информации. Сигнал, кодирование и декодирование, причины искажения информации при передаче

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

В качестве источника информации может выступать живое существо или техническое устройство. Источник посылает передаваемое сообщение, которое кодируется в передаваемый сигнал.

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

Сигнал посылается по каналу связи. В результате в приемнике появляется принимаемый сигнал, который декодируется и становится принимаемым сообщением.

Передача информации по каналам связи часто сопровождается воздействием помех, вызывающих искажение и потерю информации.

Примеры решения задач

Пример 1. Для кодирования букв А, З, Р, О используются двухразрядные двоичные числа 00, 01, 10, 11 соответственно. Этим способом закодировали слово РОЗА и результат записали шестнадцатеричным кодом. Указать полученное число.

Решение. Запишем последовательность кодов для каждого символа слова РОЗА: 10 11 01 00. Если рассматривать полученную последовательность как двоичное число, то в шестнадцатеричном коде оно будет равно: 1011 0100 2 = В4 16 .

Ответ: В4 16 .

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

Прием/передача информации может происходить с разной скоростью. Количество информации, передаваемое за единицу времени, есть скорость передачи информации , или скорость информационного потока.

Скорость выражается в битах в секунду (бит/с) и кратных им Кбит/с и Мбит/с, а также в байтах в секунду (байт/с) и кратных им Кбайт/с и Мбайт/с.

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

Примеры решения задач

Пример 1. Скорость передачи данных через ADSL-соединение равна 256000 бит/с. Передача файла через данное соединение заняла 3 мин. Определите размер файла в килобайтах.

Решение. Размер файла можно вычислить, если умножить скорость передачи информации на время передачи. Выразим время в секундах: 3 мин = 3 ⋅ 60 = 180 с. Выразим скорость в килобайтах в секунду: 256000 бит/с = 256000: 8: 1024 Кбайт/с. При вычислении размера файла для упрощения расчетов выделим степени двойки:

Размер файла = (256000: 8: 1024) ⋅ (3 ⋅ 60) = (2 8 ⋅ 10 3: 2 3: 2 10) ⋅ (3 ⋅ 15 ⋅ 2 2) = (2 8 ⋅ 125 ⋅ 2 3: 2 3: 2 10) ⋅ (3 ⋅ 15 ⋅ 2 2) = 125 ⋅ 45 = 5625 Кбайт.

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

Представление числовой информации. Сложение и умножение в разных системах счисления

Представление числовой информации с помощью систем счисления

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

Система счисления — это система записи чисел с помощью определенного набора цифр.

Система счисления называется позиционной , если одна и та же цифра имеет различное значение, которое определяется ее местом в числе.

Позиционной является десятичная система счисления. Например, в числе 999 цифра «9» в зависимости от позиции означает 9, 90, 900.

Римская система счисления является непозиционной . Например, значение цифры Х в числе ХХІ остается неизменным при вариации ее положения в числе.

Позиция цифры в числе называется разрядом . Разряд числа возрастает справа налево, от младших разрядов к старшим.

Количество различных цифр, употребляемых в позиционной системе счисления, называется ее основанием .

Развернутая форма числа — это запись, которая представляет собой сумму произведений цифр числа на значение позиций.

Например: 8527 = 8 ⋅ 10 3 + 5 ⋅ 10 2 + 2 ⋅ 10 1 + 7 ⋅ 10 0 .

Развернутая форма записи чисел произвольной системы счисления имеет вид

$∑↙{i=n-1}↖{-m}a_iq^i$,

где $X$ — число;

$a$ — цифры численной записи, соответствующие разрядам;

$i$ — индекс;

$m$ — количество разрядов числа дробной части;

$n$ — количество разрядов числа целой части;

$q$ — основание системы счисления.

Например, запишем развернутую форму десятичного числа $327.46$:

$n=3, m=2, q=10.$

$X=∑↙{i=2}↖{-2}a_iq^i=a_2·10^2+a_1·10^1+a_0·10^0+a_{-1}·10^{-1}+a_{-2}·10^{-2}=3·10^2+2·10^1+7·10^0+4·10^{-1}+6·10^{-2}$

Если основание используемой системы счисления больше десяти, то для цифр вводят условное обозначение со скобкой вверху или буквенное обозначение: В — двоичная система, О — восмеричная, Н — шестнадцатиричная.

Например, если в двенадцатеричной системе счисления 10 = А, а 11 = В, то число 7А,5В 12 можно расписать так:

7А,5В 12 = В ⋅ 12 -2 + 5 ⋅ 2 -1 + А ⋅ 12 0 + 7 ⋅ 12 1 .

В шестнадцатеричной системе счисления 16 цифр, обозначаемых 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, что соответствует следующим числам десятеричной системы счисления: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. Примеры чисел: 17D,ECH; F12AH.

Перевод чисел в позиционных системах счисления

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

Для перевода числа из любой позиционной системы счисления в десятичную необходимо использовать развернутую форму числа, заменяя, если это необходимо, буквенные обозначения соответствующими цифрами. Например:

1101 2 = 1 ⋅ 2 3 + 1 ⋅ 2 2 + 0 ⋅ 2 1 + 1 ⋅ 2 0 = 13 10 ;

17D,ECH = 12 ⋅ 16 -2 + 14 ⋅ 16 -1 + 13 ⋅ 160 + 7 ⋅ 16 1 + 1 ⋅ 16 2 = 381,921875.

Перевод чисел из десятичной системы счисления в заданную

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

Например, переведем десятичное число 475 в двоичную систему счисления. Для этого будем последовательно выполнять деление нацело на основание новой системы счисления, т. е. на 2:

Читая остатки от деления снизу вверх, получим 111011011.

Проверка:

1 ⋅ 2 8 + 1 ⋅ 2 7 + 1 ⋅ 2 6 + 0 ⋅ 2 5 + 1 ⋅ 2 4 + 1 ⋅ 2 3 + 0 ⋅ 2 2 + 1 ⋅ 2 1 + 1 ⋅ 2 0 = 1 + 2 + 8 + 16 + 64 + 128 + 256 = 475 10 .

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

Например, переведем десятичную дробь 0,375 10 в двоичную систему счисления:



Полученный результат — 0,011 2 .

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

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

Для записи восьмеричных чисел используются восемь цифр, т. е. в каждом разряде числа возможны 8 вариантов записи. Каждый разряд восьмеричного числа содержит 3 бита информации (8 = 2 І ; І = 3).

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

Например:

1234,777 8 = 001 010 011 100,111 111 111 2 = 1 010 011 100,111 111 111 2 ;

1234567 8 = 001 010 011 100 101 110 111 2 = 1 010 011 100 101 110 111 2 .

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

Например:

1100111 2 = 001 100 111 2 = 147 8 ;

11,1001 2 = 011,100 100 2 = 3,44 8 ;

110,0111 2 = 110,011 100 2 = 6,34 8 .

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

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

Например:

1100111 2 = 0110 0111 2 = 67 16 ;

11,1001 2 = 0011,1001 2 = 3,9 16 ;

110,0111001 2 = 0110,0111 0010 2 = 65,72 16 .

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

Например:

1234,AB77 16 = 0001 0010 0011 0100,1010 1011 0111 0111 2 = 1 0010 0011 0100,1010 1011 0111 0111 2 ;

CE4567 16 = 1100 1110 0100 0101 0110 0111 2 .

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

Например, переведем троичное число 211 3 в семеричную систему счисления. Для этого сначала преобразуем число 211 3 в десятичное, записав его развернутую форму:

211 3 = 2 ⋅ 3 2 + 1 ⋅ 3 1 + 1 ⋅ 3 0 = 18 + 3 + 1 = 22 10 .

Затем переведем десятичное число 22 10 в семеричную систему счисления делением нацело на основание новой системы счисления, т. е. на 7:

Итак, 211 3 = 31 7 .

Примеры решения задач

Пример 1. В системе счисления с некоторым основанием число 12 записывается в виде 110. Указать это основание.

Решение. Обозначим искомое основание п. По правилу записи чисел в позиционных системах счисления 12 10 = 110 n = 0 ·n 0 + 1 · n 1 + 1 · n 2 . Составим уравнение: n 2 + n = 12 . Найдем натуральный корень уравнения (отрицательный корень не подходит, т. к. основание системы счисления, по определению, натуральное число большее единицы): n = 3 . Проверим полученный ответ: 110 3 = 0· 3 0 + 1 · 3 1 + 1 · 3 2 = 0 + 3 + 9 = 12 .

Ответ: 3.

Пример 2. Указать через запятую в порядке возрастания все основания систем счисления, в которых запись числа 22 оканчивается на 4.

Решение. Последняя цифра в записи числа представляет собой остаток от деления числа на основание системы счисления. 22 - 4 = 18. Найдем делители числа 18. Это числа 2, 3, 6, 9, 18. Числа 2 и 3 не подходят, т. к. в системах счисления с основаниями 2 и 3 нет цифры 4. Значит, искомыми основаниями являются числа 6, 9 и 18. Проверим полученный результат, записав число 22 в указанных системах счисления: 22 10 = 34 6 = 24 9 = 14 18 .

Ответ: 6, 9, 18.

Пример 3. Указать через запятую в порядке возрастания все числа, не превосходящие 25, запись которых в двоичной системе счисления оканчивается на 101. Ответ записать в десятичной системе счисления.

Решение. Для удобства воспользуемся восьмеричной системой счисления. 101 2 = 5 8 . Тогда число х можно представить как x = 5 · 8 0 + a 1 · 8 1 + a 2 · 8 2 + a 3 · 8 3 + ... , где a 1 , a 2 , a 3 , … — цифры восьмеричной системы. Искомые числа не должны превосходить 25, поэтому разложение нужно ограничить двумя первыми слагаемыми (8 2 > 25), т. е. такие числа должны иметь представление x = 5 + a 1 · 8. Поскольку x ≤ 25 , допустимыми значениями a 1 будут 0, 1, 2. Подставив эти значения в выражение для х, получим искомые числа:

a 1 = 0; x = 5 + 0 · 8 = 5;.

a 1 =1; x = 5 + 1 · 8 = 13;.

a 1 = 2; x = 5 + 2 · 8 = 21;.

Выполним проверку:

13 10 = 1101 2 ;

21 10 = 10101 2 .

Ответ: 5, 13, 21.

Арифметические операции в позиционных системах счисления

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

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

Пример выполнения сложения : сложим двоичные числа 111 и 101, 10101 и 1111:



Пример выполнения вычитания: вычтем двоичные числа 10001 - 101 и 11011 - 1101:



Пример выполнения умножения: умножим двоичные числа 110 и 11, 111 и 101:



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

Например, выполним сложение восьмеричных чисел 36 8 и 15 8 , а также вычитание шестнадцатеричных чисел 9С 16 и 67 16:



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

Представление чисел в компьютере

Формат с фиксированной запятой

В памяти компьютера целые числа хранятся в формате с фиксированной запятой : каждому разряду ячейки памяти соответствует один и тот же разряд числа, «запятая» находится вне разрядной сетки.

Для хранения целых неотрицательных чисел отводится 8 битов памяти. Минимальное число соответствует восьми нулям, хранящимся в восьми битах ячейки памяти, и равно 0. Максимальное число соответствует восьми единицам и равно

1 ⋅ 2 7 + 1 ⋅ 2 6 + 1 ⋅ 2 5 + 1 ⋅ 2 4 + 1 ⋅ 2 3 + 1 ⋅ 2 2 + 1 ⋅ 2 1 + 1 ⋅ 2 0 = 255 10 .

Таким образом, диапазон изменения целых неотрицательных чисел — от 0 до 255.

Для п-разрядного представления диапазон будет составлять от 0 до 2 n - 1.

Для хранения целых чисел со знаком отводится 2 байта памяти (16 битов). Старший разряд отводится под знак числа: если число положительное, то в знаковый разряд записывается 0, если число отрицательное — 1. Такое представление чисел в компьютере называется прямым кодом .

Для представления отрицательных чисел используется дополнительный код . Он позволяет заменить арифметическую операцию вычитания операцией сложения, что существенно упрощает работу процессора и увеличивает его быстродействие. Дополнительный код отрицательного числа А, хранящегося в п ячейках, равен 2 n − |А|.

Алгоритм получения дополнительного кода отрицательного числа:

1. Записать прямой код числа в п двоичных разрядах.

2. Получить обратный код числа . (Обратный код образуется из прямого кода заменой нулей единицами, а единиц — нулями, кроме цифр знакового разряда. Для положительных чисел обратный код совпадает с прямым. Используется как промежуточное звено для получения дополнительного кода.)

3. Прибавить единицу к полученному обратному коду.

Например, получим дополнительный код числа -2014 10 для шестнадцатиразрядного представления:

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

Например:

1) Найдем разность 13 10 - 12 10 для восьмибитного представления. Представим заданные числа в двоичной системе счисления:

13 10 = 1101 2 и 12 10 = 1100 2 .

Запишем прямой, обратный и дополнительный коды для числа -12 10 и прямой код для числа 13 10 в восьми битах:

Вычитание заменим сложением (для удобства контроля за знаковым разрядом условно отделим его знаком «_»):



Так как произошел перенос из знакового разряда, первую единицу отбрасываем, и в результате получаем 00000001.

2) Найдем разность 8 10 - 13 10 для восьмибитного представления.

Запишем прямой, обратный и дополнительный коды для числа -13 10 и прямой код для числа 8 10 в восьми битах:

Вычитание заменим сложением:



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

11111011 - 00000001 = 11111010.

Перейдем от обратного кода к прямому, инвертируя все цифры, за исключением знакового (старшего) разряда: 10000101. Это десятичное число -5 10 .

Так как при п-разрядном представлении отрицательного числа А в дополнительном коде старший разряд выделяется для хранения знака числа, минимальное отрицательное число равно: А = -2 n-1 , а максимальное: |А| = 2 n-1 или А = -2 n-1 - 1.

Определим диапазон чисел, которые могут храниться в оперативной памяти в формате длинных целых чисел со знаком (для хранения таких чисел отводится 32 бита памяти). Минимальное отрицательное число равно

А = -2 31 = -2147483648 10 .

Максимальное положительное число равно

А = 2 31 - 1 = 2147483647 10 .

Достоинствами формата с фиксированной запятой являются простота и наглядность представления чисел, простота алгоритмов реализации арифметических операций. Недостатком является небольшой диапазон представимых чисел, недостаточный для решения большинства прикладных задач.

Формат с плавающей запятой

Вещественные числа хранятся и обрабатываются в компьютере в формате с плавающей запятой , использующем экспоненциальную форму записи чисел.

Число в экспоненциальном формате представляется в таком виде:

где $m$ — мантисса числа (правильная отличная от нуля дробь);

$q$ — основание системы счисления;

$n$ — порядок числа.

Например, десятичное число 2674,381 в экспоненциальной форме запишется так:

2674,381 = 0,2674381 ⋅ 10 4 .

Число в формате с плавающей запятой может занимать в памяти 4 байта (обычная точность ) или 8 байтов (двойная точность ). При записи числа выделяются разряды для хранения знака мантиссы, знака порядка, порядка и мантиссы. Две последние величины определяют диапазон изменения чисел и их точность.

Определим диапазон (порядок) и точность (мантиссу) для формата чисел обычной точности, т. е. четырехбайтных. Из 32 битов 8 выделяется для хранения порядка и его знака и 24 — для хранения мантиссы и ее знака.

Найдем максимальное значение порядка числа. Из 8 разрядов старший разряд используется для хранения знака порядка, остальные 7 — для записи величины порядка. Значит, максимальное значение равно 1111111 2 = 127 10 . Так как числа представляются в двоичной системе счисления, то

$q^n = 2^{127}≈ 1.7 · 10^{38}$.

Аналогично, максимальное значение мантиссы равно

$m = 2^{23} - 1 ≈ 2^{23} = 2^{(10 · 2.3)} ≈ 1000^{2.3} = 10^{(3 · 2.3)} ≈ 10^7$.

Таким образом, диапазон чисел обычной точности составляет $±1.7 · 10^{38}$.

Кодирование текстовой информации. Кодировка ASCII. Основные используемые кодировки кириллицы

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

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

Как правило, для хранения кода символа используется один байт (восемь битов), поэтому коды символов могут принимать значение от 0 до 255. Такие кодировки называют однобайтными . Они позволяют использовать 256 символов (N = 2 I = 2 8 = 256). Таблица однобайтных кодов символов называется ASCII (American Standard Code for Information Interchange — Американский стандартный код для обмена информацией). Первая часть таблицы ASCII-кодов (от 0 до 127) одинакова для всех IBM-PC совместимых компьютеров и содержит:

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

Вторая часть таблицы (коды от 128 до 255) бывает различной в различных компьютерах. Она содержит коды букв национального алфавита, коды некоторых математических символов, коды символов псевдографики. Для русских букв в настоящее время используется пять различных кодовых таблиц: КОИ-8, СР1251, СР866, Мас, ISO.

В последнее время широкое распространение получил новый международный стандарт Unicode . В нем отводится по два байта (16 битов) для кодирования каждого символа, поэтому с его помощью можно закодировать 65536 различных символов (N = 2 16 = 65536). Коды символов могут принимать значение от 0 до 65535.

Примеры решения задач

Пример. С помощью кодировки Unicode закодирована следующая фраза:

Я хочу поступить в университет!

Оценить информационный объем этой фразы.

Решение. В данной фразе содержится 31 символ (включая пробелы и знак препинания). Поскольку в кодировке Unicode каждому символу отводится 2 байта памяти, для всей фразы понадобится 31 ⋅ 2 = 62 байта или 31 ⋅ 2 ⋅ 8 = 496 битов.

Ответ: 32 байта или 496 битов.

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

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