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

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

Класс:

9

Предмет:

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

Тема урока:

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

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

13.10.2016

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

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

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

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

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

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

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

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

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

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

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

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

Тип урока:

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

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

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

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

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

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

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

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

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

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

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

Литература:

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

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

3. Шелепаева, А.Х. Поурочные разработки по информатике. Базовый уровень. 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)