Ефанова Н.В.
Кейс «Системы логических уравнений: решение с помощью битовых цепочек»
Предмет: Информатика и ИКТ
Класс: 10 кл физико-информационный профиль (а также 11кл при подготовке к ЕГЭ).
Время занятия: 2 урока
Вид кейса: обучающий
Тип кейса: аналитический
Тема урока: Решение Систем логических уравнений с помощью битовых цепочек.
Цель: Выработка умений и навыков аналитической деятельности при решении логических уравнений. Выработка умений и навыков обучающихся к работе со специальным набором учебно-методических материалов (кейсом) по решению логических задач и максимально активизировать каждого обучающегося в самостоятельную работу по решению кейса.
Задачи:
обобщить знания о преобразовании логических выражений;
освоить новый метод решений систем логических уравнений;
развивать инициативу, любознательность, умственную активность;
формировать коммуникативные навыки, умения вырабатывать и аргументировать самостоятельные решения, навыки сотрудничества в группах.
Оборудование: набор учебно-методических материалов (кейс) для самостоятельной работы, компьютеры подключенные к Интернету и локальной сети, мультимедиа проектор, интерактивная доска.
И- Идентификация проблемы:
Во время проведения ЕГЭ-2011 в контрольно-измерительных материалах (КИМ) впервые появилась задача, в которой требовалось найти количество решений системы логических уравнений. Автором этой интересной и сложной задачи, давшей начало целому классу задач, был Сергей Федорович Сопрунов, известный, в частности, своими методическими материалами по преподаванию языка Лого. Ему же в основном принадлежат идеи, на которых основаны приводимые далее решения.
При первом знакомстве с задачей состояние учеников (и учителей!) было близко к шоковому, об этом говорит и крайне низкий процент выполнения этого задания на
ЕГЭ- 2011 — 3,2% (значительно меньше, чем для самой сложной задачи по программированию, С4). В прошедшие годы (2012–2014) эта задача прочно обосновалась в КИМ, не смотря на многочисленные претензии учителей информатики. В первую очередь это связано с тем, что она действительно оказалась сложной. Многие педагоги, в том числе и в известных на всю страну физико-математических школах, открыто рекомендуют своим ученикам не решать эту задачу вообще или решать ее в последнюю очередь, когда все остальное решено и осталось свободное время. В то же время, как показал опыт, задача является хорошим ориентиром при изучении логики и позволяет сильным ученикам проявить себя при сдаче ЕГЭ.
Учителями информатики было предложено несколько методов решения систем логических уравнений, большинство из которых сводилось к последовательному подключению уравнений: сначала вычисляется количество решений первого уравнения, потом — системы из первых двух уравнений и т.д. К сожалению, все решения этого типа получаются достаточно громоздкими [4–7]. Тем не менее процент выполнения этого задания уже через год повысился до 13,2% [8]. К сожалению, аналитические отчеты Федеральной комиссии за 2013 и 2014 годы не публиковались, поэтому отследить дальнейшее развитие ситуации по официальным источникам невозможно.
Д - Вопросы для обсуждения:
Актуальна ли эта проблема для вас?
Какова причина данной ситуации?
Как собираетесь выходить из данной ситуации?
Удовлетворяют ли вас известные вам методы решения систем логических уравнений?
Как вы считаете есть ли альтернативные методы решения данных задач?
Е – Есть варианты решения:
Решение — битовый вектор.
Учитель сообщает тему урока и дает комментарии об объеме работ, формулирование вместе с учащимися цели и задач урока, ознакомление с критериями оценок и прогнозируемого результата, объяснение порядка работы с кейсом. (Так как работа рассчитана на 2 урока учащиеся заранее к первому уроку знакомятся с частью материала кейса – повторение ранее изученного материала: логические операции, законы логики, методы преобразования логических выражений) Основные материалы кейса обучающиеся получают непосредственно на занятии и работают с ним, также знакомятся с рекомендованной учителем дополнительной литературой, часть заданий по работе с кейсом выполняется дома индивидуально каждым. Ознакомление обучающихся с заданием кейса в бумажном и электронном виде (в школьных компьютерах через локальную сеть и Дневник.ru дома).
Первый этап дискуссии - организация дискуссии в подгруппах:
- обсуждение решения по заданию кейса, поиск аргументов и решений (обучающийся, познакомившись с заданием, самостоятельно анализирует ситуацию, представляют свои решения в дискуссии с другими членами подгруппы);
- выбор лучшего решения в рамках подгруппы и организация презентаций решений в подгруппах.
Второй этап дискуссии (второй урок –организация общей дискуссии в классе для принятия окончательных решений:
- выступления подгрупп, каждая группа предлагает свою версию выполненного задания (публичная, устная презентация решений);
- участие в обсуждении обучающихся других подгрупп;
- участие в обсуждении учителя.
Итоговая стадия работы над кейсом - заключительная презентация результатов решения задания (сравнение нескольких вариантов решения). Затем идет обобщающее выступление учителя - анализ ситуаций и оценивание работы каждой подгруппы учителем.
Задание:
Применяя ранее полученные знания и новую информацию (материалы кейса) освоить альтернативный метод решения характерных типов задач с системами логических уравнений, затрачивая минимум усилий и используя максимум знаний?
А – А теперь за работу!
Учитель предъявляет кейс, проясняет смыслы представленных в нем заданий. Учащиеся разбиваются на мини группы, знакомятся с представленной информацией. Учатся применять имеющиеся знания по пройденному теоретическому материалу (алгебра логики) для решения логических систем уравнений. Делают умозаключения (индуктивное и по аналогии) и выводы по решению данного типа задач на основе аргументации.
Решение — битовый вектор
Пусть задана некоторая система логических (часто говорят — булевых) уравнений от переменных x1 x2,…, xN вида
F1(x1, x2, , xN )=1
…
FM(x x xN )=1
Слово “логических” означает, что переменные x1 x2,…, xN — логические, то есть принимают значения 0 или 1, и выражения F1,...FM, зависящие от этих переменных, — тоже логические (множество их возможных значений — {0, 1}). Решением этой системы называется такой вектор значений X x1x2…xN , при котором все уравнения обращаются в тождества. Поскольку все переменные, входящие в решение X, логические (0 или 1), все решение можно рассматривать как цепочку нулей и единиц длиной N. Такие цепочки называют битовыми цепочками, или битовыми векторами.
При анализе систем логических уравнений удобно не исключать поочередно неизвестные, как это часто делается при решении алгебраических уравнений, а рассматривать битовый вектор–решение как целое, как единый объект. Результатом такого анализа будет описание множества векторов-решений, которое позволит подсчитать количество решений.
Как и в случае алгебраических уравнений, до того, как исследовать возможные решения, систему бывает полезно упростить или использовать замену переменных.
Для начала мы разберем несколько простых уравнений и систем, а затем перейдем к более сложным, которые использовались в задачах ЕГЭ прошлых лет. Отметим, что для проверки правильности решений систем логических уравнений можно использовать бесплатную программу, которая размещена на сайте [4].
Подведение итогов – второй урок.
Представление результатов групповой работы.
Проверка правильности решений систем логических уравнений используя бесплатную программу, которая размещена на сайте [4]. Обсуждение. Экспертиза между группами результатов работы групп по поиску по поиску оптимального решения для каждой из предложенных задач.
Содержание кейса:
Что нужно знать:
таблицы истинности логических операций «И», «ИЛИ», «НЕ», «ЕСЛИ…, ТО…», «ТОГДА И ТОЛЬКО ТОГДА»
правила преобразования логических выражений;
законы алгебры логики
Законы логики
Презентация « [link] »
(Простейшие случаи и Демоварианты ЕГЭ). Задание 3. Решите задачи: (Другие задачи)
Задание 4. Сохраните практическую работу под Вашей фамилией и отправьте учителю по электронной почте или Дневник.ru.
Л – логический вывод
Логический вывод:
Мы рассмотрели класс задач, связанных с решением систем логических уравнений. Эти решения удобно представлять в виде битовых векторов.
Существует аналогия между представлением решения логических систем в виде битовых векторов и представлением решения алгебраических систем в виде точек (векторов) на плоскости или в пространстве. Аналогия между алгеброй и логикой представляется продуктивной при разборе рассматриваемой темы.
Проследим эти аналогии и различия.
Рассмотренные задачи во многом непривычны, если отталкиваться от уравнений и систем, изучаемых в курсе математики.
Непривычна сама постановка задачи, предполагающая, что система имеет много решений. В школьной математике уравнение (система), как правило, имеет одно решение или немного решений. (На это отличие стоит обратить внимание учеников, особенно сильных.)
Непривычно то, что мы стараемся понять, как устроено все множество решений, и только затем, на основе этого понимания, определяем количество решений и (хотя это и не требуется по условию задачи) можем выписать сами решения. Уравнения, входящие в систему, рассматриваются как ограничения, наложенные на комбинации битов.
Аналогом такой постановки задачи в школьной математике являются вопросы типа “Как устроено множество точек (x, y), удовлетворяющих уравнению x2 y2 =1?”. Умение переводить описание набора битовых решений с языка систем логических уравнений на более “естественный” язык — это то, что требуется ученику при решении рассмотренных задач.
Отметим, что при решении некоторых задач, даже поняв, какие ограничения на множество битовых векторов-решений накладывают уравнения, мы не можем написать явную формулу для количества решений. Однако во многих подобных случаях удается написать рекуррентное уравнение и с его помощью решить задачу (см. задачи 6, 7).
Таким образом, задача сводится к тому, чтобы выявить структуру всех решений (определить, какие комбинации битов допустимы, а какие — запрещены) и подсчитать количество подходящих решений, используя формулы комбинаторики. Так же, как и при решении алгебраических уравнений, при этом нужно:
1) уметь решать базовые (“элементарные”) уравнения и
2) уметь упрощать уравнения с помощью тождественных преобразований и замен переменных.
3) знать законы логики (таблица 1 кейса).
Обоснование целесообразность применения
Данная технология соответствует принципам системно-деятельностного подхода и поэтому востребована в условиях введения ФГОС основного общего образования.
В основе технологии кейсов лежит имитационное моделирование.
Данная технология опирается на дидактические принципы:
Индивидуальный подход к каждому учащемуся, учет особенностей познавательных стилей и потребностей, в процессе обсуждения и размышления каждый будет использовать собственные возможности, дополнять и развивать групповое суждение.
Вариативность, данный метод предполагает возможность опоры на разнообразный материал и способы его обработки, что обеспечивает свободу в обучении и возможность выбора.
Активность обучения обеспечивается непосредственным вовлечением обучающихся в решение «реальных» проблем.
Умение работать с информацией.
Успешности в обучении, которая обеспечивается за счет опоры на сильные стороны обучающихся.
Проблемности, проявляющейся опоре на конкретные задачи, возникающие в реальной практике жизни, образования.
