Гимназия №1

Конспект урока открытого урока по информатике

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

в 7  «А» классе

Учитель информатики и ИКТ:

Есакова М.А.

12 марта 2013 года

Г.о. Краснознаменск

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

Цели:

Учебник: Л. Л. Босова «Информатика и ИКТ» 7 класс, рабочая тетрадь.

Ход урока:

     Граф – это средство  для наглядного представления состава и структуры системы.

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

Связи между вершинами изображаются линиями.

Если линия направленная, то она называется дугой. Если не направленная, то ребром.

Граф, в котором направлены все линии, называется ориентированным графом.  Пример, схема метро.

     Взвешенный граф –  это граф, в котором с вершинами или линиями связана некоторая дополнительная информация. Эта информация называется весом вершины или линии. Вес задается в виде надписи на вершине или линии.

     Дерево – это граф, предназначенный для отображения связей между объектами как вложенность, подчиненность, наследование и т. п.  Строится он следующим образом. Сначала рисуем «главную» вершину, которая не зависит ни от одной другой вершины. Эта вершина называется корнем дерева и является единственной вершиной «1-ого уровня». Далее добавляем вершины второго уровня.  Полученный граф напоминает куст.

Практическая работа задания № 7,8 из учебника Л.Л. Босова 

Цели урока:

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

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

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

обучающие - усвоение новых знаний учащихся об информационные моделях;

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

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

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

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

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

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

компьютерный тест «Многообразие схем», карточки для построения графов.

Учебник: Л.Л. Ббосова «Информатика и ИКТ», 7 класс и рабочая тетрадь

Ход урока:

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

Приветствие, проверка отсутствующих  

2.     Актуализация знаний.

Актуализация знаний может иметь два варианта: классический – опрос учащихся или компьютерное тестирование (приложение 2)

Классический вариант:

·        Давайте вспомним, что мы называем схемой?

·        Для чего мы используем схемы?

·        Какие виды схем вы знаете? 

Схема – это представление некоторого объекта в общих, главных чертах с помощью условных обозначений.

Схемы мы используем для представления внешнего вида объекта и его структуры.

Географическая карты, схема метро, схема движения автотранспорта, схема эвакуации.

3.     Объяснение нового материала.

Мы с вами повторили, что схемы нам  дают представление о некоторых объектах в виде условных обозначений и знаков.

Но иногда нам необходимо представление систем некоторых объектов и ее структуры, например, в наглядном виде представленные дороги, которые соединяют населенные пункты. Для этого представления мы будем использовать графы.

Итак, записываем тему нашего урока «Графы. Понятие и виды графов» (слайд 1)

Граф – это наглядное средство представления состава и структуры системы в виде совокупности вершин и линий, соединяющих данные вершины.

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

Некоторые вершины связанны друг с другом линиями. Если линия направлена (со стрелкой), то она называется дугой и граф имеет название ориентированным. В ориентированном графе можно передвигаться от вершины к вершине только по стрелкам в том направлении, которое они показывают.

Если линия ненаправленная, то она называется ребром графа, а граф имеет название неориентированный. В неориентированном  же графе можно передвигаться от вершины к вершине в любом направлении.

Приведите, пожалуйста, свои примеры, связь каких объектов мы можем представить в виде граф ориентированного и неориентированного.

В графе различают: цепь и цикл.

Цепь – это путь по вершинам и ребрам (дугам) графа не более одного раза (слайд 3)

Например, Юра – Аня – Витя – Коля.

Назовите еще пример цепи по данному графу.

Цикл – это цепь, у которой начальная и конечная вершины совпадают.

Давайте вместе определим, где в данном графе будут циклы.

 Мы сейчас с вами работали с графом неориентированным, теперь назовите мне цепи и циклы в следующем графе, который является ориентированным (слайд 4)

Молодцы! Различают еще один вид графа – взвешенный граф. Бывают ситуации, когда на вершинах графа, его ребрах или дугах нам необходимо добавить информацию.

Например, это может быть такой граф «города Золотого кольца» (слайд 5)

Что здесь будет являться вершинами графа?

Какой это будет граф и почему?

Все верно, ребрами здесь будут являться дороги, соединяющие данные города.

Итак, давайте теперь подумаем, какую информацию мы можем добавить к вершинам?

Хорошо, добавим к вершинам год основания.

А какую информацию можно добавить к ребрам?

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

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

Как правило, ребра (дуги) графа описывают однородные отношения между объектами некоторой системы. Но бывают случаи, когда нам необходимо, чтобы ребрами (дугами) были отражены разнородные отношения между объектами. Например, давайте посмотрим граф, представляющий информационную модель сказки про Царевну-лягушку (слайд 6)

Что на представленном графе будет являться его вершинами?

А какой это будет граф и почему?

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

Такой граф называется семантической сетью.

Запишем:

Семантическая сеть – это граф, на котором отражены объекты (понятия) и связи (отношения) между ними.     

(записывают за учителем и рисуют примеры с презентации)

Ориентированным графом можно представить отношение «меньше» между некоторыми целыми числам, а неориентированным – отношение «учиться в одном классе» между учащимися школы.

Маша – Юра – Аня – Витя – Коля.

Маша – Аня – Коля – Витя.

Аня – Коля – Витя – Аня.

Маша – Аня – Юра – Маша.

Цепь: Аня – Юра – Маша

Цикл: Аня – Витя – Коля – Аня

Вершинами графа являются названия городов Золотого кольца

Граф будет неориентированный, потому что  его вершины соединены ребрами

Так как вершины – это города, то можно добавить такую информацию, как год основания города, количество жителей, площадь города и т.д.

На ребрах можно отразить значение расстояний между городами, а еще можно отразить, сколько времени в пути затрачивается.

Вершинами графа будут являться персонажи и объекты из сказки

Это будет ориентированный граф, потому что вершины соединены дугами, и взвешенный граф, потому что у дуг есть вес.

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

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

Каждому ученику раздаются карточки с заданиями (приложение 1)

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

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

Какой это будем граф и почему?

Почему в данном случае вершины будут соединены дугами?

Все верно, располагаем вершины и соединяем их дугами. Еще раз повторим, что дуги будут обозначать отношение «кратно».

Построение вместе с учащимся у доски.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту:

Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.

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

Правильно, а будет ли граф содержать какую-то дополнительную информацию? Будет ли он являться взвешенным?

Давайте, попробуем его построить.

Вызывает учащегося к доске.

Вершинами графа будут являться числа.

Граф будет ориентированный, так как его вершины мы соединим дугами.

Потому что, отношение «кратно» может быть выполнено только в одну сторону, так как «15 кратно 3», но не может быть, что «3 кратно 15».

5.     Подведение итога урока. Домашнее задание

Мы сегодня с вами изучили еще один вид информационных моделей, это графы.

Давайте еще раз вспомним, что же это такое?

Какие бывают графы и как они отличаются?

Правильно.

А теперь записываем домашнее задание:

§2.10 (стр.101 – 104) учить.

§2.10 (стр.97 – 101) повторить

Творческое задание: изменить граф «города Нижегородской области» таким образом, чтобы весом ребра стало время пути между городами. Добавить вес вершины (год основания, численность жителей, площадь и т.д.) – по выбору учащегося. 

Граф – это наглядное средство представления состава и структуры системы в виде совокупности вершин и линий, соединяющих данные вершины.

Графы бывают ориентированные, если их вершины соединены дугами (стрелками) и неориентированные, если их вершины соединены ребрами (линиями).

Если на графе отображена дополнительная информация на вершинах или ребрах (дугах), то граф называется взвешенным.

Приложение 1. Карточки для работы на уроке

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту: Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.       

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту: Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту: Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту: Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.