Ефанова Н.В.

Кейс «Системы логических уравнений: решение с помощью битовых цепочек»

Предмет: Информатика и ИКТ

Класс: 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]. Обсуждение. Экспертиза между группами результатов работы групп по поиску по поиску оптимального решения для каждой из предложенных задач.

Содержание кейса:

Что нужно знать:

• таблицы истинности логических операций «И», «ИЛИ», «НЕ», «ЕСЛИ…, ТО…», «ТОГДА И ТОЛЬКО ТОГДА»

• правила преобразования логических выражений;

• законы алгебры логики

• • Законы логики

  • Презентация «Системы логических уравнений: решение с помощью битовых цепочек» (материал [1].) .

• Решение - битовый вектор

• Простейшие случаи

• Демоварианты ЕГЭ

• Другие задачи

• Литература

1. Поляков К.Ю., Ройтберг М.А. Системы логических уравнений: решение с помощью битовых цепочек // Информатика, № 12, 2014, с. 4-12.

2. Сопрунов С.Ф. Непростое программирование на Лого. М.: Московский институт открытого образования, 2011.

3. Аналитический отчет о результатах ЕГЭ-2011. Информатика и ИКТ. URL: fi pi.ru/sites/default/files/document/1408709946/2.11%20inf-11-11.pdf (дата обращения 16.09.2014).

4. Поляков К.Ю. Подготовка к ЕГЭ по информатике [Электронный ресурс] URL: kpolyakov.spb.ru/school/ege.htm (дата обращения 16.09.2014).

5. Поляков К.Ю. Логические уравнения // Информатика, № 14, 2011, с. 30-35.

6. Мирончик Е.А. Метод отображения // Информатика, № 10, 2013, с. 18-26.

7. Мирончик Е.А. Люблю ЕГЭ за В15, или Еще раз про метод отображения // Информатика, № 7-8, 2014, с. 26-32.

8. Аналитический отчет о результатах ЕГЭ-2012. Информатика и ИКТ. URL: fipi.ru/sites/default/files/document/1408709880/2.11.pdf (дата обращения 16.09.2014).

9. Поляков К.Ю., Еремин Е.А. Информатика. 10-й класс. Углубленный уровень. В двух частях. М.: Бином, 2014.

10. Демоверсия, спецификация, кодификатор ЕГЭ-2015 по информатике [Электронный ресурс] URL:fipi.ru/sites/default/files/document/1409834615/inf11_2015.zip
    
    (дата обращения 16.09.2014).

11. Лачин В.И., Савёлов Н.С. Электроника: Учебное пособие. Ростов-на-Дону: Феникс, 2007.

Творческая практическая работа

Ф.И._________________________ класс ________

Задание 1. Самостоятельно изучите суть метода решения Системы логических уравнений: решение с помощью битовых цепочек (Решение - битовый вектор).

Задание 2. Самостоятельно изучите задания с решениями из презентации «Системы логических уравнений: решение с помощью битовых цепочек</» (Простейшие случаи и Демоварианты ЕГЭ).

Задание 3. Решите задачи: (Другие задачи)

Задание 4. Сохраните практическую работу под Вашей фамилией и отправьте учителю по электронной почте или Дневник.ru.

Л - логический вывод

Логический вывод:

Мы рассмотрели класс задач, связанных с решением систем логических уравнений. Эти решения удобно представлять в виде битовых векторов.

Существует аналогия между представлением решения логических систем в виде битовых векторов и представлением решения алгебраических систем в виде точек (векторов) на плоскости или в пространстве. Аналогия между алгеброй и логикой представляется продуктивной при разборе рассматриваемой темы.

Проследим эти аналогии и различия.

• Рассмотренные задачи во многом непривычны, если отталкиваться от уравнений и систем, изучаемых в курсе математики.

• Непривычна сама постановка задачи, предполагающая, что система имеет много решений. В школьной математике уравнение (система), как правило, имеет одно решение или немного решений. (На это отличие стоит обратить внимание учеников, особенно сильных.)

• Непривычно то, что мы стараемся понять, как устроено все множество решений, и только затем, на основе этого понимания, определяем количество решений и (хотя это и не требуется по условию задачи) можем выписать сами решения. Уравнения, входящие в систему, рассматриваются как ограничения, наложенные на комбинации битов.

Аналогом такой постановки задачи в школьной математике являются вопросы типа "Как устроено множество точек (x, y), удовлетворяющих уравнению x2 y2 =1?". Умение переводить описание набора битовых решений с языка систем логических уравнений на более "естественный" язык - это то, что требуется ученику при решении рассмотренных задач.

Отметим, что при решении некоторых задач, даже поняв, какие ограничения на множество битовых векторов-решений накладывают уравнения, мы не можем написать явную формулу для количества решений. Однако во многих подобных случаях удается написать рекуррентное уравнение и с его помощью решить задачу (см. задачи 6, 7).

Таким образом, задача сводится к тому, чтобы выявить структуру всех решений (определить, какие комбинации битов допустимы, а какие - запрещены) и подсчитать количество подходящих решений, используя формулы комбинаторики. Так же, как и при решении алгебраических уравнений, при этом нужно:

1) уметь решать базовые ("элементарные") уравнения и

2) уметь упрощать уравнения с помощью тождественных преобразований и замен переменных.

3) знать законы логики (таблица 1 кейса).

Обоснование целесообразность применения

Данная технология соответствует принципам системно-деятельностного подхода и поэтому востребована в условиях введения ФГОС основного общего образования.

В основе технологии кейсов лежит имитационное моделирование.

Данная технология опирается на дидактические принципы:

1. Индивидуальный подход к каждому учащемуся, учет особенностей познавательных стилей и потребностей, в процессе обсуждения и размышления каждый будет использовать собственные возможности, дополнять и развивать групповое суждение.

2. Вариативность, данный метод предполагает возможность опоры на разнообразный материал и способы его обработки, что обеспечивает свободу в обучении и возможность выбора.

3. Активность обучения обеспечивается непосредственным вовлечением обучающихся в решение «реальных» проблем.

4. Умение работать с информацией.

5. Успешности в обучении, которая обеспечивается за счет опоры на сильные стороны обучающихся.

6. Проблемности, проявляющейся опоре на конкретные задачи, возникающие в реальной практике жизни, образования.