К.Ю. Поляков, ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, Структурные изменения 2 1)уменьшение части А (А1-А3) 2)сокращение количества задач 3)объединение простых задач (3, 6, 7, 9) Цель: оставить больше времени на решение сложных задач. 4)повышение роли части С без части С: 2014: 73 балла 2015: 70 баллов 5) язык Python 6) Вариабельность! !

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, A1: кодирование и декодирование 3 Сообщения, содержат буквы П, О, С, Т; используется двоичный код, допускающий однозначное декодирование. Кодовые слова: Т: 111, О: 0, П: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. 1 0x xx

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, A1: кодирование и декодирование 4 Сообщения содержат три гласные буквы: А, Е, И – и пять согласных букв: Б, В, Г, Д, К. Буквы кодируются префиксным кодом. Известно, что все кодовые слова для согласных имеют одну и ту же длину, и А –1, Е – 01, И – 001. Какова наименьшая возможная длина кодовых слов для согласных букв? 4: 1xx 2: 01x 1: согласных букв 3 бита 000: свободный! 6 бит

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, А2: таблица истинности 5 x1x1 x2x2 x3x3 x4x4 x5x5 x6x6 x7x7 x8x8 F )«в лоб» – подставлять в формулы… 2)если все «ИЛИ» один ноль проверяем строку, где F = 0 x 2 без инверсии, x 8 с инверсией 3)если все «И» одна единица Может ли быть иначе? ? Да! Но это не базовый уровень!

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, А3-2: табличные базы данных 6 1)сколько потомков (детей, внуков, правнуков…) у X? 2)сколько предков X есть в таблице?

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B4: системы счисления 7 Сколько единиц в двоичной записи десятичного числа 999? 1)«в лоб» – переводить… 2)999 = 1023 – 16 – = 1024 – 1 = минус две единицы: 8 519? 519 = = = плюс три единицы: 4

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B4: системы счисления 8 Укажите наименьшее число, двоичная запись которого содержит ровно три значащих нуля и три единицы. Ответ запишите в десятичной системе счисления = 35

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B4: системы счисления 9 Какое из указанных ниже чисел может быть записано в двоичной системе счисления в виде 1xxx10, где x может означать как 0, так и 1? 1) 74 2) 38 3) 60 4) 47 1) = 34 N = 62 2)1xxx10 делится на 2 3)1xxx10 не делится на 4

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B5: весовые матрицы графов 10 ABC D EF Z A46 30 B3 C 1127 D47 10 E4 8 F5 2 Z29 1)матрица несимметричная (орграф) 2)две дороги с односторонним движением 3)«сколько есть дорог проходящих через N пунктов?» 4)«… не менее, чем через N пунктов?»

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B6-1: автомат 11 Вход: четырёхзначное число. 1. Складываются первая и последняя, а также вторая и третья цифры исходного числа. 2. Полученные два числа записывают в порядке убывания. Пример. Исходное число: Суммы: = 9; = 8. Результат: 98. Укажите наименьшее число, в результате обработки которого автомат выдаст число = =

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B12: адресация в сетях 12 IP-адрес Адрес сети Чему равен третий слева байт маски? *.*.112.* *.* = = маска: = не забываем про старшие единицы!

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B14: Чертёжник 13 сместиться на (–3, –3) ПОВТОРИ N РАЗ сместиться на (a, b) сместиться на (27, 12) КОНЕЦ ПОВТОРИ сместиться на (–22, -17) 1)наименьшее N > 1 2)наибольшее N 3)все возможные N 1)наименьшее N > 1 2)наибольшее N 3)все возможные N N = общий делитель(25,20)

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B15: количество путей в графах 14 А Б В Г Д Е Ж И К Л Сколько существует различных путей из города А в город Л, не проходящих через B?

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B15: количество путей в графах 15 А Б В Г Д Е Ж И К Л Сколько существует различных путей из города А в город Л, проходящих через Д?

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B16: системы счисления 16 Сколько единиц содержится в двоичной записи числа ( –1) · ( )? ( –1) · ( ) = ( –1) · ( ) = ( –1) · ( ) –1 = – –1 = – =

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B16: системы счисления 17 Сколько единиц содержится в двоичной записи значения числа – – 17? = = = 32 – 15 = 2 5 – – – – – – =

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B17: запросы в поисковых системах 18 Запрос Страниц США | Япония | Китай 450 Япония | Китай 260 (США & Япония) | (США & Китай)50 США? A = США B = Япония | Китай Запрос Страниц А | B450 B260 А & B50 A? N А | B = N A + N B – N A & B N A = 450 – =

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B18: логические операции, множества 19 P = [37; 60] и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что выражение тождественно истинно, то есть равно 1 при любом значении переменной х. 40 x

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B18: логические операции, множества 20 Множество А: натуральные числа. Выражение истинно при любом значении х. Определите наименьшее возможное значение суммы элементов множества A. (x {2, 4, 6, 8, 10, 12}) (((x {4, 8, 12, 116}) ¬(x A)) ¬(x {2, 4, 6, 8, 10, 12})) = 24

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B19: обработка массивов 21 Массив с индексами от 0 до 9. c:= 0; for i:= 1 to 9 do if A[i-1] < A[i] then begin c:= c + 1; t:= A[i]; A[i]:= A[i-1]; A[i-1]:= t end; Какое значение будет иметь переменная «c»? перестановка пары при сортировке пузырьком

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B19: обработка массивов ) ) ) ) ) ) с = 6

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B19: обработка массивов 23 Массив с индексами от 0 до 10. s:=0; n:=10; for i:=0 to n-2 do begin s:=s+A[i]-A[i+2] end; В массиве находились трёхзначные натуральные числа. Какое наибольшее значение может иметь «s»? s:=A[0]-A[2]+A[1]-A[3]+A[2]-... +A[6]-A[8]+A[7]-A[9]+A[8]-A[10] max = – 100 – 100 =

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B20: циклы и условия 24 Укажите наименьшее пятизначное число x, при котором будет напечатано сначала 6, а потом 3. a := 0; b := 10; readln(x); while x > 0 do begin y := x mod 10; x := x div 10 if y > a then a := y; if y < b then b := y; end; writeln(a); writeln(b); { максимальная цифра } { минимальная цифра }

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, B21: циклы и процедуры 25 Найдите число различных значений k, при которых программа выдаёт тот же ответ, что и при k = 36. function f(n: longint): longint; begin f:= n*(n-1)+10 end; … readln(k); i:= 0; while f(i) < k do i:= i + 1; writeln(i); if(i) Останов: f(i)>= k 31 … 40 10

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, C24: исправление ошибок 26 Считывается натуральное число x, выводится количество значащих цифр в его двоичной записи. readln(x); c:= 0; while x > 0 do begin c:= c + x mod 2; x:= x div 10 end; writeln(c) Что считает? ? Когда работает верно? ?

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, С27: сложная задача на программирование 27 Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8. Количество элементов последовательности не превышает Задача А (2 балла). O(N 2 ) по времени, O(N) по памяти. Задача Б (3 балла). O(N) по времени, O(N) по памяти. Задача Б (4 балла). O(N) по времени, O(1) по памяти.

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, С27: сложная задача на программирование 28 Задача А (2 балла). Данные хранятся в массиве. var N: integer; a: array[ ] of integer; i, j, max: integer; begin readln(N); for i:=1 to N do read(a[i]); max:= 0; for i:= 9 to N do for j:= 1 to i-8 do if a[j]*a[i] > max then max := a[j]*a[i]; writeln(max) end. var N: integer; a: array[ ] of integer; i, j, max: integer; begin readln(N); for i:=1 to N do read(a[i]); max:= 0; for i:= 9 to N do for j:= 1 to i-8 do if a[j]*a[i] > max then max := a[j]*a[i]; writeln(max) end.

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, С27: сложная задача на программирование 29 Задача Б (3 балла). Данные в массиве, время O(N). ii-8 m a[i] накапливать! max:= 0; m:= 0; for i:= 9 to N do begin if a[i-8] > m then m := a[i-8]; if m*a[i] > max then max := m*a[i]; end; max:= 0; m:= 0; for i:= 9 to N do begin if a[i-8] > m then m := a[i-8]; if m*a[i] > max then max := m*a[i]; end;

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, С27: сложная задача на программирование 30 Задача Б (4 балла). Память O(1), время O(N). i-8 x var a: array[1..8] of integer; храним в массиве for i:=1 to 8 do read(a[i]); Начальное заполнение массива: Продвижение: for i:=1 to 7 do a[i]:=a[i+1]; a[8]:= x; for i:=1 to 7 do a[i]:=a[i+1]; a[8]:= x; i Это очередь! !

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, С27: сложная задача на программирование 31 Задача Б (4 балла). Память O(1), время O(N). const d = 8; { сдвиг }... { уже прочитали первые d штук } max:= 0; m:= 0; for i:=d+1 to N do begin read(x); if a[1] > m then m:= a[1]; if m*x > max then max:= m*x; for j:=1 to d-1 do a[j]:= a[j+1]; a[d]:= x; end; const d = 8; { сдвиг }... { уже прочитали первые d штук } max:= 0; m:= 0; for i:=d+1 to N do begin read(x); if a[1] > m then m:= a[1]; if m*x > max then max:= m*x; for j:=1 to d-1 do a[j]:= a[j+1]; a[d]:= x; end; a[1]x

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, С27: сложная задача на программирование 32 Задача Б (4 балла). Без сдвига (очередь-кольцо) N-1 0 i aa[i mod d]:= data[i]; for i:=0 to d-1 do read(a[i]); for i:=d to N-1 do begin read(x); k:= i mod d; if a[k] > m then m := a[k]; if m*x > max then max := m*x; a[k]:=x; end; for i:=d to N-1 do begin read(x); k:= i mod d; if a[k] > m then m := a[k]; if m*x > max then max := m*x; a[k]:=x; end; 9101 k 1212

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, Выводы 33 Вариабельность! !

ЕГЭ по информатике: 2015 и далее… К.Ю. Поляков, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ 163, г. Санкт-Петербург