Урок информатики по теме «Графы. Использование графов при решении прикладных задач»

Тема: Графы. Использование графов для решения прикладных задач

 

Цели-результаты:

- Предметные:

обобщить и систематизировать знания о графах, их видах и свойствах;

рассмотреть типы задач, которые можно решить с использованием графов;

отработать навыки преобразования ориентированного графа в дерево;

сформировать навыки построение путей в графе, поиска кратчайшего пути;

закрепить навыки работы в среде текстового процессора Microsoft Word;

- Личностные:

Развитие логического мышления, т.е. умения анализировать, обобщать, классифицировать, составлять план при выполнении практической работы на компьютере;

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

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

- Метапредметные: развитие у учащихся универсальных учебных действий

Регулятивные:

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

Коммуникативные:

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

Познавательные:

умения создавать графические информационным модели;

умения представлять, анализировать и обобщать информацию, полученную в ходе исследования;

умения делать выводы, формулировать алгоритм.

 

Тип урока: обобщения и систематизации знаний, проблемноориентированый

 

Виды работ: фронтальная беседа, работа в группах, обсуждение, доклады учащихся

 

Оборудование: на доске эпиграфы, граф дорог; презентация, результаты

 

ПЛАН УРОКА

Организационный момент, приветствие - 2 минуты

Проверка домашнего задания и демонстрация путей решения задач с использованием графов – 5 минут;

Постановка проблемы – 3 минуты;

Анализ проблемной ситуации и возможные пути ее решения, определение темы урока – 2 минуты;

Актуализация опорных знаний, умений, навыков, которые потребуются для решения поставленных задач на уроке - 4 минуты;

Возврат к проблемной ситуации с задачей и обсуждение способов решения – 2 минуты;

Решение задачи – 15 минут;

Анализ результатов - 3 минуты;

Проверка решения с использованием сервиса Google-карты – 5 минут;

Подведение итогов урока - 2 минуты;

Домашнее задание - 2 минуты;

 

ХОД УРОКА

 

«Безногий, ковыляющий по верной дороге, обгоняет всадника, скачущего не туда»

Френсис Бэкон

«Мир уступает дорогу тому, кто знает куда идет»

Ральф Уолдо Эмересон

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

Б. Вербер

Приветствие. Здравствуйте, ребята!

Сегодняшний наш урок я бы хотела начать со слов Френсиса Бэкона и Ральфа Уолдо Эмерсона «Безногий, ковыляющий по верной дороге, обгоняет всадника, скачущего не туда», «Мир уступает дорогу тому, кто знает куда идет». Конечно, эти философские высказывания связаны с выбором правильного жизненного пути. И вы стоите перед таким выбором в этом учебном году, как выпускной класс. Но сегодня на уроке мы увидим, что данные высказывания можно применить и к обычным путешествиям.

Проверка домашнего задания

Но прежде чем мы начнем новую тему давайте вспомним, какую тему мы изучали на прошлом уроке?

Чтобы было задано домой?

Как вы решали данную задачу?

Вызывается 1 человек к доске, для демонстрации решения домашней задачи.

Задача на Слайде 2

Решение

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

Ожидаемое решение:

расставляем бусины на первом месте (по правилу возможны три варианта)

Расставляем бусины на втором месте, исключая те варианты, когда бусина стоит на первом месте;

Расставляем бусины на третьем месте по правилу, исключая варианты, когда такая же бусина стоит на втором месте.

Считаем количество веток полученного дерева

 

Учитель:

- Каким способом мы решили данную задачу? (Ожидаемый ответ: построили дерево возможных вариантов и посчитали его ветви)

Данным методом так же можно решать и много других задач, в чем мы сегодня с вами убедимся.

 

3. Постановка проблемы.

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

Учеников 9-х классов города Алчевска пригласили в колледж Восточно-украинского национального университета им. Даля на день открытых дверей, который будет проходить в главном корпусе университета.

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

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

Слайд 3 (на слайде схема дорог)

 

 

Расшифровка остановок на Слайде 4 (приведен скриншот):

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

 

4. Анализ проблемной ситуации и возможные пути ее решения

На слайде 5 вопросы:

- Можем ли мы сразу решить эту задачу, только посмотрев на схему? (ожидаемый ответ: нет)

- Что нам мешает решить задачу? (ожидаемый ответ: слишком много возможных вариантов, нужно проследить каждый маршрут, в которых легко запутаться, не все дороги совпадают с маршрутами автобусов, нужно учесть варианты с пересадками)

- А что из изученного нами поможет решить эту задачу? (Ожидаемый ответ: графы)

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

Давайте с вами вспомним, что же такое граф и какие бывают графы.

Актуализация (фронтальный опрос):

На слайде 6 вопросы к актуализации.

- Что такое граф?

- Из каких объектов состоит граф? (Ожидаемый ответ: ребра, вершины)

- В чем особенности взвешенного графа? (Ожидаемый ответ: у взвешенного графа ребра характеризуются дополнительной величиной – весом ребра)

- Наш граф является взвешенным или нет? (Ожидаемый ответ: взвешенным)

- Что является весом ребер в графе? (Ожидаемый ответ: время пути между остановками в минутах)

- Чем отличается ориентированный граф, от неориентированного? (Ожидаемый ответ: в ориентированных графах указывается направление пути)

- Наш граф является ориентированным или нет? (Ожидаемый ответ: ориентированным)

- Что такое дерево? (Ожидаемый ответ: Дерево – это граф, представленный в виде иерархической системы)

 

Возврат к проблемной ситуации и обсуждения способа ее решения

 

Вернемся к нашей задаче и посмотрим на нее внимательно. Как можно решить эту задачу?

Ожидаемые ответы: составить дерево возможных вариантов, исключая пересадки, где это необходимо.

После ответов демонстрируется слайд 7:

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

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

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

Для ускорения работы воспользуйтесь шаблоном Маршрут.doc, который находится в Материалах. Так же в материалах находится файл с задачей Задача_маршрут. Обязательно сохраните файл в свою рабочую папку. А после того, как определите маршрут, расшифруйте по таблицу название вершин графа, чтобы понять через какие остановки следует автобус.

Решение задачи за компьютерами.

Ответы:

Количество возможных путей: 8

Самый короткий маршрут 150 автобус, 35 минут (183 – 37 минут, 117 и 129 – 40 минут)

 

Анализ результатов

Зачитывает один из учеников, что у него получилось. (Демонстрируется выполненная работа с использованием сетевой программы). Результат записывается на доске.

Учитель: У всех так получилось? Есть те, у кого получились другие варианты? Кто не успел выполнить задание?

На слайде 9 демонстрируются правильные результаты:

Проверка результата

А теперь я предлагаю вам проверить наши расчеты. Один из учеников заранее получил особое домашнее задание. С помощью сервиса Google-карты определить возможные маршруты следования от ж/д вокзала до университета и найти самый короткий путь. Ученик демонстрирует результаты свой работы

Демонстрация выполнения задания в Google-картах. (Ответ должен совпадать)

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

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

Подведение итогов и оценивание

Итак, как вы видите результаты наших расчетов и сервиса Google-карты совпадают. Значит, мы можем сделать вывод о том, что задачу мы решили правильно.

Рефлексия

- Понравилась вам задача?

- Легко ли мы нашли самый короткий путь, после изучения темы графы?

- оценивание

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

 

Нам осталось только записать домашнее задание. Откройте дневники и запишите:

Параграф 1.3 Задача №6.