Какая модель компьютера является графом
Цели урока:
- Сформировать у учащихся понятие формализация, информационная модель. Научить строить табличную информационную модель с помощью электронных таблиц и осуществлять визуализацию модели.
- Развивать исследовательскую компетентность учащихся при формализации модели через структурирование учебного материала с помощью электронных таблиц.
- Для слабых учащихся: Пробудить интерес к процессу моделирования путем использования посильных задач, учебных программных средств, позволяющих ученику работать в соответствии с его индивидуальными способностями.
- Для средних учащихся: Развить устойчивый интерес к предмету, через построение табличных моделей.
- Для сильных учащихся: Развить устойчивый интерес к процессу моделирования, через решение различных задач в Excel.
- Способствовать обогащению внутреннего мира учащихся, повышению интереса к изучению предмета, воспитание культуры поведения и компьютерной грамотности.
Программно-дидактическое обеспечение: ПК, ПО:Excel, PowerPoint, MS Word, Internet, карточки с заданиями, интерактивная доска, презентация.
Требования к знаниям и умениям:
Учащиеся должны знать:
- Что такое модель, моделирование, формализация;
- Основные этапы построения табличной модели.
Учащиеся должны уметь:
- Структурировать информацию, с помощью электронных таблиц;
- Осуществлять визуализацию модели с помощью диаграмм.
Ход урока
I. Орг. момент.
II. Актуализация прежних знаний:
1. Учащиеся выполняют электронный тест в двух вариантах и сохраняют в своих папках.
1) Модель есть замещение изучаемого объекта другим объектом, который отражает:
- все стороны данного объекта;
- некоторые стороны данного объекта;
- существенные стороны данного объекта;
- несущественные стороны данного объекта.
2) Информационной моделью организации занятий в школе является:
- свод правил поведения учащихся;
- список класса;
- расписание уроков;
- перечень учебников.
3) Материальной моделью является:
- макет самолета;
- карта;
- чертеж;
- диаграмма.
4) Укажите в моделировании процесса исследования температурного режима комнаты объект моделирования
- конвекция воздуха в комнате;
- исследование температурного режима комнаты;
- комната;
- температура;
5) Устное представление информационной модели называется:
- графической моделью;
- словесной моделью;
- математической моделью;
- логической моделью.
1) Как называется упрощенное представление реального объекта?
- оригинал;
- прототип;
- модель;
- система.
2) Процесс построения моделей называется:
- моделирование;
- конструирование;
- экспериментирование;
- проектирование.
3) Информационная модель, состоящая из строк и столбцов, называется:
4) Каково общее название моделей, которые представляют собой совокупность полезной и нужной информации об объекте?
- материальные;
- предметные;
- информационные;
- словесные.
5) Укажите в моделировании процесса исследования температурного режима комнаты цель моделирования:
- конвекция воздуха в комнате;
- исследование температурного режима комнаты;
- комната;
- температура.
2. Рассказать что такое модель, моделирование. Привести примеры учебных моделей. Что такое материальная модель? Что такое информационная модель?
3. Выполнить задание на интерактивной доске:
III. Новая тема:
С использованием мультимедийной поддержки. Проблемный вопрос «Как можно с помощью компьютера отображать информационные модели?» Давайте сегодня это попытаемся выяснить.
Человек издавна использует моделирование для исследования объектов, процессов, явлений (в дальнейшем все это будем называть объектами моделирования) в различных областях. На протяжении своей истории человечество использовало различные способы и инструменты для создания информационных моделей. Эти способы постоянно совершенствовались. Так, первые информационные модели создавались в форме наскальных рисунков. В настоящее время информационные модели обычно строятся и исследуются с помощью современных компьютерных технологий.
Первым этапом любого исследования является постановка задачи, которая определяется заданной целью. Задача формулируется на обычном языке. По характеру постановки все задачи можно разделить на две основные группы. К первой группе можно отнести задачи, в которых требуется исследовать, как изменятся характеристики объекта при некотором воздействии на него, «что будет, если?…». Вторая группа задач: какое надо произвести воздействие на объект, чтобы его параметры удовлетворяли некоторому заданному условию, «как сделать, чтобы. ».
Второй этап – анализ объекта. Результат анализа объекта – выявление его составляющих (элементарных объектов) и определения связей между ними.
Третий этап – разработка информационной модели объекта. Построение модели должно быть связано с целью моделирования. Каждый объект имеет большое количество различных свойств. В процессе построения модели выделяются главные, наиболее существенные, свойства, которые соответствуют цели.
Все то, о чем говорилось выше – это формализация, т. е замена реального объекта или процесса его формальным описанием, т.е. его информационной моделью. Как это происходит?
Примеры из математики, физики, химии, географии, музыки и т.д.
Информационная модель молекулы воды
Словесная модель: «Молекула воды состоит из атома кислорода и двух атомов водорода»
Информационная модель прямоугольного треугольника
Словесная модель: «Прямоугольным треугольником называется треугольник, у которого один из углов прямой»
Обращаю ваше внимание на математическую модель. Она записана математическим языком или формальным языком. Мы с вами знаем, что языки бывают естественные и формальные. Естественные языки используются для создания описательных информационных моделей. С помощью формальных языков строятся формальные информационные модели (математические, логические и др.). Одним из наиболее широко используемых формальных языков является математика. Модели, построенные с использованием математических понятий и формул, называются математическими моделями. Однако в некоторых случаях используются специализированные формальные языки (в химии – язык химических формул, в музыке – нотная грамота ит.д.)
Процесс построения информационных моделей с помощью формальных языков называется формализацией.
Моделирование любой системы невозможно без предварительной формализации. По сути, формализация – это первый и очень важный этап процесса моделирования.
В процессе исследования формальных моделей часто используется их визуализация. Для визуализации алгоритмов используются блок схемы, пространственных соотношений между объектами– чертежи , моделей электрических цепей – электрические схемы. При визуализации формальных моделей с помощью анимации может отображаться динамика процесса, производиться построение графиков изменения величин и т.д. Пример на слайде.
Для отражения систем с различными структурами используются следующие типы информационных моделей :табличные, иерархические, сетевые.
Одной из самых распространенных форм представления информационных моделей являются таблицы. Очень часто в табличной форме представляется информация в различных документах, справочниках, учебниках. С помощью таблиц строятся информационные модели в различных предметных областях Н-р, в математике – таблица умножения, химии таблица Менделеева, расписание уроков, поездов.
Табличные – объекты и их свойства представлены в виде списка, а их значения размещаются в ячейках прямоугольной формы. Перечень однотипных объектов размещен в первом столбце (или строке), а значения их свойств размещаются в следующих столбцах (или строках).
Давайте разберем такую жизненную ситуацию: вам необходимо приобрести мобильный телефон. При покупке на что вы обращаете внимание в первую очередь (внешний вид)? Какие сведения имеют значения?
Информация представляется в виде таблице.
Параметр
Значение параметра
Это полная информация об объекте? Что является наилучшей формой представления информации о внешнем виде телефона? На что ещё вы обращаете внимание при покупке телефона (функции телефона)? Какие сведения имеют значения? Информация представляется в виде таблице.
Параметр
Значение параметра
Работа в режиме разговора
Данная таблица является наилучшей формой представления функциональных возможностей телефона? В этом примере построены две табличные модели одного реального объекта – мобильный телефон. Первая модель удобна в графическом представлении, а вторая в табличном. При построении табличной информационной модели особое значение имеет цель создания модели.
Таким образом, табличная форма придает лаконичность и наглядность данным, структурирует данные, позволяет увидеть закономерности в характере данных.
Важную роль играют информационные модели, которые отображают иерархические системы. В биологии весь животный мир рассматривается как иерархическая система (тип, класс, отряд, семейство, род, вид), в информатике используется иерархическая файловая система, классификация компьютеров. Для описания исторического процесса смены поколений семьи используются динамические информационные модели в форме генеалогического дерева. В качестве примера можно рассмотреть фрагмент (X – XI) век генеалогического дерева династии Рюриковичей. В иерархической модели объекты расположены по уровням. Каждый элемент более высокого уровня может содержать несколько элементов нижнего уровня, а при этом каждый элемент нижнего уровня может входить в состав только одного элемента верхнего уровня.
Удобным способом наглядного представления иерархических информационных моделей являются графы. Элементы иерархической модели отображаются в графе овалами (вершинами графа). Графы, имеющие одну вершину верхнего уровня, напоминают деревья ,которые растут сверху вниз, поэтому называются деревьями. В качестве примера можно рассмотреть фрагмент генеалогического дерева династии Рюриковичей.
Представим схематически следующее описание: «Природные ресурсы по запасам разделяются на исчерпаемые и неисчерпаемые. Исчерпаемые ресурсы бывают невозобновимыми и возобновимыми. Кроме того, по назначению природные ресурсы разделяются на многоцелевые, промышленные, сельскохозяйственные». (Слайд)
А теперь представим эту информацию в виде иерархии.
Сетевые информационные модели – применяют для отражения систем, в которых связи между элементами имеют сложную структуру. Примером сетевых моделей являются, например,различные региональные части глобальной компьютерной сети Интернет (американская, европейская, российская, австралийская и так далее) связаны между собой высокоскоростными линиями связи. При этом одни части (например, американская) имеют прямые связи со всеми региональными частями Интернета, а другие могут обмениваться информацией между собой только через американскую часть (например, российская и австралийская). Вершинами графа являются региональные сети. Связи между вершинами носят двусторонний характер и поэтому изображаются ненаправленными линиями (ребрами), а сам граф поэтому называется неориентированным.
IV. Закрепление:
Задача 1.
Постройте табличную модель по позиционным системам счисления.
Что такое система счисления? На каких два класса делятся системы счисления?
В данном уроке рассматривается одна из разновидностей графических информационных моделей – графы. Учащиеся подробно смогут ознакомиться с такими понятиями, как «граф», «взвешенный граф», «цепь», «цикл», «дерево» и многое другое.
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобретя в каталоге.
Получите невероятные возможности
Конспект урока "Графические информационные модели. Многообразие графических информационных моделей"
Графическая информационная модель – это наглядный способ представления объектов и процессов в виде графических изображений. Графические информационные модели являются простейшим видом моделей. С их помощью передаются внешние признаки объекта – размер, форма, цвет. Графические модели несут в себе больше информации, чем словесные.
Для более наглядного и понятного представления информации в графических информационных моделях используются графические изображения (образные элементы), которые могут быть дополнены текстами, числами и символами. Примерами графических информационных моделей являются схемы, карты, чертежи, графики, диаграммы и много другое.
Разберёмся более подробно с каждой из них.
Cхема – это графическое отображение состава и структуры сложной системы. Можно обратиться к ранее рассматриваемому примеру: две электрические схемы соединения переключателей.
Схема последовательного соединения переключателей
Схема параллельного соединения переключателей
На первой представлено последовательное соединение, а на второй – параллельное. Можно заметить, что с помощью схемы легче разбираться с такими задачами, нежели использовать словесное описание. Схемы используются на уроках биологии, истории и так далее.
Следующая графическая информационная модель – чертеж. Чертеж – это условное графическое изображение предмета с точным соотношением его размеров, получаемое методом моделирования. При построении чертежа используются изображения, числа, текст. С помощью изображений мы получаем представление о форме объекта, с помощью чисел – о размере, с помощью текста – о названии объектов, размерах, в которых выполнены изображения. Примером чертежа является изображение детали перед её изготовлением.
На чертеже изображена деталь в разрезе, чтобы лучше было видно все части, составляющие нашу деталь, присутствуют размеры (числа).
Рассмотрим такую графическую информационную модель как карта. Карта используется для отображения местности в уменьшенном масштабе, которая является для нее объектом моделирования. Например, с помощью карты мы можем узнать сколько километров от Москвы до Санкт-Петербурга, как добраться на метро или автобусе с одного остановочного пункта до другого, где находится Будапешт и много другое. Для различных целей используются разнообразные карты: политическая, географическая, тематическая и другие.
Перейдем к графикам. График – это графическое изображение, которое отображает зависимость одной величины от другой, динамику какого-либо процесса в течение какого-либо периода и много другое.
Например, Максим учится в девятом классе. В течение 8 лет учёбы в школе он получал следующие годовые оценки по математике: первый класс – 5, второй класс – 4, третий класс – 4, четвёртый – 5, пятый – 4, шестой – 3, седьмой – 4, восьмой - 3. Посмотрим, как это можно отобразить на графике. Ось X будет отображать классы с 1 по 8. Ось Y оценки с 1 до 5. Обратите внимание, что в данном графике за единицу будем брать две клеточки.
Расставим точки в соответствии с данными на координатной плоскости и соединим их линиями.
Мы получили необходимый график, с помощью которого можно сделать вывод, что знания Максима по математике ухудшились. Ещё одним примером графика является кардиограмма сердца. Кардиограмма точно определяет в каком ритме бьётся сердце.
Перейдём к диаграммам. Диаграмма – это графическое изображение, которое даёт наглядное представление о соотношении каких-либо величин или нескольких значений одной величины, об изменении их значений. Диаграммы бывают нескольких видов, но более подробно мы с ними познакомимся при изучении электронных таблиц.
А сейчас рассмотрим несколько примеров.
Первый: Наша планета состоит из воды и суши. Вода составляет семьдесят процентов от планеты, а суша – тридцать. Изобразим всё это с помощью круговой диаграммы. Нарисуем круг. Он будет изображать планету и соответственно будет равен ста процентам. Затем изобразим семьдесят процентов суши и тридцать процентов воды.
На данной диаграмме мы можем увидеть соотношение воды и суши.
Теперь рассмотрим ещё один пример. Саша тратит на дорогу от дома до школы 10 минут, Таня – 15 минут, Ира – 7 минут и Игорь – 20 минут. Давайте все это изобразим с помощью диаграммы. На оси X напишем имена учащихся, а на оси Y – время, затраченное на дорогу. Затем каждому учащемуся нарисуем столбик по высоте соответствующий времени его пути.
Таким образом мы получили столбчатую диаграмму.
Важно запомнить:
· Графическая информационная модель – это наглядный способ представления объектов и процессов в виде графических изображений.
· Схема – это графическое отображение состава и структуры сложной системы.
· Чертёж – это условное графическое изображение предмета с точным соотношением его размеров, получаемое методом моделирования.
· График – это графическое изображение, которое отображает зависимость одной величины от другой, динамику какого-либо процесса в течение какого-либо периода и много другое.
· Диаграмма – это графическое изображение, которое дает наглядное представление о соотношении каких-либо величин или нескольких значений одной величины, об изменении их значений.
Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.
Рабочие листы и материалы для учителей и воспитателей
Более 2 500 дидактических материалов для школьного и домашнего обучения
Столичный центр образовательных технологий г. Москва
Получите квалификацию учитель математики за 2 месяца
от 3 170 руб. 1900 руб.
Количество часов 300 ч. / 600 ч.
Успеть записаться со скидкой
Форма обучения дистанционная
- Онлайн
формат - Диплом
гособразца - Помощь в трудоустройстве
311 лекций для учителей,
воспитателей и психологов
Получите свидетельство
о просмотре прямо сейчас!
9 класс, информатика
Тема: Графические информационные модели.
Сформировать у учащихся понятие «графическая модель», рассмотреть виды графических моделей
Развивать практические навыки работы в Paint
Воспитывать интерес к изучаемой теме
Организационный момент
Актуализация прежних знаний
Что называют моделью?
Что такое моделирование?
Как можно разделить модели по фактору времени?
Что называют информационной моделью?
Какие типы информационных моделей знаете?
Информационная модель – совокупность информации, характеризующая свойства и состояния объекта, процесса, явления, а также их взаимосвязь с внешним миром.
Одному и тому же объекту можно поставить в соответствие разные информационные модели (вербальные, математические, табличные, графические); все зависит от цели моделирования.
Вербальная модель – это письменное или устное представление информационной модели средствами естественного языка.
Примеры вербальных моделей:
информация в учебниках
произведения художественной литературы
тексты, описывающие алгоритмы
текстовое описание объектов и процессов
Табличная информационная модель – это модель, в которой объекты или их свойства представлены в виде списка, а их значения размещаются в ячейках прямоугольной таблицы.
Изложение нового материала
Графические (или геометрические) информационные модели являются простейшим видом моделей, которые передают внешние признаки объек та — размеры, форму, цвет.
Графические модели более информативны, чем словесные. Без карт труд но представить себе ботанику и биологию, географию, военное дело, судо ходство и т.д.
Современные технологии не могут обойтись без информационных моделей технических устройств, зданий и т.д. в виде чертежей.
Электрические и радиосхемы — это информационные модели физики, радиотехники и радиоэлектроники.
Графики и диаграммы — это информационные модели, которые в нагляд ной форме представляют числовые и статистические данные.
Особое место среди геометрических моделей занимают задачи на построение. Такие задачи возникли еще в глубокой древности и были связаны с практическими потребностями. Они тренируют ум, учат комплексно применять знания, воспитывают нестандартный подход к решению про блем.
В качестве инструмента для графического моделирования сегодня ис пользуется графический редактор. Для моделирования в среде графического редактора можно пользоваться обобщенной информационной моделью графического объекта.
Любой графический объект обладает формой, размерами, пропорциями и цветом и его можно перемещать, тиражировать, редактировать, повора чивать, отражать, изменять размеры и пропорции.
Конструирование — это процесс сбора объекта и элементов. Конструиро вать можно плоские и объемные объекты.
Графическая информационная модель – это наглядный способ представления объектов и процессов в виде графических изображений.
Виды графических моделей:
Карта как информационная модель
Чертеж – точная геометрическая копия реального объекта
Схема – информационная модель сложных систем
График – как модель процесса
Фотография – точное визуальное изображение объекта
Карта описывает конкретную местность, которая является для нее объектом моделирования.
Карта создается с определенными целями для определения :
местоположения населенных пунктов;
используя линейку и учитывая масштаб карты, для измерения расстояний между реальными объектами на местности
Чертежи создаются конструкторами, проектировщиками, они должны быть очень точным, т.к. на них указываются все необходимые размеры реального объекта.
Существует масса различных компьютерных сред для создания конструкторских чертежей: Автокад, Адем, Компас, 3 D M АХ - для трехмерного моделирования и т.д.
Схема – это графическое отображение состава и структуры сложной системы.
Структура - это определенный порядок объединения элементов системы в единое целое.
Для отображения и визуализации различных процессов (природных, экономических, общественных и технических) часто используют построение графиков.
Графики могут быть представлены в виде круговых диаграмм, столбчатых диаграмм – гистограмм и линейных графиков.
Практическая работа в графическом редакторе Paint
В графическом редакторе создайте схему кабинета информатики. Соблюдайте пропорции всех объектов
Что называют графической моделью?
Какие графические модели рассмотрели?
Какие профессии работают с компьютерными графическими моделями?
Кому может понадобится схема кабинета информатики?
Домашнее задание
Постройте графическую модель вашей комнаты, указав на ней расположение всех предметов мебели, окон и дверей. Запишите название построенной модели (карта, план, схема, чертёж, график).
ТСО: компьютер, мультимедийный проектор.
Ход урока
I. Организационный момент.
- Что нас окружает? Множество объектов.
- Какие системы объектов целесообразно и возможно представить с помощью табличных моделей?
- Что отражают информационные модели?
III. Объяснение нового материала.
Информационные модели отражают различные типы систем объектов, в которых реализуются различные структуры взаимодействия и взаимосвязи между элементами системы. В узком понимании информационная модель – это модель, описывающая, изучающая, актуализирующая информационные связи и отношения в исследуемой системе. Информационные модели представляют объекты и процессы в образной или знаковой форме. (Приложение, слайд 2.)
Для отражения систем с различными структурами используются различные типы информационных моделей: табличные, иерархические и сетевые.
Мы уже изучили табличные информационные модели, которые реализуются в виде прямоугольной таблицы. Создавая таблицу, вы выбирали некоторое количество объектов и указывали их свойства. Свойства объектов – различны.
Однако некоторые группы объектов имеют одинаковые общие свойства, которые отличают их от объектов других групп.
Группа объектов, обладающих одинаковыми общими свойствами, называется классом объектов. Внутри класса объектов могут быть выделены подклассы, объекты которых обладают некоторыми особенными свойствами, в свою очередь подклассы могут делиться на ещё более мелкие группы и так далее. (Приложение, слайд 3.) Класс Четырёхугольники можно разделить на два подкласса: Параллелограммы и Трапеции. Подкласс Параллелограммы делится, свою очередь, на Прямоугольники и Ромбы, а в Прямоугольниках выделяются ещё Квадраты. Подкласс Трапеции делится на Равнобедренные и Прямоугольные.
Такой процесс систематизации объектов называется процессом классификации. В качестве примера классификации можно рассмотреть классификацию способов решения физических задач. (Приложение, слайд 4).
В процессе классификации объектов часто строятся информационные модели, которые имеют иерархическую структуру. (Приложение, слайд 5.) В биологии весь животный мир рассматривается как иерархическая система (тип, класс, отряд, семейство, род, вид), в информатике используется иерархическая файловая система.
В иерархической структуре элементы распределяются по уровням, от первого (верхнего) уровня до нижнего (последнего) уровня. Рассмотрим на примере объекта “Часы”, в качестве основания классификации возьмём способы функционирования.
В иерархической информационной модели объекты распределены по уровням. Каждый элемент более высокого уровня может состоять из элементов нижнего уровня, а элемент нижнего уровня может входить в состав только одного элемента более высокого уровня.
Рассмотрим процесс построения статической иерархической информационной модели, которая позволяет классифицировать современные компьютеры. (Приложение, слайд 7.)
Класс компьютеры можно разделить на три подкласса: Суперкомпьютеры, Серверы, Персональные компьютеры. Подкласс Персональные компьютеры делится, в свою очередь, на Настольные, Портативные и Карманные.
Удобным способом наглядного представления структуры информационных моделей является граф. (Приложение, слайд 8.)
В случае представления информации о составе и структуре системы в виде графа компоненты системы изображаются вершинами, а связи между ними – линиями (дугами или рёбрами). Графы используются во многих областях практической научной деятельности людей. Следующий пример относится к органической химии. Известно, что свойства химических веществ, называемых углеводородами, зависят не только от того, из какого количества атомов углерода и водорода состоит молекула, но и от способа их соединения, т.е. от структуры молекулы. Возьмём молекулу углеводорода , состоящую из пяти атомов углерода и двенадцати атомов водорода. В зависимости от способа соединения мы получим пентан (Приложение, слайд 9,) или, при другом способе соединения атомов, можно получить 2,2 деметилпропан (Приложение, слайд 10). Принятый в химии способ отображения структуры молекулы фактически является графом.
Следующий пример относится к медицине. Как известно, у разных людей кровь отличается по группе. Всего групп крови четыре.
Когда важно знание группы крови?
Да, при переливании крови, когда группа крови играет существенную роль. Дело в том, что не все группы крови совместимы. Вливание человеку “не той” группы может иметь весьма печальные последствия. Возможность переливания крови разных групп на следующем слайде. (Приложение, слайд 11.)
Какую группу крови можно перелить человеку, имеющему III, II, I группы крови?
Что сейчас вы держите в руках?
Правильно, шариковую ручку.
Из чего она состоит?
Её устройство тоже можно представить в виде графа. Школьники изображают устройство шариковой ручки в виде графа, используя средства Microsoft Word, панель рисование.
Полученный граф напоминает ветвящийся куст, который “растёт сверху вниз”. Граф, отражающий состав шариковой ручки, является деревом. Корень этого дерева – вершина “Шариковая ручка”.
Дерево – это граф, предназначенный для отображения таких связей между объектами как вложенность, подчинённость, наследование.
В виде дерева можно отразить иерархическую структуру разделов книги, в том числе и нашего учебника информатики. Это были примеры статических иерархических информационных моделей.
Для описания исторического процесса смены поколений семьи используются динамические информационные модели в форме генеалогического дерева. В качестве примера можно рассмотреть фрагмент генеалогического дерева династии Рюриковичей. (Приложение, слайд 12).
Назовите предков Ярослава?
IV. Самостоятельная работа.
Отобразите в виде графа структуру объектов: велосипед, ботинок.
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобретя в каталоге.
Получите невероятные возможности
Конспект урока "Графические информационные модели. Графы"
Граф – это совокупность объектов со связями между ними. Графически это будет выглядеть следующим образом:
Вершины (точки) – это объекты, а ребра (линии между ними) – это связи. Помимо точек вершины графа могут изображаться овалами, кругами, прямоугольниками и так далее. Связи между вершинами могут быть различными: дуги, рёбра, петли.
На данном уроке мы с вами познакомимся с ориентированными и неориентированными графами. В ориентированном графе связями между вершинами будут дуги, а в неориентированном – рёбра.
Решим задачу: В соревнованиях по шахматам участвовало 6 учащихся с 9 по 11 класс. При встрече они все обменялись рукопожатиями. Вопрос: сколько всего было сделано рукопожатий?
Для решения данной задачи будем использовать граф. Вершинами графов будут являться шесть учащихся, которые участвовали в турнире. Пронумеруем их от одного до шести. Проведем от каждой вершины линии (ребра) к оставшимся пяти вершинам.
Для ответа на вопрос остается сосчитать, сколько линий изображено на графе. Ответ: на турнире было сделано 15 рукопожатий.
Взвешенный граф – это граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией – весами вершин или рёбер.
Давайте сами нарисуем взвешенный граф на основе задачи со следующим условием: Между городами A, B, C, D, Е построены дороги. Необходимо найти кратчайший путь из города А в город Е, если известно, что из города А в город В расстояние 100 километров, из А в С – 260 километров, из В в С – 140 километров, из В в Е – 400 километров, из С в D – 50 километров, из С в Е – 100 километров и из D в Е – 40 километров.
Итак, для решения данной задачи необходимо нарисовать взвешенный граф, так как нам дано расстояние, то есть вес рёбер. Для начала нарисуем вершину А. Из неё будут выходить два ребра в вершины В и С. Ребро из А в В будет короче, чем из А в С, так как расстояние из пункта А в пункт В 100 километров, а из пункта А в пункт С – 260 километров.
Далее нарисуем ребро из В в С и его вес будет равен 140.
Теперь нарисуем ребро из вершины С в вершину D и укажем вес 50
У нас получился взвешенный граф.
Нам осталось найти кратчайший путь. Для этого из вершины А будем идти в вершину В – это 100 километров, затем сразу в вершину Е. Слаживаем 100 и 400, получим 500 километров.
Аналогичным образом проходим по остальным рёбрам и получим, что путь через вершины A, B, C, E равен 340 километров. Через вершины A, C, E 360 километров. A, B, C, D, E - 330, A, C, B, E 800 километров и через вершины A, C, D, E равен 350 километров. Нам необходимо выбрать кратчайший – это путь через города A, B, C, D, E и равен он 330 километров.
Следующее понятие, с которым мы должны познакомится - Цепь. Итак, цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза. То есть при построении пути по одному и тому же ребру можно пройти только один раз. Например, всем известная детская задача, где необходимо нарисовать домик не отрывая ручки от бумаги и в то же время нельзя дважды проходить по одной и той же линии.
В свою очередь, цикл – это цепь, в которой начальная и конечная вершины совпадают. В детстве, наверное, каждый из вас рисовал звезду, не отрывая ручки от бумаги и не проходя дважды по одной и той же линии или ребру. При изображении такой звезды начальная и конечная вершины совпадают. Сеть – это граф с циклом.
Разберём ещё один пример. У Антона в семье есть мама Татьяна, папа Юрий и сестра Маша. Изобразим каждого члена семьи как вершину нашего графа и обозначим первыми буквами имён. От каждого из них проведём рёбра к оставшимся троим. Над каждым из рёбер укажем, кто кем и кому приходится. Например, если идти от вершины Антона к Юрию, то Антон является сыном. А если идти наоборот, от Юрия к Антону, то Юрий является отцом. Аналогичным образом можно провести отношения между всеми членами семьи. Данный граф является примером семантической, или же смысловой сети.
Таким образом, Семантическая сеть – это информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними. Все связи данного графа различны, поэтому их необходимо подписывать.
Графы широко распространены как информационные модели. Их можно применять, например, при планировании жилого района, где вершинами будут являться дома, а рёбрами – дороги или дорожки, которые их связывают. Ещё одним примером будет являться карта проезда по городу на любом из видов транспорта, где остановки – это вершины, а путь движения транспорта – это рёбра и так далее.
Следующее определение в данной теме: дерево. Дерево – это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину. Отличительная особенность дерева: между любыми двумя его вершинами существует единственный путь. Корень дерева – это одна и единственная главная его вершина.
Каждая вершина дерева (кроме корня) имеет только одного предка. Обозначенный предком объект входит в один класс высшего уровня. Любая вершина дерева может порождать несколько потомков. Потомки – это вершины, которые соответствуют классам нижнего уровня. Такой принцип связи называется «один-ко-многим». Листья – это вершины, которые не имеют потомков.
Разберёмся более подробно на примере:
Ученик Антон решил составить генеалогическое дерево своей семьи. Для этого ему необходимо было узнать, кто в каких отношениях находится. То есть он является сыном своего отца Юрия и мамы Татьяны. В свою очередь Татьяна является дочерью Леонида (дедушки Антона) и Елены (бабушки Антона). Юрий является сыном Григория (дедушки Антона) и Марии (бабушки Антона). У Антона есть сестра Маша. Так как словесное описание трудно для восприятия, давайте поможем Антону представить это все в виде дерева и построим генеалогическое дерево.
Видим, что самыми старшими являются дедушки и бабушки Антона, поэтому расположим их в самом верху. У Леонида и Елены есть дочь Татьяна, а у Григория и Марии сын Юрий. Значит, разместим их на втором уровне (если считать сверху) и укажем их отношения с родителями в виде стрелок. У Татьяны и Юрия есть сын Антон и дочь Маша. Разместим их аналогичным образом на нашей схеме.
Таким образом, мы построили родословное дерево.
Важно запомнить:
· Граф – это совокупность объектов со связями между ними.
· Вершины – это объекты, а ребра – это связи.
· Взвешенный граф – это граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией – весами вершин или рёбер.
· Цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
· Цикл – это цепь, в которой начальная и конечная вершины совпадают.
· Сеть – это граф с циклом.
· Семантическая сеть – это информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.
· Дерево – это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину.
Данный урок наполнен различными видами графических моделей, которые представлены не только теоретически, но и визуально.
Читайте также: