«Задача о мостах»

Петрова Ирина Викторовна,
учитель информатики БОУ «СОШ №142»,
Козлова Марина Леонидовна,
учитель информатики БОУ «СОШ №28 УИОП»,
Омская область, г. Омск

Имя задачи. Задача о мостах.

Автор. Петрова Ирина Викторовна, учитель информатики БОУ «СОШ №142» и Козлова Марина Леонидовна, учитель информатики СОШ №28 УИОП, г. Омск

Предмет. Информатика. Математика.

Класс. 9

Профиль. Общеобразовательный.

Уровень. Общий.

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

Тип урока: урок усвоения новых знаний

Цели:

Учебные:

  • Познакомить обучающихся с историей возникновения теории графов и ее применением в различных областях науки и техники.
  • Изучить основные понятия теории графов (граф, вершина графа, ребра), виды графов (сеть, дерево).
  • Решить задачу Эйлера на примере мостов города Омска.

Развивающие:

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

Терминологических изысканий, выделение ключевых слов, контекстный поиск информации, анализ информации, формулирование выводов, сопоставление выводов с результатами других исследований, коррекции выводов.

Воспитательные:

  • Воспитание информационной культуры учащихся.
  • Воспитание коллективизма, ответственности, толерантности.

Ход урока:

  1. Организационный момент.
  2. Предъявление текста условия задачи и требований к задаче.
  3. Организация работы обучающихся в группах.
  4. тур слушаний, обсуждение полученных выводов.
  5. Предъявление культурного образца. Сравнение полученных выводов с образцом.
  6. Подведение итогов.

Критерии оценки результата.

Минимальный уровень. Обучающиеся формулируют понятие «граф»; правильно выделяют вершины и ребра графа; приводят примеры применения теории графов на практике; распознают виды графов (сеть, дерево).

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

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

Текст задачи.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно). Решение было предложено в виде графа. Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Созданная Эйлером теория графов нашла очень широкое применение: например, её используют при изучении транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете.

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

Скачать полностью работу