Проверка домашнего задания Приведите различные примеры графических информационных моделей. Приведите различные примеры графических информационных моделей

Разнообразие графических моделей достаточно велико. Рассмотрим некоторые из них.

Графы

Наглядным средством отображения состава и структуры систем являются графы. Рассмотрим пример. Имеется словесное описание некоторой местности.

Район состоит из пяти поселков: Дедкино, Репкино, Бабкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино.

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

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

Построенный граф позволяет, например, ответить на вопрос: через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино? Видно, что есть два возможных пути: 1) Р - К - Б - М и 2) Р- К - Д - Б - М. Можно ли отсюда сделать вывод, что 1-й путь короче 2) –го? Нет, нельзя. Данный граф не содержит количественных характеристик. Это не карта, где соблюдается масштаб и есть возможность измерить расстояние.

Граф, приведенный на следующем рисунке, содержит количественные характеристики. Числа около ребер обозначают длины дорог в километрах. Это пример взвешенного графа. Взвешенный граф может содержать количественные характеристики не только связей, но и вершин. Например, в вершинах может быть указано население каждого поселка. Согласно данным взвешенного графа, оказывается, что второй путь длиннее первого.
Подобные графы еще называют сетью. Для сети характерна возможность множества различных путей перемещения по ребрам между некоторыми парами вершин. Для сетей также характерно наличие замкнутых путей, которые называются циклами. В данном случае имеется цикл: К-Д-Б-К

На рассмотренных схемах каждое ребро обозначает наличие дорожной связи между двумя пунктами. Но дорожная связь действует одинаково в обе стороны: если по дороге можно проехать от Б к М, то по ней же можно проехать и от М к Б (предполагаем, что действует двустороннее движение). Такие графы являются неориентированными, а их связи называются симметричными.

Качественно иной пример графа изображен на следующем рисунке.

Этот пример относится к медицине. Известно, что у разных людей кровь отличается по группе. Существуют четыре группы крови. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы. Граф показывает возможные варианты переливания крови. Группы крови – это вершины графа с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови. Например, из этого графа видно, что кровь первой группы можно переливать любому человеку, а человек с первой группой крови воспринимает только кровь своей группы. Видно также, что человеку с IV группой крови можно переливать любую, но его собственную кровь можно переливать только в ту же группу.

Связи между вершинами данного графа несимметричны и поэтому изображаются направленными линиями со стрелками. Такие линии принято называть дугами (в отличие от ребер неориентированных графов). Граф с такими свойствами называется ориентированным. Линия, выходящая и входящая в одну и ту же вершину, называется петлей. В данном примере присутствуют четыре петли.

Дерево – граф иерархической структуры

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

Граф иерархической структуры называется деревом. Основным свойством дерева является то, что между любыми двумя его вершинами существует единственный путь. Деревья не содержат циклов и петель.

Дерево административной структуры РФ

Посмотрите на граф, отражающий иерархическую административную структуру нашего государства: РФ делится на семь административных округов; округа делятся на регионы (области и национальные республики), в состав которых входят города и другие населенные пункты. Такой граф называется деревом.

У дерева существует одна главная вершина, которая называется корнем дерева. Эта вершина изображается вверху; от нее идут ветви дерева. От корня начинается отсчет уровней дерева. Вершины, непосредственно связанные с корнем, образуют первый уровень. От них идут связи к вершинам второго уровня и т.д. Каждая вершина дерева (кроме корня) имеет одну исходную вершину на предыдущем уровне и может иметь множество порожденных вершин на следующем уровне. Такой принцип связи называется “один ко многим”. Вершины, которые не имеют порожденных, называются листьями (на нашем графе это вершины, обозначающие города).

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

Общую цель научной графики можно сформулировать так: сделать невидимое и абстрактное “видимым”. Последнее слово заключено в кавычки, т.к. эта видимость часто весьма условна. Можно увидеть распределение температуры внутри неоднородно нагретого тела сложной формы без введения в него сотен микродатчиков, т.е. по существу его разрушения? – Да, можно, если есть соответствующая математическая модель и, что очень важно, договоренность о восприятии определенных условностей на рисунке. Можно увидеть распределение металлических руд под землей без раскопок? Строение поверхности чужой планеты по результатам радиолокации? Да, можно, с помощью компьютерной графики и предшествующей ей математической обработки.

Более того, можно “увидеть” и то, что, строго говоря, вообще плохо соответствует слову “видеть”. Так, возникшая на стыке химии и физики наука – квантовая химия – дает нам возможность “увидеть” строение молекулы. Эти изображения – верх абстракции и системы условностей, так как в атомном мире обычные наши понятия о частицах (ядрах, электронах и т.п.) принципиально неприменимы. Однако многоцветное “изображение” молекулы на экране компьютера для тех, кто понимает всю меру его условности, приносит большую пользу, чем тысячи чисел, являющихся результатами вычислений.

Изолинии.

Стандартный прием обработки результатов вычислительного эксперимента – построение линий (поверхностей), называемых изолиниями (изоповерхностями), вдоль которых некоторая функция имеет постоянное значение. Это очень распространенный прием визуализации характеристик некоторого скалярного поля в приближении сплошной среды: изотермы – линии равной температуры; изобары – линии равного давления; изолинии численности экологической популяции на местности и т.д.

Условные цвета, условное контрастирование

Это прием современной научной графики – условная раскраска. Она находит широчайшее применение в самых разных приложениях науки и представляет собой набор приемов по максимально удобной визуализации результатов компьютерного моделирования.

В различных исследованиях температурных полей встает проблема наглядного представления результатов, например, температур на метеорологических картах. Для этого можно рисовать изотермы на фоне карты местности. Но можно добиться еще большей наглядности, учитывая, что большинству людей свойственно воспринимать красный цвет как “горячий”, синий – как “холодный”. Переход по спектру от красного к синему отражает промежуточные значения температур. При поиске полезных ископаемых методами аэросъемки с самолетов или космических спутников компьютеры строят условные цветовые изображения распределений плотности под поверхностью Земли и т.д.

Изображения в условных цветах и контрастах – мощнейший прием научной графики.

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

Задание :

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

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

Что такое модель

Что такое знаковые информационные модели? Примеры их используют в своей работе все учителя, которые владеют современными информационными технологиями. В общем виде модель - это разные способы представления анализируемой реальности.

Разновидности

Можно привести примеры информационных моделей материального и идеального вида.

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

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

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

Текстовые идеальные модели

Вербальные модели применяют преподаватели гуманитарного цикла. Они помогают описывать последовательными предложениями определенную область, явление, объект, событие. Как будет выглядеть такая информационная модель урока? Пример возьмем из курса литературы. При изучении романа Л. Н. Толстого «Война и мир», учитель описывает образ Наташи Ростовой. Для этого он пользуется именно текстовой моделью. Ребята, слушая педагога, создают на основе его восприятия образа этой героини, свой образ героини Толстого.

Если учитель истории просит своих воспитанников: «Приведите примеры образной информационной модели событий, произошедших во время Куликовской битвы, основываясь на просмотренных фрагментах», ребята создают свой образ того сражения. Они передают его в виде связанных в рассказ предложений.

Можно привести примеры информационных моделей вербального вида и из курса физики. При изучении темы «Давление твердых тел» в седьмом классе, учитель рассказывает детям, как сложно передвигаться по рыхлому снегу без лыж. Затем школьникам предлагается объяснить причину подобного явления, выявить параметры, от которых зависит изучаемая физическая величина. Образ, который возникает в сознание ребят после рассказа педагога, помогает им ответить на поставленный вопрос.

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

Математические модели

Они считаются широким классом знаковых моделей. Основываются математические модели на использовании соотношений, сравнений, иных методах, применяемых в данной науке. Приводя примеры информационных моделей, основанных на математических методах, можно упомянуть решение квадратных уравнений, составление пропорций. Все разделы геометрии, предполагающие вывод и доказательство теорем, также связаны с построением математической модели. Не обходится без них и такой школьный предмет как экономика.

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

Они считаются классом знаковых моделей, которые описывают любые информационные процессы: появление, передачу, изменение, применение информации в разных системах. Примеры табличных информационных моделей в школе можно найти в курсе географии 10 класса. При изучении экономической географии табличная модель помогает наглядно видеть основные характеристики страны, использовать материал для составления полного рассказа.

Кроме того примеры табличных информационных моделей можно найти в любом школьном курсе. В химии это таблица растворимости соединений, а также периодическая система Менделеева. В физике без таблиц учителю сложно объяснить основные термины, изучаемые в теме «Электричество». В истории с их помощью осуществляется систематизация знаний, ребята вписывают в один столбик важные исторические даты, а в другом - описывают события, которые им соответствуют.

Взаимосвязь моделей

Между информационными, математическими, вербальными моделями существует условная грань. Все 3 примера информационных моделей встречаются в школьных дисциплинах. Так, для математики, физики, информатики, самыми востребованными считают математические и информационные варианты. Но без вербальной модели ребята не смогут объяснить явления, алгоритмы, уравнения и неравенства.

Особенности моделирования

Прежде чем рассматривать примеры графических информационных моделей, выясним особенности моделирования. Модель представляет собой объект, созданный искусственно. Это необходимо для упрощения представления о настоящем объекте либо явлении. Модель в полной мере отражает все особенности самого исходного процесса. Если дано задание: «Приведите пример информационной модели», необходимо понимать суть процесса.

Речь идет о построении модели, которая предназначена для изучения информационных явлений, процессов. В информатике в качестве такого предмета можно рассматривать программирование. Используя определенный математический язык программирования, можно представить текстовый материал в графическом виде.

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

Деятельностный подход

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

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

Если учителя просят: «Приведите пример информационной модели», он смело может выбирать любой учебный предмет. Нет такой дисциплины, в которой бы не применялись таблицы, графики, диаграммы, презентации.

Особенности современной школы

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

При изучении темы «Окислительно-восстановительные реакции» у школьников появляется информация о том, что происходит с этими отрицательными частицами при химическом взаимодействии. Несмотря на то что информация предоставляется с разных позиций, речь идет об одном объекте - электронах. Подобный системный подход позволяет формировать в сознании школьников полное представление о строении вещества, его превращениях.

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

Особое значение формирование универсальных моделей приобретает при экспериментальной деятельности. Используя персональный компьютер, можно провести вычисления параметров, которые будут связаны с анализируемым объектом.

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

Использование в рамках школы персонального компьютера возможно по трем основным вариантам:

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

Признаки моделей

Среди самых распространенных признаков, по которым можно провести классификацию всех моделей, выделим: цель применения, сферу знаний, временной фактор, вариант представления.

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

Разновидности моделей

В зависимости от области знаний, для которых составляется модель, в настоящее время выделяют экономические, биологические, социологические, химические виды. К примеру, для естественнонаучного цикла важно сформировать такую модель, которая бы позволяла объяснять явления, происходящие в живой и неживой природе. В социологии акцент делают на процессы, происходящие в социуме.

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

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

Материальные модели предполагают реальное воплощение, они в полной мере повторяют внутреннее либо внешнее строение самого объекта. Например, в географии в качестве такой уменьшенной модели выступает макет земного шара (глобус), на котором нанесены все моря и океаны, материки и острова. Данные модели непосредственным образом связаны с исследовательским подходом к обучению современных школьников. Они необходимы при преподавании химии, физики, биологии, астрономии, географии.

Нематериальное моделирование предполагает использование теоретического способа познания.

Заключение

Любая информационная модель представляет собой совокупность информации об явлении, объекте, процессе. С ее помощью можно охарактеризовать любой процесс, происходящий в живой и неживой природе. Разнообразные графики, карты, таблицы, диаграммы, которые активно применяются педагогами на всех ступенях обучения, дают свой положительный результат.

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

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

Схема - это представление некоторого объекта в общих, главных чертах с помощью условных обозначений. С помощью схем может быть представлен и внешний вид объекта, и его структура. Схема как информационная модель не претендует на полноту предоставления информации об объекте. С помощью особых приёмов и графических обозначений на ней более рельефно выделяется один или несколько признаков рассматриваемого объекта. Примеры схем приведены на рис. 2.4.

Рис. 2.4.
Примеры схем, используемых на уроках физики, биологии, истории

Уменьшенное обобщённое изображение поверхности Земли на плоскости в той или иной системе условных обозначений даёт нам географическая карта.

Чертёж - условное графическое изображение предмета с точным соотношением его размеров, получаемое методом проецирования. Чертёж содержит изображения, размерные числа, текст. Изображения дают представления о геометрической форме объекта, числа - о величине объекта и его частей, надписи - о названии, масштабе, в котором выполнены изображения.

График - линия, дающая наглядное представление о характере зависимости одной величины (например, пути) от другой (например, времени). График позволяет отслеживать динамику изменения данных.

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

2.3.2. Графы

Если объекты некоторой системы изобразить вершинами, а связи между ними - линиями, то мы получим информационную модель рассматриваемой системы в форме графа. Граф состоит из вершин, связанных линиями - рёбрами. Вершины графа могут изображаться кругами, овалами, точками, прямоугольниками и т. д.

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

На рис. 2.5 с помощью взвешенного графа изображены дороги между пятью населёнными пунктами А, Б, С, D, Е; веса рёбер - протяжённость дорог в километрах.

Рис. 2.5.
Взвешенный граф

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

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

Графы как информационные модели находят широкое применение во многих сферах нашей жизни. Например, можно существующие или вновь проектируемые дома, сооружения, кварталы изображать вершинами, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. - рёбрами графа. По таким графам можно планировать оптимальные транспортные маршруты, кратчайшие объездные пути, расположение торговых точек и других объектов.

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

Всякая иерархическая система может быть представлена с помощью дерева. У дерева выделяется одна главная вершина, называемая его корнем. Каждая вершина дерева (кроме корня) имеет только одного предка, обозначенный им объект входит в один класс 1 высшего уровня. Любая вершина дерева может порождать несколько потомков - вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один-ко-многим». Вершины, не имеющие порождённых вершин, называются листьями.

1 Класс - множество объектов, обладающих общими признаками.

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

Ресурс «Живая Родословная» (http://school-collection.edu.ru/) - инструмент для формирования и анализа генеалогических деревьев, содержащий примеры родословных. С его помощью вы можете изучить генеалогические деревья многих известных семей и построить генеалогическое дерево своей семьи.

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

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

Пример 1 . Для того чтобы записать все трёхзначные числа, состоящие из цифр 1 и 2, можно воспользоваться графом (деревом) на рис. 2.6.

Рис. 2.6.
Дерево для решения задачи о записи трёхзначных чисел

Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их количество. В этом случае рассуждать нужно так: в разряде сотен может быть любая из цифр 1 и 2, в разряде десятков - те же два варианта, в разряде единиц - те же два варианта. Следовательно, число различных вариантов: 2 2 2 = 8.

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

Пример 2. Рассмотрим несколько видоизменённую классическую задачу о переправе.

На берегу реки стоит крестьянин (К) с лодкой, а рядом с ним - собака (С), лиса (Л) и гусь (Г). Крестьянин должен переправиться сам и перевезти собаку, лису и гуся на другой берег. Однако в лодку кроме крестьянина помещается либо только собака, либо только лиса, либо только гусь. Оставлять же собаку с лисой или лису с гусем без присмотра нельзя - собака представляет опасность для лисы, а лиса - для гуся. Как крестьянин должен организовать переправу?

Для решения этой задачи составим граф, вершинами которого будут исходное размещение персонажей на берегу реки, а также всевозможные промежуточные состояния, достигаемые из предыдущих за один шаг переправы. Каждую вершину-состояние переправы обозначим овалом и свяжем рёбрами с состояниями, образованными из неё (рис. 2.7).

Рис. 2.7.
Граф переправы

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

На графе видно, что существует два решения этой задачи. Приведём соответствующий одному из них план переправы:

1. крестьянин перевозит лису;
2. крестьянин возвращается;
3. крестьянин перевозит собаку;
4. крестьянин возвращается с лисой;
5. крестьянин перевозит гуся;
6. крестьянин возвращается;
7. крестьянин перевозит лису.

Пример 3 . Рассмотрим следующую игру: сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причём за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Выясним, кто выигрывает при правильной игре - первый (I) или второй (II) игрок.

Игрок I может убрать одну спичку (в этом случае их останется 4) или сразу 2 (в этом случае их останется 3).

Если игрок I оставил 4 спички, игрок II может своим ходом оставить 3 или 2 спички. Если же после хода первого игрока осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну.

Если после игрока II осталось 3 или 2 спички, то игрок I в каждой из этих ситуаций имеет шанс на выигрыш.

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

На рис. 2.8 представлен граф, называемый деревом игры; на нём отражены все возможные варианты, в том числе ошибочные (проигрышные) ходы игроков.

Рис. 2.8.
Дерево игры

Самое главное

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

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

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

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

Вопросы и задания

1. Какие информационные модели относят к графическим?
2. Приведите примеры графических информационных моделей, с которыми вы имеете дело:
   • а) при изучении других предметов;
   • б) в повседневной жизни.
3. Что такое граф? Что является вершинами и рёбрами графа на рис. 2.5? Приведите примеры цепей и циклов, имеющихся в этом графе. Определите, какие два пункта наиболее удалены друг от друга (два пункта считаются самыми удалёнными, если длина кратчайшего пути между ними больше, чем длина кратчайшего пути между любыми другими двумя пунктами). Укажите длину кратчайшего пути между этими пунктами.
4. Приведите пример системы, модель которой можно представить в форме графа. Изобразите соответствующий граф.
5. Грунтовая дорога проходит последовательно через населённые пункты А, В, С и D. При этом длина грунтовой дороги между А и В равна 40 км, между В и С - 25 км, и между С и D - 10 км. Между А и D дороги нет. Между Л и С построили новое асфальтовое шоссе длиной 30 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге - 20 км/ч, по шоссе - 30 км/ч.
6. Составьте семантическую сеть по русской народной сказке «Колобок».
7. Что такое дерево? Моделями каких систем могут служить деревья? Приведите пример такой системы.
8. Сколько трёхзначных чисел можно записать с помощью цифр 2, 4, 6 и 8 при условии, что в записи числа не должно быть одинаковых цифр?
9. Сколько существует трёхзначных чисел, все цифры которых различны?
10. Для составления цепочек используются бусины, помеченные буквами: А, Б, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором - любая гласная, если первая буква гласная, и любая согласная, если первая согласная. На третьем месте - одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?
11. Два игрока играют в следующую игру. Перед ними лежит куча из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

4.8 Графические информационные модели.

Графическая информационная модель – это наглядный способ представления объектов и процессов в виде графических изображений. К ним относятся: чертежи, графики, диаграммы, образные модели, схемы (карты, графы, блок-схемы).

Графические (геометрические) информационные модели передают внешние признаки объекта - размеры, форму, цвет, расположение. В графических информационных моделях для наглядного отобра­жения объектов используются условные графические изображения (образные элементы). Часто графические модели дополняются числами, символами и текстами (знаковыми элементами). В этом случае их называют смешанными моделями.

Образные модели представляют собой зрительные образы объектов, зафиксированные на каком-либо носителе информации (бумаге, фото- и кинопленке и др.). К ним относятся рисунки, фотографии.

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

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

Карта описывает конкретную местность, которая является для нее объектом моделирования. Это уменьшенное обобщённое изображение поверхности Земли на плоскости в той или иной системе условных обозначений.

Карта создается с определенными целями для определения:

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

Чертеж – точная геометрическая копия реального объекта. Чертёж - условное графическое изображение предмета с точным соотношением его размеров, получаемое методом проецирования. Чертёж содержит изображения, размерные числа, текст. Изображения дают представления о геометрической форме объекта, числа - о величине объекта и его частей, надписи - о названии, масштабе, в котором выполнены изображения. Чертежи создаются конструкторами, проектировщиками, они должны быть очень точным, т.к. на них указываются все необходимые размеры реального объекта. Существует масса различных компьютерных сред для создания конструкторских чертежей: Автокад, Адем, Компас, 3D MАХ - для трехмерного моделирования и т.д.

Графики и диаграммы - это информационные модели, которые в наглядной форме представляют числовые и статистические данные.

График - линия, дающая наглядное представление о характере зависимости одной величины (например, пути) от другой (например, времени). График – отображение и визуализация различных процессов (природных, экономических, общественных и технических). График позволяет отслеживать динамику изменения дан­ных.

Диаграмма - графическое изображение, дающее наглядное пред­ставление о соотношении каких-либо величин или нескольких зна­чений одной величины, об изменении их значений. Более подробно типы диаграмм и способы их построения будут рассмотрены при из­учении электронных таблиц.

Отдельное место среди графических моделей занимают графы.

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

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

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

Одинаковые, но по-разному нарисованные графы, называют изоморфными . У изоморфных графов соединены одни и те же вершины.

Степенью вершины графа называется количество выходящих из нее ребер. Вершина, имеющая четную степень, называется четной вершиной , Вершина, имеющая нечетную степень, называется нечетной вершиной. На рисунке вершины A, B, D – чётные. Их степень равна 2. Вершины С, Е – нечётные. Их степень равна 3.

С понятием степени вершины связана одна из основных теорем теории графов – теорема о чётности числа нечетных вершин.

Теорема : Любой граф содержит четное число нечетных вершин.

Для иллюстрации рассмотрим задачу.

В городе Маленьком 5 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с 3-мя другими?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 3 провода, т.е. степень каждой вершины нашего графа – 3. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца и при суммировании степеней каждый провод взят 2 раза). (3*5)/2=15/2=7,5

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

Ответ. Соединить телефоны таким образом невозможно.
Есть еще одно важное понятие, относящееся к графам – понятие связности. Граф называется связным , если любые две его вершины можно соединить путем , т.е. непрерывной последовательностью ребер. Существует целый ряд задач, решение которых основано на понятии связности графа. Граф на рисунке ниже имеет три компоненты связности (состоит из трёх отдельных частей).

Вершина, не имеющая рёбер, называется изолированной вершиной и составляет отдельную компоненту связности. Вершина, имеющая только одно ребро, называется концевой или висячей .

Путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза, называется цепью (1) . Цепь, начальная и конечная вершины которой совпадают, называется циклом (2). Дерево (иерархия ) – это граф, в котором нет циклов (3), т. е. в нём нельзя из не­которой вершины пройти по нескольким различным рёбрам и вер­нуться в ту же вершину. Отличительной особенностью дерева явля­ется то, что между любыми двумя его вершинами существует един­ственный путь.

(1)
(2)
(3)

Всякая иерархическая система может быть представлена с по­мощью дерева. У дерева выделяется одна главная вершина, называе­мая его корнем. Каждая вершина дерева (кроме корня) имеет только одного предка, обозначенный им объект входит в один класс1 высше­го уровня. Любая вершина дерева может порождать несколько по­томков - вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один-ко-многим». Вершины, не име­ющие порождённых вершин, называются листьями.

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

Граф с циклом называется сетью. Если героев некоторого литера­турного произведения представить вершинами графа, а существую­щие между ними связи изобразить рёбрами, то мы получим граф, на­зываемый семантической сетью.

4.10 Использование графов при решении задач
Пример 1. Для того чтобы записать все трёхзначные числа, состо­ящие из цифр 1 и 2, можно воспользоваться графом (деревом)

Дерево можно не строить, если не требуется выписывать все воз­можные варианты, а нужно просто указать их количество. В этом случае рассуждать нужно так: в разряде сотен может быть любая из цифр 1 и 2, в разряде десятков - те же два варианта, в разряде еди­ниц - те же два варианта. Следовательно, число различных вариан­тов: 2 2 2 = 8.

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

Пример 2. Рассмотрим несколько видоизменённую классическую задачу о переправе.

На берегу реки стоит крестьянин (К) с лодкой, а рядом с ним - собака (С), лиса (Л) и гусь (Г). Крестьянин должен переправиться сам и перевезти собаку, лису и гуся на другой берег. Однако в лодку кроме крестьянина помещается либо только собака, либо только лиса, либо только гусь. Оставлять же собаку с лисой или лису с гу­сем без присмотра нельзя - собака представляет опасность для лисы, а лиса - для гуся. Как крестьянин должен организовать пе­реправу?

Для решения этой задачи составим граф, вершинами которого бу­дут исходное размещение персонажей на берегу реки, а также всевоз­можные промежуточные состояния, достигаемые из предыдущих за один шаг переправы. Каждую вершину-состояние переправы обозна­чим овалом и свяжем рёбрами с состояниями, образованными из неё. Недопустимые по условию задачи состояния выделены пунк­тирной линией; они исключаются из дальнейшего рассмотрения. Начальное и конечное состояния переправы выделены жирной ли­нией.

На графе видно, что существует два решения этой задачи. При­ведём соответствующий одному из них план переправы:

1. 
   крестьянин перевозит лису;
2. 
   крестьянин возвращается;
3. 
   крестьянин перевозит собаку;
4. 
   крестьянин возвращается с лисой;
5. 
   крестьянин перевозит гуся;
6. 
   крестьянин возвращается;
7. 
   крестьянин перевозит лису.

Игрок I может убрать одну спичку (в этом случае их останется 4) или сразу 2 (в этом случае их останется 3).

Если игрок I оставил 4 спички, игрок II может своим ходом оста­вить 3 или 2 спички. Если же после хода первого игрока осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну.

Если после игрока II осталось 3 или 2 спички, то игрок I в каждой из этих ситуаций имеет шанс на выигрыш.

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

На рис. 2.8 представлен граф, называемый деревом игры; на нём отражены все возможные варианты, в том числе ошибочные (проиг­рышные) ходы игроков.

Контрольные вопросы.

1. 
   Какие информационные модели относят к графическим?
2. 
   Приведите примеры графических информационных моделей, с которыми вы имеете дело:

1. 
   Что такое граф? Что является вершинами и рёбрами графа? Укажите на собственном графе-примере.
2. 
   Какой граф называют ориентированным? Взвешенным?
3. 
   Какие графы называют изоморфными?
4. 
   Что такое степень вершины? Укажите степени вершин в вашем графе.
5. 
   Сформулируйте теорему о чётности числа нечетных вершин.
6. 
   Какой граф называют связным? Изобразите граф с двумя компонентами связности.
7. 
   Какую вершину называют изолированной? Висячей? Укажите на собственном примере – графе.
8. 
   Что такое путь? Цепь? Цикл? Приведите примеры цепей и циклов, имеющихся в вашем графе.
9. 
   Что такое дерево? Моделями каких систем могут служить де­ревья? Приведите пример такой системы.
10. 
    Составьте семантическую сеть по русской народной сказке «Ко­лобок».