Информационные модели на графах

Урок "Информационные модели на графах"

Цели урока:

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

•сформировать представление о графах как наглядном средстве представления структуры и состава системы;

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

•повысить интерес учащихся к предмету.

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

•обучающие - усвоение новых знаний учащихся; закрепление практических умений создания в текстовом редакторе многоуровневых списков;

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

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

Тип урока: урок сообщения и усвоения нового учебного материала.

Технология: проблемное обучение, игровая технология, обучение в сотрудничестве.

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

•Компьютерный класс, мультимедийный проектор, экран;

•презентация "Информационные модели на графах";

•текстовый файл "Игра", практическая работа.

План урока:

1. Повторение изученного материала;

2. Изучение новой темы. Первичное закрепление;

3. Использование графов при решении задач;

4. Игра "Выигрышная стратегия";

5. Компьютерный практикум;

6. Подведение итогов;

7. Домашнее задание.

Ход урока

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

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

Проверка усвоения изученного материала, актуализация знаний. Фронтальный опрос:

•приведите примеры схем, представляющих внешний вид объекта, его структуру?

•в каких сферах нельзя обойтись без карт? Где применяют чертежи?

•какие условные обозначения применяются на блок-схемах?

•всякая ли схема может претендовать на полноту представления информации об объекте?

Подготовка к восприятию нового материала: мотивация. На экране демонстрируем 5 карточек. (Приложение 1, слайд 2)

Вопрос: что объединяет эти карточки? (Ответ: это виды смешанных моделей).

Вопрос: какую карточку можно добавить к данному набору? (Ответ: граф, как вид смешанной модели).

Формулируем тему урока и подводим учащихся к самостоятельной постановки цели занятия.

Изучение новой темы. Первичное закрепление (Приложение 1 - слайды № 4-10)

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

Осмысление и закрепление материала.

Использование графов при решении задач (Приложение 1 – слайды 11-12)

Графы удобно использовать при решении некоторых классов задач.

Задача 1

Сколькими способами можно рассадить в ряд на три стула трех учеников? Выписать все возможные случаи.

Решение этой задачи удобнее всего представить в виде дерева. За его корневую вершину возьмем произвольную точку плоскости О.

На первый стул можно посадить любого из трех учени­ков — обозначим их А, В и С. На схеме это соответствует трем ветвям, исходящим из точки О:

Посадив на первый стул ученика А, на второй стул можно посадить ученика В или С. Если же на первый стул сядет ученик В, то на второй можно посадить А или С. А если на первый стул сядет С, то на второй можно будет посадить А или В. Это соответствует на схеме двум вет­вям, исходящим из каждой вершины первого уровня:

Очевидно, что третий стул в каждом случае займет оставшийся ученик. Это соответствует одной ветви дерева, которая «вырастает» на каждой из предыдущих ветвей.

Выпишем все пути от вершин первого уровня к верши­нам третьего уровня:  А-В-С, А-С-В, ВАС, В-С-А, С-А-В, С-В-А. Каждый из выписанных путей определяет один из вариантов рассаживания учеников на стулья. Так как других путей нет, то искомое число способов — 6.

Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их число. В этом случае рассуждать нужно так: на первый стул можно усадить одного из трех человек, на второй — одного из двух оставшихся, на третий — одного оставшегося: 3-21 = 6.

Задача 2

Чтобы принести Царю-батюшке молодильные яблоки, должен Иван-царевич найти единственный верный путь к волшебному саду. Встретил Иван-царевич на развилке трех дорог старого ворона и вот какие советы от него услышал:

1)  иди сейчас по правой тропинке;

2)  на следующей развилке не выбирай правую тропинку;

3)  на третьей развилке не ходи по левой тропинке.

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

Обозначим левую, среднюю и правую тропинки соответственно Л, С и П. Возможные маршруты представим в виде графа. При этом подсказки ворона отметим более «жирными» ребрами. Так как только один совет ворона верен, то на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро. Этот маршрут обозначен дополнительной пунктирной линией.

Игра "Выигрышная стратегия" (Приложение 2)

Класс делится на три группы по 3-4 человека. Первая и вторая группа - путешественники. Третья - эксперты (из числа более сильных обучающихся). Каждой группе выдается карта-граф (проецируем на экран)

1 этап игры. Коллективно обсуждаем вопросы: укажите на графе дуги и ребра. Чем они отличаются?

- Является ли данный граф взвешенным? Докажите?

- Какой город на карте можно назвать лишним? Почему?

Игровой момент "Да-нет"

- У графа 8 вершин.

- Следующей вершиной после Лондона - Париж.

- Вена следующая вершина за Берлином.

2 этап игры. Формулируется проблема. Время поиска решения - 7 минут.

1 группа путешественников: сколькими способами можно проехать из Лондона в Москву? Какой способ самый оптимальный? (по каждой дороге можно проезжать не более одного раза).

2 группа путешественников: сколькими способами можно проехать из Лондона в Москву? Какой способ самый оптимальный? (по каждой дороге можно проезжать не более одного раза).

3 этап игры. Представитель группы докладывает о результатах работы, раскрывая логическую цепочку: проблема - гипотеза - доказательство

4 этап игры. Экспертная группа оценивает работу группы по критериям:

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

Компьютерный практикум:

Индивидуальная работа: Постройте дерево для арифметического выражения: 6*4+7*(9-1). (Приложение 3)

Подведение итогов:

выставление отметок, рефлексия:

•какая информация урока на ваш взгляд полезна?

•наиболее интересный момент урока?

•выполняя задания урока, какие знания других предметов вам пригодились?

•на какие вопросы при домашней подготовке вы обратите внимание в первую очередь?

Домашнее задание:

1. учебник стр. 101-104;

2. Рабочая тетрадь стр. 78 № 60, 61;

3. Домашняя практическая работа «Структуры данных: Графы» (Приложение 4)