Конспект урока по теме: "Графы"

Методическая разработка урока

по информатике и ИКТ в 9 классе по теме «Информационные модели на графах. Пути в графах»

Предмет: Информатика и ИКТ

Класс : 9

Тема урока: «Информационные модели на графах. Пути в графах»

Тип урока : Закрепление умений и навыков. Решение задач.

Ключевые слова или опорные понятия: Информатика, презентация, конспект урока, информационные модели, графы, пути в графах, весовая матрица, решение задач ГИА и ЕГЭ.

Цели и задачи урока:

Обучающие задачи:

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

• Отработать навыки преобразования весовой матрицы (табличной формы представления информации) в граф;

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

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

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

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

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

• Развитие умений учебного труда: работать в хорошем темпе,;

• Развитие воли и самостоятельности: развитие инициативы, уверенности в своих силах, умения преодолевать трудности, развитие умения действовать самостоятельно.

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

• Воспитание добросовестного отношения к труду и к результатам своей деятельности;

• Воспитание дисциплинированности и организованности при выполнении работы;

• Воспитание эстетического отношения к выполняемой работе;

• Воспитание мотивов учения, положительного отношения к полученным знаниям.

Оборудование :

• Компьютерный класс;

• Мультимедийный проектор;

• Интерактивная доска;

• Карточки с заданиями для работы на компьютере.

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

• Наглядный

• Исследовательский

• Проблемно-поисковый

Материал для актуализации опорных знаний и умений учащихся :

• Что такое граф

• Из каких объектов строится граф

• Виды графов

• Какой граф называют ориентированным

• Какой граф называют неориентированным

• Какой граф называют взвешенным

• Что такое вес

• Что такое весовая матрица

• Какие особенности есть у весовой матрицы

• Как преобразовать весовую матрицу в граф

• Как оптимально делать обход графа, чтобы не пропустить путь

Планируемые компетенции, формирование которых будет осуществляться на уроке:

• Умение осуществлять детальный анализ весовой матрицы;

• Умение преобразовывать весовую матрицу в граф;

• Умение строить граф;

• Умение делать обход графа и находить все возможные пути в нем;

• Умение строить весовую матрицу и граф средствами текстового редактора Word;

• Умение эстетично оформлять свою работу.

Ход урока

1. Организационный момент (1мин)

листы самооценки раздать учащимся к началу урока

(1 слайд на экране)

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

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

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

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

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

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

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

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

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

Какие виды графов вы знаете (слайд 8):

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

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

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

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

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

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

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

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

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

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

(слайд ). А цели и задачи урока следующие (учащиеся предлагают) (13 слайд):

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

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

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

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

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

Проанализируем таблицу (14 слайд).

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

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

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

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

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

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

(21 слайд).

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

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

1. ABCDF - 14 км

2. ABCEF - 15 км

3. ACDF - 13 км

4. ACEF - 14 км

5. AF - 15 км

Физкультминутка (1 мин)

Совершите 15 колебательных движений глазами по горизонтали: справа-налево, затем слева-направо.

Совершите 15 колебательных движений глазами по диагонали.

Совершите 15 упражнений «Качалочка».

То же самое, но вверх.

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

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

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

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

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

10. Выполнение практической работы на компьютере для закрепления навыков преобразования таблицы в граф и поиска путей в нем с использованием текстового редактора Word (10 мин)

(24 слайд).

Сейчас каждый из вас получит индивидуальное практическое задание, в котором необходимо будет преобразовать таблицу в граф и определить необходимые пути. Выполнять данную задачу вы будете с использованием текстового редактора Word. Обращаю ваше внимание на аккуратность и правильность построения графа с использованием "Фигур", вершины графа обозначать окружностями с вписанными значениями, ребра графа - линии с подписанными длинами путей. Каждый путь вместе с суммарным расстоянием выписываете отдельно.

11. Сохранение выполненной работы в файле (10 мин)

После завершения работы, сохраните свои файлы в папке "Мои документы". В имени файла укажите тему сегодняшнего урока (Пути в графах), номер варианта, фамилию и класс.

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

(25 слайд).

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

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

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

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

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

(26 слайд).

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