7


  • Учителю
  • Решение задач с применением графа

Решение задач с применением графа

Автор публикации:
Дата публикации:
Краткое описание:
предварительный просмотр материала

ВИЗИТНАЯ КАРТОЧКА УРОКАТ.Ю. Сергеева

Класс:

9

Предмет:

Информатика и ИКТ

Тема урока:

Решение задач с применением графа

Дата проведения

13.10.2016

Задачи урока:



  • образовательные:

  • систематизировать и расширить представления учащихся о графах;

  • продолжить формирование познавательного интереса к информатике.

  • развивающие:

  • развивать познавательные процессы (внимание, восприятие, мышление);

  • развивать эмоциональную сферу;

  • развивать коммуникативные умения;

  • развивать мыслительные процессы (анализ, синтез, классификация и другие).

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

  • воспитывать умение слушать;

  • воспитывать умение работать в парах.

Тип урока:

Закрепление изученного материала.

Форма проведения:

Лекция, практическая работа

Методы обучения:

фронтальная, парная, индивидуальная.

Методы учения:

Практическое применение знаний, самостоятельная работа.

Средства обучения:

  • Конспект урока

  • Карточки (Приложение 1,2)

  • Индивидуальные самостоятельные работы - 5 вариантов (Приложение 3)

Литература:

    1. Босова. Информатика. Базовый уровень. Учебник для 9 класса, - ЮИНОМ, Лаборатория знаний, 2014 г.

  1. Воронкова, О.Б. Информатика: методическая копилка преподавателя. - Изд. 2-е. - Ростов н/Д: Феникс, 2011. - 313, [1] с. - (Сердце отдаю детям).

  2. Шелепаева, А.Х. Поурочные разработки по информатике. Базовый уровень. 9-й классы. Издательство BAKO - 2-е изд.: 2011. - 352 c.



Структура урока:Организационный момент

2 мин.

2

Вводное слово

1 мин.

3

Презентация нового материала

10 мин.

4

Закрепление пройденного материала

15 мин.

5

Рефлексия, домашнее задание

5 мин



Ход урока

1. Организационный момент. Здравствуйте, друзья. Сегодня хотелось начать наш урок со слов Шарля де Голля, французского генерала второй мировой войны и выдающегося политика. "Всегда выбирайте самый трудный путь, на нем вы не встретите конкурентов!".

2. Постановка проблемы. Формулирование условия задачи и предложение решить ее сразу (1 мин).

Говоря о выборе путей, предлагаю вам решить следующую задачу:A

B

C

D

E

A



2

10

8

16

B

2



9

1



C

10

9



3

4

D

8

1

3



11

E

16



4

11



В таблице представлено расстояние между населенными пунктами в километрах. Определить кратчайшее расстояние между пунктами A и E. Какими способами мы можем решить эту задачу.

Предлагайте решения (учащиеся предлагают решения задачи: методом рассуждения).

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

Очевидно, что данная форма представления информации в этой задаче (в виде таблицы) не слишком удобна для решения методом рассуждений. Можно предположить что форму представления необходимо изменить.

В геометрии, при решении некоторых задач удобно использовать чертежи (слайд задача показывается в текстовом виде, затем в графическом). А что в информатике позволяет представить условия задачи в графическом виде? (графы). Вспомним, что такое графы. Где в повседневной жизни мы можем столкнуться с графами (навигаторы в машинах, при построении маршрутов на уроках географии, при поездках,

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

Граф - это множество точек или вершин и линий или ребер, соединяющих между собой все или часть этих точек. Граф - это информационная модель объекта или системы объектов.

Какие виды графов вы знаете?

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

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

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

«От великого до смешного один шаг, но от смешного уже нет пути к великому.»

Лион Фейхтвангер

«Ковыляющий по прямой дороге опередит бегущего, который сбился с пути.» Фрэнсис Бэкон.

«Три пути у человека, чтобы разумно поступать: первый, самый благородный, - размышление; второй, самый легкий, - подражание; третий, самый горький, - опыт.»

5. Формулирование темы урока учащимися самостоятельно (1 мин)

Т.е. тема урока определение путей или если говорить точнее "Пути в графах".

6. Возврат к проблемной ситуации с задачей и актуализация целей и задач на предстоящем уроке. Учащиеся сами формулируют цели и задачи (1 мин). А цели и задачи урока следующие (учащиеся предлагают):

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

как определить все пути в графе;

как определить кратчайший путь.

7. Разбор задачи с таблицей и преобразование ее в граф. Обход графа и поиск всех возможных путей с вычислением длины пути (15 мин)

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

Проанализируем таблицу.

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

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

(строим все направления).

Определим пути в графе и расстояние, пройденное на этом пути. После просмотра всех путей и нахождения их длин, определяем, что кратчайшим путем будет ABDCE.

8. Постановка задачи из демоверсии и ее решение учащимися у доски (5 мин).

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

Решение задач с применением графа

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

















Указываем все пути в алфавитном порядке:

1. ABCDF - 14 км

2. ABCEF - 15 км

3. ACDF - 13 км

4. ACEF - 14 км

5. AF - 15 км

9. Демонстрация задачи из демоверсии ОГЭ 2017 года без решения (1 мин)

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

Проведем анализ данной таблицы.

Решение задач с применением графа

Мы видим, что из точки А мы можем попасть только в В и в точку F ведет только один путь из точке Е. Фактические решение задачи сводится к нахождению кратчайшего пути из В в E, что упрощает решение данной задачи.

10. Выполнение самостоятельной работы по карточкам(10 мин)

11. Подведение итогов урока (2 мин)

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

научились строить графы и определять пути в нем на основе табличной модели;

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

Выставление оценок учащимся на основе их самооценки и оценок учителя.

13. Домашнее задание (1 мин)

Домашнее задание указано на доске. Выпишите себе условие задачи в тетради.





Приложение 1

1. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

Решение задач с применением графа

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

1) 5

2) 6

3) 7

4) 8

2. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

Решение задач с применением графа

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

1) 6

2) 7

3) 8

4) 9

3. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

Решение задач с применением графа

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

1) 6

2) 7

3) 8

4) 9

4. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

Решение задач с применением графа

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

1) 6

2) 7

3) 8

4) 9

5. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

Решение задач с применением графа

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

1) 4

2) 5

3) 6

4) 7

15.У Кати Евтушенко родственники живут в 5 разных городах России. Расстояния между го. родами внесены в таблицу:

Решение задач с применением графа

Катя перерисовала её в блокнот в виде графа. Считая, что девочка не ошиблась при копировании, укажите, какой граф у Кати в тетради.

1) Решение задач с применением графа

2) Решение задач с применением графа

3) Решение задач с применением графа

</ 4) Решение задач с применением графа





 
 
X

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

После этого кнопка ЗАГРУЗКИ станет активной!

Кнопки рекомендации:

загрузить материал