Системы логических уравнений в задачах ЕГЭ по информатике
Постановка задачи (ЕГЭ-2011)
Методы решения
Аналогии с алгеброй
Формулы логики – I
Формулы логики – II
Формулы логики – III
Формулы логики – IV
Основные идеи
Типичные ограничения
Типичные ограничения
Более сложный пример
Более сложный пример
Более сложный пример
Более сложный пример
Ещё пример
И снова – рекуррентные уравнения
Последний пример
Демо-вариант ЕГЭ-2017
Демо-вариант ЕГЭ-2017
Демо-вариант ЕГЭ-2017
Демо-вариант ЕГЭ-2017
Демо-вариант ЕГЭ-2016
Демо-вариант ЕГЭ-2016
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2013
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2012
Демо-вариант ЕГЭ-2014
Демо-вариант ЕГЭ-2014
Демо-вариант ЕГЭ-2015
Демо-вариант ЕГЭ-2015
Демо-вариант ЕГЭ-2018
Демо-вариант ЕГЭ-2018
Демо-вариант ЕГЭ-2018
Демо-вариант ЕГЭ-2018
Ещё одна задача (2015)
Ещё одна задача (2015)
Ещё одна задача (2015)
И ещё одна задача (2015)
И ещё одна задача (2015)
Пробное тестирование (2015)
Ещё одна задача (2016)
Ещё одна задача (2016)
Ещё одна задача (2018)
Ещё одна задача(2018)
Основные шаги решения
Как можно рассказать детям?
1.72M
Category: informaticsinformatics

Системы логических уравнений в задачах ЕГЭ по информатике

1. Системы логических уравнений в задачах ЕГЭ по информатике

К.Ю. Поляков,
М.А. Ройтберг
Системы логических
уравнений в задачах
ЕГЭ по информатике
К.Ю. Поляков, М.А. Ройтберг, 2015-2016
http://kpolyakov.spb.ru

2. Постановка задачи (ЕГЭ-2011)

Системы логических уравнений в задачах ЕГЭ по информатике
2
Постановка задачи (ЕГЭ-2011)
Сколько решений имеет система уравнений:
x1 x2 x1 x2 x3 x4 x3 x4 1
x3 x4 x3 x4 x5 x6 x5 x6 1
...
x7 x8 x7 x8 x9 x10 x9 x10 1
где
x1 , x2 , , x10 – логические переменные.
2011: Решаемость 3,2%
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

3. Методы решения

Системы логических уравнений в задачах ЕГЭ по информатике
3
Методы решения
1) замена переменных
2) последовательное подключение уравнений
3) метод отображения (Е.А. Мирончик)
(динамическое программирование)
«Информатика. Первое сентября»
1. Е. А. Мирончик, Метод отображения // Информатика, № 10, 2013,
с. 18-26.
2. Е.А. Мирончик, Люблю ЕГЭ за В15, или Еще раз про метод
отображения // Информатика, № 7-8, 2014, с. 26-32.
2012: Решаемость 13,2%
трудоёмко
длинная запись решения
арифметические ошибки
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

4. Аналогии с алгеброй

Системы логических уравнений в задачах ЕГЭ по информатике
4
Аналогии с алгеброй
Алгебра
Логика
Обычно уравнение имеет
одно или несколько
решений.
Уравнение может иметь
большое, но конечное
число решений.
Элементарные уравнения:
линейные, квадратные.
Элементарные уравнения
не выделяются.
Методы преобразования:
законы сложения и
умножения, формулы
сокращенного умножения,
свойства степеней.
Методы преобразования:
законы логики (см. далее).
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

5. Формулы логики – I

Системы логических уравнений в задачах ЕГЭ по информатике
5
Формулы логики – I
A. Свойства 0, 1 и отрицания
Свойства 0 и 1
a 0 0
a 1 a
Свойства отрицания
a a 0
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
a 0 a
a 1 1
a a 1
a a
http://kpolyakov.spb.ru

6. Формулы логики – II

Системы логических уравнений в задачах ЕГЭ по информатике
6
Формулы логики – II
Б. Дизъюнкция и конъюнкция
Сочетательный закон
a (b c) (a b) c
a (b c) (a b) c
Переместительный закон
a b b a
a b b a
Закон повторения
a a a
a a a
Распределительный закон
a (b c) a b a c
a b c ( a b) ( a c )
Правила де Моргана
a b a b
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
a b a b
http://kpolyakov.spb.ru

7. Формулы логики – III

Системы логических уравнений в задачах ЕГЭ по информатике
7
Формулы логики – III
В. Импликация
Определение импликации
a b a b
Свойства импликации
a b a b
a b b a
a (b c) (a b) c
b a
a (b c) a (b c) a b c
(a b) c (a b) c a b c
a (b c) (a b) (a c)
a (b c) (a b) (a c)
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

8. Формулы логики – IV

Системы логических уравнений в задачах ЕГЭ по информатике
8
Формулы логики – IV
Г. Эквивалентность
Представление через базис:
(a b) a b a b
( a b) a b a b
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

9. Основные идеи

Системы логических уравнений в задачах ЕГЭ по информатике
9
Основные идеи
1) Решение системы уравнений – это битовая
цепочка (битовый вектор)
X x1 x2 xN ( xi {0,1}
для любого i
)
2) Битовый вектор рассматривается как единый
объект.
3) Уравнения – это ограничения на битовый
вектор (ограничения на комбинации битов).
4) Нужно выделить элементарные уравнения и
записать ограничения «на русском языке».
5) Количество решений находится по правилам
комбинаторики.
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

10. Типичные ограничения

Системы логических уравнений в задачах ЕГЭ по информатике
10
Типичные ограничения
Задача 1.
( x1 x2 ) ( x2 x3 ) ( x4 x5 ) 1
«соседние биты одинаковы»
Решения: 00000, 11111
Задача 2.
( x1 x2 ) ( x2 x3 ) ( x4 x5 ) 1
«соседние биты различны»
«биты чередуются»
Решения: 01010, 10101
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

11. Типичные ограничения

Системы логических уравнений в задачах ЕГЭ по информатике
11
Типичные ограничения
Задача 3.
( x1 x2 ) ( x2 x3 ) ( x5 x6 ) 1
«запрещена комбинация 10»
«после первой единицы все следующие биты – 1»
«все нули, потом все единицы»
Решения: 000000, 000001, 000011, 000111,
001111, 011111, 111111
Для уравнения с N переменными: N+1 решений.
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

12. Более сложный пример

Системы логических уравнений в задачах ЕГЭ по информатике
12
Более сложный пример
Задача 4.
(( x1 x2 ) x3 ) (( x2 x3 ) x4 ) (( x4 x5 ) x6 ) 1
«запрещена комбинация 1 0»
«запрещена комбинация xi xi 1 1, xi 2 0»
«слева от каждого нулевого бита (начиная с 3-го)
должны стоять два нуля»
«все нули, потом все единицы»
Решения: 000000, 000001, 000011, 000111,
001111, 011111, 111111
и ещё: 101111
Для уравнения с N переменными: N+2 решений.
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

13. Более сложный пример

Системы логических уравнений в задачах ЕГЭ по информатике
13
Более сложный пример
Задача 5.
( x1 x2 ) ( x2 x3 ) ( x5 x6 ) 1
«запрещена комбинация 00»
?
Сколько есть цепочек длиной N, в которых нет
двух соседних нулей?
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

14. Более сложный пример

Системы логических уравнений в задачах ЕГЭ по информатике
14
Более сложный пример
KN – количество «правильных» цепочек длиной N
K1 2 {0, 1}
Все цепочки длиной
K 2 3 {01, 10, 11}
N
K N 2
нет 00!
1
0
1
K N K N 1 K N 2
непересекающиеся
множества!
K N 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

15. Более сложный пример

Системы логических уравнений в задачах ЕГЭ по информатике
15
Более сложный пример
K1 2 {0, 1}
K 2 3 {01, 10, 11}
K N K N 1 K N 2
KN
!
Рекурсия: ЕГЭ-11 (B6)
Динамическое
программирование:
ЕГЭ-22 (B13), ЕГЭ-15 (B9)
1, 1, 2, 3, 5, 8, 13, 21, 34, …
Числа Фибоначчи FN
K N FN 2
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

16. Ещё пример

Системы логических уравнений в задачах ЕГЭ по информатике
16
Ещё пример
Задача 6.
( x1 x2 x3 ) ( x2 x3 x4 ) ( x4 x5 x6 ) 1
«запрещена комбинация 1 0»
«после двух единиц подряд следуют только единицы»
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

17. И снова – рекуррентные уравнения

Системы логических уравнений в задачах ЕГЭ по информатике
17
И снова – рекуррентные уравнения
Структура решения:
«голова»
«хвост»
0
1
1
m
нет комбинации 11
последний бит – 0
m 0 : одна «голова» (пустая)
m 1 : одна «голова» (0)
m 1 : Fm 1 «голов»
1
N m
N
K N Fm 1
m 0
N 6 : K N 1 1 2 3 5 8 13 33
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

18. Последний пример

Системы логических уравнений в задачах ЕГЭ по информатике
19
Демо-вариант ЕГЭ-2017
( x1 ( x2 y1 )) ( y1 y2 ) 1
( x2 ( x3 y2 )) ( y2 y3 ) 1
...
( x5 ( x6 y5 )) ( y5 y6 ) 1
x6 y6 1
xi ( xi 1 yi ) 1
xi xi 1 1
xi yi 1
Группировка по вертикали:
( x1 ( x2 y1 )) ... ( x5 ( x6 y5 )) 1
( y1 y2 ) ( y2 y3 ) ... ( y5 y6 ) 1
x6 y6 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

19. Демо-вариант ЕГЭ-2017

Системы логических уравнений в задачах ЕГЭ по информатике
20
Демо-вариант ЕГЭ-2017
( x1 x2 ) ( x2 x3 ) ... ( x5 x6 ) 1
( y1 y2 ) ( y2 y3 ) ... ( y5 y6 ) 1
( x1 y1 ) ... ( x5 y5 ) ( x6 y6 ) 1
Решение:
( x1 x2 ) ( x2 x3 ) ... ( x5 x6 ) 1
000000, 000001, 000011, 000111, 001111, 011111, 111111
( y1 y2 ) ( y2 y3 ) ... ( y5 y6 ) 1
000000, 000001, 000011, 000111, 001111, 011111, 111111
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

20. Демо-вариант ЕГЭ-2017

Системы логических уравнений в задачах ЕГЭ по информатике
21
Демо-вариант ЕГЭ-2017
Уравнение связи:
( x1 y1 ) ... ( x5 y5 ) ( x6 y6 ) 1
Ограничения:
xi 0 yi {0, 1} без ограничений!
xi 1 yi 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

21. Демо-вариант ЕГЭ-2017

Системы логических уравнений в задачах ЕГЭ по информатике
22
Демо-вариант ЕГЭ-2017
X:
7 000000
6 000001
5 000011
4 000111
3 001111
2 011111
1 111111
Y:
000000
000001
000011
000111
001111
011111
111111
7 + 6 + 5 + 4 + 3 + 2 + 1 = 28
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

22. Демо-вариант ЕГЭ-2017

Системы логических уравнений в задачах ЕГЭ по информатике
23
Демо-вариант ЕГЭ-2016
( x1 y1 ) ( x2 y2 )
( x2 y2 ) ( x3 y3 )
...
( x8 y8 ) ( x9 y9 )
Замена переменных:
z1 ( x1 y1 )
z2 ( x2 y2 )

z9 ( x9 y9 )
z1 z 2 , z2 z3, z8 z9
z1 z 2 , z2 z3, z8 z9
( z1 z2 ) ( z2 z3 ) ( z2 z3 ) ( z8 z9 ) 1
!
Биты чередуются!
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
Решения: Z = 010101010,
Z = 101010101
http://kpolyakov.spb.ru

23. Демо-вариант ЕГЭ-2016

Системы логических уравнений в задачах ЕГЭ по информатике
24
Демо-вариант ЕГЭ-2016
Решения: Z = 010101010,
Z = 101010101
zi ( xi yi )
9 битов
zi 0 ( xi , yi ) (0,1) (1,0)
zi 1 ( xi , yi ) (0,0) (1,1)
!
0 и 1 дают по
2 решения!
29 + 29 = 1024
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

24. Демо-вариант ЕГЭ-2016

Системы логических уравнений в задачах ЕГЭ по информатике
25
Демо-вариант ЕГЭ-2013
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) 1
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
( y1 x1 ) ( y2 x2 ) ( y3 x3 ) ( y4 x4 ) 1
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) 1
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
( y1 x1 ) ( y2 x2 ) ( y3 x3 ) ( y4 x4 ) 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

25. Демо-вариант ЕГЭ-2013

Системы логических уравнений в задачах ЕГЭ по информатике
26
Демо-вариант ЕГЭ-2013
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) 1
5 решений:
X = 0000, 0001, 0011, 0111, 1111
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
5 решений:
Y = 0000, 0001, 0011, 0111, 1111
Связь X и Y:
( y1 x1 ) ( y2 x2 ) ( y3 x3 ) ( y4 x4 ) 1
yi 1 xi 1
yi 0 xi {0, 1}
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
без ограничений!
http://kpolyakov.spb.ru

26. Демо-вариант ЕГЭ-2013

Системы логических уравнений в задачах ЕГЭ по информатике
27
Демо-вариант ЕГЭ-2013
X:
0000
0001
0011
0111
1111
Y:
0000
0001
0011
0111
1111
5
4
3
2
1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
5 + 4 + 3 + 2 + 1 = 15
http://kpolyakov.spb.ru

27. Демо-вариант ЕГЭ-2013

Системы логических уравнений в задачах ЕГЭ по информатике
28
Демо-вариант ЕГЭ-2012
(( x1 x2 ) ( x3 x4 )) (( x1 x2 ) ( x3 x4 )) 1
(( x3 x4 ) ( x5 x6 )) (( x3 x4 ) ( x5 x6 )) 1
(( x7 x8 ) ( x9 x10 )) (( x7 x8 ) ( x9 x10 )) 1
Замена переменных:
z1 ( x1 x2 )
z2 ( x3 x4 )

z5 ( x9 x10 )
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
( z1 z 2 ) ( z1 z 2 ) 1
( z 2 z3 ) ( z 2 z3 ) 1
( z 4 z5 ) ( z 4 z5 ) 1
http://kpolyakov.spb.ru

28. Демо-вариант ЕГЭ-2012

Системы логических уравнений в задачах ЕГЭ по информатике
29
Демо-вариант ЕГЭ-2012
(a b) (a b ) a b a b (a b)
( z1 z 2 ) ( z1 z 2 ) 1
( z1 z 2 ) 1
( z 2 z3 ) ( z 2 z3 ) 1
( z 2 z3 ) 1
( z 4 z5 ) ( z 4 z5 ) 1
( z 4 z5 ) 1
К одному уравнению:
( z1 z2 ) ( z2 z3 ) ( z2 z3 ) ( z4 z5 ) 1
Решения:
Z 01010,
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
Z 10101
http://kpolyakov.spb.ru

29. Демо-вариант ЕГЭ-2012

Системы логических уравнений в задачах ЕГЭ по информатике
30
Демо-вариант ЕГЭ-2012
Переход к исходным переменным:
zi ( xk xk 1 )
zi 0 ( xk , xk 1 ) (0,1), (1,0)
zi 1 ( xk , xk 1 ) (0,0), (1,1)
!
Каждый бит в Z даёт удвоение вариантов в X!
Z 01010,
Z 10101
5 бит
5 бит
K10 2 2 64
5
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
5
http://kpolyakov.spb.ru

30. Демо-вариант ЕГЭ-2012

Системы логических уравнений в задачах ЕГЭ по информатике
31
Демо-вариант ЕГЭ-2014
( x1 x2 ) ( x1 x3 x1 x3 ) 0
( x2 x3 ) ( x2 x4 x2 x4 ) 0
( x8 x9 ) ( x8 x10 x8 x10 ) 0
( x1 x2 ) ( x1 x3 ) 0
( x2 x3 ) ( x2 x4 ) 0
?
Как перевести на
русский язык?
( x8 x9 ) ( x8 x10 ) 0
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

31. Демо-вариант ЕГЭ-2014

X
Системы логических уравнений в задачах ЕГЭ по информатике
32
Демо-вариант ЕГЭ-2014
( xi xi 1 ) ( xi xi 2 ) 0
«очередной бит равен хотя бы одному из 2-х следующих»
«запрещены комбинации 100 и 011»
«после 01 или 10 биты чередуются»
1) сначала цепочка нулей, потом биты чередуются (1/0)
2) сначала цепочка единиц, потом биты чередуются.
0000000000
0000000001
0000000010
0000000101

0101010101
1111111111
1111111110
1111111101
1111111010

1010101010
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
10 + 10 = 20
http://kpolyakov.spb.ru

32. Демо-вариант ЕГЭ-2014

Системы логических уравнений в задачах ЕГЭ по информатике
33
Демо-вариант ЕГЭ-2015
( x1 x2 ) ( x1 x2 x3 ) ( x1 y1 ) 1
( x2 x3 ) ( x2 x3 x4 ) ( x2 y2 ) 1
( x6 x7 ) ( x6 x7 x8 ) ( x6 y6 ) 1
( x7 x8 ) ( x7 y7 ) 1
xi xi 1 1
«запрещено 00»
( xi xi 1 xi 2 ) 1
«после двух единиц
идут только единицы»
x8 y8 1
Если не трогать Y :
«голова»
«хвост»
0
1
1
1
«запрещено 00 и 11»
«биты чередуются»
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

33. Демо-вариант ЕГЭ-2015

Системы логических уравнений в задачах ЕГЭ по информатике
34
Демо-вариант ЕГЭ-2015
Варианты отличаются местом последнего нуля:
11111111, 01111111, 10111111, 01011111, 10101111,
01010111, 10101011, 01010101, 10101010
Учитываем
Y:
xi yi 1
xi yi 1
xi 1 yi 1
1 решение
xi 0 yi {0, 1} 2 решения
01011111
2 нулевых бита, 22 вариантов
K 8 2 2 (2 2 2 2 ) 61
0
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
1
2
3
4
http://kpolyakov.spb.ru

34. Демо-вариант ЕГЭ-2015

Системы логических уравнений в задачах ЕГЭ по информатике
35
Демо-вариант ЕГЭ-2018
( x1 y1 ) ( x2 y2 ) 1
( x2 y2 ) ( x3 y3 ) 1
...
( x6 y6 ) ( x7 y7 ) 1
( xi yi ) ( xi 1 yi 1 ) 1
a (b c) (a b) (b c)
(( xi yi ) xi 1 ) (( xi yi ) yi 1 ) 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

35. Демо-вариант ЕГЭ-2018

Системы логических уравнений в задачах ЕГЭ по информатике
36
Демо-вариант ЕГЭ-2018
(( xi yi ) xi 1 ) (( xi yi ) yi 1 ) 1
a b b a
( xi 1 xi yi ) ( yi 1 xi yi ) 1
( xi 1 xi ) ( xi 1 yi ) ( yi 1 xi ) ( yi 1 yi ) 1
( xi 1 xi ) ( xi 1 yi ) ( yi 1 xi ) ( yi yi 1 ) 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

36. Демо-вариант ЕГЭ-2018

Системы логических уравнений в задачах ЕГЭ по информатике
37
Демо-вариант ЕГЭ-2018
( xi 1 xi ) ( xi 1 yi ) ( yi 1 xi ) ( yi yi 1 ) 1
только x
уравнения связи
Все X-решения:
0000000
1000000
1100000
1110000
1111000
1111100
1111110
1111111
только y
Все Y-решения:
!
Как стыкуются?
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111
http://kpolyakov.spb.ru

37. Демо-вариант ЕГЭ-2018

Системы логических уравнений в задачах ЕГЭ по информатике
38
Демо-вариант ЕГЭ-2018
( yi 1 xi ) ( xi 1 yi ) 1
xi 0 yi 1 1
xi 1 yi 1 0
Все X-решения:
2
3
3
3
3
3
3
2
0000000
1000000
1100000
1110000
1111000
1111100
1111110
1111111
Все Y-решения:
*111111
**11111
0**1111
00*1111
000**11
0000**1
00000**
000000*
0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111
2+3+3+3+3+3+3+2 = 22
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

38. Демо-вариант ЕГЭ-2018

Системы логических уравнений в задачах ЕГЭ по информатике
39
Ещё одна задача (2015)
( x1 y1 ) ( x2 y2 x1 y1 ) 1
( x2 y2 ) ( x3 y3 x2 y2 ) 1
( x6 y6 ) ( x7 y7 x6 y6 ) 1
x7 y7 1
Замена переменных:
z1 x1 y1
z 2 x2 y 2
z6 x6 y6
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
z 2 z1 1
z3 z 2 1
z7 z6 1
http://kpolyakov.spb.ru

39. Ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
40
Ещё одна задача (2015)
z 2 z1 1 ( z2 z1 ) ( z3 z2 ) ( z7 z6 ) 1
Z z1 z2 z3 z4 z5 z6 z7
z3 z 2 1
Решение:
«запрещена комбинация 01»
z7 z6 1
«все единицы, потом – все нули»
!
8 решений: 0000000
1000000
1100000
1110000
Но в zi!
1111000
1111100
1111110
1111111
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

40. Ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
41
Ещё одна задача (2015)
zi xi yi 0
xi yi 1
zi xi yi 1
xi yi 1
Z
0000000
1000000
1100000
1110000
2 решения: (0;1) и (1;0)
!
Каждый 0 удваивает
количество решений!
1 решение: (1;1)
X,Y
128
64
32
16
Z
1111000
1111100
1111110
1111111
X,Y
8
4
2
1
128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

41. Ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
44
Пробное тестирование (2015)
( x1 y1 ) ( x2 y2 )
( x2 y2 ) ( x3 y3 )
Замена переменных:
z1 ( x1 y1 )
z 2 ( x2 y 2 )
...
( x5 y5 ) ( x6 y6 )
z6 ( x6 y6 )
( z1 z2 ) ( z2 z3 ) ( z5 z6 ) 1
«биты чередуются»
Решения: 010101, 101010
zi 1 ( xi , yi ) (1,1)
Ответ: 33+33= 54
zi 0 ( xi , yi ) (0,0)(0,1)(1,0)
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

42. И ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
45
Ещё одна задача (2016)
(( x1 y1 ) ( x2 y2 )) ( x1 x2 ) ( y1 y2 ) 1
(( x2 y2 ) ( x3 y3 )) ( x2 x3 ) ( y2 y3 ) 1
(( x7 y7 ) ( x8 y8 )) ( x7 x8 ) ( y7 y8 ) 1
В другой форме:
( x1 x2 ) ( x2 x3 ) ... ( x7 x8 ) 1
( y1 y2 ) ( y2 y3 ) ... ( y7 y8 ) 1
!
Все нули,
потом 1!
(( x1 y1 ) ( x2 y2 )) ... (( x7 y7 ) ( x8 y8 )) 1
Ограничения
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

43. И ещё одна задача (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
46
Ещё одна задача (2016)
X
00000000
00000001
...
11111111
Ограничение:
Запрещено:
?
Как стыкуются?
Y
00000000
00000001
...
11111111
( xi yi ) ( xi 1 yi 1 ) 1
xi yi и xi 1 yi 1
Получим 10!
(0,0)
(1,1)
(1,0) или (0,1)
Если есть 0,
то X=Y!
X=11111111 стыкуется со всеми! (N+1 решений)
остальные – только с равными и с Y=11111111!
(+2N решений)
Ответ: 3·8+1= 25
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

44. Пробное тестирование (2015)

Системы логических уравнений в задачах ЕГЭ по информатике
47
Ещё одна задача (2018)
( x1 x2 ) ( y1 y2 ) 1
( x2 x3 ) ( y2 y3 ) 1
( x6 x7 ) ( y6 y7 ) 1
( x1 y1 ) ( x2 y2 ) 1
?
Замена переменных???
( x1 x2 ) ( y1 y2 ) 1
Если x1 y1 , то x2 y2
Если x1 y1 , то x2 y2
( x1 y1 ) ( x2 y2 ) 1
( x2 y2 ) ( x3 y3 ) 1
zi ( xi yi )
( x6 y6 ) ( x7 y7 ) 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

45. Ещё одна задача (2016)

Системы логических уравнений в задачах ЕГЭ по информатике
48
Ещё одна задача(2018)
zi ( xi yi )
( z1 z2 ) 1
( z 2 z3 ) 1
( z6 z7 ) 1
( z1 z2 ) ( z2 z3 ) ( z6 z7 ) 1
Решения: Z 0000000, 1111111
zi 0 (0,1) (1,0)
zi 1 (0,0) (1,1)
!
0 и 1 удваивают число
решений!
27 + 27 = 256
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

46. Ещё одна задача (2016)

Системы логических уравнений в задачах ЕГЭ по информатике
49
Основные шаги решения
1) упрощение уравнений с помощью
эквивалентных преобразований
2) замена переменных (если возможно)
3) исследование структуры всех решений
(«голова+хвост»)
4) подсчёт количества решений по формулам
комбинаторики
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

47. Ещё одна задача (2018)

Системы логических уравнений в задачах ЕГЭ по информатике
50
Как можно рассказать детям?
1) x1 x2 x3 x4 x5 0
2) x1 x2 x3 x4 x5 1
3) ( x1 x2 ) ( x3 x4 ) 1
4) ( x1 x2 ) ( x3 x4 ) 0
5) ( x1 x2 ) ( x2 x3 ) ( x9 x10 ) 1
6) ( x1 x2 ) ( x2 x3 ) ( x9 x10 ) 1
7) ( x1 x2 ) ( x2 x3 ) ( x9 x10 ) 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

48. Ещё одна задача(2018)

Системы логических уравнений в задачах ЕГЭ по информатике
51
Как можно рассказать детям (II)?
8) ( x1 x2 ) ( x2 x3 ) ( x3 x4 ) ( x4 x5 ) 1
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
9)
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) ( x4 x5 ) 1
( y1 y2 ) ( y2 y3 ) ( y3 y4 ) 1
x2 y3 1
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

49. Основные шаги решения

Системы логических уравнений в задачах ЕГЭ по информатике
52
Как можно рассказать детям (III)?
10)
( x1 y1 ) ( x2 y2 )
( x2 y2 ) ( x3 y3 )
Демо-2016
...
( x8 y8 ) ( x9 y9 )
11)
( x1 y1 ) ( x2 y2 )
( x2 y2 ) ( x3 y3 )
Пробное
тестирование
...
( x5 y5 ) ( x6 y6 )
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru

50. Как можно рассказать детям?

Системы логических уравнений в задачах ЕГЭ по информатике
53
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
РОЙТБЕРГ Михаил Абрамович
д.ф.-м.н., зав. кафедрой АТП ФИВТ МФТИ,
зам. руководителя Федеральной комиссии по
разработке КИМ ЕГЭ по информатике и ИКТ
[email protected]
К.Ю. Поляков, М.А. Ройтберг, 2015 -2016
http://kpolyakov.spb.ru
English     Русский Rules