Подготовка к егэ по информатике онлайн. Онлайн тесты гиа по информатике

Для решения этой задачи нам потребуется сделать несколько логических умозаключений, поэтому "следите за руками".

От нас хотят, чтобы мы нашли минимальное целое неотрицательное А, при котором выражение всегда истинно.
Что из себя представляет выражение в целом? Что-то там импликация что-то там в скобках.
Давайте вспомним таблицу истинности для импликации:
1 => 1 = 1
1 => 0 = 0
0 => 1 = 1
0 => 0 = 1
Значит, возможно три варианта, когда это будет истинно. Рассматривать все эти три варианта — это убиться и не жить. Давайте подумаем, можем ли мы пойти "от противного ".
Давайте вместо того, чтобы искать А, попробуем найти x, при котором это выражение ложно.
То есть, возьмём некоторое число А (пока не знаем какое, просто какое-то). Если вдруг мы найдём такое x, при котором всё высказывание ложно, значит, выбранное А — плохое (потому что в условии требуется, чтобы всегда выражение было истинным)!
Таким образом мы сможем получить какие-то ограничение на число А.
Итак, давайте пойдём от противного и вспомним, когда импликация бывает ложной? Когда первая часть истинна, а вторая — ложна.
Значит
\((\mathrm{x}\&25\neq 0)= 1 \\ (\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
Что означает, что \((x\&25\neq 0) = 1\) ? Это означает, что действительно \(\mathrm{x}\&25\neq 0\) .
Давайте переведём 25 в двоичную. Получим: 11001 2 .
Какие ограничения это накладывает на x? Раз не равно нулю, значит, при поразрядной конъюнкции должна где-то получиться единица. Но где она может быть? Только там, где в 25 уже есть единица!
Значит, в числе x хотя бы в одном кресте должна быть единица: XX**X.
Отлично, теперь рассмотрим второй множитель: \((\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
Это выражение из себя также представляет импликацию. При этом оно так же ложно.
Значит, его первая часть обязана быть истинной, а вторая — ложной.
Значит
\((\mathrm{x}\&17=0) = 1 \\ ((\mathrm{x}\&\mathrm{A}\neq 0) = 0) = 0\)
Что означает, что \(\mathrm{x}\&17=0\) ? То, что на всех местах, где в 17 стоят единицы, в x должны стоять нули (иначе в результате не получится 0).
Переведём 17 в двоичную: 10001 2 . Значит, в x на последнем с конца и на 5 с конца месте должны стоять нули.
Но стоп, мы же в пункте 13 получили, что на последнем ИЛИ на 4 с конца ИЛИ на 5 с конца должна быть единица.
Раз согласно строке 19 на последнем или 5 с конца местах единицы быть не может, значит, она обязана быть на 4 с конца месте.
То есть, если мы хотим, что при нашем x всё выражение было ложным, на 4 с конца месте обязана стоять единица: XX...XX1XXX 2 .
Отлично, рассмотрим теперь последнее условие: \((\mathrm{x}\&\mathrm{A}\neq 0) = 0\) . Что это означает?
Это означает, что неверно, что \(\mathrm{x}\&\mathrm{A}\neq 0\) .
То есть, на самом деле, \(\mathrm{x}\&\mathrm{A}=0\) .
Что мы знаем про x? Что на 4 с конца месте там единица. Во всём остальном x может быть практически любым.
Если мы хотим, чтобы исходное выражение в условии задачи было всегда истинным, то мы не должны найти х, который бы удовлетворял всем условиям. Ведь, действительно, если бы мы нашли такой x, получилось бы, что исходное выражение не всегда истинно, что противоречит условию задачи.
Значит, вот это самое последнее условие просто обязано не выполняться.
А как оно может не выполняться? Если только мы будем уверены на 100%, что при поразрядной конъюнкции где-то останется единица.
И это возможно: если в А тоже на 4 месте с конца будет единица, то в результате поразрядной конъюнкции на 4 с конца месте останется единица.
Какое минимально возможное двоичное число имеет единицу на 4 с конца месте? Очевидно, что 1000 2 . Значит, это число и будет ответом.
Осталось только перевести его в десятичную: \(1000_2=0\times 2^0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3=8\)

Ответ: минимально возможное A, удовлетворяющее условиям, равно 8 .

Евгений Смирнов

Эксперт в IT, учитель информатики

Решение №2

Можно предложить несколько более короткий подход. Обозначим наше высказывание как F = (A->(B->C)), где А - это высказывание "Х&25 не равно 0", В= "Х&17=0" и C="X&A не равно 0".

Раскроем импликации, пользуясь известным законом X->Y = не(Х) ИЛИ Y, получим F = A -> (не(В) ИЛИ C) = не(А) ИЛИ не(B) ИЛИ С. Распишем также двоичные значения констант 25 и 17:

Наше выражение - логическое ИЛИ от трёх высказываний:

1) не(А) - это значит, X&25 = 0 (биты 0,3,4 числа Х все равны 0)

2) не(B) - значит, X&17 не равно 0 (биты 0 и 4 числа Х хотя бы один равен 1)

3) C - знаит, X&A не равно 0 (биты, задаваемые маской A, хотя бы 1 равен 1)

Х - произвольное число. Все его биты независимы. Поэтому требовать выполнения какого-то условия на биты произвольного числа можно только в одном единственном случае - когда речь идёт об одной и той же маске (наборе битов). Мы можем заметить, что двоичная маска 17 - почти то же самое, что и 25, только не хватает бита номер 3. Вот если бы дополнить 17 битом номер 3, то выражение (не(В) ИЛИ С) превратилось бы в не(неА), т.е. в А = (X&25 не равно 0). По-другому: допустим, А=8 (бит 3=1). Тогда требование (не(В) B или С) равносильно требованию: (Хотя бы один из битов 4,0 равен 1) ИЛИ (бит 3 равен 1) = (хотя бы один из битов 0,3,4 не равен 1) - т.е. инверсия не(А) = А = (Х&25 не равно 0).

В итоге мы заметили, что если А=8, то наше выражение принимает вид F = не(А) ИЛИ А, что, по закону исключённого третьего, всегда тождественно истинно. При других, меньших, значениях А независимость от значения Х получить не удаётся, т.к. маски выходят разные. Ну, а при наличии в старших битах А единиц в битах выше 4 ничего не меняется, т.к. в остальных масках у нас нули. Получается, что только при А=8 формула превращается в тавтологию для произвольного Х.

Дмитрий Лисин

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

Структурные изменения в 2015-2016

2
Структурные изменения в 2015-2016
1) удаление части А
2) сокращение количества задач
3) объединение простых задач (4, 6, 7, 9)
Цель: оставить больше времени на решение
сложных задач.
4) язык Python
!
К.Ю. Поляков, 2015
Вариабельность!
http://kpolyakov.spb.ru

ЕГЭ по информатике: 2016 и далее…
3

Сколько единиц в двоичной записи
шестнадцатеричного числа 12F016.
1
2
12 102
F
11112
0
1+1+4=6
Укажите наименьшее число, двоичная запись которого
содержит ровно три значащих нуля и три единицы.
Ответ запишите в десятичной системе счисления
1000112 = 35
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B1: двоичная система счисления

ЕГЭ по информатике: 2016 и далее…
4
B1: двоичная система счисления

числа 1025?
1) «в лоб» – переводить…
2) 1025 = 1024 + 1
1024 = 100000000002
1025 = 100000000012
Ответ: 2
511?
511 = 512 - 1
= 10000000002 - 1 = 1111111112
Ответ: 9
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B1: двоичная система счисления

ЕГЭ по информатике: 2016 и далее…
5
B1: двоичная система счисления
Сколько единиц в двоичной записи десятичного
числа 999?
1) «в лоб» – переводить…
2) 999 = 1023 – 16 – 8
1023 = 1024 – 1 = 11111111112
минус две единицы: 8
519?
519 = 512 + 7
512 = 10000000002
7 = 1112
плюс три единицы: 4
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B1: системы счисления

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

B2: логические функции

ЕГЭ по информатике: 2016 и далее…
7
B2: логические функции
x1
1
!
x2
0
x3
x4
0
1
x5
x6
x7
x8
1
1
F
0
1
1
Все варианты – простые И или ИЛИ!
1) «в лоб» – подставлять в формулы…
2) если все «ИЛИ» один ноль
проверяем строку, где F = 0
x2 без инверсии, x8 с инверсией
3) если все «И» одна единица
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B2: логические функции

ЕГЭ по информатике: 2016 и далее…
8
B2: логические функции
Задана таблица функции z x x

?z
0
0
0
0
1
1
1
1
?y
0
0
1
1
0
0
1
1
К.Ю. Поляков, 2015
?x
0
1
0
1
0
1
0
1
F
0
1
0
1
0
0
0
1
y.
z x x y
x (z y)
x 0 F 0
x 1
z 1
F 0
y 0
Ответ: zyx
http://kpolyakov.spb.ru

B2: логические функции

ЕГЭ по информатике: 2016 и далее…
9
B2: логические функции
Задана таблица функции x y z x
Определите, в каких столбцах x, y и z.
?z
0
0
0
0
1
1
1
1
?x
0
0
1
1
0
0
1
1
К.Ю. Поляков, 2015
?y
0
1
0
1
0
1
0
1
F
0
0
1
0
1
1
1
1
y z.
x y z x y z
z 0 F x y
z 1 F x y x y
(x x) (y x) y
y x y 1
z 0
x 1 Ответ: zxy
F 1
y 0
http://kpolyakov.spb.ru

B3: весовые матрицы графов

ЕГЭ по информатике: 2016 и далее…
10
B3: весовые матрицы графов
A
A
B
C
D
E
F
Z
B
4
C
6
3
D
E
F
11
4
5
7
4
Z
30
27
10
8
2
29
1) матрица несимметричная (орграф)
2) две дороги с односторонним движением
3) «сколько есть дорог проходящих через N
пунктов?»
4) «… не менее, чем через N пунктов?»
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B3: весовые матрицы графов

ЕГЭ по информатике: 2016 и далее…
11
B3: весовые матрицы графов
1
1
2
2
3
45
4
5
6
6
45
55
3
15 60
2
10 40
15
20 35
4
55
2
55 60 20 55
35
45
45
Е
А
5
2
степени
вершин
К.Ю. Поляков, 2015
Д
2
40
7
Б
7
10
3
4
5
К
В
степень 4
степень 5
Г
Ответ: 20
http://kpolyakov.spb.ru

B4-1: табличные базы данных

ЕГЭ по информатике: 2016 и далее…
12
B4-1: табличные базы данных
1) сколько потомков (детей, внуков, правнуков…) у X?
2) сколько предков X есть в таблице?
3) найдите дедушку по материнской линии
23
24
25
К.Ю. Поляков, 2015
34
57
35
42
http://kpolyakov.spb.ru

ЕГЭ по информатике: 2016 и далее…
13

Сообщения, содержат буквы П, О, С, Т; используется
двоичный код, допускающий однозначное
декодирование. Кодовые слова:
Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при
котором код будет допускать однозначное
декодирование. Если таких кодов несколько, укажите
код с наименьшим числовым значением.
1
0
0x 10
0xx
О
11
101
П
К.Ю. Поляков, 2015
0
0
110
1
1
1
0
1
Т
http://kpolyakov.spb.ru

B5: кодирование и декодирование

ЕГЭ по информатике: 2016 и далее…
14
B5: кодирование и декодирование
Сообщения содержат три гласные буквы: А, Е, И – и пять
согласных букв: Б, В, Г, Д, К. Буквы кодируются
префиксным кодом. Известно, что все кодовые слова для
согласных имеют одну и ту же длину, и
А –1, Е – 01, И – 001.
Какова наименьшая возможная длина кодовых слов для
согласных букв?
0
5 согласных букв 3 бита 4 бита 5 бит
4: 1xx
0
1
2: 01x
0
1
А
1: 001
1
Е
свободны: 000
000x 000xx
1
2
4
И
К.Ю. Поляков, 2015
6 бит
000xxx
8
http://kpolyakov.spb.ru

B6-1: автомат

ЕГЭ по информатике: 2016 и далее…
15
B6-1: автомат
чётность восстановлена!
Вход: натуральное число N.
1. В конец двоичной записи дописывается бит чётности
(сумма цифр mod 2).
2. К полученной строке дописывается ещё бит чётности.
Укажите наименьшее число, для которого в результате
выполнения этого алгоритма получится число
больше 125.
!
На шаге 2 добавляется 0 2!
Должны получить чётное = 126 или 128
После div 2 должна сохраниться чётность!
126 / 2 = 63 = 1111112: – 6 единиц, чётность
Ответ:
К.Ю. Поляков, 2015
31
http://kpolyakov.spb.ru

B10: комбинаторика

ЕГЭ по информатике: 2016 и далее…
16
B10: комбинаторика
Сколько есть 5-буквенных слов, в которых есть только
буквы П, И, Р, причём буква П появляется ровно 1 раз.
П****
*П***
**П**
***П*
****П
К.Ю. Поляков, 2015
24 = 16 слов
Ответ: 16· 5 = 80.
http://kpolyakov.spb.ru

B12: адресация в сетях

ЕГЭ по информатике: 2016 и далее…
17
B12: адресация в сетях
IP-адрес 224.128.112.142
Адрес сети 224.128.64.0.
Чему равен третий слева байт маски?
не забываем про
*.*.112.*
старшие единицы!
*.*.64.0
маска: 110000002 = 192
192
112 = 011100002
64 = 010000002
!
К.Ю. Поляков, 2015
Поразрядная конъюнкция!
http://kpolyakov.spb.ru

B12: адресация в сетях

ЕГЭ по информатике: 2016 и далее…
18
B12: адресация в сетях
IP-адрес 111.81.208.27
Адрес сети 111.81.192.0.
Каково минимальное значение третьего слева
байта маски?
*.*.208.*
*.*.192.0
208 =
192 =
маска:
маска:
110100002
110000002
111000002
110000002
192
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B14: Чертёжник

ЕГЭ по информатике: 2016 и далее…
19
B14: Чертёжник
сместиться на (–3, –3) 1)
ПОВТОРИ N РАЗ
2)
сместиться на (a, b) 3)
сместиться на (27, 12) 4)
КОНЕЦ ПОВТОРИ
сместиться на (–22, -7)
3 N x 22 0
3 N y 7 0
наименьшее N > 1
наибольшее N
все возможные N
сумма всех N
N x 25
N y 10
N = общий делитель(25,10)
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B14: Редактор

ЕГЭ по информатике: 2016 и далее…
20
B14: Редактор
1) заменить(v,w)
2) нашлось(v)
ПОКА нашлось (222) ИЛИ нашлось (888)
ЕСЛИ нашлось (222)
ТО заменить (222, 8)
ИНАЧЕ заменить (888, 2)
Каков результат обработки строки 88888…8 ?
888888888…8
2 2 2
8
К.Ю. Поляков, 2015
!
За 4 шага
убрали
8 восьмёрок!
68 - 8·8 = 4
68
8888 28
http://kpolyakov.spb.ru

ЕГЭ по информатике: 2016 и далее…
21

города А в город Л, не проходящих через B?
Д
Б
Ж
В
А
Г
К.Ю. Поляков, 2015
И
Е
Л
К
http://kpolyakov.spb.ru

B15: количество путей в графах

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

B16: системы счисления

ЕГЭ по информатике: 2016 и далее…
23
B16: системы счисления
Сколько единиц содержится в двоичной
(троичной, …) записи числа X?
10N = 100…0
10N-1 = 99…9
N
N
2N = 100…02
N
3N = 100…03
N
К.Ю. Поляков, 2015
2N-1 = 11…1
N
3N-1 = 22…2
N
http://kpolyakov.spb.ru

B16: системы счисления

ЕГЭ по информатике: 2016 и далее…
24
B16: системы счисления
2N – 2M = 2M · (2N-M – 1)
= 100…02 · 11…12
N-M
M
= 11…100…02
N-M
К.Ю. Поляков, 2015
M
http://kpolyakov.spb.ru

B16: системы счисления

ЕГЭ по информатике: 2016 и далее…
25
B16: системы счисления

числа (24400–1)·(42200+2)?
(24400–1)·(42200+2) = (24400–1)·(24400+1+1)
= (24400–1)·(24400+1) + 24400–1
= 28800 – 1 + 24400–1
= 28800 + 24400 – 21
1
4399
1 + 4399 = 4400
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B16: системы счисления

ЕГЭ по информатике: 2016 и далее…
27
B16: системы счисления
Сколько единиц содержится в двоичной записи
значения числа 8148 – 4123 + 2654 – 17?
8148 = 2444
4123 = 2246
2654
17 = 16 + 1
= 24 + 2 0
2654 + 2444 – 2246 – 24 – 20
444 – 2246 – 24 – 20
2
1
444 – 2
1 + 444 – 2 = 443
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B16: системы счисления

ЕГЭ по информатике: 2016 и далее…
28
B16: системы счисления
Сколько двоек содержится в троичной записи
значения числа 9118 + 3123 – 27?
9118 = 3236
27 = 33
К.Ю. Поляков, 2015
3236 + 3123 – 33
1
120 двоек
http://kpolyakov.spb.ru

B16: системы счисления

B17: запросы в поисковых системах

ЕГЭ по информатике: 2016 и далее…
30
P = и Q = . Укажите наименьшую
возможную длину такого отрезка A, что выражение
(x P) (((x Q) (x A)) (x P))
тождественно истинно, то есть равно 1 при любом
значении переменной х.
P (x P),
Q (x Q),
A (x A)
P (Q A P)
P (Q A P)
P Q A P P Q A
P Q A
P
Q
К.Ю. Поляков, 2015
P
37
40
60
77
x
20
Q
http://kpolyakov.spb.ru

B18: логические операции, множества

ЕГЭ по информатике: 2016 и далее…
31

Множество А: натуральные числа. Выражение
(x {2, 4, 6, 8, 10, 12}) → (((x {4, 8, 12, 116})
¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12}))
истинно при любом значении х. Определите
наименьшее возможное значение суммы элементов
множества A.
P x {2, 4, 6, 8, 10, 12},
Q x {4, 8, 12, 116},
A x A
P (Q A P)
P Q A
Amin P Q P Q {4, 8, 12}
К.Ю. Поляков, 2015
= 24
http://kpolyakov.spb.ru

B18: логические операции, множества

ЕГЭ по информатике: 2016 и далее…
32
B18: логические операции, множества

(x & 49 <> 0) ((x & 33 = 0) (x & A <> 0))

P x & 49 0,
A x & A 0
P (Q A)
Q x & 33 0,
P (Q A) P Q A
P Q A (P Q) A
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B18: логические операции, множества

ЕГЭ по информатике: 2016 и далее…
33
B18: логические операции, множества
"&" – побитовая конъюнкция (И). Выражение
(x & 49 <> 0) ((x & 33 = 0) (x & A <> 0))
истинно при любом натуральном х. Определите
наименьшее возможное значение A.
x & 49
номер бита
5 4 3 2 1 0
49 = 110001
X = abcdef
X & 49 = ab000f
x & 49 = 0 все биты {5, 4, 0} нулевые
x & 49 <>
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B18: логические операции, множества

ЕГЭ по информатике: 2016 и далее…
34
B18: логические операции, множества
"&" – побитовая конъюнкция (И). Выражение
(x & 49 <> 0) ((x & 33 = 0) (x & A <> 0))
истинно при любом натуральном х. Определите
наименьшее возможное значение A.
(P Q) A
P: x & 49 <> 0 среди битов {5, 4, 0} есть ненулевые
Q: x & 33 = 0 все биты {5, 0} нулевые
номер бита
5 4 3 2 1 0
33 = 100001
!
?
Бит 4 ненулевой!
К.Ю. Поляков, 2015
Что из этого следует?
Amin = 24 = 16
http://kpolyakov.spb.ru

B18: логические операции, множества

ЕГЭ по информатике: 2016 и далее…
35
B18: логические операции, множества
"&" – побитовая конъюнкция (И). Выражение
(x & A <> 0) ((x & 20 = 0) (x & 5 <> 0))
истинно при любом натуральном х. Определите

P x & 20 0,
A x & A 0
A (P Q)
Q x & 5 0,
A (P Q) A P Q
P Q A (P Q) A
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B18: логические операции, множества

ЕГЭ по информатике: 2016 и далее…
36
B18: логические операции, множества
"&" – побитовая конъюнкция (И). Выражение
(x & A <> 0) ((x & 20 = 0) (x & 5 <> 0))
истинно при любом натуральном х. Определите
наибольшее возможное значение A.
(P Q) A
P: x & 20 = 0 все биты {4, 2} нулевые
Q: x & 5 = 0 все биты {2, 0} нулевые
!
Биты {4, 2, 0} в x нулевые!
Amax = 24 + 22 + 20 = 21
К.Ю. Поляков, 2015
Они обнулят
биты числа
при &!
http://kpolyakov.spb.ru

B18: логические операции, множества

ЕГЭ по информатике: 2016 и далее…
37
B19: обработка массивов

c:= 0;
for i:= 1 to 9 do
if A < A[i] then begin
c:= c + 1;
t:= A[i];
перестановка пары
A[i]:= A; при сортировке
A:= t
пузырьком
end;

К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B19: обработка массивов

ЕГЭ по информатике: 2016 и далее…
38
B19: обработка массивов
1)
2)
3)
4)
5)
6)
6
9
9
9
9
9
9
9
6
7
7
7
7
7
7
7
6
6
6
6
6
2
2
2
2
2
2
2
1
1
1
5
5
5
5
5
5
5
1
1
1
1
0
0
0
0
3
3
3
3
3
3
3
0
4
4
4
4
4
4
4
0
8
8
8
8
8
8
8
0
с=6
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B19: обработка массивов

ЕГЭ по информатике: 2016 и далее…
39
B19: обработка массивов
Массив с индексами от 0 до 9.
c:= 0;
for i:= 1 to 9 do
if A[i] < A then begin
c:= c + 1;
t:= A[i];
A[i]:= A;
перестановка пары
A:= t
end;
Какое значение будет иметь переменная «c»?
4 7 3 8 5 0 1 2 9 6
4 7 3 8 5 0 1 2 9 6
4 7 3 8 5 0 1 2 9 6
К.Ю. Поляков, 2015
с=2
http://kpolyakov.spb.ru

B19: обработка массивов

ЕГЭ по информатике: 2016 и далее…
40
B19: обработка массивов

s:=0;
n:=10;
for i:=0 to n-1 do begin
s:=s+A[i]-A
end;

s:=A-A+A-A+A-...
+A-A+A-A+A-A
max = 999 – 100 = 899
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B19: обработка массивов

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

B19: обработка массивов

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

B20: циклы и условия («узнай алгоритм»)

ЕГЭ по информатике: 2016 и далее…
43
B20: циклы и условия
Укажите наименьшее число x, большее 100, при котором
будет напечатано 26.
var x, L, M: integer;
begin
x нечётное: НОД(x,65) = 26
readln(x);
x чётное: НОД(x,52) = 26
L:= x; M:= 65;
if L mod 2 = 0 then x делится на 26,
M:= 52;
не делится на 52!
while L <> M do
НОД(104,52) = 52
104
if L > M then
L:= L - M
Ответ: 130
else
M:= M – L;
writeln(M);
Алгоритм Евклида!
end.
!
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B20: циклы и условия

ЕГЭ по информатике: 2016 и далее…
44
B21: циклы и процедуры

begin
i
f(i)
f:= n*(n-1)+10
1
10
end;
…
2
12
readln(k);
3
16
i:= 0;
4
22
while f(i) < k do
5
30
36
i:= i + 1;
writeln(i);
6
40
Останов: k <= f(i)
31 … 40
10
К.Ю. Поляков, 2015
?
Для k = 30?
23 … 30
8
http://kpolyakov.spb.ru

B21: циклы и процедуры

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

B21: циклы и процедуры

ЕГЭ по информатике: 2016 и далее…
46
B21: циклы и процедуры
Найдите наименьшее значение k, при котором
программа выдаёт тот же ответ, что и при k = 10.
def f(n):
Останов:
return n*n*n
f(i-1) < g(k) <= f(i)
def g(n):
(i-1)3 < 2k+3 <= i3
return 2*n+3
3 < 23 <= i3
k=10:
(i-1)
k = int(input())
i=3
i = 1
while f(i) < g(k):
8 < 2k+3 <= 27
i+=1
3 … 12
print (i)
Ответ: 3
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

B21: циклы и процедуры

ЕГЭ по информатике: 2016 и далее…
47
B22: программы для исполнителей
1) прибавь 1
2) умножь на 2
Сколько существует программ, для которых из числа 2
получается число 29 и при этом траектория вычислений
содержит число 14 и не содержит числа 25?
N нечётное
K N 1
Рекуррентная формула: K N
K N 1 K N / 2 N чётное
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
1
1
2
2
3
3
5
5
7
7
10
10
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
13
13
13
13
13
13
13
13
13
13
13
0
0
0
13
13
новый старт
К.Ю. Поляков, 2015
сюда нельзя
http://kpolyakov.spb.ru

B22: программы для исполнителей

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

C24: исправление ошибок

ЕГЭ по информатике: 2016 и далее…
49
C24: исправление ошибок
Нужно написать программу, которая выводит на экран
максимальную цифру числа, кратную 3. Если в числе нет
цифр, кратных 3, требуется на экран вывести «NO».
-1
readln(N);
maxDigit:= N mod 10;
Когда работает
while N > 0 do begin
верно?
digit:= N mod 10;
if digit mod 3 1)=последняя
0 then цифра делится на 3
if digit > maxDigit
then
2) последняя
цифра меньше, чем
maxDigit:= нужный
digit;результат
N:= N div 10;
-1
end;
if maxDigit = 0 then writeln("NO")
else writeln(maxDigit);
?
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

C24: исправление ошибок

ЕГЭ по информатике: 2016 и далее…
50

Для заданной последовательности неотрицательных
целых чисел необходимо найти максимальное
произведение двух её элементов, номера которых
различаются не менее чем на 8. Количество элементов
последовательности не превышает 10000.
Задача А (2 балла). O(N2) по времени, O(N) по памяти.
Задача Б (3 балла). O(N) по времени, O(N) по памяти.
Задача Б (4 балла). O(N) по времени, O(1) по памяти.
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

ЕГЭ по информатике: 2016 и далее…
51
С27: сложная задача на программирование
Задача А (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:= -1;
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
http://kpolyakov.spb.ru

С27: сложная задача на программирование

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

С27: сложная задача на программирование

ЕГЭ по информатике: 2016 и далее…
53
С27: сложная задача на программирование

i-8
i
храним в массиве
var a: array of integer;
x
Начальное заполнение массива:
for i:=1 to 8 do read(a[i]);
Продвижение:
for i:=1 to 7 do
a[i]:=a;
a:= x;
К.Ю. Поляков, 2015
!
Это очередь!
http://kpolyakov.spb.ru

С27: сложная задача на программирование

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

С27: сложная задача на программирование

ЕГЭ по информатике: 2016 и далее…
55
С27: сложная задача на программирование
Задача Б (4 балла). Без сдвига (очередь-кольцо).
i 0
1
2
3
9
1
5
6
7
k
0
a
4
10
2 11
3 12
4 5
8
9
N-1
10 11 12 13 14 15 16 17 18
7
6
7
8
a:= 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;
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

С27: сложная задача на программирование

ЕГЭ по информатике: 2016 и далее…
56
С27: сложная задача на программирование
Вычислить максимальное чётное произведение двух
показаний, между моментами передачи которых
прошло не менее 8 минут.
x
поддерживаем
1) максимальное из всех
2) максимальное чётное
x
чётное чётное * любое
чётное любое * чётное
К.Ю. Поляков, 2015
храним в массиве
(очередь)
http://kpolyakov.spb.ru

С27: сложная задача на программирование

ЕГЭ по информатике: 2016 и далее…
57
С27: сложная задача на программирование
for i:=d to N-1 do begin
read(x);
k:= i mod d;
максимальное
чётное
if a[k] > m then m:= a[k];
if ((a[k] mod 2 = 0) and
(a[k] > mEven)) then mEven:= a[k];
if x mod 2 = 1 then begin
получено
нечётное
if mEven*x > max then
max:= mEven*x;
end
получено
чётное
else
if m*x > max then max:= m*x;
a[k]:=x;
end;
К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

С27: сложная задача на программирование

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

Выводы

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

К.Ю. Поляков, 2015
http://kpolyakov.spb.ru

Для выпускников школ. Его нужно сдавать тем, кто планирует поступать в вузы на самые перспективные специальности, такие как информационная безопасность, автоматизация и управление, нанотехнологии, системный анализ и управление, ракетные комплексы и космонавтика, ядерные физика и технологии и многие другие.

Ознакомьтесь с общей информацией об экзамене и приступайте к подготовке. Изменений по сравнению с прошлым годом в новом варианте КИМ ЕГЭ 2019 практически нет. Единственное, что из заданий исчезли фрагменты программ, написанных на языке Си: их заменили на фрагменты, написанные на языке С++. И еще из задания № 25 убрали возможность написать в качестве ответа алгоритм на естественном языке.

Оценка ЕГЭ

В прошлом году чтобы сдать ЕГЭ по информатике хотя бы на тройку, достаточно было набрать 42 первичных балла. Их давали, например, за правильно выполненные первые 9 заданий теста.

Как будет в 2019 году пока точно неизвестно: нужно дождаться официального распоряжения от Рособрнадзора о соответствии первичных и тестовых баллов. Скорее всего оно появится в декабре. Учитывая, что максимальный первичный балл за весь тест остался прежним, скорее всего не изменится и минимальный балл. Ориентируемся пока на эти таблицы:

Структура теста ЕГЭ

Информатика – это самый продолжительный экзамен (столько же длится ЕГЭ по математике и литературе), длительность составляет 4 часа.

В 2019 году тест состоит из двух частей, включающих в себя 27 заданий.

Часть 1: 23 задания (1–23) с кратким ответом, который является числом, последовательностью букв или цифр.
Часть 2: 4 задания (24–27) с развернутым ответом, полное решение заданий записывается на бланке ответов 2.

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

Подготовка к ЕГЭ

Пройдите тесты ЕГЭ онлайн бесплатно без регистрации и СМС. Представленные тесты по своей сложности и структуре идентичны реальным экзаменам, проводившимся в соответствующие годы.

Скачайте демонстрационные варианты ЕГЭ по информатике, которые позволят лучше подготовиться к экзамену и легче его сдать. Все предложенные тесты разработаны и одобрены для подготовки к ЕГЭ Федеральным институтом педагогических измерений (ФИПИ). В этом же ФИПИ разрабатываются все официальные варианты ЕГЭ.
Задания, которые вы увидите, скорее всего, не встретятся на экзамене, но будут задания, аналогичные демонстрационным, по той же тематике или просто с другими цифрами.

Общие цифры ЕГЭ

Год	Миним. балл ЕГЭ	Средний балл	Кол-во сдававших	Не сдали, %	Кол-во 100-балльников	Длитель- ность экзамена, мин.
2009	36
2010	41	62,74	62 652	7,2	90	240
2011	40	59,74	51 180	9,8	31	240
2012	40	60,3	61 453	11,1	315	240
2013	40	63,1	58 851	8,6	563	240
2014	40	57,1				235
2015	40	53,6				235
2016	40					235
2017	40					235
2018

Государственная итоговая аттестация 2019 года по информатике для выпускников 9 класса общеобразовательных учреждений проводится с целью оценки уровня общеобразовательной подготовки выпускников по данной дисциплине. Основные проверяемые в тестировании элементы содержания из раздела информатики:

Умение оценивать количественные параметры информационных объектов.
Умение определять значение логического выражения.
Умение анализировать формальные описания реальных объектов и процессов.
Знание о файловой системе организации данных.
Умение представлять формульную зависимость в графическом виде.
Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд.
Умение кодировать и декодировать информацию.
Умение исполнить линейный алгоритм, записанный на алгоритмическом языке.
Умение исполнить простейший циклический алгоритм, записанный на алгоритмическом языке.
Умение исполнить циклический алгоритм обработки массива чисел, записанный на алгоритмическом языке.
Умение анализировать информацию, представленную в виде схем.
Умение осуществлять поиск в готовой базе данных по сформулированному условию.
Знание о дискретной форме представления числовой, текстовой, графической и звуковой информации.
Умение записать простой линейный алгоритм для формального исполнителя.
Умение определять скорость передачи информации.
Умение исполнить алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки.
Умение использовать информационно-коммуникационные технологии.
Умение осуществлять поиск информации в Интернете.
Умение проводить обработку большого массива данных с использованием средств электронной таблицы или базы данных.
Умение написать короткий алгоритм в среде формального исполнителя или на языке программирования.

Даты сдачи ОГЭ по информатике 2019 года:
4 июня (вторник), 11 июня (вторник) .

Изменения структуры и содержания экзаменационной работы 2019 года по сравнению с 2018 годом отсутствуют .

В данном разделе вы найдёте онлайн тесты, которые помогут вам подготовиться к сдаче ОГЭ (ГИА) по информатике. Желаем успехов!

Стандартный тест ОГЭ (ГИА-9) формата 2019-го года по информатике и ИКТ содержит две части. Первая часть содержит 18 заданий с кратким ответом, вторая часть содержит 2 задания, которые необходимо выполнить на компьютере. В связи с этим в данном тесте представлена только первая часть (первые 18 заданий). Согласно текущей структуре экзамена, среди этих 18 заданий варианты ответов предлагаются только в 6 первых заданиях. Однако для удобства прохождения тестов администрация сайта сайт приняла решение предложить для каждого задания варианты ответов. Однако для заданий, в которых варианты ответов составителями реальных контрольно измерительных материалов (КИМ) не предусмотрены, мы решили значительно увеличить количество этих вариантов ответов для того, чтобы максимально приблизить наш тест к тому, с чем Вам придется столкнуться в конце учебного года.

Стандартный тест ОГЭ (ГИА-9) формата 2018-го года по информатике и ИКТ содержит две части. Первая часть содержит 18 заданий с кратким ответом, вторая часть содержит 2 задания, которые необходимо выполнить на компьютере. В связи с этим в данном тесте представлена только первая часть (первые 18 заданий). Согласно текущей структуре экзамена, среди этих 18 заданий варианты ответов предлагаются только в 6 первых заданиях. Однако для удобства прохождения тестов администрация сайта сайт приняла решение предложить для каждого задания варианты ответов. Однако для заданий, в которых варианты ответов составителями реальных контрольно измерительных материалов (КИМ) не предусмотрены, мы решили значительно увеличить количество этих вариантов ответов для того, чтобы максимально приблизить наш тест к тому, с чем Вам придется столкнуться в конце учебного года.

Стандартный тест ОГЭ (ГИА-9) формата 2018-го года по информатике и ИКТ содержит две части. Первая часть содержит 18 заданий с кратким ответом, вторая часть содержит 2 задания, которые необходимо выполнить на компьютере. В связи с этим в данном тесте представлена только первая часть (первые 18 заданий). Согласно текущей структуре экзамена, среди этих 18 заданий варианты ответов предлагаются только в 6 первых заданиях. Однако для удобства прохождения тестов администрация сайта сайт приняла решение предложить для каждого задания варианты ответов. Однако для заданий, в которых варианты ответов составителями реальных контрольно измерительных материалов (КИМов) не предусмотрены, мы решили значительно увеличить количество этих вариантов ответов для того, чтобы максимально приблизить наш тест к тому, с чем Вам придется столкнуться в конце учебного года.

Стандартный тест ОГЭ (ГИА-9) формата 2017-го года по информатике и ИКТ содержит две части. Первая часть содержит 18 заданий с кратким ответом, вторая часть содержит 2 задания, которые необходимо выполнить на компьютере. В связи с этим в данном тесте представлена только первая часть (первые 18 заданий). Согласно текущей структуре экзамена, среди этих 18 заданий варианты ответов предлагаются только в 6 первых заданиях. Однако для удобства прохождения тестов администрация сайта сайт приняла решение предложить для каждого задания варианты ответов. Однако для заданий, в которых варианты ответов составителями реальных контрольно измерительных материалов (КИМов) не предусмотрены, мы решили значительно увеличить количество этих вариантов ответов для того, чтобы максимально приблизить наш тест к тому, с чем Вам придется столкнуться в конце учебного года.

Стандартный тест ОГЭ (ГИА-9) формата 2016-го года по информатике и ИКТ содержит две части. Первая часть содержит 18 заданий с кратким ответом, вторая часть содержит 2 задания, которые необходимо выполнить на компьютере. В связи с этим в данном тесте представлена только первая часть (первые 18 заданий). Согласно текущей структуре экзамена, среди этих 18 заданий варианты ответов предлагаются только в 6 первых заданиях. Однако для удобства прохождения тестов администрация сайта сайт приняла решение предложить для каждого задания варианты ответов. Однако для заданий, в которых варианты ответов составителями реальных контрольно измерительных материалов (КИМов) не предусмотрены, мы решили значительно увеличить количество этих вариантов ответов для того, чтобы максимально приблизить наш тест к тому, с чем Вам придется столкнуться в конце учебного года.

Стандартный тест ОГЭ (ГИА-9) формата 2015-го года по информатике и ИКТ содержит две части. Первая часть содержит 18 заданий с кратким ответом, вторая часть содержит 2 задания, которые необходимо выполнить на компьютере. В связи с этим в данном тесте представлена только первая часть (первые 18 заданий). Согласно текущей структуре экзамена, среди этих 18 заданий варианты ответов предлагаются только в 6 первых заданиях. Однако для удобства прохождения тестов администрация сайта сайт приняла решение предложить для каждого задания варианты ответов. Однако для заданий, в которых варианты ответов составителями реальных контрольно измерительных материалов (КИМов) не предусмотрены, мы решили значительно увеличить количество этих вариантов ответов для того, чтобы максимально приблизить наш тест к тому, с чем Вам придется столкнуться в конце учебного года.

При выполнении задания 1-18 выберите только один правильный ответ.

При выполнении задания 1-8 выберите только один правильный ответ.

СПЕЦИФИКАЦИЯ
контрольных измерительных материалов
единого государственного экзамена 2016 года
по информатике и ИКТ

1. Назначение КИМ ЕГЭ

Единый государственный экзамен (далее - ЕГЭ) представляет собой форму объективной оценки качества подготовки лиц, освоивших образовательные программы среднего общего образования, с использованием заданий стандартизированной формы (контрольных измерительных материалов).

ЕГЭ проводится в соответствии с Федеральным законом от 29.12.2012 № 273-ФЗ «Об образовании в Российской Федерации».

Контрольные измерительные материалы позволяют установить уровень освоения выпускниками Федерального компонента государственного стандарта среднего (полного) общего образования по информатике и ИКТ, базовый и профильный уровни.

Результаты единого государственного экзамена по информатике и ИКТ признаются образовательными организациями среднего профессионального образования и образовательными организациями высшего профессионального образования как результаты вступительных испытаний по информатике и ИКТ.

2. Документы, определяющие содержание КИМ ЕГЭ

3. Подходы к отбору содержания, разработке структуры КИМ ЕГЭ

Содержание заданий разработано по основным темам курса информатики и ИКТ, объединенных в следующие тематические блоки: «Информация и ее кодирование», «Моделирование и компьютерный эксперимент», «Системы счисления», «Логика и алгоритмы», «Элементы теории алгоритмов», «Программирование», «Архитектура компьютеров и компьютерных сетей», «Обработка числовой информации», «Технологии поиска и хранения информации».
Содержанием экзаменационной работы охватывается основное содержание курса информатики и ИКТ, важнейшие его темы, наиболее значимый в них материал, однозначно трактуемый в большинстве преподаваемых в школе вариантов курса информатики и ИКТ.

Работа содержит как задания базового уровня сложности, проверяющие знания и умения, предусмотренные стандартом базового уровня, так
и задания повышенного и высокого уровней сложности, проверяющие знания и умения, предусмотренные стандартом профильного уровня. Количество заданий в варианте КИМ должно, с одной стороны, обеспечить всестороннюю проверку знаний и умений выпускников, приобретенных за весь период обучения по предмету, и, с другой стороны, соответствовать критериям сложности, устойчивости результатов, надежности измерения. С этой целью в КИМ используются задания двух типов: с кратким ответом и развернутым ответом. Структура экзаменационной работы обеспечивает оптимальный баланс заданий разных типов и разновидностей, трех уровней сложности, проверяющих знания и умения на трех различных уровнях: воспроизведения, применения в стандартной ситуации, применения в новой ситуации. Содержание экзаменационной работы отражает значительную часть содержания предмета. Все это обеспечивает валидность результатов тестирования и надежность измерения.

4. Структура КИМ ЕГЭ

Каждый вариант экзаменационной работы состоит из двух частей и включает в себя 27 заданий, различающихся формой и уровнем сложности.

Часть 1 содержит 23 задания с кратким ответом.

В экзаменационной работе предложены следующие разновидности заданий с кратким ответом:

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

Ответ на задания части 1 дается соответствующей записью в виде натурального числа или последовательности символов (букв и цифр), записанных без пробелов и других разделителей.

Часть 2 содержит 4 задания с развернутым ответом.

Часть 1 содержит 23 задания базового, повышенного и высокого уровней сложности. В этой части собраны задания с кратким ответом, подразумевающие самостоятельное формулирование и запись ответа в виде числа или последовательности символов. Задания проверяют материал всех тематических блоков. В части 1 12 заданий относится к базовому уровню, 10 заданий к повышенному уровню сложности, 1 задание - к высокому уровню сложности.

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