Дополнительные задания для подготовки. Часть вторая
Вот и обещанный в первой части анонс. Здесь мы рассмотрим другие нетривиальные задачи, рекомендуемые для подготовки к сдаче ЕГЭ.
7. Шифрование и дешифрование информации
7.1. Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код:
|
A |
B |
C |
D |
E |
|
00 |
100 |
11 |
101 |
01 |
При передачи сообщения на линии были помехи, и сообщения исказились. Известно, что лишь одно из представленных ниже четырех сообщений пришло адресату без помех. Запишите номер, под которым оно находится.
1) 100110001111
2) 100011100000
3) 111110000111
4) 100111010100
Начнем перебирать все ответы с первого по четвертый и пробовать расшифровать их. Отметим, что для представленного выше шифра выполняется условие Фано, и его можно расшифровать единственно верным способом.
Рассмотрим первый ответ. Расшифровываем слева направо: BCAEC и остается 1, а в таблице нет ни одного символа с кодом 1. Следовательно, данное сообщение пришло с помехами. Перейдем ко второму ответу. Получаем BECAA и остается 0. В таблице также нет символа с таким кодом. Следовательно, оно также пришло с помехами. Перейдем к ответ №3. При расшифровке получаем CCBAC и 1. Повторяется ситуация с ответом №1. Остается лишь 4 ответ.
Ответ: 4
Источник: Яндекс: Тренировочная работа ЕГЭ по информатике. Вариант 2
7.2. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–011, Б–000, В–11, Г–001, Д–10. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) это невозможно
2) для буквы А – 01
3) для буквы Б – 00
4) для буквы Г – 00
Будем оптимистами, и пока пропустим ответ под номером 1. Если мы сократим для буквы A длину до 01, то условие Фано будет исполняться. Следовательно, это возможно, и правильный ответ под номером 2.
Ответ: 2
7.3. Для кодирования некоторой последовательности, состоящей из букв A, B, C, D и E, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв A, B, C и D использовали такие кодовые слова: A — 00, B — 11, C — 100, D — 011.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква E. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
1) 10
2) 01
3) 000
4) 11
Рассмотрим в таблице все возможные комбинации для 1, 2 и 3 символьных кодовых слов и будем вычеркивать те, которые не удовлетворяют условию Фано для данного шифра:
|
|
001 |
|
|
010 |
|
|
|
|
|
|
|
|
101 |
|
|
110 |
|
000 |
111 |
Следовательно, подходит: 000, 001, 010, 101, 110, 111. Т.е. ответ №3.
Ответ: 3
7.4. По каналу связи передаются сообщения, содержащие только 4 буквы: Б, Р, А, T. Для кодирования букв Б, Р, А используются 6-битовые кодовые слова: Б — 000111, Р — 001000, А — 110001
Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в четырех позициях.
Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы T, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?
1) 011101
2) 010100
3) 100111
4) 111110
Первый ответ отличается от буквы Б всего лишь тремя битами. Второй – также тремя. Третий – всего одним. Остается последний, четвертый ответ.
Рассмотрим второй вариант решения задачи:
Произведем побитовую инверсию кода каждой буквы и запишем их друг над другом в таблицу:
|
Б |
1 |
1 |
1 |
0 |
0 |
0 |
|
Р |
1 |
1 |
0 |
1 |
1 |
1 |
|
А |
0 |
0 |
1 |
1 |
1 |
0 |
Исходя из таблицы, в искомом числе на первом месте слева вероятнее всего встретить 1, на втором – 1, на третьем – 1, на четвертом – 1, на 5 – 1, на 6 – 0. Такое число здесь есть под номером 4.
Ответ: 4
Источник: ЕГЭ 05.05.2015. Досрочная волна.
7.5. По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
1) А:0, Б:10, В:110, Г:111
2) А:0, Б:10, В:01, Г:11
3) А:1, Б:01, В:011, Г:001
4) А:00, Б:01, В:10, Г:11
Рассмотрим предложенные ответы. Условию Фано удовлетворяют лишь 1 и 4 (во втором А является началом B, а в третьем – Б является началом B). Обратим внимание на код под номером 1. Посчитаем, какая длина сообщения будет в этом случае: 1*16 + 2*8 + 4*3 + 4*3 = 16 + 16 + 12 + 12 = 56.
Аналогично для 4: 2*16 + 2*8 + 2*4 + 2*4 = 32 + 16 + 8 + 8 = 64.
Для первого ответа закодированное сообщение получается короче на 8 символов. Таким образом, ответ под номером 1.
Ответ: 1
7.6. По каналу связи передаются сообщения, содержащие только 3 буквы:
Р, Ц, Ы
В любом сообщении больше всего букв Ы, следующая по частоте буква − Р, затем − Ц.
Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?
1) Р – 110, Ц – 101, Ы – 001
2) Р – 10, Ц – 000, Ы – 1
3) Р – 111, Ц – 10, Ы – 0
4) Р – 1, Ц – 00, Ы – 111
Четвертый ответ не удовлетворяет условию Фано, поэтому будет рассматривать лишь первые три. Пусть количество букв Ы – x, Р – y, Ц – z. Тогда конечная в сообщении в первом случае будет:
3x + 3y + 3z символов.
Во втором – x + 2y + 3z.
В третьем – x + 3y + 2z.
Обратим внимание, что длина сообщения при использовании первого шифра будет наибольшей. Перейдем ко второму и третьем случаю. Из уравнения видно, что при x>y>z, наименьшая длина будет при использовании второго шифра.
Ответ: 2
Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Дальний Восток. Вариант 1.
7.7. Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:
А — 11010, Б — 00110, В — 10101.
При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается 'х').
Получено сообщение 00111 11110 11000 10111. Декодируйте это сообщение — выберите правильный вариант.
1) БААх
2) БААВ
3) хААх
4) хххх
Первые пять битов отличаются от кода буквы Б на 1 бит, а от отставшихся двух букв – больше, чем на бит. Следовательно, в закодированном сообщении первой была буква Б. Следующие 5 битов отличаются от кода буквы А на 1 бит, а от оставшихся двух букв – более, чем на бит, буква А. Аналогично вторым 5 битам – третьи 5 битов, буква А. Последние 5 битов отличаются от кода буквы А на 3 бита, от кода буквы Б – на 2 бита, а от кода буквы В – на 1 бит. Последняя буква – В. И код – БААВ.
Ответ: 2
Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Урал. Вариант 1.
7.8. В некоторой информационной системе информация кодируется двоичными шестиразрядными словами. При передаче данных возможны их искажения, поэтому в конец каждого слова добавляется седьмой (контрольный) разряд таким образом, чтобы сумма разрядов нового слова, считая контрольный, была чётной. Например, к слову 110011 справа будет добавлен 0, а к слову 101100 — 1.
После приёма слова производится его обработка. При этом проверяется сумма его разрядов, включая контрольный. Если она нечётна, это означает, что при передаче этого слова произошёл сбой, и оно автоматически заменяется на зарезервированное слово 0000000. Если она чётна, это означает, что сбоя не было или сбоев было больше одного. В этом случае принятое слово не изменяется.
Исходное сообщение
0100100 0001001 0011000
было принято в виде
0100110 0001100 0011000.
Как будет выглядеть принятое сообщение после обработки?
1) 0100110 0000000 0011000
2) 0000000 0001100 0011000
3) 0000000 0000000 0011000
4) 0100110 0001100 0000000
Рассмотрим первые слева 7 битов. Сумма разрядов нечетная (3), поэтому оно будет заменено на 0000000. Во вторых и третьих семи битах сумма разрядов четная, поэтому они будут переданы без изменения.
Следовательно, ответ под номером 2.
Ответ: 2
8. Проверка буквенной последовательности на соответствие алгоритму
8.1. Из букв А, Б, В, Г, Д, Е, Ё, Ж, З формируется слово. Известно, что слово сформировано по следующим правилам:
а) Первая буква слова не является согласной и в русском алфавите стоит после буквы «Е».
б) В слове две согласные буквы не стоят рядом;
Какое из следующих слов удовлетворяет всем перечисленным условиям?
1) ЗАВ
2) ЁГГА
3) ЁЖА
4) ЗБАВ
После буквы «Е» есть лишь одна гласная – «Ё». Следовательно, «Ё» – это первая буква ответа. Здесь таких ответов 2 (второй и третий). Во втором варианте стоят подряд две согласных буквы «Г». Значит, этот ответ не подходит. Остается №3.
Ответ: 3
9. Таблицы и формулы
Источник: Яндекс: Тренировочная работа ЕГЭ по информатике. Вариант 1.
9.1. В ячейке G4 электронной таблицы записана формула =D$22*$D23. Какой вид приобретет формула, после того как ячейку G4 скопируют в ячейку F3?
Примечание: знак $ используется для обозначения абсолютной адресации.
1) =C$22*$C23
2) =D$21*$D22
3) =D$21*$C23
4) =C$22*$D22
В первом выражении D изменится на C, во втором – 23 на 22. Следовательно, конечное выражение: =C$22*$D22.
Ответ: 4
Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Дальний Восток. Вариант 2.
9.2. Коле нужно с помощью электронных таблиц построить таблицу умножения чисел от 3 до 6.
Для этого сначала в диапазонах В1:Е1 и А2:А5 он записал числа от 3 до 6. Затем в ячейку Е2 записал формулу умножения, после чего скопировал её во все ячейки диапазона В2:Е5. В итоге на экране получился фрагмент таблицы умножения (см. рисунок).
|
|
A |
B |
C |
D |
E |
|
1 |
|
3 |
4 |
5 |
6 |
|
2 |
3 |
9 |
12 |
15 |
18 |
|
3 |
4 |
12 |
16 |
20 |
24 |
|
4 |
5 |
15 |
20 |
25 |
30 |
|
5 |
6 |
18 |
24 |
30 |
36 |
Какая формула была записана в ячейке Е2?
1) =А$2*$Е1
2) =А2*Е1
3) =$А2*$Е1
4) =$А2*Е$1
Заметим, что у первого множителя абсолютное значение должен принимать столбец, а у второго – строка. Таким образом, подходит только ответ 4.
Ответ: 4
10. Логические уравнения
Источник: Яндекс: Тренировочная работа ЕГЭ по информатике. Вариант 1.
10.1. Для какого из приведенных чисел X логическое условие истинно?
((X<25) → (X<23)) /\ ((X<22) →(X>21))
1) 21
2) 22
3) 23
4) 24
Конъюнкция истинна, когда каждое из выражений истинно. Рассмотрим первое.
(X<25) → (X<23) можно преобразовать в X≥25 | X<23
(X<22) →(X>21) можно преобразовать в X≥22 | X>21
Нанесем на числовую прямую и выясним, что подходят либо числа от 25 до +∞, либо 22. Из представленных ответов подходит лишь 2.
Ответ: 2
11. Массивы
Источник: Яндекс: Тренировочная работа ЕГЭ по информатике. Вариант 2.
В программе описан одномерный целочисленный массив с индексами от 0 до n (т.е. первый элемент имеет индекс 0, последний - индекс n). Ниже представлен фрагмент программы, записанный на языке программирования Pascal, обрабатывающей данный массив:
s: = n;
z: = A[0];
for i: = 1 to n do
begin
if A[i] = z then
s: = s - 1;
end
Чему будет равно значение переменной s после выполнения данной программы, при любых значениях элементов массива?
1) Количеству элементов массива A, больших первого элемента массива
2) Количеству элементов массива A, не превосходящих первого элемента массива
3) Количеству элементов массива A, не равных первому элементу массива
4) Количеству элементов массива A, равных первому элементу массива
Данный алгоритм для всех элементов массива с 1 по n проверяет, равны ли они нулевому элементу или нет. Если да, то вычитает из количества всех элементов 1. Т.е. здесь представлен поиск количества элементов массива A, не равных первому элементу.
Ответ: 3
Вывод
Задачи довольно простые, но, пожалуй, наибольшое затруднение может вызывать лишь шифрование и дешифрование.
