ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ
АССОЦИАЦИЯ МОСКОВСКИХ ВУЗОВ
СПЕЦИАЛИЗИРОВАННАЯ ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА
ИФОРМАТИКА
ПОДГОТОВКА К ЭГЭ
Составители: ст. преподаватель Ильина И.А.,
ст. преподаватель Малышева Л.Н.,
доцент Шевченко М.О.
Москва 2010
АННОТАЦИЯ
Научно – образовательный материал
Специализированная образовательная программа «Информатика и ИКТ»
Представляет собой структурированный материал по информатике по программе
средней школы. Включает в себя три раздела, вызывающие наибольшие
затруднения при подготовке к ЕГЭ:
1. Системы счисления.
2. Кодирование информации.
3. Алгоритмизация и программирование.
Каждый раздел завершается рубежным контролем, а весь курс – итоговым тестом по
материалам ЕГЭ.
Рекомендуется абитуриентам для подготовки к сдаче ЕГЭ и поступления в ГУУ
2
Рабочая программа
Название раздела и темы программы
№ п/п
1
2
3
4
Информация и ее кодирование
1.1
Позиционные системы счисления. Представление произвольных чисел в
позиционных системах счисления. Перевод чисел из P-ичных системы счисления в
десятичную. Перевод чисел из десятичной системы счисления в P-ичную.
Арифметические операции в P-ичных системах счисления. Системы счисления с
кратными основаниями.
1.2
Кодирование текстовой информации. Представление целых чисел. Представление
вещественных чисел. Кодирование графической информации.
1.3
Методы измерения количества информации: вероятностный и алфавитный; Единицы
измерения количества информации. Числовые параметры информационных объектов
и процессов: объем памяти, необходимый для хранения информации, скорость
обработки информации
1.4
Процесс передачи информации. Сигнал, кодирование и декодирование, причины
искажения информации при передаче. Скорость передачи информации и пропускная
способность канала связи
Основы логики
2.1
Алгебра логики. Понятие высказывания. Логические операции. Таблицы истинности.
Логические формулы. Законы алгебры логики. Логические выражения и их
преобразование.
2.2
Методы решения логических задач.
2.3
Алгебра переключательных схем.
Алгоритмизация и программирование
3.1
Алгоритмы, виды алгоритмов, описания алгоритмов. формальное исполнение
алгоритма. Формальное исполнение алгоритма, записанного на естественном языке.
Исполнение алгоритма в среде формального исполнителя. Построение дерева игры
по заданному алгоритму.
3.2
Основные алгоритмические конструкции: следование, ветвление, цикл.
Исполнение алгоритма, записанного в виде блок-схемы или программы на
алгоритмическом языке.
3.3
Использование переменных. Объявление переменной (тип, имя, значение).
Локальные и глобальные переменные
3.4
Работа с массивами (заполнение, считывание, поиск, сортировка и др.)
3.5
Технология программирования
Программные средства информационных и коммуникационных технологий
4.1
5
Файлы и файловые системы (файловые менеджеры и архиваторы)
Телекоммуникационные технологии
5.1
Базовые принципы организации и функционирования компьютерных сетей.
Локальные и глобальные сети. Адресация в сети.
3
5.2
6
7
8
Услуги компьютерных сетей: World Wide Web (WWW), электронная почта,
файловые архивы, поисковые системы, чат и пр. Поиск информации в Интернете.
Технология обработки информации в электронных таблицах
6.1
Ввод и редактирование данных в электронных таблицах, операции над данными.
Типы и формат данных. Работа с формулами. Абсолютная и относительная
адресация. Функции.
6.2
Визуализация данных с помощью диаграмм и графиков.
Технология хранения, поиска и сортировки информации в базах данных
7.1
Табличное представление баз данных. Структура базы данных (записи и поля).
7.2
Сортировка и отбор записей. Различные способы формирования запросов к базам
данных.
Моделирование и компьютерный эксперимент
8.1
Представление и считывание данных в разных типах информационных моделей
(схемы, карты, таблицы, графики и формулы).
Общее распределение часов по разделам курса для различных видов
обучения.
№
Название раздела
Часы
Зан
Часы
Зан
Часы
Зан
1.
Информация и её кодирование.
23,5
18,5
14,5
2.
Основы логики.
Алгоритмизация и программирование.
Технология программирования
Программные средства
информационных и
коммуникационных технологий.
Телекоммуникационные технологии
Технология обработки информации в
электронных таблицах
Технология хранения, поиска и
сортировки информации в базах
данных
Моделирование и компьютерный
эксперимент
Резервные
21,5
16,5
12
54,5
44
26
3
2,5
2,5
6
3,5
3,5
9
6
4
5
3,5
2,5
5
3,5
2,5
0
-
7
2
2,5
1
Итого
135
27
105
30
70
28
3.
4.
5.
6.
7.
8.
4
А1
2
А2
3
А3
4
А4
5
А5
6
А6
Умение представлять и считывать данные в
разных типах информационных моделей (схемы,
карты, таблицы, графики и формулы)
7
А7
8
А8
9
А9
10
А10
11
А11
12
А12
13
А13
14
А14
15
А15
16
А16
Формальное исполнение алгоритма, записанного
на естественном языке
Использование переменных. Операции над
переменными различных типов в языке
программирования.
Умение строить таблицы истинности и
логические схемы
Умение строить и преобразовывать логические
выражения
Знание технологии обработки информации в
электронных таблицах
Знания о визуализации данных с помощью
диаграмм и графиков
Знание технологии хранения, поиска и
сортировки информации в базах данных
Знание технологии обработки графической
информации
Знание основных понятий и законов
математической логики
Умение подсчитывать информационный объём
сообщения
Умение выполнять арифметические операции в
двоичной, восьмеричной и шестнадцатеричной
системах счисления.
Умение кодировать и декодировать информацию
Примерное время
выполнения
1
Максимальный балл
за задание
Часть 1
Знания о системах счисления и двоичном
представлении информации в памяти
компьютера
Кодирование текстовой информации. Кодировка
ASCII. Основные используемые кодировки
кириллицы
Знания о файловой системе организации данных
Уровень сложности
задания
Проверяемые элементы
№ темы
№
Обозначение
задания
Обобщённый план экзаменационной работы в соответствии с рабочей программой.
1.3
Б
1
2
1.2
Б
1
1
Б
1
2
1.1
Б
1
2
1.4
Б
1
2
Б
1
2
Б
1
2
Б
1
2
2.1
Б
1
2
2.1
Б
1
1
Б
1
3
Б
1
2
Б
1
4
1.2
П
1
2
2.1
П
1
2
П
1
3
5
17
А17
18
А18
19
В1
20
В2
21
В3
22
В4
23
В5
24
В6
25
В7
26
В8
27
В9
28
В10
29
С1
30
С2
31
С3
32
С4
Работа с массивами (заполнение, считывание,
поиск, сортировка, массовые операции и др.)
Умение исполнить алгоритм для конкретного
исполнителя с фиксированным набором команд
Часть 2
Знание о методах измерения количества
информации
П
1
6
В
1
6
Б
1
1
Б
1
3
Б
1
5
Б
1
2
1.1
П
1
2
1.4
П
1
3
П
1
3
П
1
8
П
1
3
В
1
10
П
3
30
В
2
30
В
3
30
В
4
60
1.1
Знание и умение использовать основные
алгоритмические конструкции: следование,
ветвление, цикл
Умение исполнять алгоритм в среде
формального исполнителя
Знание базовых принципов организации и
функционирования компьютерных сетей,
адресации в сети
Знание позиционных систем счисления
Умение определять скорость передачи
информации при заданной пропускной
способности канала
Умение строить и преобразовывать логические
выражения
Умение исполнять алгоритм, записанный на
естественном языке
Умение осуществлять поиск информации в
Интернете
Умение строить и преобразовывать логические
выражения
Часть 3
Умение прочесть фрагмент программы на языке
программирования и исправить допущенные
ошибки
Умение написать короткую (10–15 строк)
простую программу (например, обработки
массива) на языке программирования или
записать алгоритм на естественном языке
Умение построить дерево игры по заданному
алгоритму и обосновать выигрышную стратегию
Умение создавать собственные программы (30–
50 строк) для решения задач средней сложности
2.1
2.2
Всего заданий – 32;
Из них, по типу заданий: А – 18, В – 10; С – 4;
по уровню сложности: Б – 17, П – 10, В – 5.
Максимальный первичный балл за работу – 40.
Общее время выполнения работы –240 мин.
6
Тема 1.1
Системы счисления представление информации в памяти
компьютера
Позиционные системы счисления. Представление произвольных чисел в позиционных
системах счисления. Перевод чисел из P-ичных системы счисления в десятичную.
Перевод чисел из десятичной системы счисления в P-ичную.
Арифметические операции в P-ичных системах счисления. Системы счисления с
кратными основаниями.
Задание А1. Знания о системах счисления и двоичном представлении информации в
памяти компьютера (базовый уровень, время выполнения– 2 мин).
Необходимо знать:
перевод чисел между десятичной, двоичной, восьмеричной и шестнадцатеричной
системами счисления;
Примеры заданий ЕГЭ
Пример 1
Дано: a D716 и b 3318 . Какое из чисел с, записанных в двоичной системе
счисления, удовлетворяет неравенству a < c < b?
1) 110110012
2) 110111002
3) 110101112
4) 110110002
Общий подход:
перевести все числа (и исходные данные, и ответы) в одну (любую!) систему
счисления и сравнить.
Решение 1 (через десятичную систему):
1) a D716 13 16 7 215
2) b 3318 3 82 3 8 1 217
3) переводим в десятичную систему все ответы:
110110012 = 217,
11011100 2= 220,
110101112 = 215,
110110002=216
4) очевидно, что между числами 215 и 217 может быть только 216
5) таким образом, верный ответ – 4
Решение 2 (через двоичную систему):
1) a D716 1101 01112 11010111 2 (каждая цифра шестнадцатеричной системы
отдельно переводится в четыре двоичных – тетраду);
2) b 3318 011 011 0012 11011001 2 (каждая цифра восьмеричной системы
отдельно переводится в три двоичных – триаду, старшие нули можно не
писать);
3) теперь нужно сообразить, что между этими числами находится только двоичное
число 110110002 – это ответ 4.
Решение 3 (через восьмеричную систему):
1) a D716 11010111 2 011 010 1112 327 8 (сначала перевели в двоичную систему,
потом двоичную запись числа разбили на триады справа налево, каждую
триаду перевели отдельно в десятичную систему, так как для чисел от 0 до 7 их
восьмеричная запись совпадает с десятичной);
2) b 3318 , никуда переводить не нужно;
3) переводим в восьмеричную систему все ответы:
7
110110012 = 011 011 0012 = 3318 (разбили на триады справа налево, каждую
триаду перевели отдельно в десятичную систему, как в п. 1)
11011100 2= 3348,
110101112 = 3278, 110110002=3308
4) в восьмеричной системе между числами 3278 и 3318 может быть только 3308
5) таким образом, верный ответ – 4 .
Решение 4 (через шестнадцатеричную систему):
1) a D716 никуда переводить не нужно;
2) b 3318 11011001 2 1101 10012 D916 (сначала перевели в двоичную систему,
потом двоичную запись числа разбили на тетрады справа налево, каждую
тетраду перевели в шестнадцатеричную систему; при этом тетрады можно
переводить из двоичной системы в десятичную, а затем заменить все числа,
большие 9, на буквы – A, B, C, D, E, F);
3) переводим в шестнадцатеричную систему все ответы:
110110012 = 1101 10012 = D916 (разбили на тетрады справа налево, каждую
тетраду перевели отдельно в десятичную систему, все числа, большие 9,
заменили на буквы – A, B, C, D, E, F, как в п. 1)
11011100 2= DC16,
110101112 = D716, 110110002=D816
4) в шестнадцатеричной системе между числами D716 и D916 может быть только
D816
5) таким образом, верный ответ – 4 .
Задачи для самостоятельного решения:
1) Как представлено число 8310 в двоичной системе счисления?
1) 10010112 2) 11001012
3) 10100112
4) 1010012
2) Как представлено число 25 в двоичной системе счисления?
1) 10012
2) 110012
3) 100112
4) 110102
3) Как представлено число 263 в восьмеричной системе счисления?
1) 3018
2) 6508
3) 4078 4) 7778
4) Как записывается число 5678 в двоичной системе счисления?
1) 10111012 2) 1001101112
3) 1011101112 4) 111101112
5) Как записывается число A8716 в восьмеричной системе счисления?
1) 4358
2) 15778
3) 52078
4) 64008
6) Как записывается число 7548 в шестнадцатеричной системе счисления?
1) 73816
2) 1A416
3) 1EC16
4) A5616
7) Дано: a 9D16 , b 237 8 . Какое из чисел С, записанных в двоичной системе
счисления, удовлетворяет неравенству a C b ?
1) 100110102
2) 100111102
3) 100111112 4) 110111102
8) Дано: a F 716 , b 3718 . Какое из чисел С, записанных в двоичной системе
счисления, удовлетворяет неравенству a C b ?
1) 111110012
2) 110110002
3) 111101112 4) 111110002
9) Дано: a DD16 , b 337 8 . Какое из чисел С, записанных в двоичной системе
счисления, удовлетворяет неравенству a C b ?
1) 110110102
2) 111111102
3) 110111102 4) 110111112
8
10) Дано: a EA16 , b 3548 . Какое из чисел С, записанных в двоичной системе
счисления, удовлетворяет неравенству a C b ?
1) 111010102
2) 111011102
3) 111010112 4) 111011002
11) Сколько единиц в двоичной записи числа 127?
1) 1
2) 2
3) 6
4) 7
12) Сколько значащих нулей в двоичной записи числа 48?
1) 1
2) 2
3) 4
4) 6
13) Какое из чисел является наименьшим?
1) E616
2) 3478
3) 111001012
4) 232
14) Какое из чисел является наибольшим?
1) 9B16
2) 2348
3) 100110102
4) 153
15) Дано: a A716 , b 2518 . Какое из чисел С, записанных в двоичной системе
счисления, удовлетворяет неравенству a C b ?
1) 101011002
2) 101010102
3) 101010112 4) 101010002
Задание А4. Выполнение арифметических операций в двоичной, восьмеричной и
шестнадцатеричной системах счисления (базовый уровень, время выполнения– 2
мин).
Необходимо знать:
перевод чисел между двоичной, восьмеричной и шестнадцатеричной системами
счисления;
выполнение сложения (вычитания, умножения) в этих системах.
Примеры заданий ЕГЭ
Пример 1:
Чему равна сумма чисел x 438 и y 5616 ?
1) 1218
2) 1718
3)6916
4) 10000012
Общий подход:
перевести оба исходных числа и ответы в одну (любую!) систему счисления, и
выполнить сложение
Решение 1 (через десятичную систему):
6) x 438 4 8 3 35
7) y 5616 5 16 6 86
8) сложение: 35 + 86 = 121
4a) переводим результат во все системы, в которых даны ответы (пока не найдем
нужный):
121 = 11110012 = 1718 = 7916
4b) или переводим все ответы в десятичную систему
1218 = 81,
1718 = 121,
6916 = 105,
10000012 = 65
5) таким образом, верный ответ – 2 .
Решение 2 (через двоичную систему):
9
4) x 438 100 0112 100011 2 (каждая цифра восьмеричной системы отдельно
переводится в три двоичных – триаду, старшие нули можно не писать)
5) y 5616 0101 0110 2 1010110 2 (каждая цифра шестнадцатеричной системы
отдельно переводится в четыре двоичных – тетраду)
6) складываем
1000112
+
10101102
11110012
7) переводим все ответы в двоичную систему
1218 = 001 010 0012 = 10100012 (по триадам)
1718 = 001 111 0012 = 11110012 (по триадам)
6916 = 0110 10012 = 11010012 (по тетрадам)
10000012 не нужно переводить
8) правильный ответ – 2.
Решение 3(через восьмеричную систему):
6) x 438 , переводить не нужно
7) y 5616 0101 0110 2 001 010 110 2 126 8 (сначала перевели в двоичную систему,
потом двоичную запись числа разбили на триады справа налево, каждую
триаду перевели отдельно в десятичную систему, так как для чисел от 0 до 7 их
восьмеричная запись совпадает с десятичной)
8) складываем
438
+
1268
1718
9) видим, что такой ответ есть, это ответ 2.
Решение (вариант 4, через шестнадцатеричную систему):
6) x 438 100 0112 0010 00112 2316 (сначала перевели в двоичную систему,
потом двоичную запись числа разбили на тетрады справа налево, каждую
тетраду перевели в шестнадцатеричную систему; при этом тетрады можно
переводить из двоичной системы в десятичную, а затем заменить все числа,
большие 9, на буквы – A, B, C, D, E, F)
7) y 5616 , переводить не нужно
8) складываем
2316
+
5616
7916
9) переводим в шестнадцатеричную систему все ответы:
1218 = 001 010 0012 = 0101 00012 = 5116 (перевели в двоичную систему по
триадам, разбили на тетрады справа налево, каждую тетраду перевели
отдельно в десятичную систему, все числа, большие 9, заменили на буквы – A,
B, C, D, E, F)
171 2 = 001 111 0012 = 0111 10012 = 7916,
6916, переводить не нужно
10000012 = 0100 00012 = 4116
10) таким образом, верный ответ – 2 .
Пример 2:
Чему равна разность чисел x 1101110 2 и y 111111 2 ?
1) 1001112
2) 1101112
3)1011112
4) 1011012
10
Общий подход:
для выполнения операций оба исходных числа должны быть в одной
системе счисления;
в этой задаче оба числа и все результаты уже даны в двоичной системе;
вероятность сделать ошибку выше всего при выполнении сложения и
вычитания в двоичной системе, поэтому можно перевести их в другую
систему счисления, а потом перевести результат обратно.
Решение 1(через двоичную систему):
1) просто выполняем вычитание:
11011102
1111112
1011112
2) таким образом, ответ – 3.
Решение 2(через десятичную систему):
1) переводим в десятичную систему
11011102 = 26 + 25 + 23 + 22 + 21 = 64 + 32 + 8 + 4 + 2 = 110
1111112 = 25 + 24 + 23 + 22 + 21 + 20
= 32 + 16 + 8 + 4 + 2 + 1 = 63
2) выполняем вычитание: 110 – 63 = 47
3) переводим результат в двоичную систему:
47 = 32 + 8 + 4 + 2 + 1 = 25 + 23 + 22 + 21 + 20 = 1011112
4) таким образом, ответ – 3.
Решение 3(через восьмеричную систему):
1) переводим в восьмеричную систему (разбиваем на триады справа налево)
11011102 = 1 101 1102 = 1568
1111112 = 111 1112 = 778
2) выполняем вычитание:
1568
778
578
3) переводим результат в двоичную систему (заменяем каждую восьмеричную
цифру триадой):
578 = 101 1112
4) таким образом, ответ – 3.
Решение 4(через шестнадцатеричную систему):
1) переводим в восьмеричную систему (разбиваем на тетрады справа налево)
11011102 = 110 11102 = 6E16
1111112 = 11 11112 = 3F16
2) выполняем вычитание:
6E16
3F16
2F16
3) переводим результат в двоичную систему (заменяем каждую
шестнадцатеричную цифру тетрадой):
2F16 = 10 11112
4) таким образом, ответ – 3.
Задачи самостоятельного решения:
1) Вычислите сумму чисел x и y, при x = A616, y = 758. Результат представьте в
двоичной системе счисления.
11
1) 110110112
2) 111100012
3) 111000112
4) 100100112
2) Значение выражения 1016 + 108 • 102 в двоичной системе счисления равно
1) 10102
2) 110102
3) 1000002
4) 1100002
3) Вычислите сумму двоичных чисел x и y, если x = 10101012 и y = 10100112
1) 101000102
2) 101010002
3) 101001002
4) 101110002
4) Вычислите значение суммы 102 + 108 +1016 в двоичной системе счисления.
1) 101000102
2) 111102
3) 110102
4) 101002
5) Вычислите сумму чисел x и y, при x = 2718, y = 111101002. Результат представьте
в шестнадцатеричной системе счисления.
1) 15116
2) 1AD16
3) 41216
4) 10B16
6) Вычислите сумму чисел x и y, при x = A116, y = 11012. Результат представьте в
десятичной системе счисления.
1) 204
2) 152
3) 183
4) 174
7) Вычислите сумму чисел x и y, при x = 568, y = 11010012. Результат представьте в
двоичной системе счисления.
1) 111101112
2) 100101112
3) 10001112
4) 110011002
8) Вычислите сумму чисел x и y, при x = 5A16, y = 10101112. Результат представьте
в восьмеричной системе счисления.
1) 1518
2) 2618
3) 4338
4) 7028
9) Вычислите сумму чисел x и y, при x = 1278, y = 100101112. Результат представьте
в десятичной системе счисления.
1) 214
2) 238
3) 183
4) 313
10) Вычислите A8116 + 37716. Результат представьте в той же системе счисления.
1) 21B16
2) DF816
3) C9216
4) F4616
11) Чему равна разность чисел 10116 и 1101112?
1) 3128
2) 128
3) 3216
4) 6416
12) Чему равна разность чисел 1248 и 5216?
1) 112
2) 102
3) 1002
4) 1102
13) Чему равна сумма чисел 278 и 3416?
1) 1138
2) 638
3) 5116
4) 1100112
14) Чему равна сумма чисел 438 и 5616?
1) 7916
2) A316
3) 1258
4) 10101012
15) Вычислите сумму чисел x и y, при x = 1101112, y = 1358. Результат представьте в
двоичном виде.
12
1) 110101002
2) 101001002
3) 100100112
4) 100101002
16) Чему равна сумма чисел С516 и 478?
1) 111010102
2) 111011002
3) 100011002
4) 111101002
17) Чему равна сумма чисел x 678 и y 1011101 2 ?
1) 101000102
2) 101001002
3) 100101002
4) 100011002
18) Чему равна сумма чисел 578 и 4616?
1) 3518
2) 1258
3) 5516
4) 7516
Задание B5. Знание позиционных систем счисления (повышенный уровень, время – 2
мин).
Необходимо знать:
принципы кодирования чисел в позиционных системах счисления с произвольным
основанием
чтобы перевести число, скажем, 12345N, из системы счисления с основанием N в
десятичную систему, нужно умножить значение каждой цифры на N в степени,
равной ее разряду:
4 3 2 1 0 ← разряды
1 2 3 4 5N = 1·N4 + 2·N3 + 3·N2 + 4·N1 + 5·N0
последняя цифра записи числа в системе счисления с основанием N – это
остаток от деления этого числа на N
две последние цифры – это остаток от деления на N 2 , и т.д.
Примеры заданий ЕГЭ
Пример 1
Укажите через запятую в порядке возрастания все десятичные числа, не
превосходящие 25, запись которых в системе счисления с основанием четыре
оканчивается на 11?
Общий подход:
вспомним алгоритм перевода числа из десятичной системы в систему с
основанием N , из него следует, что младшая цифра результата – это остаток от
деления исходного числа на N , а две младших цифры – это остаток от деления
на N 2 и т.д.
в данном случае N 4 , остаток от деления числа на N 2 16 должен быть равен
114 = 5
потому задача сводится к тому, чтобы определить все числа, которые меньше или
равны 25 и дают остаток 5 при делении на 16
Решение (вариант 1, через десятичную систему):
1) общий вид чисел, которые дают остаток 5 при делении на 16:
k 16 5
где k – целое неотрицательное число (0, 1, 2, …)
2) среди всех таких чисел нужно выбрать те, что меньше или равны 25 («не
превосходят 25»); их всего два: 5 (при k 0 ) и 21 (при k 1 )
3) таким образом, верный ответ – 5, 21 .
Решение (вариант 2, через четверичную систему, предложен О.А. Тузовой):
13
1) переведем 25 в четверичную систему счисления: 25 = 1214, все интересующие
нас числа не больше этого значения
2) из этих чисел выделим только те, которые заканчиваются на 11, таких чисел
всего два:
это 114 = 5 и 1114 = 21
3) таким образом, верный ответ – 5, 21 .
Пример 2
Укажите через запятую в порядке возрастания все основания систем счисления, в
которых запись числа 23 оканчивается на 2.
Общий подход:
здесь обратная задача – неизвестно основание системы счисления, мы
обозначим его через N
поскольку последняя цифра числа – 2, основание должно быть больше 2, то есть
N 2
вспомним алгоритм перевода числа из десятичной системы в систему с
основанием N (см. презентацию), из него следует, что младшая цифра
результата – это остаток от деления исходного числа на N
Решение:
1) итак, нужно найти все целые числа N 3 , такие что остаток от деления 23 на N
равен 2, или (что то же самое)
23 k N 2
(*)
где k – целое неотрицательное число (0, 1, 2, …);
2) сложность в том, что и k , и N неизвестны, однако здесь нужно «играть» на том,
что это натуральные числа
3) из формулы (*) получаем k N 21 , так что задача сводится к тому, чтобы найти
все делители числа 21, которые больше 2
4) в этой задаче есть только три таких делителя: N 3, 7 и 21
5) таким образом, верный ответ – 3, 7, 21 .
Пример 3
Укажите через запятую в порядке возрастания все основания систем счисления, в
которых запись числа 31 оканчивается на 11.
Общий подход:
неизвестно основание системы счисления, мы обозначим его через N
пока будем считать, что запись числа 31 в системе с основанием N состоит из
трех цифр, причем две младшие (11) нам даны, а одну (обозначим ее через k )
нужно найти:
2 1 0 ← разряды
31 = k 1 1N = k·N2 + N1 + N0 = k·N2 + N + 1
можно показать, что при большем количестве разрядов эта формула также верна,
то есть, число 31 можно представить как 31 k N 2 N 1 при некотором целом k ;
например, для числа с пятью разрядами получаем:
4 3
2 1 0 ← разряды
31 = k4 k3 k2 1 1N = k4·N4 + k3·N3 + k2·N2 + N1 + N0
= k·N2 + N + 1
для k k4 N 2 k3 N k2 (из первых трех слагаемых вынесли общий множитель
N2 )
14
Решение:
1) итак, нужно найти все целые числа N 2 , такие что
(**)
31 k N 2 N 1
где k – целое неотрицательное число (0, 1, 2, …);
2) сложность в том, что и k , и N неизвестны, однако здесь нужно «играть» на том,
что это натуральные числа
3) из формулы (**) получаем (k N 1) N 30 , так что задача сводится к тому, чтобы
найти все делители N числа 30 и отобрать только те из них, для которых
30 N
уравнение (**) разрешимо при целом k , то есть, k
– целое число
N2
4) выпишем все делители числа 30, большие или равные 2: 2, 3, 5, 6, 10, 15, 30
30 N
5) из всех этих делителей только для 2, 3, 5 и 30 значение k
– целое число
N2
(оно равно соответственно 7, 3, 1 и 0)
6) таким образом, верный ответ – 2, 3, 5, 30.
Пример 4
Укажите, сколько всего раз встречается цифра 2 в записи чисел 10, 11, 12, …, 17
в системе счисления с основанием 5.
Решение (вариант 1):
1) запишем первое и последнее число в заданном диапазоне в системе счисления
с основанием 5:
10 = 205, 17 = 325 .
2) заметим, что оба они содержат цифру 2, так что, 2 цифры мы уже нашли
3) между 205 и 325 есть еще числа
215, 225, 235, 245, 305, 315.
4) в них 5 цифр 2 (в числе 225 – сразу две двойки), поэтому всего цифра 2
встречается 7 раз
5) таким образом, верный ответ – 7.
Решение (вариант 2):
1) переведем все указанные числа в систему счисления с основанием 5:
10 = 205, 11 = 215, 12 = 225, 13 = 235, 14 = 245, 15 = 305, 16 = 315, 17 = 325 .
2) считаем цифры 2 – получается 7 штук
3) таким образом, верный ответ – 7 .
Пример 5
Укажите наименьшее основание системы счисления, в которой запись числа 30
трехзначна.
Решение:
1) обозначим через N неизвестное основание системы счисления, тогда запись
числа 30 в этой системе имеет вид
x y z N 30
2) вспомним алгоритм перевода числа из системы счисления с основанием N в
десятичную систему: расставляем сверху номера разрядов и умножаем каждую
цифру на основание в степени, равной разряду:
2 1 0
x y z N x N 2 y N z 30
3) поскольку запись трехзначная, x 0 , поэтому 30 N 2
15
4) с другой стороны, четвертой цифры нет, то есть, в третьем разряде – ноль,
поэтому 30 N 3
5) объединяя последние два условия, получаем, что искомое основание N
удовлетворяет двойному неравенству
N 2 30 N 3
6) учитывая, что N – целое число, методом подбора находим целые решения
этого неравенства; их два – 4 и 5:
42 16 30 43 64
52 25 30 53 125
7) минимальное из этих значений – 4
8) таким образом, верный ответ – 4 .
Решение (без подбора):
1) выполним п.1-4 так же, как и в предыдущем варианте решения
2) найдем первое целое число, куб которого больше 30; это 4, так как
33 27 30 43 64
3) проверяем второе неравенство: 42 16 30 , поэтому в системе счисления с
основанием 4 запись числа 30 трехзначна
4) таким образом, верный ответ – 4 .
Пример 6
Укажите через запятую в порядке возрастания все десятичные числа, не
превосходящие 30, запись которых в системе счисления с основанием 5
начинается на 3?
Решение:
1) нас интересуют числа от 1 до 29
2) сначала определим, сколько цифр может быть в этих числах, записанных в
системе счисления с основанием 5
3) поскольку 52 29 53 , в интересующих нас числах может быть от 1 до 3 цифр
4) рассмотрим трехзначные числа, начинающиеся на 3 в системе с основанием 5:
3xy5 3 52 x 5 y
все они заведомо не меньше 3 52 75 29 , поэтому в наш диапазон не
попадают;
5) таким образом, остается рассмотреть только однозначные и двухзначные числа
6) есть всего одно однозначное число, начинающееся на 3, это 3
7) общий вид всех двузначных чисел, начинающихся на 3 в системе с основанием
5:
3 5 k 15 k
где k – целое число из множества {0, 1, 2,3,4} (поскольку система счисления
имеет основание 5 и цифр, больших 4, в записи числа быть не может)
8) используя эту формулу, находим интересующие нас двузначные числа – 15, 16,
17, 18 и 19
9) таким образом, верный ответ – 3, 15, 16, 17, 18, 19 .
Задачи для самостоятельного решения:
16) В системе счисления с некоторым основанием число 12 записывается в виде 110.
Укажите это основание.
17) Укажите через запятую в порядке возрастания все основания систем счисления, в
которых запись числа 39 оканчивается на 3.
16
18) В системе счисления с некоторым основанием десятичное число 129 записывается
как 1004. Укажите это основание.
19) Укажите через запятую в порядке возрастания все десятичные числа, не
превосходящие 30, запись которых в четверичной системе счисления оканчивается
на 31?
20) Укажите через запятую в порядке возрастания все десятичные натуральные числа,
не превосходящие 17, запись которых в троичной системе счисления оканчивается
на две одинаковые цифры?
21) Укажите, сколько всего раз встречается цифра 3 в записи чисел 19, 20, 21, …, 33 в
системе счисления с основанием 6.
22) Десятичное число, переведенное в восьмеричную и в девятеричную систему, в
обоих случаях заканчивается на цифру 0. Какое минимальное натуральное число
удовлетворяет этому условию?
23) Укажите наименьшее основание системы счисления, в которой запись числа 70
трехзначна.
24) Укажите наименьшее основание системы счисления, в которой запись числа 50
двузначна.
25) Сколько значащих цифр в записи десятичного числа 357 в системе счисления с
основанием 7?
26) Укажите через запятую в порядке возрастания все десятичные числа, не
превосходящие 25, запись которых в системе счисления с основанием 6 начинается
на 4?
27) Укажите через запятую в порядке возрастания все десятичные числа, не
превосходящие 20, запись которых в системе счисления с основанием 3 начинается
на 2?
28) Какое десятичное число при записи в системе счисления с основанием 5
представляется как 12345?
29) Укажите через запятую в порядке возрастания все основания систем счисления, в
которых запись числа 32 оканчивается на 4.
30) Укажите через запятую в порядке возрастания все десятичные числа, не
превосходящие 27, запись которых в двоичной системе счисления оканчивается на
110?
31) Укажите через запятую в порядке возрастания все десятичные числа, не
превосходящие 25, запись которых в троичной системе счисления оканчивается на
21?
32) Укажите через запятую в порядке возрастания все десятичные числа, не
превосходящие 45, запись которых в двоичной системе счисления оканчивается на
1010?
33) Десятичное число кратно 16. Какое минимальное количество нулей будет в конце
этого числа после перевода его в двоичную систему счисления?
34) Укажите, сколько всего раз встречается цифра 3 в записи чисел 13, 14, 15, …, 23 в
системе счисления с основанием 4.
35) Укажите, сколько всего раз встречается цифра 2 в записи чисел 13, 14, 15, …, 23 в
системе счисления с основанием 3.
36) В саду 100 фруктовых деревьев – 14 яблонь и 42 груши. Найдите основание
системы счисления, в которой указаны эти числа.
37) Найдите основание системы счисления, в которой выполнено сложение: 144 + 24 =
201.
38) Найдите основание системы счисления, в которой выполнено умножение: 3·213 =
1043.
17
Тема 1.2
Кодирование информации
Задание А2. Кодирование текстовой информации. Кодировка ASCII. Основные кодировки
кириллицы (базовый уровень, время – 1 мин).
Необходимо знать:
все символы кодируются одинаковым числом бит (алфавитный подход)
чаще всего используют кодировки, в которых на символ отводится 8 бит (8битные) или 16 бит (16-битные)
при измерении количества информации принимается, что в одном байте 8 бит, а в
одном килобайте (1 Кбайт) – 1024 байта, в мегабайте (1 Мбайт) – 1024 Кбайт.
после знака препинания внутри (не в конце!) текста ставится пробел
чтобы найти информационный объем текста I, нужно умножить количество
символов N на число бит на символ K: I N K
две строчки текста не могут занимать 100 Кбайт в памяти
Примеры заданий ЕГЭ
Пример 1
Автоматическое устройство осуществило перекодировку информационного
сообщения на русском языке, первоначально записанного в 16-битном коде
Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение
уменьшилось на 480 бит. Какова длина сообщения в символах?
1) 30
2) 60
3) 120
4) 480
Решение:
1) обозначим количество символов через N
2) при 16-битной кодировке объем сообщения – 16*N бит
3) когда его перекодировали в 8-битный код, его объем стал равен– 8*N бит
4) таким образом, сообщение уменьшилось на 16*N – 8*N = 8*N = 480 бит
5) отсюда находим N = 480/8 = 60 символов (ответ 2).
Пример 2
В таблице ниже представлена часть кодовой таблицы ASCII:
Символ
1 5 A B Q a b
Десятичный код
49 53 65 66 81 97 98
Шестнадцатеричный код 31 35 41 42 51 61 62
Каков шестнадцатеричный код символа «q» ?
1) 7116
2) 8316
3) A116
4) B316
Решение:
1) в кодовой таблице ASCII (American Standard Code for Information Interchange,
американский стандартный код для обмена информацией) все заглавные
латинские буквы A-Z расставлены по алфавиту, начиная с символа с кодом
65=4116
2) все строчные латинские буквы a-z расставлены по алфавиту, начиная с символа
с кодом 97=6116
3) отсюда следует, что разница кодов букв «q» и «a» равна разнице кодов букв «Q»
и «A», то есть, 5116 – 4116=1016
4) тогда шестнадцатеричный код символа «q» равен коду буквы «a» плюс 1016
18
5) отсюда находим 6116 + 1016=7116 (ответ 1).
Задачи для самостоятельного решенияi:
1) Считая, что каждый символ кодируется одним байтом, определите, чему равен
информационный объем следующего высказывания Алексея Толстого:
Не ошибается тот, кто ничего не делает, хотя это и есть его основная
ошибка.
1) 512 бит
2) 608 бит
3) 8 Кбайт
4) 123 байта
2) Считая, что каждый символ кодируется одним байтом, определите, чему равен
информационный объем следующего высказывания Рене Декарта:
Я мыслю, следовательно, существую.
1) 28 бит
2) 272 бита 3) 32 Кбайта 4) 34 бита
3) В кодировке Unicode на каждый символ отводится два байта. Определите
информационный объем слова из двадцати четырех символов в этой кодировке.
1) 384 бита
2) 192 бита 3) 256 бит
4) 48 бит
4) Считая, что каждый символ кодируется одним байтом, оцените информационный
объем следующего предложения из пушкинского четверостишия:
Певец-Давид был ростом мал, Но повалил же Голиафа!
1) 400 бит
2) 50 бит
3) 400 байт 4) 5 байт
1) 106 бит
2) 848 бит
3) 106 Кбайт 4) 848 Кбайт
5) Автоматическое устройство осуществило перекодировку информационного
сообщения на русском языке, первоначально записанного в 8-битном коде, в 16битную кодировку Unicode. При этом информационное сообщение увеличилось на
2048 байт. Каков был информационный объем сообщения до перекодировки?
1) 1024 байт 2) 2048 бит 3) 2 Кбайта 4) 2 Мбайта
6) Считая, что каждый символ кодируется одним байтом, оцените информационный
объем следующего предложения:
Белеет Парус Одинокий В Тумане Моря Голубом!
1) 352 бита
2) 44 бита
3) 352 байта 4) 88 байт
7) Автоматическое устройство осуществило перекодировку информационного
сообщения на русском языке, первоначально записанного в 16-битном коде Unicode,
в 8-битную кодировку
КОИ-8. При этом информационное сообщение уменьшилось на 800 бит. Какова
длина сообщения в символах?
1) 50
2) 100
3) 200
4) 800
8) В таблице ниже представлена часть кодовой таблицы ASCII:
Символ
1 5 J K P j
k
Десятичный код
49 53 74 75 80 106 107
Шестнадцатеричный код 31 35 4A 4B 50 6A 6B
Каков шестнадцатеричный код символа «p» ?
1) 7016
2) 8516
3) 6F16
4) СЕ16
19
9) В таблице ниже представлена часть кодовой таблицы:
Символ
С
Т
У
Я
с
т
у
Десятичный код
145 146 147 159 225 226 227
Шестнадцатеричный код 91 92 93 9F E1 E2 E3
Каков шестнадцатеричный код символа «я» ?
1) 2A116
2) DF16
3) EF16
4) 18016
10) Автоматическое устройство осуществило перекодировку информационного
сообщения на русском языке, первоначально записанного в 16-битном коде Unicode,
в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось
на 160 бит. Какова длина сообщения в символах?
1) 10
2) 20
3) 40
4) 160
11) Автоматическое устройство осуществило перекодировку информационного
сообщения на русском языке длиной 8 символов, первоначально записанного в 16битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационный
объем сообщения уменьшился на
1) 8 байт
2) 8 бит
3) 64 байта 4) 128 бит
12) Автоматическое устройство осуществило перекодировку информационного
сообщения на русском языке, первоначально записанного в 16-битном коде Unicode,
в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось
на 240 бит. Какова длина сообщения в символах?
1) 15
2) 30
3) 60
4) 240
13) Информационный объем сообщения равен 40960 бит. Чему равен объем этого
сообщения в Кбайтах?
1) 5
2) 8
3) 32
4) 12
14) В таблице ниже представлена часть кодовой таблицы ASCII:
Символ
1 5 A B a b r
Десятичный код
49 53 65 66 97 98 114
Шестнадцатеричный код 31 35 41 42 61 62 72
Каков шестнадцатеричный код символа «R»?
1) A016
2) 7216
3) A216
4) 5216
Задание А5. Кодирование и декодирование информации (базовый уровень, время – 2
мин).
Необходимо знать:
кодирование – это перевод информации с одного языка на другой (запись в
другой системе символов, в другом алфавите)
обычно кодированием называют перевод информации с «человеческого» языка
на формальный, например, в двоичный код, а декодированием – обратный
переход
один символ исходного сообщения может заменяться одним символом нового
кода или несколькими символами, а может быть и наоборот – несколько символов
исходного сообщения заменяются одним символом в новом коде (китайские
иероглифы обозначают целые слова и понятия)
20
кодирование может быть равномерное и неравномерное; при равномерном
кодировании все символы кодируются кодами равной длины; при неравномерном
кодировании разные символы могут кодироваться кодами разной длины, это
затрудняет декодирование.
Примеры заданий ЕГЭ
Пример 1
Для кодирования букв А, Б, В, Г решили использовать двухразрядные
последовательные двоичные числа (от 00 до 11, соответственно). Если таким
способом закодировать последовательность символов БАВГ и записать
результат шестнадцатеричным кодом, то получится
1) 4B16
2) 41116 3)BACD16
4) 102316
Решение:
1) из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный
2) последовательность БАВГ кодируется так: 01 00 10 11 = 1001011
3) разобьем такую запись на тетрады справа налево и каждую тетраду переведем
в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим
все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем
1001011 = 0100 10112 = 4B16
4) правильный ответ – 1.
Пример 2
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв –
из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
A
B
C
D
E
000
01
100
10
011
Определить, какой набор букв закодирован двоичной строкой 0110100011000
1) EBCEA 2) BDDEA 3) BDCEA 4) EBAEA
Решение (вариант 1, декодирование с начала):
1) здесь используется неравномерное кодирование, при котором декодирование
может быть неоднозначным, то есть, заданному коду может соответствовать
несколько разных исходных сообщений
2) попробуем декодировать с начала цепочки, первой буквой может быть B или E,
эти случаи нужно рассматривать отдельно
3) пусть первая буква – E с кодом 011, тогда остается цепочка 0100011000
для кода 0100011000 первой буквой может быть только B с кодом 01, тогда
остается 00011000 ( начало исходной цепочки – EB?)
для кода 00011000 первой буквой может быть только A с кодом 000, тогда
остается 11000, а эта цепочка не может быть разложена на заданные коды
букв
поэтому наше предположение о том, что первая буква – E, неверно
4) пусть первая буква – B с кодом 01, тогда остается цепочка 10100011000
для кода 10100011000 первой буквой может быть только D с кодом 10, тогда
остается 100011000 (можно полагать, что начало исходной цепочки – BD?)
для кода 100011000 первой буквой может быть только С с кодом 100, тогда
остается 011000 (начало исходной цепочки – BDC?) Несмотря на то, что среди
ответов есть единственная цепочка, которая начинается с BDC, здесь нельзя
останавливаться, потому что «хвост» цепочки может «не сойтись»
21
для кода 011000 на первом месте может быть B (код 01) или E (011); в первом
случае «хвост» 1000 нельзя разбить на заданные коды букв, а во втором –
остается код 000 (буква А), поэтому исходная цепочка может быть
декодирована как BDCEA
5) правильный ответ – 3
Решение (вариант 2, декодирование с конца):
1) для кода 0110100011000 последней буквой может быть только А (код 000), тогда
остается цепочка 0110100011
2) для 0110100011 последней может быть только буква E (011), тогда остается
цепочка 0110100
3) для 0110100 последней может быть только буква C (100), тогда остается
цепочка 0110
4) для 0110 последней может быть только буква D (10), тогда остается 01 – это код
буквы B
5) таким образом, получилась цепочка BDCEA
6) правильный ответ – 3
Решение (вариант 3, кодирование ответов):
1) в данном случае самое простое и надежное – просто закодировать все ответы,
используя приведенную таблицу кодов, а затем сравнить результаты с заданной
цепочкой
2) получим
1) EBCEA – 01101100011000 2) BDDEA – 011010011000
3) BDCEA – 0110100011000
4) EBAEA – 01101000011000
3) сравнивая эти цепочки с заданной, находим, что правильный ответ – 3.
Пример 3
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г,
решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно
закодировать букву Г, чтобы длина кода была минимальной и допускалось
однозначное разбиение кодированного сообщения на буквы?
1) 1
2) 1110 3) 111
4) 11
Решение (вариант 1, метод подбора):
1) рассмотрим все варианты в порядке увеличения длины кода буквы Г
2) начнем с Г=1; при этом получается, что сообщение «10» может быть
раскодировано двояко: как ГА или Б, поэтому этот вариант не подходит
3) следующий по длине вариант – Г=11; в этом случае сообщение «110» может
быть раскодировано как ГА или В, поэтому этот вариант тоже не подходит
4) третий вариант, Г=111, дает однозначное раскодирование во всех сочетаниях
букв, поэтому…
5) … правильный ответ – 3.
Пример 4
Черно-белое растровое изображение кодируется построчно, начиная с левого
верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает
черный цвет, а 0 – белый.
22
Для компактности результат записали в шестнадцатеричной системе
счисления. Выберите правильную запись кода.
1) BD9AA5
2) BDA9B5
3) BDA9D5
4) DB9DAB
Решение:
1) «вытянем» растровое изображение в цепочку: сначала первая (верхняя) строка,
потом – вторая, и т.д.:
1 строка
2 строка
3 строка
4 строка
2) в этой полоске 24 ячейки, черные заполним единицами, а белые – нулями:
1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1
1 строка
2 строка
3 строка
4 строка
3) поскольку каждая цифра в шестнадцатеричной системе раскладывается ровно в
4 двоичных цифры, разобьем полоску на тетрады – группы из четырех ячеек (в
данном случае все равно, откуда начинать разбивку, поскольку в полоске целое
число тетрад – 6):
1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1
4) переводя тетрады в шестнадцатеричную систему, получаем последовательно
цифры B (11), D(13), A(10), 9, D(13) и 5, то есть, цепочку BDA9D5
5) поэтому правильный ответ – 3.
Задачи для самостоятельного решения:
1) Для кодирования букв А, Б, В, Г решили использовать двухразрядные
последовательные двоичные числа (от 00 до 11 соответственно). Если таким
способом закодировать последовательность символов ГБАВ и записать
результат в шестнадцатеричной системе счисления, то получится:
1) 13216
2) D216
3) 310216 4) 2D16
2) Для кодирования букв А, В, С, D используются трехразрядные
последовательные двоичные числа, начинающиеся с 1 (от 100 до 111
соответственно). Если таким способом закодировать последовательность
символов CDAB и записать результат в шестнадцатеричном коде, то получится:
1) А5216 2) 4С816 3) 15D16 4) DE516
3) Для кодирования букв К, L, М, N используются четырехразрядные
последовательные двоичные числа от 1000 до 1011 соответственно. Если таким
способом закодировать последовательность символов KMLN и записать
результат в восьмеричном коде, то получится:
1) 846138 2) 1052338
3) 123458 4) 7763258
4) Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв
– из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
а
b
с
d
е
100
110
011
01
10
Определите, какой набор букв закодирован двоичной строкой 1000110110110, если
известно, что все буквы в последовательности – разные:
1) cbade 2) acdeb 3) acbed 4) bacde
5) Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв
из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
23
А
В
С
D
Е
F
00
100
10
011
11
101
Определите, какая последовательность из 6 букв закодирована двоичной строкой
011111000101100.
1) DEFBAC
2) ABDEFC
3) DECAFB
4) EFCABD
6) Для кодирования букв А, В, С, D используются четырехразрядные
последовательные двоичные числа, начинающиеся с 1 (от 1001 до 1100
соответственно). Если таким способом закодировать последовательность
символов CADB и записать результат в шестнадцатеричном коде, то получится:
1) AF5216 2) 4CB816
3) F15D16
4) В9СА16
7) Для кодирования сообщения, состоящего только из букв А, Б, В и Г,
используется неравномерный по длине двоичный код:
А
Б
В
Г
00
11
010
011
Если таким способом закодировать последовательность символов ГАВБВГ и
записать результат в шестнадцатеричном коде, то получится:
1) 62D316
2) 3D2616
3) 3132616
4) 6213316
8) Для кодирования сообщения, состоящего только из букв А, Б, В и Г,
используется неравномерный по длине двоичный код:
А
Б
В
Г
00
11
010
011
Если таким способом закодировать последовательность символов ГАВБГВ и
записать результат в шестнадцатеричном коде, то получится:
1) DACBDC16 2) AD2616
3) 62131016
4) 62DA16
9) Для кодирования сообщения, состоящего только из букв A, B, C, D и E,
используется неравномерный по длине двоичный код:
A
B
C
D
E
000
11
01
001
10
Какое (только одно!) из четырех полученных сообщений было передано без ошибок
и может быть раскодировано:
1) 110000010011110
2) 110000011011110
3) 110001001001110
4) 110000001011110
10) Для передачи по каналу связи сообщения, состоящего только из символов А, Б,
В и Г используется посимвольное кодирование: А-00, Б-11, В-010, Г-011. Через
канал связи передается сообщение: ВАГБГВ. Закодируйте сообщение данным
кодом. Полученную двоичную последовательность переведите в
шестнадцатеричный вид.
1) AD34
2) 43DA
3) 101334
4) CADBCD
11) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г,
решили использовать неравномерный по длине код: A=0, Б=01, В=001. Как нужно
закодировать букву Г, чтобы длина кода была минимальной и допускалось
однозначное разбиение кодированного сообщения на буквы?
24
1) 0001
2) 000
3) 11
4) 101
12) Черно-белое растровое изображение кодируется построчно, начиная с левого
верхнего угла и заканчивая в правом нижнем углу. При кодировании 1
обозначает черный цвет, а 0 – белый.
Для компактности результат записали в восьмеричной системе счисления. Выберите
правильную запись кода.
1) 57414
2) 53414
3) 53412
4) 53012
13) Для передачи по каналу связи сообщения, состоящего только из символов А, Б,
В и Г используется посимвольное кодирование: А-0, Б-11, В-100, Г-011. Через
канал связи передается сообщение: ГБАВАВГ. Закодируйте сообщение данным
кодом. Полученную двоичную последовательность переведите в восьмеричный
код.
1) DBACACD 2) 75043
3) 7A23
4) 3304043
14) Для передачи по каналу связи сообщения, состоящего только из символов А, Б,
В и Г используется посимвольное кодирование: А-10, Б-11, В-110, Г-0. Через
канал связи передается сообщение: ВАГБААГВ. Закодируйте сообщение данным
кодом. Полученную двоичную последовательность переведите в
шестнадцатеричный код.
1) D3A6
2) 62032206
3) 6A3D
4) CADBAADC
Задание А14 Кодирование и обработка графической информации (повышенный уровень,
время – 1 мин).
Что нужно знать:
графическая информация может храниться в растровом и векторном форматах
векторное изображение – это набор геометрических фигур, которые можно
описать математическими зависимостями; задачи на эту тему в ЕГЭ автору пока
не встречались
растровое изображение хранится в виде набора пикселей, для каждого из
которых задается свой цвет, независимо от других
глубина цвета – это количество бит на пиксель (обычно от 1 до 24 бит на
пиксель)
в режиме истинного цвета (True Color) информация о цвете каждого пикселя
растрового изображения хранится в виде набора его RGB-составляющих (Red,
Green, Blue); каждая из RGB-составляющих – целое число (яркость) в интервале
[0,255] (всего 256 вариантов), занимающее в памяти 1 байт или 8 бит (так как
28 = 256); таким образом, на каждый пиксель отводится 3 байта = 24 бита памяти
(глубина цвета – 24 бита); нулевое значение какой-то составляющей означает, что
ее нет в этом цвете, значение 255 – максимальная яркость; в режиме истинного
цвета можно закодировать 2563 = 224 = 16 777 216 различных цветов
палитра – это ограниченный набор цветов, которые используются в изображении
(обычно не более 256); при кодировании с палитрой выбираются N любых цветов
(из полного набора 16 777 216 цветов), для каждого из них определяется RGB-код
и уникальный номер от 0 до N-1; тогда информация о цвете пикселя – это номер
его цвета в палитре; при кодировании с палитрой количество бит на 1 пиксель (K)
зависит от количества цветов в палитре N, они связаны формулой: N 2K ; объем
25
памяти на все изображение вычисляется по формуле M Q K , где K – число
бит на пиксель, а Q – общее количество пикселей
полезно знать на память таблицу степеней двойки: она показывает, сколько
вариантов N (а данном случае – сколько цветов) можно закодировать с помощью
K бит:
K, бит
1
2
3
4
5
6
7
8
9
10
N, вариантов
2
4
8
16
32
64
128 256 512 1024
цвет на Web-страницах кодируется в виде RGB-кода в шестнадцатеричной
системе: #RRGGBB, где RR, GG и BB – яркости красного, зеленого и синего,
записанные в виде двух шестнадцатеричных цифр; это позволяет закодировать
256 значений от 0 (0016) до 255 (FF16) для каждой составляющей; коды некоторых
цветов:
#FFFFFF – белый, #000000 – черный,
#CCCCCC и любой цвет, где R = G = B, – это серый разных яркостей
#FF0000 – красный, #00FF00 – зеленый,
#0000FF – синий,
#FFFF00 – желтый, #FF00FF – фиолетовый,
#00FFFF – цвет морской волны
чтобы получить светлый оттенок какого-то «чистого» цвета, нужно одинаково
увеличить нулевые составляющие; например, чтобы получить светло-красный
цвет, нужно сделать максимальной красную составляющую и, кроме этого,
одинаково увеличить остальные – синюю и зеленую: #FF9999 (сравните с
красным – #FF0000)
чтобы получить темный оттенок чистого цвета, нужно одинаково уменьшить все
составляющие, например, #660066 – это темно-фиолетовый цвет (сравните с
фиолетовым #FF00FF)
Примеры заданий ЕГЭ
Пример 1:
Для хранения растрового изображения размером 32×32 пикселя отвели 512
байтов памяти. Каково максимально возможное число цветов в палитре
изображения?
1) 256
2) 2
3)16
4) 4
Общий подход:
Решения этих задач основаны на двух формулах: M Q K и N 2K (обозначения
см. выше). Поэтому нужно:
5) найти общее количество пикселей Q
6) перевести объем памяти M в биты
7) найти количество бит на пиксель K M / Q
8) по таблице степеней двойки найти количество цветов N
Решение:
1) находим общее количество пикселей Q 32 32 25 25 210
2) находим объем памяти в битах M 512 байт 29 байт 29 23 бит 212 бит
212
3) определяем количество бит на пиксель: K 10 2 2 4 бита на пиксель
2
4) по таблице степеней двойки находим, что 4 бита позволяют закодировать 24 = 16
цветов
5) поэтому правильный ответ – 3.
26
Пример 2
Для кодирования цвета фона страницы Интернет используется атрибут
bgcolor="#ХХХХХХ", где в кавычках задаются шестнадцатеричные значения
интенсивности цветовых компонент в 24-битной RGB-модели. Какой цвет будет у
страницы, заданной тэгом <body bgcolor="#FFFFFF">?
1) белый
2) зеленый
3)красный
4) синий
Решение:
6) значение FF16 = 255 соответствует максимальной яркости, таким образом,
яркость всех составляющих максимальна, это белый цвет
7) правильный ответ – 1
Задачи для самостоятельного решения:
1) Для хранения растрового изображения размером 64 на 64 пикселя отвели 512
байт памяти. Каково максимально возможное число цветов в палитре
изображения?
1) 16
2) 2
3) 256
4) 1024
2) Для хранения растрового изображения размером 128 x 128 пикселей отвели 4
килобайт памяти. Каково максимально возможное число цветов в палитре
изображения?
1) 8
2)2
3) 16
4) 4
3) В процессе преобразования растрового графического файла количество цветов
уменьшилось с 1024 до 32. Во сколько раз уменьшился информационный объем
файла?
1) 5
2) 2
3) 3
4) 4
4) Для хранения растрового изображения размером 1024 х 512 пикселей отвели
256 Кбайт памяти. Каково максимально возможное число цветов в палитре
изображения?
1) 16
2) 64
3) 32
4) 128
5) Для хранения растрового изображения размером 128 х 128 пикселей
используется 8 Кбайт памяти. Каково максимально возможное количество
цветов в палитре данного изображения?
1) 8
2) 16
3) 32
4) 4
6) В процессе преобразования растрового графического файла количество цветов
уменьшилось с 512 до 8. Во сколько раз уменьшился информационный объем
файла?
1) 5
2) 2
3) 3
4) 4
7) После преобразования растрового 256-цветного графического файла в чернобелый формат (2 цвета) его размер уменьшился на 70 байт. Каков был размер
исходного файла?
1) 70 байт
2) 640 бит3) 80 бит
4) 560 бит
27
8) В процессе преобразования растрового графического изображения количество
цветов уменьшилось с 64 до 8. Во сколько раз уменьшился объем, занимаемый
им в памяти?
1) 2
2) 4
3) 8
4) 64
9) Сколько памяти нужно для хранения 64-цветного растрового графического
изображения размером 32 на 128 точек?
1) 32 Кбайта
2) 64 байта
3) 4096 байт
4) 3 Кбайта
10) Для кодирования цвета фона страницы Интернет используется атрибут
bgcolor="#ХХХХХХ", где в кавычках задаются шестнадцатеричные значения
интенсивности цветовых компонент в 24-битной RGB-модели. Какой цвет будет у
страницы, заданной тэгом <body bgcolor="#00FF00">?
1) белый
2) зеленый 3)красный
4) синий
11) Для кодирования цвета фона страницы Интернет используется атрибут
bgcolor="#ХХХХХХ", где в кавычках задаются шестнадцатеричные значения
интенсивности цветовых компонент в 24-битной RGB-модели. Какой цвет будет у
страницы, заданной тэгом <body bgcolor="#0000FF">?
1) белый
2) зеленый 3)красный
4) синий
12) Для кодирования цвета фона страницы Интернет используется атрибут
bgcolor="#ХХХХХХ", где в кавычках задаются шестнадцатеричные значения
интенсивности цветовых компонент в 24-битной RGB-модели. К какому цвету
будет близок цвет страницы, заданной тэгом <body bgcolor="#999999">?
1) белый
2) серый
3)желтый
4) фиолетовый
13) Для кодирования цвета фона страницы Интернет используется атрибут
bgcolor="#ХХХХХХ", где в кавычках задаются шестнадцатеричные значения
интенсивности цветовых компонент в 24-битной RGB-модели. К какому цвету
будет близок цвет страницы, заданной тэгом <body bgcolor="#992299">?
1) белый
2) серый
3)желтый
4) фиолетовый
14) Какова ширина (в пикселях) прямоугольного 64-цветного неупакованного
растрового изображения, занимающего на диске 1,5 Мбайт, если его высота
вдвое меньше ширины?
1) 256
2) 512
3) 1024
4) 2048
15) Какова ширина (в пикселях) прямоугольного 16-цветного неупакованного
растрового изображения, занимающего на диске 1 Мбайт, если его высота вдвое
больше ширины?
1) 256
2) 512
3) 1024
4) 2048
16) Какой минимальный объем памяти (в Кбайтах) необходим для хранения 4-х
страниц экранного изображения, если разрешающая способность экрана 640
480 пикселей, а количество используемых цветов равно 64?
1) 64
2) 640
3) 800
4) 900
28
29
