Теория графов в школьной информатике согласно ФГОС ООО 2021

Учитель: Приветствует обучающихся, проверяет готовности к уроку. На доске написан эпиграф к уроку: “Кто владеет информацией, тот владеет миром”. Учитель спрашивает у учеников, как они понимают данный эпиграф и задает наводящие вопросы.

Зачем нам нужна информация? Зачем мне надо это знать? Чему я могу научиться? Что узнаю? Что для этого использую? Как смогу применять полученные знания? Как можно использовать информацию?

Учащиеся: Отвечают на вопросы учителя и вместе с ним приходят к следующим выводам.

Вовремя полученная информация и умение правильно распорядиться ею позволяют достичь поставленные цели и разрешить многие проблемы.

Знания это тоже информация и они расширяют возможности человека.

Учитель:

1.Что мы изучали на последнем уроке?

2.А что такое информационная модель?

3.Перечислите основные формы представления информационных моделей!

4.Что такое графическая модель?

5.Какие виды графических моделей бывают?

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

Рис. 1

6.Что общего у этих моделей?

Как эти модели называются и какими свойствами они обладают?

Учащиеся:

1.Информационные модели.

2.Описание объекта моделирования

3.Вербальные (словесные), табличные, графические, математические и др. 4.Графическая информационная модель – это наглядный способ представления объектов и процессов в виде графических изображений.

5.Чертежи, графики, диаграммы, модели, схемы.

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

6.Этот вопрос вызывает затруднение учащихся.

Учитель: Давайте еще раз проговорим в чем заключается затруднение, вызванное пробным учебным заданием.

Учащиеся: Мы не знаем как называется данный вид моделей и какими свойствами они обладают.

Учитель: Представленные на рисунке модели называются графами. Так как можно сформулировать тему нашего урока?

И что нужно для раскрытия этой темы?

Учащиеся: Формулируют с помощью учителя тему урока и план урока.

Тема урока - Графы

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

Учитель: Даются определения таких понятий как графы, вершина, ребро, путь, связные и несвязные графы, степень вершины, Лемма о «рукопожатиях».

Задачи на построение оптимального пути между вершинами графа.

Затем даются такие понятия как ориентированный и неориентированный граф, цикл, ациклический граф.

Задачи на определение количества различных путей между вершинами ориентированного ациклического графа.

Учащиеся: Вначале учащиеся слушают учителя и знакомятся с основными понятиями, связанными с графами.

Учащиеся разбиваются на две группы

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

Вторая группа по карточке 2 изучает определение различных путей между вершинами ориентированного графа.

Затем группы обмениваются знаниями.

Учитель: Задаются вопросы на определение изученных понятий, связанных с графами.

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

Учащиеся: Отвечают на поставленные вопросы и задания учителя и проговаривают все это во внешней речи.

Учитель: Задача 1. Города А, В, С связаны дорогами. Известно, что существуют дороги А и С, С и В (две дороги), А и В, С и D (две дороги), В и D. Сколькими различными способами можно проехать из города A в город D, не заезжая дважды в один город? [1, c. 7]

Рис. 2

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

Рис.3 

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

Учитель: Задача ОГЭ. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только водном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? (Ответ: 6) [2, c. 7]

Рис. 4

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

Учитель: Дает серию вопросов для оценки учащимися свой работы на уроке.

Достигнута ли цель урока?

Что понравилось, что не понравилось.

С какими трудностями встретились?

Учащиеся: Отвечают на вопросы и тем самым оценивают свою работу на уроке.

Учитель: На доске написан эпиграф к уроку.

 «Знание только тогда знание, когда оно приобретено усилиями своей мысли, а не памятью». Л.Н. Толстого:

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

Зачем мне нужны знания? Где и как я могу их применить??

Учащиеся:

Отвечают на вопросы учителя и вместе с ним приходят к следующим выводам.

Смысл высказывания Л.Н. Толстого в том, что знания тогда наиболее эффективны, когда человек не просто пассивно запоминает новые знания, а принимает активное участие в их освоении, усилиями собственных мыслей и разума

Учитель:

1.Что мы изучали на последнем уроке?

2.А что такое граф?

3.Какие понятия связаны с графами?

Здесь представлен определенный вид графов

Рис. 5

4.Как называется этот вид графов? Какими свойствами обладают? При решении каких задач используется?

Учащиеся:

1.Графы.

2.Графом называется геометрическая фигура, состоящая из точек и соединяющих их линий.

3.Вершина, ребро, путь, связные и несвязные графы, степень вершины, ориентированные и неориентированные графы, цикл.

4.Эти вопросы вызывает затруднение учащихся.

Учитель: Давайте еще раз проговорим в чем заключается затруднение, вызванное пробным учебным заданием.

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

Учитель: Представленные на рисунке виды графов называются деревьями. Так как можно сформулировать тему нашего урока?

И что нужно для раскрытия этой темы?

Учащиеся: Формулируют с помощью учителя формулируют тему урока и план урока.

Тема урока - Деревья

План урока – изучить понятия,

связанные с деревьев, свойства деревьев и их использование при решении задач

Учитель: Вводятся следующие понятия.

Дерево. Корень, вершина (узел), лист, ребро (дуга) дерева. Высота дерева. Поддерево.

Рис. 6

Задача. Два игрока, куча из S камней. За один ход игрок может взять один или два камня. Тот, кто возьмет последний камень проигрывает.

Рис. 7

Учащиеся:Вначале учащиеся слушают учителя и знакомятся с основными понятиями, связанными с деревьями и их свойствами.

Затем вместе с учителем строят дерево перебора вариантов решения задачи.

Для того, чтобы доказать выигрыш строят неполное дерево

Рис. 8

В неполном дереве указываются всевозможные ходы того, кто проигрывает и достаточно одного хода того, кто выигрывает.

И приходят к выводу, чтобы выиграть нужно оставлять сопернику 3k+1 камней

Учитель: Задаются вопросы на определение понятий, связанных с деревьями.

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

Учащиеся: Отвечают на поставленные вопросы и задания учителя и проговаривают все это во внешней речи.

Учитель: Задача 1. Шоколадка представляет собой прямоугольник, разделенный углублениями на квадратики. Двое по очереди разламывают ее на части по углублениям: за один ход можно разломать любой из кусков (больше одного квадратика) на два. Кто выигрывает при правильной игре? (У кого из игроков есть выигрышные стратегии?).

Задача 2. В коробке 24 спички, за один ход можно взять любое количество спичек от одного до пяти. Проигрывает тот, кто не может сделать ход. Кто из игроков выиграет при правильной игре?

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

Учитель: Задача. Фишка стоит в углу шахматной доски размером 8 на 8. Двое игроков по очереди передвигают ее на соседнее поле. Поля соседние, если у них есть общая сторона. Второй раз ходить на поле, где уже побывала фишка нельзя. Тот, кому некуда ходить, проигрывает. Кто победит в правильной игре?

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

Учитель: Дает серию вопросов для оценки учащимися свой работы на уроке.

Достигнута ли цель урока?

Что понравилось, что не понравилось.

С какими трудностями встретились?

Учащиеся: Отвечают на вопросы и тем самым оценивают свою работу на уроке.