МОДЕЛИ ЗНАНИЙ НА ГРАФАХ
ВАРИАНТ № 1
Изобразите в виде графа взаимосвязи между персонажами и различными предметами из сказки про Царевну-Лягушку.
Иван Царевич пустил стрелу.
Стрела прилетела к лягушке.
Иван Царевич нашел лягушку.
Лягушка сбросила лягушачью кожу.
Лягушка превратилась в Василису Премудрую.
Иван Царевич сжег лягушачью кожу.
Василиса Премудрая превратилась в лебедя.
Лебедь улетела к Кащею Бессмертному.
Баба Яга указала дорогу Ивану Царевичу.
Иван Царевич нашел Кащея Бессмертного.
Про мистера Форса:
Широкоплечие мужчины
Поют, садясь за руль машины.
Мужчины с узкими плечами,
Садясь за руль, молчат, как камень.
Те, кто за руль садятся с пеньем,
Не отличаются терпеньем.
Те, кто в машине молчаливы,
Бывают очень терпеливы.
Терпенье тем дано с избытком,
Кто чинит домики улиткам.
Чтоб домик починить улитке,
Клей варят на электроплитке.
Форс не выносит запах клея,
Он сразу падает, бледнея.
Прошу ответить на вопрос:
Широкоплеч ли мистер Форс?
Представьте в виде графа связи в следующих предложениях и придумайте предложение имеющее такую же семантическую структуру:
Однажды в студёную зимнюю пору я из лесу вышел.
Отплякиваясь от сурых пляк, каждый хамсик шмыряет на глын по пять гнусиков.
Глокая куздра штепо кудланула бокра и кудлачит мохрястенького бокренка.
^ МОДЕЛИ ЗНАНИЙ НА ГРАФАХ
ВАРИАНТ № 2
Изобразите в виде графа взаимосвязи между персонажами и различными предметами из сказки про Красную Шапочку.
Мама приготовила пирожок и горшочек с маслом.
Красная шапочка взяла пирожок и горшочек с маслом.
Красная Шапочка пошла в лес.
Красная Шапочка встретила волка.
Волк побежал к бабушке.
Волк съел бабушку.
Красная шапочка пришла к бабушке.
Волк съел Красную Шапочку.
Охотники убили волка.
Охотники освободили бабушку и Красную Шапочку.
Хвост Барбоса:
Собаки с рыжими хвостами
Себе овсянку варят сами.
Тем, чьи хвосты стального цвета,
Не позволяют делать это.
Кто варит сам себе овсянку,
Гулять выходит спозаранку.
Все, кто гулять выходят рано,
Не терпят фальши и обмана.
Вид добродушный у Барбоса,
Но на сорок он смотрит косо.
Он видит: норовят сороки
У воробьев списать уроки!
Скажите – проще нет вопроса! –
Какого цвета хвост Барбоса?
Представьте в виде графа связи в следующих предложениях и придумайте предложение имеющее такую же семантическую структуру:
На международный женский день 8 марта Маша получила в подарок букет розовых и желтых тюльпанов и большого плюшевого мишку.
Мряка друсит пусики и на друську одного пусика тратит полдолготика.
Сяпала Калуша по напушке и увазила бутявку, и волит: «Калушата, калушаточки! Бутявка!»
^ МОДЕЛИ ЗНАНИЙ НА ГРАФАХ
ВАРИАНТ № 3
Изобразите в виде графа взаимосвязи между персонажами и различными предметами из сказки про Царевну-Лягушку.
Иван Царевич пустил стрелу.
Стрела прилетела к лягушке.
Иван Царевич нашел лягушку.
Лягушка сбросила лягушачью кожу.
Лягушка превратилась в Василису Премудрую.
Иван Царевич сжег лягушачью кожу.
Василиса Премудрая превратилась в лебедя.
Лебедь улетела к Кащею Бессмертному.
Баба Яга указала дорогу Ивану Царевичу.
Иван Царевич нашел Кащея Бессмертного.
Про мистера Форса:
Широкоплечие мужчины
Поют, садясь за руль машины.
Мужчины с узкими плечами,
Садясь за руль, молчат, как камень.
Те, кто за руль садятся с пеньем,
Не отличаются терпеньем.
Те, кто в машине молчаливы,
Бывают очень терпеливы.
Терпенье тем дано с избытком,
Кто чинит домики улиткам.
Чтоб домик починить улитке,
Клей варят на электроплитке.
Форс не выносит запах клея,
Он сразу падает, бледнея.
Прошу ответить на вопрос:
Широкоплеч ли мистер Форс?
Представьте в виде графа связи в следующих предложениях и придумайте предложение имеющее такую же семантическую структуру:
Четыре маленьких чумазеньких чертенка чертили черными чернилами чертеж черепа человека чрезвычайно четко на чердаке в четверг.
Глокая куздра штепо кудланула бокра и кудлачит мохрястенького бокренка.
Сяпала Калуша по напушке и увазила бутявку, и волит: «Калушата, калушаточки! Бутявка!»
^ МОДЕЛИ ЗНАНИЙ НА ГРАФАХ
ВАРИАНТ № 4
Изобразите в виде графа взаимосвязи между персонажами и различными предметами из сказки про Красную Шапочку.
Мама приготовила пирожок и горшочек с маслом.
Красная шапочка взяла пирожок и горшочек с маслом.
Красная Шапочка пошла в лес.
Красная Шапочка встретила волка.
Волк побежал к бабушке.
Волк съел бабушку.
Красная шапочка пришла к бабушке.
Волк съел Красную Шапочку.
Охотники убили волка.
Охотники освободили бабушку и Красную Шапочку.
Хвост Барбоса:
Собаки с рыжими хвостами
Себе овсянку варят сами.
Тем, чьи хвосты стального цвета,
Не позволяют делать это.
Кто варит сам себе овсянку,
Гулять выходит спозаранку.
Все, кто гулять выходят рано,
Не терпят фальши и обмана.
Вид добродушный у Барбоса,
Но на сорок он смотрит косо.
Он видит: норовят сороки
У воробьев списать уроки!
Скажите – проще нет вопроса! –
Какого цвета хвост Барбоса?
Представьте в виде графа связи в следующих предложениях и придумайте предложение имеющее такую же семантическую структуру:
Четыре маленьких чумазеньких чертенка чертили черными чернилами чертеж черепа человека чрезвычайно четко на чердаке в четверг.
Мряка 7 раз фрякнула Бряку марфуфочкой по чему попало, а Бряка фрякнул Мряку той же марфуфочкой по чему попало 9 раз.
Выстребаны обстряхнуться и дутой чернушенькой объятно хлюпнут по маргазам.
§ 13. Схемы
ИНФОРМАТИКА. 6 КЛАССА. БОСОВА Л.Л. ОГЛАВЛЕНИЕ
Многообразие схем
Ключевые слова:
• схема
• граф
• сеть
• дерево
В повседневной жизни нас окружает множество разнообразных схем: схемы проезда, схемы дорожных развязок, схема метрополитена, схема расположения мест в зрительном зале, схема движения пригородных электропоездов и многие другие.
Схема — это представление некоторого объекта в общих, главных чертах с помощью условных обозначений. С помощью схемы может быть представлен и внешний вид объекта, и его структура.
Например, внешний вид зрительного зала представлен на схеме, изображённой на рис. 40. Представление о внешнем виде квартиры можно получить по схеме на рис. 41.
Уменьшенное обобщённое изображение поверхности Земли на плоскости в той или иной системе условных обозначений даёт нам географическая карта. На карте (рис. 42) изображён внешний вид территории северо-восточной части Центральной России. На ней показаны древние русские города, образующие знаменитое на весь мир Золотое кольцо.
Схемы на рис. 40-42 являются информационными моделями внешнего вида соответствующих объектов. Они предназначены для того, чтобы у человека была возможность, например, выбрать подходящее место в зрительном зале, оценить размеры и расположение комнат будущей квартиры, разработать маршрут путешествия по Золотому кольцу и т. д. Для этих моделей большое значение имеет соблюдение масштаба. Для карты также имеет значение соблюдение ориентации по сторонам света. Но, несмотря на точность рассмотренных информационных моделей, более подробные сведения об изображённых на них объектах (местах в зале, домах, дорогах, городах) из них получить нельзя.
Схема как информационная модель не претендует на полноту предоставления информации об объекте. С помощью особых приёмов и графических обозначений на ней более рельефно выделяется один или несколько признаков рассматриваемого объекта.
Например, туристический маршрут «Золотое кольцо России» более образно запечатлен на схеме на рис. 43.
Здесь не полностью выдержан масштаб, но зато акцентировано внимание на городах, образующих Золотое кольцо, и их достопримечательностях.
Информационные модели на графах
Наглядным средством представления состава и структуры системы является граф. Граф состоит из вершин, связанных линиями. Если линия направленная (со стрелкой), то она называется дугой; линия ненаправленная (без стрелки) называется ребром. Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей. Вершины могут изображаться кругами, овалами, точками, прямоугольниками и т. д.
Если объекты некоторой системы изобразить вершинами, а связи между ними — линиями, то мы получим информационную модель рассматриваемой системы в форме графа.
Ранее мы рассматривали графы — схемы отношений, отражающие имеющиеся связи между объектами.
Например, граф, отражающий отношение «переписываются» между объектами класса «дети», может выглядеть, как показано на рис. 44.
Отношение «переписываются» («пишут письма друг другу») является двухсторонним (симметричным). Поэтому соответствующие вершины соединены линиями без стрелок (рёбрами).
Граф называется неориентированным, если его вершины соединены ребрами.
Путь по вершинам и рёбрам графа, включающий любое ребро графа не более одного раза, называется цепью.
Пример цепи: Юра — Аня — Витя — Коля (см. рис. 44).
Цепь, начальная и конечная вершины которой совпадают, называется циклом.
Пример цикла: Аня — Коля — Витя — Аня.
Иначе выглядит граф, отражающий отношение «пишет письма» между теми же объектами класса «дети». Линии со стрелками (дуги) придают ему совершенно иной смысл (рис. 45).
Граф называется ориентированным, если его вершины соединены дугами.
Приведите примеры цепи и цикла в графе на рис. 45.
Граф называется взвешенным, если его вершины или рёбра (дуги) характеризуются некоторой дополнительной информацией — весом вершины или ребра (дуги).
На рисунке 46 информация о городах Золотого кольца представлена взвешенным графом: веса его вершин — года основания городов, веса рёбер — расстояния в километрах между городами.
Назовите пути и циклы в графе на рис. 46.
Граф с циклами называется сетью.
На рисунке 47 в виде графа представлена информационная модель сказки про Царевну-лягушку.
Вершины этого графа — персонажи и предметы из сказки, дуги — связи между ними. В отличие от предыдущих примеров,
здесь все связи различны. Поэтому они подписываются рядом с соответствующими дугами.
Такой граф называется семантической сетью. Считается, что любую информацию можно представить в виде семантической сети, на которой будут отражены объекты (понятия) и связи (отношения) между ними.
Деревья
Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчинённости, называются иерархическими системами (системами с иерархической структурой).
Например, иерархическую структуру имеет школа, потому что в ней установлены следующие отношения подчинённости: директор — заместители директора — учителя — ученики.
Иерархическую структуру имеют системы, элементы которых связаны отношением «входит в состав».
На рисунке 48 изображён граф иерархической системы, представляющий состав прикладного программного обеспечения (ПО) компьютера.
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.
Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка — обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один ко многим». Вершины, не имеющие порождённых вершин, называются листьями.
Древовидными являются схемы отношений «является разновидностью», используемые для наглядного представления классификации объектов (рис. 49).
Иерархию легко изобразить «лесенкой» — в виде многоуровневого списка. Объекты одного уровня иерархии располагаются на одном уровне в списке. Чем ниже уровень иерархии, тем правее находится соответствующий уровень списка:
Рептилии
Черепахи
Крокодилы
Клювоголовые
Чешуйчатые
Ящерицы
Змеи
По иерархическому принципу организована система хранения файлов во внешней памяти компьютера. Операционная система позволяет получить на экране компьютера изображение файловой системы в виде дерева (рис. 50).
Родственные связи между членами семьи удобно изображать с помощью схемы, называемой генеалогическим или родословным деревом. Изображать генеалогическое дерево можно в любом направлении — это дело вкуса разработчика модели.
Использование графов при решении задач
Графы удобно использовать при решении некоторых классов задач.
Задача 1
Сколькими способами можно рассадить в ряд на три стула трёх учеников? Выписать все возможные случаи.
Решение этой задачи удобнее всего представить в виде дерева. За его корневую вершину возьмём произвольную точку плоскости О.
На первый стул можно посадить любого из трёх учеников — обозначим их А, В л С. На схеме это соответствует трём ветвям, исходящим из точки О (рис. 51).?
Посадив на первый стул ученика А, на второй стул можно посадить ученика В или С. Если же на первый стул сядет ученик В, то на второй можно посадить А или С. Если на первый стул сядет С, то на второй можно будет посадить А или В. Это соответствует на схеме двум ветвям, исходящим из каждой вершины первого уровня (рис. 52).
Очевидно, что третий стул в каждом случае займёт оставшийся ученик. Это соответствует одной ветви дерева, которая «вырастает» на каждой из предыдущих ветвей (рис. 53).
Выпишем все пути от вершин первого уровня к вершинам третьего уровня: А-В-Су А-С-В, В-А-С, В-С-А, С-А-Б, С-В-А. Каждый из выписанных путей определяет один из вариантов рассаживания учеников на стулья. Так как других путей нет, то искомое число способов — 6.
Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их число. В этом случае рассуждать нужно так: на первый стул можно усадить одного из трёх человек, на второй — одного из двух оставшихся, на третий — одного оставшегося: 3-2-1 = 6.?
Задача 2
Чтобы принести Царю-батюшке молодильные яблоки, должен Иван-царевич найти единственный верный путь к волшебному саду. Встретил Иван-царевич на развилке трёх дорог старого ворона и вот какие советы от него услышал:
1) иди сейчас по правой тропинке;
2) на следующей развилке не выбирай правую тропинку;
3) на третьей развилке не ходи по левой тропинке.
Пролетавший мимо голубь шепнул Ивану-царевичу, что только один совет ворона верный и что обязательно надо пройти по тропинкам разных направлений. Наш герой выполнил задание и попал в волшебный сад. Каким маршрутом он воспользовался?
Обозначим левую, среднюю и правую тропинки соответственно Л, С и П. Возможные маршруты представим в виде графа. При этом подсказки ворона отметим более «жирными» рёбрами. Так как только один совет ворона верен, то на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро. Этот маршрут обозначен дополнительной пунктирной линией (рис. 54).
Вопросы и задания
1. Приведите 2-3 примера схем, с которыми вы сталкиваетесь в повседневной жизни. Информационными моделями каких объектов являются эти схемы?
2. На каждом этаже в вашей школе должен быть план эвакуации при пожаре. Найдите и изучите его. Какие объекты представлены на этой схеме?
3. В каких сферах деятельности невозможно обойтись без карт — информационных моделей поверхности Земли?
4. Определите сказку, для которой следующий граф определяет отношения между персонажами.
5. С разных сторон на холм поднимаются три тропинки и сходятся на вершине. Перечислите множество маршрутов, по которым можно подняться на холм и спуститься с него. Решите ту же задачу, если вверх и вниз надо идти по разным тропинкам.
6. Сколько трёхзначных чисел можно записать с помощью цифр 1, 3, 5 и 7 при условии, что в записи числа не должно быть одинаковых цифр?
§ 12. Графики и диаграммы
§ 13. Схемы
§ 14. Что такое алгоритм
1
Модели знаний на графах учитель информатики 1 категории МОУ «Центр образования 11» Лобанов А.А.
2
Определить сказку КРДБ ЯЗМ снесла бил, не разбилбила, не разбила уронила и разбила Курочка Ряба (КР) снесла яичко золотое (ЯЗ). Дед (Д) бил, не разбил. Баба (Б) била, не разбила, а мышка (М) уронила и разбила.
3
Семантические сети Семантическая сеть- модель знаний в форме графа. Семантическая сеть- модель знаний в форме графа. Пример 1. Описать в форме семантической сети информацию, заключённую в следующем тексте: «Петух Петя является птицей и он умеет кукарекать. Попугай Кеша живёт у моего одноклассника Васи. Попугай птица. Птица являются животными. Медведь – это животное, имеющее тёмный цвет». «Петух Петя является птицей и он умеет кукарекать. Попугай Кеша живёт у моего одноклассника Васи. Попугай птица. Птица являются животными. Медведь – это животное, имеющее тёмный цвет».
4
Пример 1 Во всех фразах есть объекты, понятия и связи между ними. В Вершинах будем изображать объекты и понятия, а дуги, соединяющие их будут обозначать отношения. Во всех фразах есть объекты, понятия и связи между ними. В Вершинах будем изображать объекты и понятия, а дуги, соединяющие их будут обозначать отношения. Изобразим первую фразу : Изобразим первую фразу : Петух Петя является птицей и он умеет кукарекать. Петух Птица Кукарекать Петя умеет является зовут Объект «петух» вступает в отношение с объектами и понятиями «Петя», «птица», «кукарекать»
5
Пример 1 Изобразим вторую фразу : Изобразим вторую фразу : Попугай Кеша живёт у моего одноклассника Васи Попугай Одноклассник Вася Кеша зовут живёт у зовут
6
Пример 1 Третья фраза позволяет объединить два графа, построенных по предыдущим фразам Третья фраза позволяет объединить два графа, построенных по предыдущим фразам ПопугайОдноклассник Вася Кеша зовут живёт у зовут Петух Птица Кукарекать Петя умеет является зовут Четвёртая и пятая фразы – расширяют семантическую сеть. Четвёртая и пятая фразы – расширяют семантическую сеть. Животное Медведь Тёмный Птица
7
Семантические сети Семантическая сеть наглядно отражает взаимосвязь свойств входящих в неё объектов. Семантическая сеть наглядно отражает взаимосвязь свойств входящих в неё объектов. По семантической связи ответь на вопросы: По семантической связи ответь на вопросы: 1) Какие общие свойства есть у Пушинки и Джонни? 2) Определите возраст Мурки Передвигаются на 4х ногах, вскармливают детей молоком, дышат воздухом, имеют позвоночник. Передвигаются на 4х ногах, вскармливают детей молоком, дышат воздухом, имеют позвоночник. 3 года
8
Пример 2 Построить семантическую сеть, отражающую следующую информацию: Построить семантическую сеть, отражающую следующую информацию: «У мельника было три сына. Мельник оставил наследство. Оно состояло из мельницы, осла и кота. Старший сын взял мельницу. Средний взял осла. Младший взял кота.» мельник наследство сына оставил мельница осёл кот состояло старший средний младший было три взял
9
Пример 3 Построить семантическую сеть, отражающую следующую информацию: Построить семантическую сеть, отражающую следующую информацию: Мария работает в дневную смену. Сергей работает в вечернюю смену. Борис работает в вечернюю смену Валентина работает в вечернюю смену. Два служащих знают друг друга, если они работают в одну смену. Определить: 1) Знает ли Сергей Бориса 2) Кого знает Валентина 3)Кого знает Мария?
10
Пример 3 Составим семантическую сеть Составим семантическую сеть Мария Борис Сергей Валентина дневная сменаВечерняя смена работает
11
ДОМАШНЕЕ ЗАДАНИЕ Представить в виде семантической сети систему высших органов власти российской Федерации. Представить в виде семантической сети систему высших органов власти российской Федерации. Изобразите в виде графа взаимосвязи между персонажами и различными предметами из сказки про Красную Шапочку. Изобразите в виде графа взаимосвязи между персонажами и различными предметами из сказки про Красную Шапочку.