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

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

2 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Постановка задачи (ЕГЭ-2011) : Решаемость 3,2% Сколько решений имеет система уравнений: где– логические переменные.

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

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

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

6 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Формулы логики – II 6 Б. Дизъюнкция и конъюнкция Сочетательный закон Переместительный закон Закон поглощения Распределительный закон Правила де Моргана

7 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Формулы логики – III 7 В. Импликация и эквивалентность Определение импликации Свойства импликации Эквивалентность

8 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Основные идеи 8 1)Решение системы уравнений – это битовая цепочка (битовый вектор) 2)Битовый вектор рассматривается как единый объект. 3)Уравнения – это ограничения на битовый вектор (ограничения на комбинации битов). 4)Нужно выделить элементарные уравнения и записать ограничения «на русском языке». 5)Количество решений находится по правилам комбинаторики. для любого i

9 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Типичные ограничения 9 Задача 1. «соседние биты одинаковы» Решения: 00000, Задача 2. «соседние биты различны» Решения: 01010, «биты чередуются»

10 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Типичные ограничения 10 Задача 3. «запрещена комбинация 10» Решения: , , , , , , «после первой единицы все следующие биты – 1» «все нули, потом все единицы» Для уравнения с N переменными: N+1 решений.

11 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример 11 Задача 4. «запрещена комбинация 1 0» Решения: , , , , , , «слева от каждого нулевого бита (начиная с 3-го) должны стоять два нуля» «все нули, потом все единицы» Для уравнения с N переменными: N+2 решений. «запрещена комбинация » и ещё:

12 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример 12 Задача 5. «запрещена комбинация 00» Сколько есть цепочек длиной N, в которых нет двух соседних нулей? ?

13 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример Все цепочки длиной нет 00! непересекающиеся множества! {0, 1}{01, 10, 11}

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

15 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё пример 15 Задача 6. «запрещена комбинация 1 0» «после двух единиц подряд следуют только единицы»

16 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, И снова – рекуррентные уравнения 16 Структура решения: 11 1 «хвост»«голова» нет комбинации 11 последний бит – 0 : одна «голова» (пустая) : одна «голова» (0) «голов»

17 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Последний пример 17 Задача 7. Последовательность выполнения: запрещена комбинация 1 0 на последнем шаге Сколько решений у уравнения Начальное значение:

18 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ «запрещено 00» «после двух единиц идут только единицы» Если не трогать : 11 1 «хвост»«голова» «запрещено 00 и 11» «биты чередуются»

19 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Варианты отличаются местом последнего нуля: , , , , , , , , Учитываем : 1 решение 2 решения нулевых бита, 2 2 вариантов

20 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Как перевести на русский язык? ?

21 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ «очередной бит равен хотя бы одному из 2-х следующих» «запрещены комбинации 100 и 011» 1)сначала цепочка нулей, потом биты чередуются (1/0) 2)сначала цепочка единиц, потом биты чередуются. 1)сначала цепочка нулей, потом биты чередуются (1/0) 2)сначала цепочка единиц, потом биты чередуются … … = 20 «после 01 или 10 биты чередуются»

22 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ

23 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ решений: X = 0000, 0001, 0011, 0111, решений: Y = 0000, 0001, 0011, 0111, 1111 без ограничений! Связь X и Y:

24 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ X: Y:Y: = 15

25 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Замена переменных: …

26 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ К одному уравнению: Решения:

27 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Переход к исходным переменным: Каждый бит в Z даёт удвоение вариантов в X! ! 5 бит

28 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё одна задача (2015) 28 Замена переменных:

29 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё одна задача (2015) 29 Решение: «запрещена комбинация 01» «все единицы, потом – все нули» 8 решений: Но в z i ! !

30 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё одна задача (2015) 30 2 решения: (0;1) и (1;0) 1 решение: (1;1) Каждый 0 удваивает количество решений! ! ZZ X,Y =

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

32 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ 163, г. Санкт-Петербург РОЙТБЕРГ Михаил Абрамович д.ф.-м.н., зав. кафедрой АТП ФИВТ МФТИ, зам. руководителя Федеральной комиссии по разработке КИМ ЕГЭ по информатике и ИКТ