Конспект урока "Информационные модели на графах" 11 класс


Урок 5 «Информационные модели на графах»
Цель: познакомить учащихся с информационными моделями на
графах.
Задачи урока:
1) образовательные:
сформировать навыки работы с моделями;
Познакомить учащихся с понятиями: «сетевая ИМ»,
«иерархическая система», «иерархическая ИМ»,
«генеалогическое дерево», «дерево», «граф»
Научиться приводить примеры ИМ на графах
2) развивающие:
развитие познавательного интереса учащихся, творческой
активности учащихся;
развитие умения слушать товарищей, учителя;
развитие логического мышления учащихся.
3) воспитательные:
привить интерес к предмету;
воспитать эмоционально-положительную направленность на
практическую деятельность.
Тип урока: урок сообщения новых знаний
Методы урока: объяснительно–иллюстративный
Этапы урока:
Организационный момент:
1. проверка отсутствующих
2. проверка домашнего задания (см. работа по основным
определениям предыдущей темы)
Объяснение нового материала:
Запишите тему урока «Информационные модели на графах».
На прошлом уроке мы с вами уже начали знакомиться с
информационными моделями. Скажите мне пожалуйста, какие модели
называются информационными?
Информационные модели это модели которые носят описательный
характер.
А что необходимо осуществить при построении информационных
моделей?
Системный анализ
А в чем он заключается?
Мы берем какой либо объект (который является системой),
выделяем в нем существенные части и свойства, затем устанавливаем связь
между ними.
Таким образом можно сказать, что Информационная модель всякой
системы должна отражать ее состав и связи между ее частями
Т.е нарисуем такую картинку:
На этом рисунке в овалах записаны названия населенных пунктов.
Овалы (Пункты) связаны линиями (дорогами). Глядя на этот рисунок мы
можем узнать (получить информацию), между какими населенными
пунктами есть дороги. Такой рисунок является графом.
Граф информация о составе и структуре системы,
представленная в графической форме.
Граф средство для наглядного представления состава и
структуры системы.
В нашем примере мы рассматриваем данную местность, как систему
взаимосвязанных населенных пунктов. Что по вашему мнению будет здесь
являться элементами этой системы?
Поселки.
Т.к. данная система представляет собой граф, то элементы этой
системы называются вершинами графа
А расположение дорог между поселками (или линий между
элементами системы) определяют структуру данной системы.
Структура определенный порядок объединения элементов,
составляющих систему
Мы с вами знаем что связи между элементами системы на графе
изображаются линиями. Если линия направленная (т со стрелочкой),
имеет место односторонняя связь, такие линии называются дугами,
иначе ребрами
Две вершины соединенные дугой или ребром называются
смежными.
Назовите смежные вершины?
какими линиями соединены вершины нашего графа?
ненаправленными
Почему вы так решили?
Т.к. линии без стрелок
Дача
ст. Озерная
д. Подгорная
п. Поддужное
д. Красное
Тогда как их иначе можно назвать?
Ребрами
А как по вашему почему вершины графа соединены ребрами, а не
дугами?
Т.к. поселок А связан с поселком Б соответственно и поселок Б
связан с поселком А.
Т.о. имеет место двустороння связь, которую еще можно назвать
симметричной.
Связи, справедливые в обе стороны, называются симметричными
А теперь посмотрите на такой рисунок:
Данный рисунок будит являться графом?
да
Почему
Т.к. он отражает информацию о составе и структуре системы в
графическом виде.
Что является составными частями этого графа?
«Отец», «Сын»
А что, по вашему мнению, определяет структуру этой системы?
Линия
Какая связь имеет место в данном случае?
Направленная
Почему вы так решили
Т.к. линия со стрелкой
Тогда как ее иначе можно назвать
дугой
По вашему мнению данная связь будет являться двусторонней или
нет?
Нет, это односторонняя связь
Почему вы так решили?
Т.к. Иван является отцом Саше, но Саша не как не может являться
отцом для Ивана.
Граф, в котором связи изображаются дугами, называется
ориентированным графом
А теперь посмотрите на рисунок в книге (рис. 5.5 стр 250) и
перечислите вершины графа?
Перечислите дуги данного графа?
Перечислите ребра
Посмотрите на следующий рисунок в книге (рис 5.6 стр. 251) по
вашему мнению это какой граф?
Ориентированный
Отец Иван
Сын Саша
Почему?
Правильно, здесь дуги обозначают связь «быть отцом», т.к у каждого
человека может быть только один отец, но несколько детей. Поэтому
сколько стрелок может входить в каждую вершину графа?
Только одна.
А исходить?
–Несколько.
Такой граф называется генеалогическое дерево (ДИНАМИЧЕСКАЯ
ИНФОРМАЦИОННАЯ МОДЕЛЬ)
Генеалогическое дерево граф в котором в каждую вершину
может входить только одна стрелка, а выходить несколько.
Дерево это любой граф. в котором нет петель,. ‘го есть
связанных по замкнутой линии вершин.
Вершина графа является корнем дерева. От корня идут ветви, по
которым можно
добраться до любой другой вершины дерева только по одному пути.
Конечные вершины каждой ветви называются листьями.
Скажите граф на первом рисунке можно назвать деревом?
Нет
Почему?
В нем есть петля: Дачи – Подгорная Красное – Поддужное – Дачи
А если между Красное и Поддужное не будет линии, то тогда он
будет являться деревом?
да
что будет являться корнем, а что листьями? (ничего, т.к. это не
дерево)
на нашем рисунке в книге (рис. 5.6 стр.251) что будет являться
корнем, а что листьями?
Теперь рассмотрев все необходимые нам определения можно
выделить два типа информационных моделей. Одним из них является
иерархическая система
Система, информационная модели которых представлены в виде
дерева, называются иерархическими системами
В иерархической информационной модели объекты распределены
по уровням. Каждый элемент более высокого уровня может состоять из
элементов нижнего уровня, а элемент нижнего уровня может входить в
состав только одного элемента более высокого уровня.
Запишите правило: вершины верхнего уровня связаны с вершинами
нижнего уровня как «один ко многим»
Т.е. один континент содержит множество стран, одна страна
множество регионов, а не на оборот.
Приведите мне пример иерархических систем
в биологии весь животный мир Земли система: типы животных–
классы – отряды – семейства – ряды виды.
Следующий тип информационных моделей – сетевые ИМ.
Запишите: Сетевая информационная модель применяется для
отображения систем со сложной структурой, в которой связи между
элементами имеют произвольный характер.
В Сетевой ИМ вершины различных уровней связаны м/у собой по
принципу «многие ко многим».
В качестве примера сетевой модели может быть представлен граф из
книжки (рис 5.7). Внимательно посмотрите на данный граф и скажите в чем
его отличие от
дерева?
В данном случае связи между элементами имеют произвольный
характер – «многие ко многим».
Практическая часть:
1. Представьте себе перечисленные ниже объекты в виде системы
взаимосвязанных
элементов и перечислите эти элементы:
1) чайник, 2) костюм, 3) грузовик
2. Рассматривая каждый из перечисленных ниже объектов как
систему, выберите из
списка и сопоставьте каждой системе подходящие входы и выходы:
1) утюг, 2) холодильник, 3) водопровод
1 Вода 2 Одежда 3 Тепло
4 Краны 5 Холод 6 Продукты питания
7 Звук 8 Электроэнергия
Например:
Система взаимодействует со средой, среда оказывает влияние на
систему, а система на среду. Воздействие среды на систему называется
ВХОДОМ системы, а воздействие системы на среду ВЫХОДОМ системы.
Т.е. например: автомат по продажи газет (он является системой) на входе
монетка, на выходе газета, ручная мясорубка на входе мясо и вращение
руки, на выходе – фарш.
3. Отразите в виде графа структуру следующих объектов рассматривая
их как системы:
1) чайник, 2) костюм
Домашнее задание:
1. Укажите входы и выходы для следующих систем: карандаш,
телевизор,
радиоприемник, автомобиль.
2. Отразите в виде графа структуру следующих объектов рассматривая
их как
системы:
1) учебник по математике, 2) чайник
3. Пусть структура системы изображается графом, приведенным на
рисунке
Назовите объекты, имеющие такую структуру.
4.