Обзор и решение заданий ЕГЭ по информатике

B1 (базовый уровень, время – 1 мин)

Тема : Кодирование текстовой информации. Кодировка ASCII. Основные кодировки кириллицы.

Что нужно знать :

• все символы кодируются одинаковым числом бит [1] (алфавитный подход)
• чаще всего используют кодировки, в которых на символ отводится 8 бит (8-битные) или 16 бит (16-битные)
• при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 Кбайт) –
• 1024 байта, в мегабайте (1 Мбайт) – 1024 Кбайта [2]
• после знака препинания внутри (не в конце!) текста ставится пробел
• чтобы найти информационный объем текста I , нужно умножить количество символов N на число бит на символ K :

• две строчки текста не могут занимать 100 Кбайт в памяти
• при кодировании текста каждому символу ставится в соответствие свой код
• символы-цифры в кодовой таблице идут подряд в порядке возрастания, от «0» до «9» (символ «0» имеет код 48, символ «9» – код 57)
• большие (прописные) латинские буквы в кодовой таблице идут подряд в алфавитном порядке от «A» до «Z»
• маленькие (строчные) латинские буквы в таблице кодировки идут подряд в алфавитном порядке, от «a» до «z»
• в большинстве кодовых таблиц (но не во всех!) русские буквы, как заглавные, так и строчные, также расположены по алфавиту (за исключением буквы «Ё»)

Ещё пример задания:

Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке длиной в 20 символов, первоначально записанного в

2-байтном коде Unicode, в 8-битную кодировку КОИ-8. На сколько бит уменьшилась длина сообщения? В ответе запишите только число.

Решение :

• при 16-битной кодировке объем сообщения – 16*20 бит
• когда его перекодировали в 8-битный код, его объем стал равен– 8*20 бит
• таким образом, сообщение уменьшилось на 16*20 – 8*20 = 8*20 = 160 бит
• Ответ: 160 бит.

Возможные ловушки и проблемы :

• нужно внимательно читать, в каких единицах требуется записать ответ
• нужно внимательно читать, в каких единицах требуется записать ответ

[1] В самом деле, есть кодировки с переменным количеством бит на символ, например, кодировка UTF -8 , но они не изучаются в школе.

[2] Чаще всего килобайт обозначают «Кб», а мегабайт – «Мб», но в демо-тестах ЕГЭ разработчики привели именно такие обозначения.

Ещё пример задания:

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

16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит.

Какова длина сообщения в символах?

Решение :

• обозначим количество символов через N
• при 16-битной кодировке объем сообщения – 16* N бит
• когда его перекодировали в 8-битный код, его объем стал равен– 8* N бит
• таким образом, сообщение уменьшилось на 16* N – 8* N = 8* N = 480 бит
• отсюда находим N = 480/8 = 60 символов.

Ещё пример задания:

Определите информационный объем текста в битах

Бамбарбия! Кергуду!

Решение :

• в этом тексте 19 символов (обязательно считать пробелы и знаки препинания)
• если не дополнительной информации, считаем, что используется 8-битная кодировка (чаще всего явно указано, что кодировка 8- или 16-битная)
• поэтому в сообщении 19*8 = 152 бита информации

B 2 (базовый уровень, время – 4 мин)

Тема : Поиск алгоритма минимальной длины для исполнителя.

Что нужно знать :

каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором

вариантов, просто его нужно организовать оптимальным образом

исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать

и выполнять некоторые команды

Пример задания:

У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 3

2. умножь на 4

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

команд в

программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.

(Например, программа 21211 это программа

умножь на 4

прибавь 3

умножь на 4

прибавь 3

прибавь 3

которая преобразует число 2 в 50.)

B3 (базовый уровень, время – 3 мин)

Тема : Анализ программы.

Что нужно знать :

• основные конструкции языка программирования:

• объявление переменных оператор присваивания оператор вывода циклы
• объявление переменных
• оператор присваивания
• оператор вывода
• циклы

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

-ого элемента арифметической прогрессии:

• формулу для вычисления суммы первых
• формулу для вычисления суммы первых

членов арифметической прогрессии:

1024 для достижения этого значения переменную s нужно 103 раза увеличить на 10, поэтому цикл выполнится 103 раза так как k – это счётчик шагов цикла, конечное значение k будет равно 103 Ответ: 103. v ar k, s: integer; begin s:=0; k:=0; while s begin s:=s+10; k:=k+1; end; write(k); end . Возможные ловушки и проблемы :" width="640"

Пример задания:

Определите, что будет напечатано в результате работы следующего фрагмента программы:

Решение:

• из программы видно, что начальные значения переменных k и s равны нулю
• цикл заканчивается, когда нарушается условие s , то есть количество шагов цикла определяется изменением переменной s
• после окончания цикла выводится значение переменной k
• таким образом, задача сводится к тому, чтобы определить число шагов цикла, необходимое для того, чтобы значение s стало не меньше 1024
• с каждым шагом цикла значение s увеличивается на 10, а значение k – на единицу, так что фактически k – это счётчик шагов цикла
• поскольку s увеличивается на 10, конечное значение s должно быть кратно 10, то есть это 1030 1024
• для достижения этого значения переменную s нужно 103 раза увеличить на 10, поэтому цикл выполнится 103 раза
• так как k – это счётчик шагов цикла, конечное значение k будет равно 103
• Ответ: 103.

v ar k, s: integer;

begin

s:=0;

k:=0;

while s begin

s:=s+10;

k:=k+1;

end;

write(k);

end .

Возможные ловушки и проблемы :

• можно перепутать переменную, которая выводится на экран (внимательно смотрим на оператор вывода)

B4 (базовый уровень, время – 2 мин)

Тема : Анализ последовательностей, системы счисления.

Что нужно знать :

русский алфавит

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

Пример задания:

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

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

Решение (2 способ, троичная система, идея М. Густокашина):

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

выпишем начало списка, заменив буквы на цифры:

1. 00000

2. 00001

3. 00002

4. 00010

……

это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д.

тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления

переведем 239 в троичную систему: 239 = 222123

заменяем обратно цифры на буквы: 22212  УУУОУ

Ответ: УУУОУ.

B5 (базовый уровень, время – 2 мин)

Тема : Представление данных в электронных таблицах в виде диаграмм и графиков.

Что нужно знать :

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

адрес ячейки в электронных таблицах состоит из имени столбца и следующего за ним номера строки, например, C15

формулы в электронных таблицах начинаются знаком = («равно»)

знаки +, –, *, / и ^ в формулах означают соответственно сложение, вычитание, умножение, деление и возведение в степень

в заданиях ЕГЭ могут использоваться стандартные функции СУММ (сумма), СРЗНАЧ (среднее значение), МИН (минимальное значение), МАКС (максимальное значение)

запись B2:C4 означает диапазон, то есть, все ячейки внутри прямоугольника, ограниченного ячейками B2 и C 4; например, с помощью формулы =СУММ(B2:C4) вычисляется сумма значений ячеек B2, B3, B4, C2, C3 и C4

1

A

B

2

3

C

=( C 1+ A 1)/2

D

= C 1– D 1

3

2

= A 1– D 1

=B1/2

Пример задания:

Дан фрагмент электронной таблицы:

Какое число должно быть записано в ячейке B1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:D2 соответствовала рисунку:

Решение:

• прежде всего, нужно понять, что мы видим круговую диаграмму, которая строится по одному ряду данных и показывает доли частей в чем-то целом
• по диаграмме находим, что первая часть составляет половину целого, а остальные три равны, каждая составляет по одной шестой (в 3 раза меньше, чем первая).
• вычислим значения во второй строке, которые уже можно найти по исходным данным:

1

A

2

3

B

C

3

D

3

1

2

1

=B1/2

• единственная неизвестная ячейка (зависящая от B1 ) – это D2 , содержащая формулу B1/2
• как мы узнали из диаграммы (п. 2), значение одной (первой) ячейки должно быть в 3 раза больше каждой из
• оставшихся, поэтому в D2 должно быть
• число 1; это возможно только при B1 = 2
• ответ: 2.

B 6 (базовый уровень, время – 2 мин)

Тема : Оператор присваивания в языке программирования [1] .

Что нужно знать :

• переменная – это величина, которая имеет имя, тип и значение; переменная может изменяться во время выполнения программы
• оператор присваивания служит для записи значения в переменную
• если в переменную записывают новое значение, старое стирается
• знаки + , - , * , / используются для обозначения операций сложения, вычитания, умножения и деления
• запись вида a div b означает результат целочисленного деления a на b (остаток отбрасывается)
• запись вида a mod b означает остаток от деления a на b
• запись вида a := b + 2*c + 3; означает «вычислить значения выражения справа от знака присваивания := и записать результат в переменную a »; при этом
• значения других переменных (кроме a ) не изменяются
• для многократного выполнения одинаковых операций используют циклы;
• цикл с переменной выполняется N раз, в этом примере переменная i принимает последовательно все значения от 1 до N с шагом 1

for i:=1 to N do begin

{ что-то делаем }

end ;

• цикл с условием выполняется до тех пор, пока условие в заголовке цикла не нарушится;

while { условие } do begin

{ что-то делаем }

end ;

• главная опасность при использовании цикла с условием – зацикливание ; эта такая ситуация, когда цикл работает бесконечно долго из-за того, что условие все время остается
• истинным

Пример задания:

Определите значение переменной c после выполнения следующего фрагмента программы.

a := 5;

a := a + 6;

b := –a;

c := a – 2*b;

0 do begin L:=L+1; if M M:=x mod 10; end; x:= x div 10; end; writeln(L); write(M); end." width="640"

B7 (повышенный уровень, время – 6 мин)

Тема : Анализ программы, содержащей подпрограммы, циклы и ветвления.

Что нужно знать :

• операции целочисленного деления ( div ) и взятия остатка ( mod )
• как работают операторы присваивания, циклы и условные операторы в языке программирования

Пример задания:

Ниже записана программа. Получив на вход число

, эта программа печатает два числа,

и

. Укажите наибольшее из таких чисел

, при вводе которых алгоритм печатает сначала 3, а потом 7.

var x, L, M: integer;

begin

readln(x);

L:=0; M:=0;

while x 0 do begin

L:=L+1;

if M

M:=x mod 10;

end;

x:= x div 10;

end;

writeln(L); write(M);

end.

Решение :

для решения задачи необходимо понять, что делает эта программа, если это не видно сразу,

можно выполнить ручную прокрутку для какого-то простого числа,

например, для числа 251:

• можно догадаться, что в результате работы программы в переменной L окажется число цифр числа,
• а в переменной M – наибольшая цифра, но это предположение нужно постараться доказать
• нужно вспомнить (и запомнить), что для целого числа

остаток от деления на 10 ( x   mod   10 ) – это последняя цифра в десятичной записи числа, а целочисленное

деление ( x   div   10 ) отсекает последнюю цифру, то есть из 123 получается 12

итак, по условию задачи фактически требуется найти наибольшее трехзначное число со старшей

цифрой 7; очевидно, что это 777.

ответ: 777.

Решение:

• выделим в заданных больших числах степени двойки и переведем размер файла в биты, чтобы «согласовать» единицы измерения:

128000 бит/c = 128 · 1000 бит/с = 2 7 · 125 · 8 бит/с = 2 7 · 5 3 · 2 3 бит/с = 2 10 · 5 3 бит/с

625 Кбайт = 5 4  Кбайт = 5 4 · 2 13 бит

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

• таким образом, ответ – 40 с .

Возможные проблемы :

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

255) таким образом, верный ответ – ГБВА. Возможные проблемы :" width="640"

Пример задания:

Петя записал IP-адрес школьного сервера на листке бумаги и положил его в карман куртки.

Петина мама случайно постирала

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

фрагментами IP-адреса.

Эти фрагменты обозначены буквами А, Б, В и Г. Восстановите IP-адрес. В ответе укажите

последовательность букв,

обозначающих фрагменты, в порядке, соответствующем IP-адресу.

Решение:

• самое главное – вспомнить, что каждое из 4-х чисел в IP-адресе должно быть в интервале от 0 до 255
• поэтому сразу определяем, что фрагмент А – самый последний, так как в противном случае одно из чисел получается больше 255 (643 или 6420)
• фрагмент Г (число 20) может быть только первым, поскольку варианты 3.1320 и 3.13320 дают число, большее 255
• из фрагментов Б и В первым должен быть Б, иначе получим 3.1333.13 (1333 255)
• таким образом, верный ответ – ГБВА.

Возможные проблемы :

• если забыть про допустимый диапазон 0..255, то может быть несколько «решений» (все, кроме одного – неправильные)
• если забыть про допустимый диапазон 0..255, то может быть несколько «решений» (все, кроме одного – неправильные)

B 12 (повышенный уровень, время – 2 мин)

Тема : Составление запросов для поисковых систем с использованием логических выражений.

Что нужно знать :

таблицы истинности логических операций «И», «ИЛИ», «НЕ» (см. презентацию «Логика»)

если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ»

логическое произведение A ∙ B ∙ C ∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)

логическая сумма A + B + C +… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

правила преобразования логических выражений (законы алгебры логики):

Пример задания:

В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц,

которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ | ,

а для логической операции «И» – &.

1) принтеры & сканеры & продажа

2) принтеры & сканеры

3) принтеры | сканеры

4) принтеры | сканеры | продажа

B 13 (повышенный уровень, время – 7 мин)

Тема : Анализ дерева решений.

Что нужно знать :

уметь строить дерево решений

уметь искать одинаковые числа в списке

уметь считать разные числа в списке

Пример задания:

У исполнителя Калькулятор две команды:

1. прибавь 3,

2. вычти 2.

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).

Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?

Решение (3 способ, Л.В. Зенцова, лицей № 36 ОАО "РЖД" г.Иркутска):

для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения

поэтому существует всего 6 возможных программ, состоящих ровно из 5 команд (с точностью до перестановки): 11111 11112 11122 11222 12222 22222

Ответ: 6.

B 14 (повышенный уровень, время – 6 мин)

Тема : Анализ программы с подпрограммами.

Пример задания:

Определите, какое число будет напечатано в результате выполнения следующего алгоритма:

Var a,b,t,M,R :integer;

Function F(x:integer):integer;

begin

F:=4*(x-1)*(x-3);

end;

BEGIN

a:=-20; b:=20;

M:=a; R:=F(a);

for t:=a to b do begin

if (F(t)

M:=t;

R:=F(t);

end;

end;

write(M);

END.

B 15 (высокий уровень, время – 10 мин)

Тема : Преобразование логических выражений.

Сколько различных решений имеет логическое уравнение

X1 → X 2 → X 3 → X 4 → X 5 → X 6 = 1