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

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

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

2. Демоверсия 2011

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

3. Демоверсия 2011

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

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

Системы логических уравнений в задачах ЕГЭ по информатике
4
Постановка задачи (ЕГЭ-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%
К.Ю. Поляков, М.А. Ройтберг, 2014
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

Системы логических уравнений в задачах ЕГЭ по информатике
8
Формулы логики – 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
К.Ю. Поляков, М.А. Ройтберг, 2014
a b a b
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

Системы логических уравнений в задачах ЕГЭ по информатике
13
Более сложный пример
Задача 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 решений.
К.Ю. Поляков, М.А. Ройтберг, 2014
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

Системы логических уравнений в задачах ЕГЭ по информатике
17
Демо-вариант ЕГЭ-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
К.Ю. Поляков, М.А. Ройтберг, 2014
1
2
3
4
http://kpolyakov.spb.ru

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

Системы логических уравнений в задачах ЕГЭ по информатике
18
Демо-вариант ЕГЭ-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
К.Ю. Поляков, М.А. Ройтберг, 2014
? Как перевести на
русский язык?
http://kpolyakov.spb.ru

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

X
Системы логических уравнений в задачах ЕГЭ по информатике
19
Демо-вариант ЕГЭ-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
К.Ю. Поляков, М.А. Ройтберг, 2014
10 + 10 = 20
http://kpolyakov.spb.ru

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

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

21. Конец фильма

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

22.

Системы логических уравнений в задачах ЕГЭ по информатике
Задание 23 из варианта TR-4
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) ( x4 x5 ) ( x5 x6 ) 1
( x1 y1 ) ( x2 y2 ) ( x3 y3 ) ( x4 y4 ) ( x5 y5 ) ( x6 y6 ) 1
xi xi 1 1
«запрещена комбинация 1 0»
«после первой единицы все следующие биты – 1»
«все нули, потом все единицы»
Решения: 000000, 000001, 000011, 000111,
001111, 011111, 111111
Для уравнения с N переменными: N+1 решений.
К.Ю. Поляков, М.А. Ройтберг, 2014
А.Г. Тамаревская
http://kpolyakov.spb.ru

23.

Системы логических уравнений в задачах ЕГЭ по информатике
Задание 23 из варианта TR-4
( x1 x2 ) ( x2 x3 ) ( x3 x4 ) ( x4 x5 ) ( x5 x6 ) 1
( x1 y1 ) ( x2 y2 ) ( x3 y3 ) ( x4 y4 ) ( x5 y5 ) ( x6 y6 ) 1
Решения по х: 000000, 000001, 000011, 000111,
001111, 011111, 111111
xi yi 1
«запрещена комбинация 1 0»
xi 1 yi 0
1 решение
xi 0 yi {0, 1} 2 решения
K 2 2 2 2 2 2 2 127
6
5
К.Ю. Поляков, М.А. Ройтберг, 2014
4
3
2
1
0
А.Г. Тамаревская
http://kpolyakov.spb.ru

24.

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

25.

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

26.

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