informaticsSimilar presentations:
Системы логических уравнений в задачах ЕГЭ по информатике
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