К.Ю. Поляков, М.А. Ройтберг, 2014 Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг. — презентация
Презентация была опубликована 6 лет назад пользователемАркадий Воронец
Похожие презентации
Презентация по предмету «Математика» на тему: «К.Ю. Поляков, М.А. Ройтберг, 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>
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, г. Санкт-Петербург РОЙТБЕРГ Михаил Абрамович д.ф.-м.н., зав. кафедрой АТП ФИВТ МФТИ, зам. руководителя Федеральной комиссии по разработке КИМ ЕГЭ по информатике и ИКТ
Системы логических уравнений поляков к
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5 ) = 1
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5 ) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
1) Из последнего уравнения следует, что глобально мы имеем три варианта — x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.
2) Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.
3) Уравнение (1) описывает ряд переменных
4) Рассмотрим вариант x1=1, y1=1. Так как первые числа каждого ряда равны 1, то все следующие тоже равны 1. Существует только одна комбинация для этого варианта.
5) Рассмотрим вариант x1=0, y1=1. Для y-ряда все переменные равны 1, для x же существует 5 комбинаций, так как в ряде x может быть от 1 до 5 нолей включительно.
6) Последний вариант рассмотрим аналогично предыдущему. Там существует всего 5 комбинаций.
Правильный ответ: 5+5+1=11 комбинаций.
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям?
(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, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Конъюнкция истина тогда и только тогда, когда каждое высказывание истинно.
Для первого выражения это означает, что, если х1 равен 1, то х2, х3 и х4 также равны 1, т. е. для х1. х4 решения существуют только в виде «1111», «0111», «0011», «0001» и «0000».
Применив преобразование импликации ко второму выражению, увидим, что оно аналогично первому.
В третьем выражении из «y» следует соответствующее ему «x», это означает, что если y = 1, то и x = 1.
Следовательно, первому набору для x «1111» соответствует 5 наборов y. Второму — 4, третьему — 3, и. т. д.
Следовательно, ответ: 5 + 4 + 3 + 2 + 1 = 15.
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, которые удовлетворяют всем перечисленным ниже условиям?
(x1→x2) ∧ (x2→x3) ∧ (x3→x4) = 1
(¬x1 ∧ y1 ∧ z1) ∨ (x1 ∧ ¬y1 ∧ z1) ∨ (x1 ∧ y1 ∧ ¬z1) = 1
(¬x2 ∧ y2 ∧ z2) ∨ (x2 ∧ ¬y2 ∧ z2) ∨ (x2 ∧ y2 ∧ ¬z2) = 1
(¬x3 ∧ y3 ∧ z3) ∨ (x3 ∧ ¬y3 ∧ z3) ∨ (x3 ∧ y3 ∧ ¬z3) = 1
(¬x4 ∧ y4 ∧ z4) ∨ (x4 ∧ ¬y4 ∧ z4) ∨ (x4 ∧ y4 ∧ ¬z4) = 1
В ответе не нужно перечислять все различные наборы значений переменных
x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Рассмотрим первое уравнение. Ему удовлетворяют следующие наборы переменных x1, x2, x3, x4: 1111, 0111, 0011, 0001, 0000.
Рассмотрим оставшиеся уравнения для первого набора x1, x2, x3, x4: 1111. Во втором уравнении первая скобка будет равна 0. Из второй и третьей скобок ясно, что переменные y1 и z1 могут принимать значения 01 или 10. Имеем два набора решений второго уравнения. Аналогично для третьего, четвёртого и пятого уравнений. Таким образом, для набора x1, x2, x3, x4: 1111, получаем 16 наборов переменных y1, y2, y3, y4, z1, z2, z3, z4 (см. рис).
Рассмотрим второй набор переменных x1, x2, x3, x4: 0111. В этом случае из второго уравнения ясно, что переменные y1 и z1 могут принимать значения 11. Для оставшихся уравнений ситуация аналогична первому набору. Таким образом, для набора x1, x2, x3, x4: 0111, получаем 8 наборов переменных y1, y2, y3, y4, z1, z2, z3, z4 (см. рис).
Проведя аналогичные рассуждения для наборов 0011, 0001 и 0000, получаем, соответственно 4, 2 и 1 набор переменных y1, y2, y3, y4, z1, z2, z3, z4 соответственно.
Урок по информатике и ИКТ на тему «Системы логических уравнений: решение с помощью битовых цепочек» (10 класс физико-информационный профиль)
Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.
Кейс «Системы логических уравнений: решение с помощью битовых цепочек»
Предмет: Информатика и ИКТ
Класс: 10 кл физико-информационный профиль (а также 11кл при подготовке к ЕГЭ).
Время занятия: 2 урока
Вид кейса: обучающий
Тип кейса: аналитический
Тема урока: Решение Систем логических уравнений с помощью битовых цепочек.
Цель: Выработка умений и навыков аналитической деятельности при решении логических уравнений. Выработка умений и навыков обучающихся к работе со специальным набором учебно-методических материалов (кейсом) по решению логических задач и максимально активизировать каждого обучающегося в самостоятельную работу по решению кейса.
обобщить знания о преобразовании логических выражений;
освоить новый метод решений систем логических уравнений;
развивать инициативу, любознательность, умственную активность;
формировать коммуникативные навыки, умения вырабатывать и аргументировать самостоятельные решения, навыки сотрудничества в группах.
Оборудование: набор учебно-методических материалов (кейс) для самостоятельной работы, компьютеры подключенные к Интернету и локальной сети, мультимедиа проектор, интерактивная доска.
Во время проведения ЕГЭ-2011 в контрольно-измерительных материалах (КИМ) впервые появилась задача, в которой требовалось найти количество решений системы логических уравнений. Автором этой интересной и сложной задачи, давшей начало целому классу задач, был Сергей Федорович Сопрунов, известный, в частности, своими методическими материалами по преподаванию языка Лого. Ему же в основном принадлежат идеи, на которых основаны приводимые далее решения.
При первом знакомстве с задачей состояние учеников (и учителей!) было близко к шоковому, об этом говорит и крайне низкий процент выполнения этого задания на
ЕГЭ- 2011 — 3,2% (значительно меньше, чем для самой сложной задачи по программированию, С4). В прошедшие годы (2012–2014) эта задача прочно обосновалась в КИМ, не смотря на многочисленные претензии учителей информатики. В первую очередь это связано с тем, что она действительно оказалась сложной. Многие педагоги, в том числе и в известных на всю страну физико-математических школах, открыто рекомендуют своим ученикам не решать эту задачу вообще или решать ее в последнюю очередь, когда все остальное решено и осталось свободное время. В то же время, как показал опыт, задача является хорошим ориентиром при изучении логики и позволяет сильным ученикам проявить себя при сдаче ЕГЭ.
Учителями информатики было предложено несколько методов решения систем логических уравнений, большинство из которых сводилось к последовательному подключению уравнений: сначала вычисляется количество решений первого уравнения, потом — системы из первых двух уравнений и т.д. К сожалению, все решения этого типа получаются достаточно громоздкими [4–7]. Тем не менее процент выполнения этого задания уже через год повысился до 13,2% [8]. К сожалению, аналитические отчеты Федеральной комиссии за 2013 и 2014 годы не публиковались, поэтому отследить дальнейшее развитие ситуации по официальным источникам невозможно.
Актуальна ли эта проблема для вас?
Какова причина данной ситуации?
Как собираетесь выходить из данной ситуации?
Удовлетворяют ли вас известные вам методы решения систем логических уравнений?
Как вы считаете есть ли альтернативные методы решения данных задач?
Решение — битовый вектор.
Учитель сообщает тему урока и дает комментарии об объеме работ, формулирование вместе с учащимися цели и задач урока, ознакомление с критериями оценок и прогнозируемого результата, объяснение порядка работы с кейсом. (Так как работа рассчитана на 2 урока учащиеся заранее к первому уроку знакомятся с частью материала кейса – повторение ранее изученного материала: логические операции, законы логики, методы преобразования логических выражений) Основные материалы кейса обучающиеся получают непосредственно на занятии и работают с ним, также знакомятся с рекомендованной учителем дополнительной литературой, часть заданий по работе с кейсом выполняется дома индивидуально каждым. Ознакомление обучающихся с заданием кейса в бумажном и электронном виде (в школьных компьютерах через локальную сеть и Дневник. ru дома).
Первый этап дискуссии — организация дискуссии в подгруппах:
— обсуждение решения по заданию кейса, поиск аргументов и решений (обучающийся, познакомившись с заданием, самостоятельно анализирует ситуацию, представляют свои решения в дискуссии с другими членами подгруппы);
— выбор лучшего решения в рамках подгруппы и организация презентаций решений в подгруппах.
Второй этап дискуссии (второй урок –организация общей дискуссии в классе для принятия окончательных решений:
— выступления подгрупп, каждая группа предлагает свою версию выполненного задания (публичная, устная презентация решений);
— участие в обсуждении обучающихся других подгрупп;
— участие в обсуждении учителя.
Итоговая стадия работы над кейсом — заключительная презентация результатов решения задания (сравнение нескольких вариантов решения). Затем идет обобщающее выступление учителя — анализ ситуаций и оценивание работы каждой подгруппы учителем.
Применяя ранее полученные знания и новую информацию (материалы кейса) освоить альтернативный метод решения характерных типов задач с системами логических уравнений, затрачивая минимум усилий и используя максимум знаний?
Учитель предъявляет кейс, проясняет смыслы представленных в нем заданий. Учащиеся разбиваются на мини группы, знакомятся с представленной информацией. Учатся применять имеющиеся знания по пройденному теоретическому материалу (алгебра логики) для решения логических систем уравнений. Делают умозаключения (индуктивное и по аналогии) и выводы по решению данного типа задач на основе аргументации.
Решение — битовый вектор
Пусть задана некоторая система логических (часто говорят — булевых) уравнений от переменных x1 x2,…, xN вида
Слово “логических” означает, что переменные x1 x2,…, xN — логические, то есть принимают значения 0 или 1, и выражения F1. FM, зависящие от этих переменных, — тоже логические (множество их возможных значений — <0, 1>). Решением этой системы называется такой вектор значений X x1x2…xN , при котором все уравнения обращаются в тождества. Поскольку все переменные, входящие в решение X, логические (0 или 1), все решение можно рассматривать как цепочку нулей и единиц длиной N. Такие цепочки называют битовыми цепочками, или битовыми векторами.
При анализе систем логических уравнений удобно не исключать поочередно неизвестные, как это часто делается при решении алгебраических уравнений, а рассматривать битовый вектор–решение как целое, как единый объект. Результатом такого анализа будет описание множества векторов-решений, которое позволит подсчитать количество решений.
Как и в случае алгебраических уравнений, до того, как исследовать возможные решения, систему бывает полезно упростить или использовать замену переменных.
Для начала мы разберем несколько простых уравнений и систем, а затем перейдем к более сложным, которые использовались в задачах ЕГЭ прошлых лет. Отметим, что для проверки правильности решений систем логических уравнений можно использовать бесплатную программу, которая размещена на сайте [4].
Подведение итогов – второй урок.
Представление результатов групповой работы.
Проверка правильности решений систем логических уравнений используя бесплатную программу, которая размещена на сайте [4]. Обсуждение. Экспертиза между группами результатов работы групп по поиску по поиску оптимального решения для каждой из предложенных задач.
Что нужно знать:
таблицы истинности логических операций «И», «ИЛИ», «НЕ», «ЕСЛИ…, ТО…», «ТОГДА И ТОЛЬКО ТОГДА»
правила преобразования логических выражений;
http://inf-ege.sdamgia.ru/test?theme=308
http://infourok.ru/urok-po-informatike-i-ikt-na-temu-sistemi-logicheskih-uravneniy-reshenie-s-pomoschyu-bitovih-cepochek-klass-fizikoinformacionniy-1233934.html