Что такое дерево моделями каких систем могут служить деревья приведите пример такой системы кратко
Обновлено: 05.07.2024
Дерево — это граф, в котором нет циклов, т. е. в нём нельзя из некоторой вершины пройти по нескольким различным рёбрам и вернуться в ту же вершину. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь.
Всякая иерархическая система может быть представлена с помощью дерева.
У дерева выделяется одна главная вершина, называемая его корнем. Каждая вершина дерева (кроме корня) имеет только одного предка, обозначенный предком объект входит в один класс (класс — множество объектов, обладающих общими признаками.) высшего уровня.
Родственные связи между членами семьи удобно изображать с помощью графа, называемого генеалогическим или родословным деревом.
В графических информационных моделях для наглядного отображения объектов используются условные графические изображения (образные элементы), зачастую дополняемые числами, символами и текстами (знаковыми элементами). Примерами графических моделей могут служить всевозможные схемы, карты, чертежи, графики и диаграммы.
Схема — это представление некоторого объекта в общих, главных чертах с помощью условных обозначений. С помощью схем может быть представлен и внешний вид объекта, и его структура. Схема как информационная модель не претендует на полноту предоставления информации об объекте. С помощью особых приёмов и графических обозначений на ней более рельефно выделяется один или не сколько признаков рассматриваемого объекта. Примеры схем приведены на рис. 1.5.
Уменьшенное обобщённое изображение поверхности Земли на плоскости в той или иной системе условных обозначений даёт нам географическая карта.
Чертёж — условное графическое изображение предмета с точным соотношением его размеров, получаемое методом проецирования. Чертёж содержит изображения, размерные числа, текст. Изображения дают представления о геометрической форме объекта, числа — о величине объекта и его частей, надписи — о названии, масштабе, в котором выполнены изображения.
График — графическое изображение, дающее наглядное представление о характере зависимости одной величины (например, пути) от другой (например, времени). График позволяет отслеживать динами ку изменения данных.
Диаграмма — графическое изображение, дающее наглядное представление о соотношении каких-либо величин или нескольких значений одной величины, об изменении их значений. Более подробно типы диаграмм и способы их построения будут рассмотрены при изучении электронных таблиц.
Если объекты некоторой системы изобразить вершинами, а связи между ними — линиями (рёбрами), то мы получим информационную модель рассматриваемой системы в форме графа. Вершины графа могут изображаться кругами, овалами, точками, прямоугольниками и т. д.
Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер.
На рис. 1.6 с помощью взвешенного графа изображены дороги между пятью населёнными пунктами А, В, С, D, Е; веса рёбер — протяжённость дорог в километрах.
Путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза, называется цепью. Цепь, начальная и конечная вершины которой совпадают, называется циклом.
Граф с циклом называется сетью. Если героев некоторого литературного произведения представить вершинами графа, а существующие между ними связи изобразить рёбрами, то мы получим граф, называемый семантической сетью.
Графы как информационные модели находят широкое применение во многих сферах нашей жизни. Например, можно существующие или вновь проектируемые дома, сооружения, кварталы изображать вершинами, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — рёбрами графа. По таким графам можно планировать оптимальные транспортные маршруты, кратчайшие объездные пути, расположение торговых точек и других объектов.
Дерево — это граф, в котором нет циклов, т. е. в нём нельзя из некоторой вершины пройти по нескольким различным рёбрам и вер нуться в ту же вершину. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь.
Родственные связи между членами семьи удобно изображать с помощью графа, называемого генеалогическим или родословным деревом.
Пример 1. Для того чтобы записать все трёхзначные числа, состоящие из цифр 1 и 2, можно воспользоваться графом (деревом) на рис. 1.7.
Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их количество. В этом случае рассуждать нужно так: в разряде сотен может быть любая из цифр 1 и 2, в разряде десятков — те же два варианта, в разряде единиц — те же два варианта. Следовательно, число различных вариантов: 2*2*2 = 8.
В общем случае, если известно количество возможных вариантов выбора на каждом шаге построения графа, то для вычисления общего количества вариантов нужно все эти числа перемножить.
Для решения этой задачи составим граф, вершинами которого будут исходное размещение персонажей на берегу реки, а также всевозможные промежуточные состояния, достигаемые из предыдущих за один шаг переправы. Каждую вершину-состояние переправы обозначим овалом и свяжем рёбрами с состояниями, образованными из неё (рис. 1.8),
Недопустимые по условию задачи состояния выделены пунктирной линией; они исключаются из дальнейшего рассмотрения. Начальное и конечное состояния переправы выделены жирной линией.
На графе видно, что существуют два решения этой задачи. Приведём соответствующий одному из них план переправы:
Свидетельство и скидка на обучение каждому участнику
Зарегистрироваться 15–17 марта 2022 г.
Описание презентации по отдельным слайдам:
ГРАФИЧЕСКИЕ ИНФОРМАЦИОННЫЕ МОДЕЛИ МОДЕЛИРОВАНИЕ И ФОРМАЛИЗАЦИЯ
Ключевые слова схема карта чертёж график диаграмма граф сеть дерево
Многообразие графических информационных моделей Схема Карта Чертёж Диаграмма Графическая модель График Граф
Схемы в физике Схемы в истории Схемы в биологии Р ♀ ♂ генотип гаметы F1
Географическая карта Евразии
График описания движения
Диаграмма Средняя разница между минимальной и максимальной ставкой (разы)
Графы Граф состоит из вершин, связанных линиями - рёбрами. Вершины графа изображаются кругами, овалами, точками, прямоугольниками и т. д. Объекты представляются как вершины графа, а связи – как его рёбра.
Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин или рёбер. Взвешенный граф Протяжённость дорог в километрах
Сеть и дерево Цепь – путь по вершинам и рёбрам граф, в который любое ребро графа входит не более одного раза. Дерево – это граф, в котором нет циклов Цикл - цепь, начальная и конечная вершины которой совпадают. Сеть - граф с циклом.
Генеалогическое древо Родословная А. В. Суворова
Дерево для решения задачи Использование графов при решении задач Сколько существует трёхзначных чисел, состоящих из цифр 1 и 2?
С Л Г К Граф задачи о переправе СЛГ || К ЛГ || КС СГ || КЛ СЛ || КГ КСГ || Л Г || КСЛ С || КГЛ КГ || СЛ КЛГ || С КЛС || Г КС || ЛГ ЛГ || КС Л || КСГ ЛС || КГ КЛ || СГ || КЛСГ КСЛГ ||
Самое главное В графических информационных моделях для наглядного отображения объектов используются условные графические изображения, дополняемые числами, символами и текстами: схемы, карты, чертежи, графики и диаграммы, графы. Граф состоит из вершин, связанных линиями - рёбрами. У взвешенного графа вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин (рёбер). Цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза. Цикл - цепь, начальная и конечная вершины которой совпадают. Сеть - граф с циклом. Дерево - граф иерархической системы. Между любыми двумя вершинами дерева существует единственный путь.
Схема Карта Чертёж Диаграмма График Опорный конспект Графические информационные модели используются для наглядного отображения объектов. Графическая информационная модель
Ответы (решебник) к учебнику по Информатике — 9 класс, параграф 1.3 — Босова Л.Л., Босова А.Ю. , задания 1-12
Глава 1. МОДЕЛИРОВАНИЕ И ФОРМАЛИЗАЦИЯ
2. Какие информационные модели относят к графическим?
К графическим информационным моделям являются простейшим видом моделей, которые передают внешние признаки объекты — размеры, форму, цвет.
3. Приведите примеры графических информационных моделей, с которыми вы имеете дело:
а) при изучении других предметов;
б) в повседневной жизни.
а) Электрические схемы по физике, схема Куликовской битвы по истории, политическая карта мира, чертежи по черчению.
б) График погоды на неделю, карта.
4. Что такое граф? Что является вершинами и рёбрами графа на рис. 1.6? Приведите примеры цепей и циклов, имеющихся в этом графе. Определите, какие два пункта наиболее удалены друг от друга (два пункта считаются самыми удалёнными, если длина кратчайшего пути между ними больше, чем длина кратчайшего пути между любыми другими двумя пунктами). Укажите длину кратчайшего пути между этими пунктами.
Граф — это объект изображенный с помощью вершин, а связи между ними — линиями (ребрами).
На данном рисунке вершины — города A, B, C, D, E; рёбра — дороги(линии) между ними.
Города B и D — наиболее удалены друг от друга. Длина кратчайшего пути между ними составляет 170.
5. Приведите пример системы, модель которой можно представить в форме графа. Изобразите соответствующий граф.
Пример графа: Персональный компьютер
6. Грунтовая дорога проходит последовательно через населённые пункты А, В, С и D. При этом длина грунтовой дороги между А и В равна 40 км, между В и С — 25 км, и между С и D — 10 км. Между А и D дороги нет. Между A и С построили новое асфальтовое шоссе длиной 30 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге — 20 км/ч, по шоссе — 30 км/ч.
На графе черная линия — асфальтированное шоссе, а серая линия — грунтовая дорога.
По условию скорость велосипедиста по грунтовой — 20 км/ч, по шоссе — 30 км/ч.
От A до B можно добраться двумя способами: 1) 40 км по грунтовой дороге; 2) 30 по шоссе и 25 км по грунту.
Найдем время, которое может затратить велосипедист этими двумя способами(Расстояние делим на скорость).
1) 40:20 = 2 часа.
2) 25:20 = 1,25 часа по грунту, 30:30 = 1 час по шоссе, 2,25 часа займёт весь путь.
Ответ: 2 часа по грунтовой дороге в 40 км.
8. Что такое дерево? Моделями каких систем могут служить деревья? Приведите пример такой системы.
Дерево — это граф, в котором нет циклов. Все иерархические системы можно представить в виде дерева.
Пример: генеалогическое дерево.
9. Сколько трёхзначных чисел можно записать с помощью цифр 2, 4, 6 и 8 при условии, что в записи числа не должно быть одинаковых цифр?
246; 248; 264; 284; 268; 286
426; 428; 462; 468; 482; 486
624; 628; 642; 648; 682; 684
824; 826; 842; 846; 862; 864
Всего 24 числа.
10. Сколько существует трёхзначных чисел, все цифры которых различны?
Всего цифр 10: 0,1,2,3,4,5,6,7,8,9
В трёхзначном числе три места
На первое можно поставить любую из девяти цифр( 0 нельзя)- 9 способов
На второе место останется 8 цифр + 0 = 9 цифр — 9 способов
На третье место 8 цифр, — 8 способов
Всего 9·9·8=648 чисел
11. Для составления цепочек используются бусины, помеченные буквами А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором — любая гласная, если первая буква гласная, и любая согласная, если первая согласная. На третьем месте — одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?
Составляем дерево вариантов и мы получаем:
Ветки начинающиеся с A: AAC AAD AAE; AEC AED AEE.
Ветки начинающиеся с C: CBD CBE; CCD CCE; CDD CDE.
Ветки начинающиеся с E: EAC EAD; EEC EED.
Ответ: 16 вариантов
12. Два игрока играют в следующую игру. Перед ними лежит куча из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
При безошибочной игре выигрывает первый игрок. Своим первых ходом он должен взять один камень. В куче остается пять камней. Какой бы ход ни сделал второй игрок, в куче останется 4, 3 или 2 камня. Это позволяет первому игроку своим вторым ходом оставить в куче ровно один камень, его и должен будет забрать своим вторым ходом второй игрок.
Решение заданий из учебника Информатика 9 класс Босова, параграф 1.3.Графические информационные модели.
На этой странице размещен вариант решения заданий с страниц учебника по информатике за 9 класс авторов Босова. Здесь вы сможете списать решение домашнего задания или просто посмотреть ответы. ГДЗ
Литература: Учебник по Информатике, 9 класс. Автор: Босова Л.Л., Босова А.Ю. Издательство: Бином. Год: 2016, 2017
Читайте также: