Разбор заданий ЕГЭ базового уровня сложности (2014 год)

Разбор заданий базового уровня сложности, вызвавших наибольшие затруднения у выпускников 2014 г.

Чернышова Е.И.,

учитель информатики МБОУ СОШ№10 г.Хабаровска

ЕГЭ по информатике 2014 года

Всего 32 задания, из них:

• 15 заданий базового уровня,
• 13 заданий повышенного уровня,
• 4 задания высокого уровня

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

Примерный интервал выполнения заданий базового уровня был определен в 60%-90%

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

Примерный интервал выполнения заданий базового уровня был определен в 60%-90%

Наиболее трудные задания

• А9 (умение кодировать информацию с использованием неравномерного кода)  B1 в 2015 году
• В4 (знания о методах измерения количества информации)  B10 в 2015 году
• В6 (умение исполнить рекурсивный алгоритм)  B11 в 2015 году

Пример задания А9

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.

Вот этот код: А — 00, Б — 01, В — 100, Г — 101, Д — 110.

Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.

Выберите правильный вариант ответа:

• для буквы Д — 11;
• это невозможно;
• для буквы Г — 10;
• для буквы Д — 10.

Немного теории

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

Немного теории

• Условие Фано. Никакое кодовое слово не совпадает с началом другого кодового слова.
• Коды, для которых выполняется условие Фано, называют префиксными. Все сообщения, закодированные с помощью префиксных кодов, декодируются однозначно.
• “ обратное” условие Фано : никакое кодовое слово не совпадает с окончанием другого кодового слова. Коды, для которых выполняется обратное условие Фано, называют постфиксными . В этом случае тоже обеспечивается однозначное декодирование.

• Подробнее читайте:
• http://kpolyakov.narod.ru/download/inf-2012-11b.pdf

Решение задачи А9

• Можно заметить, что код префиксный — для него выполняется условие Фано: ни один из трехбитных кодов не начинается ни с 00 (код А), ни с 01 (код Б). Поэтому сообщения, закодированные с помощью такого кода, декодируются однозначно.
• А — 00, Б — 01, В — 100, Г — 101, Д — 110.

А — 00, Б — 01, В — 100, Г — 101, Д — 110.

Варианты ответов:

• для буквы Д — 11;
• это невозможно;
• для буквы Г — 10;
• для буквы Д — 10.

• Проверим, что получится, если сократить код буквы Д до 11 (вариант 1).

Свойство однозначной декодируемости может быть потеряно только тогда, когда в результате такого сокращения нарушится условие Фано, то есть код буквы Д совпадет с началом какого-то другого кодового слова. Видим, что этого не произошло — нет других кодовых слов, которые начинаются с 11, поэтому вариант 1 — это и есть верное решение

А — 00, Б — 01, В — 100, Г — 101, Д — 110.

Еще пример задания А9

• По каналу связи передаются сообщения, содержащие только 4 буквы: С, Л, О, Н; для передачи используется двоичный код, допускающий однозначное декодирование.
• Для букв С, О, Н используются такие кодовые слова:

С: 011, О: 00, Н: 11.

Укажите такое кодовое слово для буквы Л, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите тот, у которого меньшая длина. 

• 1) 1
• 2) 10
• 3) 010
• 4) 0

2

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

Пример задания А9

  По каналу связи передаются сообщения, содержащие только 4 буквы: Е, Н, О, Т.

В любом сообщении больше всего букв О, следующая по частоте буква − Е, затем − Н. Буква Т встречается реже, чем любая другая.

Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать? 

1) Е−0, Н−1, O−00, Т−11

2) O−1, Н−0, Е−01,Т−10

3) Е−1, Н−01, O−001, Т−000

4) О−0, Н−11, Е−101, Т−100

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

4

Пример задания В4

Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы.

Вот начало списка:

1. КККК

2. КККЛ

3. КККР

4. КККТ ……

Запишите слово, которое стоит под номером 67.

Решение задачи В4

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

выполним замену К  0, Л  1, Р  2, Т  3; поскольку нумерация слов начинается с единицы,

а первое число КККК  0000 равно 0,

под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 1002 4

Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.

Ответ: ЛККР.

Пример задания В4

Все 4-буквенные слова, составленные из букв М, А, Р, Т, записаны в алфавитном порядке. 

Вот начало списка:

1. АААА

2. АААМ

3. АААР

4. АААТ

5. ААМА

……

Запишите слово, которое стоит на 250-м месте от начала списка.

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

ТТРМ

Еще пример задания В4

  Все 5-буквенные слова, составленные из букв В, Е, К, Н, О, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 

1. ВВВВВ

2. ВВВВЕ

3. ВВВВК

4. ВВВВН

5. ВВВВО

6. ВВВЕВ

Под каким номером стоит первое из слов, которое начинается с буквы О?

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

2501

Задание В6 немного теории

• рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа
• чтобы определить рекурсию, нужно задать

• условие остановки рекурсии (базовый случай или несколько базовых случаев) рекуррентную формулу
• условие остановки рекурсии (базовый случай или несколько базовых случаев)
• рекуррентную формулу

• любую рекурсивную процедуру можно запрограммировать с помощью цикла

1 Чему равно значение функции F(5)? В ответе запишите только натуральное число. " width="640"

Пример задания В6

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (n + 2), при n 1

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

1 тогда F(2) = 1 * 4 =4 F(3) = 4 * 5 = 20 F(4) = 20 * 6 = 120 F(5) = 120 * 7 = 840. Следовательно ответ 840. " width="640"

Решение задания В6

Посчитаем по порядку каждое F(n):

F(1) = 1

F(n) = F(n–1) * (n + 2), при n 1

тогда

F(2) = 1 * 4 =4

F(3) = 4 * 5 = 20

F(4) = 20 * 6 = 120

F(5) = 120 * 7 = 840.

Следовательно ответ 840.

1. Чему равно значение функции  F (12)? В ответе запишите только натуральное число. Правильный ответ 4095 " width="640"

Пример задания В6

Алгоритм вычисления значения функции  F ( n ), где  n  — натуральное число, задан следующими соотношениями:

F (1) = 1

F ( n ) =  F ( n –1) + 2 n –1  , если  n   1.

Чему равно значение функции  F (12)?

В ответе запишите только натуральное число.

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

4095

2.   Чему равно значение функции  F (6)?  В ответе запишите только натуральное число. 45 Правильный ответ " width="640"

Еще пример задания В6

  Алгоритм вычисления значения функции  F ( n ), где  n  — натуральное число, задан следущими соотношениями: 

F ( n ) = n + 4 при  n  =

F ( n ) =  F ( n  − 1) +  F ( n  − 2) при  n   2.

  Чему равно значение функции  F (6)? 

В ответе запишите только натуральное число.

45

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

Еще пример задания В6

• Процедура F(n), где n – натуральное число, задана следующим образом (язык Паскаль):
• procedure F(n: integer);
• begin
• if n
• write('*')
• else begin
• F(n-1);
• F(n-2);
• F(n-2)
• end;
• end;
• Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число.

Решение

для n (то есть, для 1 и 2) функция выводит одну звездочку

F (1) = F (2) = 1

а для бóльших n имеем рекуррентную формулу

F(n) = F(n-1) + F(n-2) + F(n-2)=

= F(n-1) + 2 *F(n-2)

запишем в таблицу базовые случаи

заполняем таблицу, используя рекуррентную формулу:

0 then begin F(n-2); F(n div 2) end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? Правильный ответ 21 " width="640"

Еще пример задания В6

• Дан рекурсивный алгоритм:
• procedure F(n: integer);
• begin
• writeln('*');
• if n 0 then begin
• F(n-2);
• F(n div 2)
• end
• end ;
• Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

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

21

Использованные ресурсы

http://kpolyakov.spb.ru/school/ege.htm

http://inf.reshuege.ru/?redir=1

http://fipi.ru/ege-i-gve-11/analiticheskie-i-metodicheskie-materialy