Презентация к мастер-классу "Внеурочное занятие по курсу "Логика" "Решение комбинаторных задач с помощью графов"

Основные понятия

• ГРАФ – совокупность объектов со связями между ними. Объекты представляются как вершины , или узлы графа , а связи – как дуги , или ребра . Исследование графов ведется комбинаторными методами математики.
• КОМБИНАТОРНАЯ ЗАДАЧА – задача, требующая осуществления перебора всех возможных вариантов или подсчета их числа.

Цель занятия:

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

Разминка «Улыбнёмся»

• Сколько концов у одной палки? А у двух? А у двух с половиной?
• Когда черной кошке легче всего пробраться в дом?
• На столе лежат линейка, карандаш, циркуль и резинка. На листе бумаги нужно начертить окружность. С чего начать?

Цель занятия: организовать деятельность учащихся по освоению понятия «граф» и способа решения комбинаторных задач с помощью графов

• Сколько месяцев в году имеют 28 дней?
• Как правильно сказать: "9 и 7 будет 15" или "9 плюс 7 равно 15"?
• Что можно приготовить, но нельзя съесть?
• Возможно ли такое: две головы, две руки и шесть ног, а в ходьбе только четыре?

Способы решения комбинаторных задач

Организованный перебор

вариантов

Таблица

Задача 1

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

Решают одним из известных способов, затем предлагаем заменить этот способ на чертёж. Актуализация

Способы решения комбинаторных задач

Организованный перебор

вариантов

Таблица

Решение комбинаторных задач с помощью графов

Познакомьтесь с темой нашего занятия. Какие вопросы хотите задать? (Что такое графы? Как с их помощью решать комбинаторные задачи?)

Сегодня на занятии я хочу узнать:

• Что такое графы?
• Как графы могут помочь решить задачу?

Сегодня на занятии я хочу научиться:

1. Решать комбинаторные задачи с помощью графов.

Целеполагание

Задача 1

10 рукопожатий

Как устроен граф

Вершина графа

Ребро

Сколько вершин у графа? А рёбер? Что обозначает вершина? Ребро?

Задача 2

Сколько двузначных чисел можно составить, используя цифры 1, 2, 3, 4?

Решение

Решают коллективно. Строят граф на доске. Может получится граф без стрелок. Тогда будет только 8 ребер. Это не верно. Могут забыть про число 11, 22 , 33, 44. Обсуждаем варианты построения графа учитывая все ошибки.

Задача 2

16 чисел

1

2

3

4

Заготовить для каждой (ученика) лист с числами. Сравните своё решение с решениями других учеников и с образцом. Почему здесь рёбра со стрелками?(Можно менять местами числа 13, 31), что означает круглая стрелка? (Можно составить число 11, 33, 44 ,22) Таким образом ребро графа может иметь направление(односторонняя связь между вершинами), а может быть не направленным, т. е. связь между вершинами двусторонняя. Попробуем в этом разобраться. Если ребро графа имеет направление его принято называть дугой. Промежуточная рефлексия: Что узнали о новом способе?

13

13

Групповая работа Задача 3

Сколько разностей, значения которых вы сумеете найти, можно составить из чисел 30, 25, 17, 9 , если для их составления брать два числа?

Решите задачу, изобразив граф.

Решение

В группах. Дать установку делать крупно, писать номер группы.

13

13

Задача 3

10 разностей

13

Задача 4

Соедини линией каждое задание с графом, который ему соответствует.

Решение

1. Используя цифры 4, 5, 6, запиши все возможные двузначные числа.

2. Используя цифры 4, 5, 6, запиши двузначные числа, которые меньше 50.

Самостоятельно. Самооценка.

3. Используя цифры 4, 5, 6, запиши двузначные числа, которые больше 50.

Задача 4

1. Используя цифры 4, 5, 6, запиши все возможные двузначные числа.

2. Используя цифры 4, 5, 6, запиши двузначные числа, которые меньше 50.

Проверка решения. Самооценка.

3. Используя цифры 4, 5, 6, запиши двузначные числа, которые больше 50.

Задача 5

Рассмотри граф.

Подчеркни те задания, которые ему соответствуют.

Из каждой пары чисел 18, 36, 54 составь все возможные:

а) суммы; б) разности;

в) произведения; г) частные,

значение которых ты можешь вычислить.

Решение

Самостоятельно.

Задача 5

а) суммы; б) разности;

в) произведения; г) частные.

Задача 6

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

Решение

Самостоятельная работа

Задача 6

15 пар

Рефлексия

• Сегодня на занятии я узнал(а)…
• Сегодня на занятии я научился (лась)…

Резервное задание 1

Из каждой пары чисел 63, 9, 7, 70 составь всевозможные суммы.

Выбери граф, который соответствует данному заданию.

Решение

Решение резервного задания 1

Резервная задача 2

Миша, Вася, Катя и Лиза поздравили друг друга с Новым годом, подписав открытки. Покажи красным цветом стрелки, которые показывают, кому Миша подписал открытки, а синим – кто подписал Мише.

МИША ЛИЗА

КАТЯ ВАСЯ

Решение

Что означают стрелки? (Кто кому подписал открытки)

Решение резервной задачи 2

Миша Лиза

Катя Вася

Решение комбинаторных задач с помощью дерева возможных вариантов

ДЕРЕВО ВОЗМОЖНЫХ ВАРИАНТОВ – граф, схема, отражающая структуру задачи, упорядочения многошагового процесса принятия решений. Ветви дерева отображают различные события, которые могут иметь место, а корень дерева – состояние, в котором возникает необходимость выбора.

Лиса Алиса и кот Базилио решили украсть из сейфа золотой ключик Буратино, который знает пока 4 цифры:1,2,3,4.Сколько вариантов придётся перебрать им, чтобы проникнуть в сейф, подобрав двузначный код?

Код сейфа

1

2

4

3

4

3

2

1

3

1

2

4

3

2

1

4

3

1

2

4

Логические задачи, которые решаются с помощью графов

В нашем лесу каждый занят своим делом: одни плетут корзины, другие ловят рыбу. Ремеслу мы научились друг у друга. Кот учился у Выдры, Ёж – у Зайца, Лиса – у Волка, а Мышь – у Ежа. Бобёр учил Волка и Выдру, Заяц – Белку, а Барсук – Зайца. Бобёр был учеником Медведя, а Ёж – учителем Дятла. Лучше всех плетёт корзины Ёж. Кто чем занимается? Кто из зверей раньше всех научился ловить рыбу, а кто плести корзины?

Плетёт корзины.

Рассмотрим отношение быть учителем, т.е. стрелку ведём от учителя к ученику. Т. к. ёж плетёт корзины, то вместе с ним их плетут Дятел, Барсук, Белка, Мышь и Заяц.