В реальном мире особенно в сложных системах между предметами существуют различные отношения. При моделировании предметы представляются как объекты, а отношения между ними как связи. Каждый тип связи в модели имеет свое имя. В графической форме связь отображается в виде линии между связанными объектами с указанием идентификатора связи.
Существует три вида элементарных связей: один-к-одному (рис. 4.1.), один-ко-многим (рис. 4.2.) и многие-ко-многим (рис. 4.3.).
Связь один-к-одному существует, когда один экземпляр одного объекта связан с единственным экземпляром другого. Связь один-к-одному обозначается стрелками ←или→.
Рис. 4.1. Пример связи «один-к-одному».
Связь один-ко-многим существует, когда один экземпляр первого объекта связан с более чем с одним экземпляром второго объекта, но каждый экземпляр второго объекта связан только с одним экземпляром первого. Такая связь изображается двойной стрелкой →→.
Рис. 4.2. Пример связи «один-ко-многим».
Связь многие-ко-многим существует, когда каждый экземпляр первого объекта связан с одним или большим количеством экземпляров второго, и каждый экземпляр второго связан с одним или многими экземплярами первого. Этот тип связи изображается двусторонней стрелкой ↔.
Adobe InDesign — «САМОЕ ВАЖНОЕ». Урок 5 — Страницы/Мастер-шаблоны/Связи/Колонтитулы
Рис. 4.3. Пример связи «многие-ко-многим».
Помимо множественности, связи могут подразделяться на безусловные и условные. В безусловной связи участвует каждый экземпляр объекта. В условной связи принимают участие не все экземпляры объекта. Связь может быть условной как с одной, так и с обеих сторон.
Все связи в информационной модели требуют описания, которое, как минимум, включает:
• вид связи (ее множественность и условность).
Элементарные связи являются составными частями структур связей. Безусловная последовательность связей один-к-одному называется структурой типа очередь и графически отображена на рис.4.4.а. Обобщением структуры типа очередь является циклическая структура, изображенная на рис. 4.4.б.
Очень важную роль играет древовидная информационная модель, являющаяся одной из самых распространенных типов классификационных структур. Древовидная связь является безусловной связью типа один-ко-многим и графически изображена на рис. 4.4. в. Особенностью такой структуры является то, что каждый объект может иметь не более одного предка, произвольное количество потомков.
Объект, который не имеет потомков, называют листовым. Иерархическое дерево начинается с одного объекта, называемого корневым объектом. Очень важно, что каждый объект должен иметь свое уникальное имя или идентификатор. Эту структуру связи еще называют иерархической. На рис. 4.4. в. прямоугольник R является корневым объектом. Объекты B1.
B8 являются листовыми. Иерархическая модель довольно удобна для представления предметных областей, так как иерархические отношения довольно часто встречаются между сущностями реального мира. Но иерархическая модель не поддерживает отношения «многие ко многим», когда множество объектов одного типа связаны со множеством объектов другого типа. Предположим, что требуется построить модель отношения между множеством преподавателей и множеством предметов. Для моделирования таких отношений иерархическая древовидная структура не подходит.
Adobe InDesign — «САМОЕ ВАЖНОЕ». Урок 1 — Знакомство с программой
Источник: studopedia.ru
Урок 4
§1.3 Графические информационные модели
В графических информационных моделях для наглядного отображения объектов используются условные графические изображения (образные элементы), зачастую дополняемые числами, символами и текстами (знаковыми элементами). Примерами графических моделей могут служить всевозможные схемы, карты, чертежи, графики и диаграммы.
Схема — это представление некоторого объекта в общих, главных чертах с помощью условных обозначений. С помощью схем может быть представлен и внешний вид объекта, и его структура. Схема как информационная модель не претендует на полноту предоставления информации об объекте.
С помощью особых приёмов и графических обозначений на ней более рельефно выделяется один или несколько признаков рассматриваемого объекта. Примеры схем приведены на рис. 1.5.
Рис. 1.5. Примеры схем, используемых на уроках физики, биологии, истории
Уменьшенное обобщённое изображение поверхности Земли на плоскости в той или иной системе условных обозначений даёт нам географическая карта.
Чертёж — условное графическое изображение предмета с точным соотношением его размеров, получаемое методом проецирования. Чертёж содержит изображения, размерные числа, текст. Изображения дают представления о геометрической форме объекта, числа — о величине объекта и его частей, надписи — о названии, масштабе, в котором выполнены изображения.
График — графическое изображение, дающее наглядное представление о характере зависимости одной величины (например, пути) от другой (например, времени). График позволяет отслеживать динамику изменения данных.
Диаграмма — графическое изображение, дающее наглядное представление о соотношении каких-либо величин или нескольких значений одной величины, об изменении их значений. Более подробно типы диаграмм и способы их построения будут рассмотрены при изучении электронных таблиц.
1.3.2. Графы
Если некоторые объекты изобразить вершинами, а связи между ними — линиями, то мы получим информационную модель в форме графа. Вершины графа могут изображаться кругами, овалами, точками, прямоугольниками и т. д. Ненаправленная (без стрелки) линия, соединяющая вершины графа, называется ребром. Линия направленная (со стрелкой) называется дугой; при этом вершина, из которой дуга исходит, называется начальной, а вершина, куда дуга входит, — конечной.
Граф называется неориентированным, если его вершины соединены рёбрами (рис. 1.6, а). Вершины ориентированного графа соединены дугами (рис. 1.6, б). Путь — это последовательность рёбер (дуг), по которым можно перейти из одной вершины в другую.
Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер. На рис. 1.6, в с помощью взвешенного неориентированного графа изображены дороги между пятью населёнными пунктами А, В, С, D, Е; веса рёбер — протяжённость дорог в километрах.
Путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза, называется цепью. Цепь, начальная и конечная вершины которой совпадают, называется циклом.
Рис. 1.6. Графы
Граф с циклом называется сетью. Если героев некоторого литературного произведения представить вершинами графа, а существующие между ними связи изобразить рёбрами, то мы получим граф, называемый семантической сетью.
Графы как информационные модели находят широкое применение во многих сферах нашей жизни. Например, можно существующие или вновь проектируемые дома, сооружения, кварталы изображать вершинами, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — рёбрами графа. По таким графам можно планировать оптимальные транспортные маршруты, кратчайшие объездные пути, расположение торговых точек и других объектов.
Дерево — это граф, в котором нет циклов, т. е. в нём нельзя из некоторой вершины пройти по нескольким различным рёбрам и вернуться в ту же вершину. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь.
Всякая иерархическая система может быть представлена с помощью дерева. У дерева выделяется одна главная вершина, называемая его корнем. Каждая вершина дерева (кроме корня) имеет только одного предка, обозначенный предком объект входит в один класс1* высшего уровня.
Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один-ко-многим». Вершины, не имеющие порождённых вершин, называются листьями.
Родственные связи между членами семьи удобно изображать с помощью графа, называемого генеалогическим или родословным деревом.
Ресурс «Живая Родословная» (145555) — инструмент для формирования и анализа генеалогических деревьев, содержащий примеры родословных. С его помощью вы можете изучить генеалогические деревья многих известных семей и построить генеалогическое дерево своей семьи (http://sc.edu.ru/).
Класс — множество объектов, обладающих общими признаками.
1.3.3. Использование графов при решении задач
Графы удобно использовать при решении некоторых классов задач.
Пример 1. На рисунке 1.7 изображена схема дорог, связывающих торговые точки А, В, С, D, Е. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей от точки А до точки Е?
Рис. 1.7. Схема дорог, представленная ориентированным графом
В вершину Е можно попасть только из вершин С и D. Если мы будем знать число путей из вершины А в вершину С и из вершины А в вершину D, то, сложив их, получим искомое число путей из А в Е. Действительно, для того чтобы попасть из вершины А в вершину Е, мы просто все пути из вершины А в вершину С дополним дугой СЕ, а пути из вершины А в вершину D дополним дугой DE. Число путей при этом не изменится. Итак, число путей из вершины А в вершину Е равно сумме путей из А в С и из А в П.
Можно сказать, что наша задача распалась на две более простые задачи. Решим каждую из них в отдельности.
В вершину С можно попасть непосредственно из вершины А и из вершины В. В свою очередь, существует единственный путь из вершины А в вершину В. Таким образом, из вершины А в вершину С можно попасть двумя путями: 1 (напрямую из А) + 1 (через В) = 2.
Попробуйте доказать, что путь из вершины А в вершину В — единственный.
Что касается вершины D, она является конечной вершиной для трёх дуг: BD, AD и CD. Следовательно, в неё можно попасть из вершин А, В и С:
1 (напрямую из А) + 1 (через В) + 2 (через С) = 4.
Итак, существуют четыре пути из вершины А в вершину D.
Теперь выполним подсчёт путей из А в Е:
2 (через С) + 4 (через D) = 6.
Решение задачи будет гораздо проще, если двигаться от вершины А (начало маршрута) к вершине Е и проставлять веса вершин — число путей из А в текущую вершину (рис. 1.8). При этом вес вершины А можно принять за 1. Действительно, существует единственный способ попасть из А в А — оставаться на месте.
Рис. 1.8. Схема дорог, представленная взвешенным ориентированным графом
Пример 2. Для того чтобы записать все трёхзначные числа, состоящие из цифр 1 и 2, можно воспользоваться графом (деревом) на рис. 1.9.
Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их количество. В этом случае рассуждать нужно так: в разряде сотен может быть любая из цифр 1 и 2, в разряде десятков — те же два варианта, в разряде единиц — те же два варианта. Следовательно, число различных вариантов: 2 • 2 • 2 = 8.
Рис. 1.9. Дерево для решения задачи о записи трёхзначных чисел
В общем случае, если известно количество возможных вариантов выбора на каждом шаге построения графа, то для вычисления общего количества вариантов нужно все эти числа перемножить. (Вспомните правило умножения из комбинаторики!)
Пример 3. Рассмотрим несколько видоизменённую классическую задачу о переправе.
На берегу реки стоит крестьянин (К) с лодкой, а рядом с ним — собака (С), лиса (Л) и гусь (Г). Крестьянин должен переправиться сам и перевезти собаку, лису и гуся на другой берег. Однако в лодку кроме крестьянина помещается либо только собака, либо только лиса, либо только гусь. Оставлять же собаку с лисой или лису с гусём без присмотра крестьянина нельзя — собака представляет опасность для лисы, а лиса — для гуся. Как крестьянин должен организовать переправу?
Для решения этой задачи составим граф, вершинами которого будут исходное и результирующее размещение персонажей на берегах реки, а также всевозможные промежуточные состояния, достигаемые из предыдущих за один шаг переправы. Каждую вершину-состояние переправы обозначим овалом и свяжем рёбрами с состояниями, образованными из неё (рис. 1.10).
Недопустимые по условию задачи состояния выделены пунктирной линией; они исключаются из дальнейшего рассмотрения. Начальное и конечное состояния переправы выделены жирной линией.
На графе видно, что существуют два решения этой задачи. Приведём соответствующий одному из них план переправы:
1) крестьянин перевозит лису;
2) крестьянин возвращается;
3) крестьянин перевозит собаку;
4) крестьянин возвращается с лисой;
5) крестьянин перевозит гуся;
6) крестьянин возвращается;
7) крестьянин перевозит лису.
Пример 4. Рассмотрим следующую игру: сначала в кучке лежат 5 спичек; два игрока убирают спички по очереди, причём за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Выясним, кто выигрывает при правильной игре — первый (I) или второй (II) игрок.
Игрок I может убрать одну спичку (в этом случае их останется 4) или сразу 2 (в этом случае их останется 3).
Если игрок I оставил 4 спички, игрок II может своим ходом оставить 3 или 2 спички. Если же после хода первого игро- . ка останутся 3 спички, второй игрок может выиграть, взяв две спички и оставив одну.
Если после игрока II осталось 3 или 2 спички, то игрок I в каждой из этих ситуаций имеет шанс на выигрыш.
Таким образом, при правильной стратегии игры всегда выиграет первый игрок. Для этого своим первым ходом он должен взять одну спичку.
На рис. 1.11 представлен граф, называемый деревом игры; на нём отражены все возможные варианты, в том числе ошибочные (проигрышные) ходы игроков.
Рис. 1.11. Дерево игры
САМОЕ ГЛАВНОЕ
В графических информационных моделях для наглядного отображения объектов используются условные графические изображения (образные элементы), зачастую дополняемые числами, символами и текстами (знаковыми элементами). Примерами графических моделей могут служить всевозможные схемы, карты, чертежи, графики и диаграммы, графы.
Граф состоит из вершин, связанных линиями — рёбрами или дугами. Граф называется взвешенным, если его вершины или рёбра (дуги) характеризуются некоторой дополнительной информацией — весами вершин (рёбер, дуг).
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь.
Вопросы и задания
1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Что вы можете сказать о формах представления информации в презентации и в учебнике? Какими слайдами вы могли бы дополнить презентацию?
2. Какие информационные модели относят к графическим?
3. Приведите примеры графических информационных моделей, с которыми вы имеете дело:
а) при изучении других предметов;
б) в повседневной жизни.
4. Что такое граф? Что является вершинами и рёбрами графа на рис. 1.6, в? Приведите примеры цепей и циклов, имеющихся в этом графе. Определите, какие два пункта наиболее удалены друг от друга (два пункта считаются самыми удалёнными, если длина кратчайшего пути между ними больше, чем длина кратчайшего пути между любыми другими двумя пунктами). Укажите длину кратчайшего пути между этими пунктами.
5. Приведите пример системы, модель которой можно представить в форме графа. Изобразите соответствующий граф.
6. Грунтовая дорога проходит последовательно через населённые пункты А, В, С и D. При этом длина грунтовой дороги между А и В равна 40 км, между В и С — 25 км, и между С и D — 10 км. Между А и D дороги нет. Между А и С построили новое асфальтовое шоссе длиной 30 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге — 20 км/ч, по шоссе — 30 км/ч.
7. На рисунке изображена схема дорог, связывающих торговые точки А, Б, В, Г, Д, Б, К. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей от точки А до точки К?
8. Работая в группе, составьте семантическую сеть по одной из русских народных сказок: «Колобок», «Курочка Ряба», «Репка».
9. Что такое дерево? Моделями каких систем могут служить деревья? Приведите пример такой системы.
10. Сколько трёхзначных чисел можно записать с помощью цифр 2, 4, 6 и 8 при условии, что в записи числа не должно быть одинаковых цифр?
11. Сколько существует трёхзначных чисел, все цифры которых различны?
12. Для составления цепочек используются бусины, помеченные буквами А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором — любая гласная, если первая буква гласная, и любая согласная, если первая согласная. На третьем месте — одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?
13. Два игрока играют в следующую игру. Перед ними лежит куча из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень.
Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Электронное приложение к уроку
| Файлы | Материалы урока | Ресурсы ЭОР |
Cкачать материалы урока
Источник: xn—-7sbbfb7a7aej.xn--p1ai
Структурные модели систем. Графы
В начале урока учащиеся узнают, что такое структурная модель системы и из каких моделей она образуется. А затем познакомятся с такими понятиями, как граф, вершины, рёбра, ориентированные, неориентированный, взвешенный графы и так далее. Также учащиеся научатся различать эти графы и решать задачи благодаря визуальному представлению информации.
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет.
Получите невероятные возможности
1. Откройте доступ ко всем видеоурокам комплекта.
2. Раздавайте видеоуроки в личные кабинеты ученикам.
3. Смотрите статистику просмотра видеоуроков учениками.
Получить доступ
Конспект урока «Структурные модели систем. Графы»
Вспомним ключевые термины прошлого урока.
Системный анализ – это исследование реальных объектов и явлений с точки зрения системного подхода, состоящее из этапов анализа и синтеза.
Модель «чёрного ящика» – это указание входов и выходов системы, а также зависимости между ними.
Модель состава – это своеобразный список элементов системы.
На данном уроке мы с вами узнаем, что такое структурная модель системы, что используется для её отображения, а также вспомним, из чего состоят графы.
Если обобщить всё пройдённое на прошлом уроке, можно сказать, что модель «чёрного ящика», модель состава и модель структуры полностью описывают систему и образуют ещё одну модель, которая называется структурной моделью системы или структурной схемой. На структурной схеме отражается состав системы и её внутренние связи. Для отображения структурной схемы системы используются графы.
Граф – это совокупность объектов со связями между ними.
Графически это будет выглядеть следующим образом: вершины (точки) – это элементы системы, а ребра (линии между ними) – это связи (отношения) между элементами системы.
Примером графа является схема движения автобусов в городе, где вершины – это остановки, а рёбра – это пути передвижения автобусов. С помощью такой схемы проще определить на каком автобусе нужно доехать с одной остановки до другой.
Графы бывают ориентированными и неориентированными.
В неориентированных графах связь между элементами системы не имеет выделенного направления, то есть рёбра не имеют ориентации. Примером неориентированного графа будет являться решение задачи на нахождение кратчайшего пути. Граф для решения одной из таких задач, условием которой является нахождение кратчайшего пути из точки A в точку F, будет выглядеть следующим образом.
В ориентированных графах наоборот отражается связь между элементами системы с помощью ориентированных рёбер (стрелок). Такие рёбра называются дугами.
Так же с помощью дуг указывается не только наличие связи, но и какой из двух элементов является «началом» связи, а какой «концом». К примеру ориентированного графа можно отнести графическое изображение следующего условия: ученик 11 класса Рома на перемене узнал, что сегодня будет проходить самостоятельная работа по информатике, и решил рассказать об это одноклассникам. Он позвонил Лене, Лена позвонила Маше, Маша рассказала Саше, Саша – Даше, Даша – Кате, Катя – Маше.
Изобразим каждого учащегося как вершины графа, название которых будут отмечены первыми буквами имён, а звонки или разговоры дугами. Начало дуги будет находиться у вершины учащегося, который рассказывал про самостоятельную, а конец – у вершины того, кому рассказывали. Таким образом, мы получим ориентированный граф.
В ориентированном графе связями между вершинами будут дуги, а в неориентированном – рёбра.
Ещё графы бывают взвешенными. Взвешенный граф – это граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией – весами вершин или рёбер.
Нарисуем взвешенный граф на основе следующего условия: четыре торговца продают друг другу товары. Первый торговец продаёт товар второму по 20 рублей, а четвёртому по 15 рублей. Цена товара у второго торговца для четвёртого составляет 5 рублей, а для третьего – десять. Третий продаёт свой товар первому и четвёртому по 15 рублей, а четвёртый продаёт первому и третьему по 20 рублей. Для обозначения рыночных отношений между торговцами будем использовать дуги, а для указания веса, будем писать его над каждой дугой.
Для начала рисуем все вершины и обозначим их цифрами от одного до четырёх. Затем, по условию задачи первый торговец продаёт свой товар второму и четвёртому. Проведём стрелку от первого ко второму и от первого к четвёртому. Затем над каждой из них запишем соответствующую цену. Таким же образом оформляем весь граф.
С помощью данного графа мы можем увидеть, что, например, для четвёртого торговца выгоднее продать товар первому и третьему, а купить у второго. И так далее.
Так же графы бывают связными и несвязными.
Связный граф – это граф, между любой парой которого существует хотя бы один путь.
Примерами связных графов являются все вышерассмотренные графы.
Несвязный граф – это граф, в котором существует хотя бы одна пара вершин, между которыми нет пути. Такие вершины называются несвязными. Например, на показанном графе несвязными вершинами является G и любая другая вершина данного графа.
Следующее понятие, с которым мы должны познакомиться: цепь. Итак, цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза. То есть, при построении пути, по одному и тому же ребру можно пройти только один раз.
Например, водитель грузового автомобиля совершает один и тот же маршрут в день, чтобы развезти товар в пять различных магазинов. Давайте построим с помощью графа путь водителя. Обозначим вершинами все пять магазинов, и пронумеруем их от одного до пяти. Далее, водитель заехал в первый магазин, выгрузил необходимый товар и поехал во второй магазин.
Изобразим ребром путь от первого магазина ко второму. Затем поехал в третий, четвёртый и пятый. Также изобразим данные пути с помощью рёбер. Обратите внимание, что водитель проезжает по каждому ребру только один раз. Данный граф будет являться примером цепи.
Цикл – это цепь, в которой начальная и конечная вершины совпадают.
Разберём пример, похожий на предыдущий, но с некоторыми изменениями. Водитель грузового автомобиля совершает один и тот же маршрут каждый день, чтобы развезти товар. Изначально он выезжает со склада, на котором загружает товар. Затем едет в пять различных магазинов. А после того, как весь товар был доставлен, он возвращается на склад.
Давайте снова построим путь водителя на следующий день с помощью графа. Обозначим вершинами склад и все пять магазинов, где цифры от одного до пяти будут обозначать магазины, а склад обозначим буквой «С». Изначально водитель заезжает на склад, затем едет в первый магазин, чтобы выгрузить необходимый товар. Обозначим этот путь ребром. Далее он едет из первого магазина во второй.
Также изобразим ребром этот путь. Затем водитель едет в третий, четвёртый и пятый магазины. Снова изобразим данные пути с помощью рёбер. Из пятого магазина он едет на склад. Отметим этот путь на нашем графе. Обратите внимание, что водитель проезжает по каждому ребру только один раз и в конце возвращается в первоначальную вершину – на склад.
Данный граф будет являться примером цикла.
Сеть – это граф с циклом.
В качестве примера сюда можно отнести пятиконечную звезду, но прежде чем проводить ребра, обозначим точкой каждую из вершин. Затем начиная с нижней соединим их.
На практике часто приходится строить системы с иерархической системой. Такой граф называется деревом.
Дерево – это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину. Отличительная особенность дерева: между любыми двумя его вершинами существует единственный путь.
Корень дерева – это единственная главная его вершина.
Каждая вершина дерева (кроме корня) имеет только одного предка. Обозначенный предком объект входит в один класс высшего уровня. Любая вершина дерева может порождать несколько потомков.
Потомки – это вершины, которые соответствуют классам нижнего уровня. Такой принцип связи называется «один-ко-многим».
Листья – это вершины, которые не имеют потомков.
Разберёмся более подробно на примере.
Давайте построим иерархическую структуру школы. Во главе будет находиться директор и соответственно он будет корневой вершиной нашего дерева. Далее на втором уровне будут находиться завуч по учебной работе, завуч по воспитательной работе, завуч младших классов, далее учителя и учащиеся. В данной структуре мы можем видеть, что Потомками являются все, кроме директора, предками – все, кроме учащихся, а листьями – учащиеся, так как в данной структуре у них нет потомков.
Итоги урока:
· Структурная модель системы отражает состав и внутренние связи системы.
· Граф – это графическое отображение структурной модели; состоит из вершин и линий (рёбер и дуг).
· Дерево – это ориентированный граф системы с иерархической структурой; связь – «один ко многим».
Источник: videouroki.net