ГБОУ Гимназия №107

Пугаева Ольга Израилевна, учитель информатики высшей категории

Киреева Ирина Семеновна, учитель информатики первой категории

Из опыта преподавания практического использования

основ математической логики и теории множеств

в задачах по запросам к поисковому серверу

В современном образовании используются различные подходы к достижению важных целей:

формирования у учащихся интеллектуальной активности, приобретения навыков

самостоятельного «добывания» знаний, выработки познавательного инстинкта,

позволяющего испытывать удовлетворения от решения поставленных задач.

К ним относится и системно-деятельностный подход, который осуществляется через такую

организацию учебного процесса, в которой главное место отводится активной и в

максимальной степени самостоятельной познавательной деятельности ученика.

Не малую роль играет и метапредметный подход, призванный не только способствовать

выработке у учащихся обобщенности знания, но и минимизировать разобщенность,

оторванность друг от друга различных учебных предметов.

Решение задач по запросам к поисковому серверу позволяет учителю использовать эти оба

эти подхода с высокой степенью эффективности. В них используются как знание основ

математической логики из информатики, так и знание основ теории множеств из математики.

И так как эти разделы являются в высокой степени абстрактными, то их изучение

подразумевают развитие у учащихся обобщенного, абстрактного мышления, способности

использовать обобщенные приемы для решения конкретных задач.

Решение задач по запросам к поисковому серверу напрямую связано с темами «Основы

математической логики» и «Телекоммуникации», а также, что немаловажно, является частью

ЕГЭ по информатике.

В статье рассматривается один их вариантов изучения этой темы и решение некоторых

проблем, которые при этом могут возникнуть.

По ходу изучения данной темы учитель может решить следующие задачи:



Формирование у учащихся умения анализировать задачу с целью выработки

оптимального пути ее решения.



Формирование у учащихся коммуникативных навыков при групповой работе.



Способствование приобретению навыков применения абстрактных знаний к

решению конкретных задач.

Предполагается, что перед изучением данной темы учитель выдает учащимся домашнее

задание:



Повторить элементарные понятия теории множеств из школьного курса

математики и, в частности, операции пересечения и объединения множеств,

мощность множества и представление отношений между множествами с помощью

кругов Эйлера-Венна.



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



Предложил подумать, какое отношение могут иметь понятия из теории множеств к

решению предъявленной задачи.

На следующем уроке учитель предлагает решить задачу из домашнего задания двумя

способами: с помощью кругов Эйлера-Венна и с использованием формул включения-

исключения из теории множеств.

Условие задачи:

Подключившись к сети Интернет, вы выдали три запроса и получили количество

найденных страниц по каждому из них:

Запрос

Количество страниц

Джульетта

45

Ромео & Джульетта

30

Ромео + Джульетта

57

Сколько страниц выдал бы поисковик по запросу Ромео?

С решением этой простейшей задачи с помощью кругов Эйлера-Венна при контроле и

коррекции учителя дети справляются достаточно быстро:

Обозначения: ч1, ч2, ч3 – части рисунка 1.2.3

Учащиеся самостоятельно, но при коррекции учителя определяют, какие части

рисунка какому запросу соответствуют, и находят искомое количество страниц:

1.

Ромео & Джульетта = ч3 = 30

2.

Ромео + Джульетта = 57 = ч1 + ч2 + ч3



ч1 = 57 – ч2 -30 = 27 – ч2

3.

Т.к. слово Джульетта было и на тех страницах, где только Джульетта, и на тех,

где была Джульетта, но был еще и Ромео, то:

Джульетта = ч2 + ч3 = 45



ч2 = 45 – 30 = 15



ч1 = 27-15-12

4.

Т.к. слово Ромео было и на тех страницах, где только Ромео, и на тех, где был

Ромео, но была еще и Джульетта, то:

Х = Ромео = ч1 + ч3 = 12 + 30 = 42

Но учащиеся никогда не решали подобные задачи с помощью формул включения-

исключения из комбинаторики ( правда, в дальнейшем они достаточно быстро убеждаются,

что этот способ удобнее предыдущего). Поэтому здесь необходимо объяснение учителя.



Обозначение: kN – количество элементов в множестве N



Формула включения-исключения для двух множеств А и В:

к(А+B) = к(А) + К(В) – к(A * B),

где к – количество элементов в объединении множеств А и В.



И здесь появляется некоторая проблема.



За несколько лет преподавания этой темы ни разу не было случая, чтобы дети не

спросили, откуда берется «минус».



Поэтому здесь необходимы подробные объяснения учителя:



Из условия задачи мы с вами знаем, что по запросу Ромео + Джульетта

поисковик выдал 57 страниц.



Подсчитаем теперь количество элементов в объединении множеств Ромео и

Джульетта по формуле включения-исключения без смутившего нас

отрицания:

к(Ромео + Джульетта) = к(Ромео) + К(Джульетта) =

ч1 + ч3 + ч2 + ч3 = 42 + 45 = 87, а должно быть 57!



Почему так? Потому, что ч3 мы вынуждены были включить дважды!!!

Вот поэтому в формуле и предусматривается отрицание одного из этих двух

включений.

После этих объяснений решение этой задачи по формулам включения-исключения не

вызывает у учащихся проблем:

к(Ромео + Джульетта) = к(Ромео) + К(Джульетта) – к(Ромео * Джульетта) =

= Х+45-30 = 57



Х = 87-45 = 42

Следующий этап в изучении данной темы – совместно с учителем, но максимально

самостоятельно попытаться решить задачу с тремя множествами, но с использованием

формулы включения-исключения для двух множеств.

Пример задачи:

Запрос

Количество страниц

Польша & Литва

320

(Польша & Литва) | (Польша & Молдова)

455

Польша & Молдавия

355

Какое количество страниц будет найдено по запросу Польша&Литва&Молдавия?

Исходя из нашего опыта, можно предположить, что вряд ли дети сразу самостоятельно

справятся с подобной задачей. Поэтому нужна подсказка учителя:



В этой задаче три множества: Польша, Литва и Молдова.



Казалось бы, нельзя использовать формулу включения-исключения для двух

множеств!



Но… если сделать обозначения: А = (Польша & Литва); В = (Польша & Молдова),

то у нас останется два множества, а не три, и формулу можно будет использовать.

Наиболее успешное продолжение – переход к коллективной работе учащихся:



Быстрое разделение учащихся на группы.



Сообщение учителя, что победителем будет та группа, которая быстрее и

правильнее всех выполнит задание.



Определение количества времени на выполнение задачи.

При коллективной работе и мягкой корректировке учителя кто быстрее, кто медленнее, но

дети справляются с решением задач такой сложности:



Сокращения: (П - Польша, Л –Литва, М – Молдова)



Если А = (П * Л), а В = (П * М), то

к((П *Л) + (П*М)) = к(П*Л) + к(П*М) – к ((П*Л) * (П*М))



Отсюда к(П*Л*М) = к(П*Л) + к(П*М) – к((П *Л) + (П + М)) =

320 + 355 – 455 = 220

Дальнейшее увеличение уровня сложности заключается в том, что для решения необходимо

знание распределительных законов алгебры логики:

(A * B) + C = (A + C) * (B + C)

(A + B) * C = (A * C) + (B * C)

Решение задач этого уровня можно рассмотреть на следующем примере:

Запрос

Кол-во страниц (в тыс.)

Парк & Сад

255

Парк & Заповедник

222

Парк & Сад & Заповедник

50

Определить количество страниц, которое будет найдено

по запросу Парк & (Сад | Заповедник).

Коллективное решение с помощью кругов Эйлера-Венна приводит к достаточно быстрому

результату.

Но опять же дети вряд ли самостоятельно решат эту задачу с помощью формул включения-

исключения. Поэтому нужны объяснения учителя:



Сокращения: П – парк; С – сад; З - заповедник



П & (С | З) = по распределительному закону = (П*С) + (З*С)



Если принять за первое множество П*С, а за второе - З*С, то можно использовать

формулу включения-исключения для двух множеств.



Х = к((П*С) + (З*С)) = к (П*С) + к(З*С) – к(П*С*З) = 255+222-50 = 427

Дальнейшее усложнение задач подобного рода (вплоть до сложности заданий №17 из ЕГЭ по

информатике) заключается в использовании более сложных обозначений с объединенными

или пересекаемыми множествами и применением формулы включения-исключения для трех

множеств.

Примером подобных задач может быть следующая:

Какое количество страниц будет найдено по запросу Город & Регион?

Решить задачу с помощью формулы включения-исключения для трех множеств и

проверить решение с помощью кругов Эйлера-Венна.

Запрос

Кол-во страниц (в тыс.)

Город

540

Область

350

Регион

120

Город | Область | Регион

700

Город & Область

300

Область & Регион

0

По завершении изучения темы не стоит забывать о награждении группы победителей.

Успешность и результативность изучения предлагаемой темы зависит как от качества

режиссуры учителя, так и от мотивированности учащихся.

Обычно на этих уроках соревновательный элемент, вводимый учителем, и, в особенности,

учет скорости решения задачи, вызывает высокую мотивацию и большую активность

учащихся. Чаще всего учащиеся находят решение задач, что, естественно, вызывает

удовлетворение от проделанной работы, еще более увеличивающееся при эмоциональном

поощрении учителя.