Постройте граф классификации биологической системы по следующему описанию word
Цель работы: формирование навыков системного анализа, построения структурных схем и графов классификаций, знакомство с векторным редактором.
Для выполнения работы вы будете использовать векторный редактор Draw , входящий в состав Libre Office .
З апустите Libre Office с Рабочего стола, затем запустите редактор (Рисунок Draw слева внизу).
И нтерфейс векторного редактора интуитивно понятен и прост. Слева располагаются инструменты рисования, справа свойства этих инструментов, а посередине активная страница. Сначала мы выбираем нужный инструмент (эллипс, круг, прямоугольник, стрелку, линию …, в левой части на панели инструментов), затем рисуем на выбранной странице и выбираем свойства нарисованного объекта справа на панели свойств.
2 . Выберите первую страницу, кликнув на нее ЛКМ, после этого выберите любой инструмент на панели слева, например прямоугольник, и нарисуйте его. Вы можете изменить размер объекта, потянув за любой его край, его заливку (цвет), толщину и цвет его линий на панели свойств в правой части окна редактора. Также можно вставить любой текст внутри выбранного объекта. Для рисования графов используйте линии, эллипсы, прямоугольники и другие объекты. Цвет объектов графа может быть любой. По окончании работы сохраните ее в формате . pdf на Рабочем столе (Файл – экспорт в PDF ) под своим именем.
Задание 1. Постройте граф, отображающий состав и структуру мотопехотного батальона по следующему описанию.
Во главе батальона БМП стоял командир, которому подчинялись штаб и 5 рот: штабная и снабжения, минометная и три мотопехотные. Рота штабная и снабжения состояла из управления и трех взводов: штабного, связи и снабжения. В штабном взводе было четыре отделения: штабное, мотоциклистов, транспортное и разведывательное. Во взводе связи было три отделения радиосвязи и два отделения проводной связи. Во взводе снабжения было четыре отделения: материально-технического обеспечения, продовольственного снабжения, транспортное и санитарное.
Задание 2. Постройте граф классификации биологической системы по следующему описанию.
Согласно биологической классификации, выделяют три империи (надцарства): археобактерии, эукариоты и прокариоты. К империи эукариотов относятся царства грибов, растений и животных. К царству животных относятся типы членистоногих, моллюсков, иглокожих, кишечнополостных, хордовых и др. К типу хордовых относятся классы рыб, амфибий, рептилий, млекопитающих, птиц. К классу млекопитающих относятся отряды китов, ластоногих, хищных, грызунов, копытных и др. К отряду хищных относятся семейства медвежьих, енотовых, псовых, виверровых, кошачьих и др. К семейству псовых относятся роды лисиц, енотовидных собак, собак, песцов и др. К роду собак относятся виды собак домашних, волков, шакалов, койотов. К виду собак домашних относятся овчарки, спаниели, водолазы, сенбернары, доги, болонки и др.
Задание 3. Постройте граф классификации в русском языке по следующему описанию.
Предложения в русском языке классифицируются по составу, по интонации и по цели высказывания. По составу предложения делятся на нераспространенные и распространенные. Нераспространенные предложения состоят только из двух членов: подлежащего и сказуемого. Пример нераспространенного предложения: «Птицы прилетели». Распространенные предложения состоят из подлежащего, сказуемого и второстепенных членов предложения. Пример распространенного предложения: «Ранней весной прилетели первые птицы».
По интонации предложения делятся на восклицательные («Пришла весна!») и невосклицательные («Пришла весна»).
По цели высказывания предложения делятся на повествовательные, вопросительные и побудительные. Повествовательное предложение: «Мы собрали много грибов и ягод». Вопросительное предложение: «Вы собрали много грибов и ягод?». Побудительное предложение: «Собирайте грибы и ягоды!».
С помощью данного урока учащиеся узнают, что такое графы. Подробно, на примерах, описано как изображаются графы, виды графов, а также рассматривается решение задачи с использованием графов. В практической части данного урока рассматривается работа в текстовом редакторе Microsoft Word: добавление надписей, вставка фигур и построение графа, сохранение документа.
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобретя в каталоге.
Получите невероятные возможности
Конспект урока "Информационные модели на графах. Использование графов при решении задач"
На прошлых уроках мы с вами узнали об информационных моделях, которые в сжатой форме помогают представлять информацию и решать задачи.
Сделать табличную информацию более наглядной и легко доступной помогают графики и диаграммы.
График – это линия, применяемая для наглядного изображения зависимости одной какой-либо величины от другой.
Диаграмма – это чертёж, показывающий соотношение нескольких величин. В зависимости от цели можно использовать разные типы диаграмм. Например, круговые или столбчатые.
Следующий вид графических средств представления информации – схемы.
Схема – это информационная модель, в которой с помощью особых приемов и географических обозначений выделяется один или несколько признаков рассматриваемого объекта.
Есть ещё один вид графических средств – это графы.
Сегодня на уроке мы узнаем:
Какие информационные модели называются графами, для чего применяются графы, и как с помощью графов решать задачи.
Граф — это группа объектов со связями между ними.
Объекты представляются как вершины графа, а связи — это линии соединяющие вершины.
Например, все шестиклассники пользуются мобильными телефонами и многие общаются друг с другом через SMS.
В данном примере вершины графа – это отдельные ребята, а связи – это процесс «пишут друг другу SMS».
Вершины графа можно изображать по-разному. Это может быть овал либо круг, точка или прямоугольник.
Разберёмся более подробно со связями, то есть с линиями, соединяющими вершины графа.
Если линия, соединяющая вершины графа направленная, то есть со стрелкой, то она называется дугой.
То есть дугой называется направленная линия, соединяющая вершины графа.
Если линия ненаправленная, то есть, нет стрелки, то эта линия называется ребром.
Ребро – это ненаправленная линия, которая соединяет вершины графа.
Если линия выходит из некоторой вершины и входит в неё же, то эта линия называется петлёй.
Петля – это линия, которая выходит из некоторой вершины и входит в нее же
Вернёмся к примеру, с шестиклассниками. Здесь система – это ученики шестого класса в какой-то школе. Мы, объекты этой системы (т.е. отдельных ребят) изобразили вершинами, и соединили вершины ненаправленными линиями (рёбрами). Ребра в данном случае являются двухсторонними отношениями, потому что ребята пишут SMS-ки друг другу.
Мы получили информационную модель рассматриваемой системы в форме графа.
Рассмотрим виды графов.
Если вершины графа соединены рёбрами, то такой граф называется неориентированным.
Рассмотрим пример: Таня написала SMS Никите, Никита ответил Тане, Таня написала Маше, Маша ответила Тане, Никита написал Маше. Здесь ребята отвечали друг другу на смски.
Данное отношение называется цепью графа.
Цепь графа – это путь по вершинам и рёбрам графа, который включает любое ребро не меньше одного раза.
Если в цепи начальная и конечная вершины совпадают, то такая цепь называется циклом.
Например, Таня написала SMS Никите, Никита – Маше, Маша – Платону, а Платон написал Тане.
Здесь цикл – это цепь Таня – Никита – Маша – Платон – Таня.
Далее, рассмотрим следующий вид графа.
Если вершины графа соединены дугами (стрелками), то такой граф называется ориентированным.
В нашем примере цепь будет выглядеть следующим образом: Таня написала SMS Никите, Никита – Маше, Маша – Платону. То есть СМС-ки были без ответа.
Рассмотрим следующий пример:
Город Москва основан в 1147 году, город Санкт-Петербург основан в1703 году. Расстояние от Москвы до Санкт-Петербурга 713 км. Год основания города Тверь 1135 год, расстояние от Москвы до Твери 175 км. Ярославль основан в 1010 год, расстояние от Москвы до Ярославля 272 км. Город Смоленск основан в 863 году, а расстояние от Москвы до Смоленска 400 км.
Мы получили взвешенный граф.
Взвешенным называется граф, который характеризуется дополнительной информацией – весом вершины или весом ребра (дуги).
Рассмотрим следующий вид графа с циклами, то есть граф, в цепи которого начальная и конечная вершины совпадают.
Помните сказку о царе Солтане? Давайте построим граф по отрывкам из сказки.
К морю лишь подходит он,
Вот и слышит будто стон.
Бьётся лебедь средь зыбей,
Коршун носится над ней;
Но как раз стрела запела,
В шею коршуна задела —
Коршун в море кровь пролил,
Лук царевич опустил;
Смотрит: коршун в море тонет
И не птичьим криком стонет,
Лебедь около плывёт,
Злого коршуна клюёт,
И царевичу потом
Молвит русским языком…
Вот открыл царевич очи;
Отрясая грёзы ночи
И дивясь, перед собой
Видит город он большой,
Мать и сын идут ко граду.
Лишь ступили за ограду,
Пышный двор встречает их;
Все их громко величают
И царевича венчают
Княжий шапкой, и главой
Возглашают над собой…
Мы получили граф с циклами, который называется сетью. Если раньше мы рассматривали примеры, в которых связи были одинаковые (ребята писали смски), то в данном примере связи различны. Поэтому мы их подписывали.
Следующий вид графа, называется дерево.
Дерево – это граф с иерархической системой, где Иерархия – это структура распределения частей целого от высшего к низшему. А Иерархическая система – это система, части которой находятся в определённых отношениях. К отношениям иерархической системы относятся «является разновидностью», «входит в состав» и другие «отношения подчинённости».
Рассмотрим иерархическую систему фирмы, которая, например, занимается реализацией техники. Здесь будет такая система подчинённости: генеральный директор - самый главный человек и владелец фирмы, ему подчиняются директора магазинов, которые руководят работой администраторов, ну а тем, в свою очередь, подчиняются продавцы.
Рассмотрим систему, связанную системой подчинённости «входят в состав». Она имеет иерархическую структуру. Например, изобразим следующий граф иерархической системы:
Периодическая система элементов в неё состав входят металлы и неметаллы. В свою очередь металлы делятся на 2 группы – группа 1 и группа 2, неметаллы делятся также на 2 группы – группа 5 и группа 6 и так далее. В отличие от остальных графов дерево не содержит циклов и петель, так как между любыми двумя его вершинами существует только один путь.
Так же у графа «Дерево» выделяется главная вершина, которая называется корень дерева. У любой вершины дерева могут быть потомки. А вершины, у которых нет потомков, называются листьями.
Следующий вид древовидного графа с отношением «является разновидностью» применяется для представления классификации объектов.
Например, разновидностями отряда «Насекомые» являются: Прямокрылые к ним относятся кузнечики, сверчки. Полужёсткокрылые – к ним относятся клопы, Чешуекрылые к ним относятся бабочки и Стрекозы.
Некоторые виды задач удобно решать с помощью графов.
Давайте решим одну из задач.
В коробке три шарика: жёлтый, зелёный и красный. Шестиклассница Таня со своими двумя друзьями Машей и Никитой вынимают их из коробки по одному. Сколько комбинаций выбора при этом возможно? Нужно выписать все варианты выбора.
Решение данной задачи удобно представить в виде дерева. Возьмём за корневую вершину произвольную току О., Таня может взять из коробки один из трёх шариков. Обозначим их буквами Ж, З и К. На схеме это соответствует трём ветвям, исходящим из точки О. Первый уровень в нашей задаче – это выбор Тани.
Теперь мы будем строить второй уровень графа. Второй уровень – это выбор Никиты.
Если Таня взяла жёлтый шарик, то Никита может взять зелёный или красный. Если же Таня взяла зелёный шарик, то Никита может взять жёлтый или красный. Аналогично, если Таня взяла красный шарик, то Никита может взять жёлтый или зелёный.
Осталось построить третий уровень, который отображает выбор Маши. Маша в каждом случае может взять оставшийся шарик. То есть если Таня взяла жёлтый шарик, а Никита зелёный, то Таня возьмёт красный шарик. Следующий вариант: если Таня взяла жёлтый шарик, а Никита Красный, Маша возьмёт зелёный шарик. И так далее мы достраиваем оставшиеся ветви.
Выпишем все пути от вершин первого уровня к вершине третьего. Каждый из выписанных путей определяет один из вариантов вытягивания шестиклассниками шариков из коробки. Так как других путей нет, то искомое число вариантов – 6.
Если при решении задачи не нужно указывать все возможные варианты, а нужно просто указать их число, то дерево можно и не строить. Тогда рассуждаем так: Таня может взять один из трёх шариков, Никита может взять один из двух оставшихся шариков, а Маша – один оставшийся. Получаем: 3, умножить на 2, умножить на 1 получаем ответ – 6 вариантов.
Итак, сегодня на уроке мы узнали:
Граф является наглядным средством представления информации состава и структуры системы.
Дерево – это граф с иерархической системой. Отличительная особенность дерева – это то, что между любыми двумя вершинами существует единственный путь.
Иерархия – это структура распределения частей целого от высшего к низшему.
Иерархическая система – это система, части которой находятся в отношениях подчинённости «является разновидностью», «входит в состав» и других.
Перейдём к практической части урока.
Сегодня на уроке мы научимся:
пользоваться инструментом Надпись
добавлять (вписывать) текст в автофигуру
1-e задание. Солнечная система.
1. Открыть текстовый документ «Солнечная система.docx».
2. На картинке по информации из таблицы указать положение планет.
3. Сохранить документ под именем «Солнечная система надписи».
Открываем в своей рабочей папке документ Солнечная система.docx. Здесь мы видим схему солнечной системы, по информации из таблицы, нам нужно указать положение планет.
Смотрим внимательно на схему и таблицу.
Ближе всего к солнцу находится Меркурий. Обозначим на схеме Меркурий.
Выбираем вкладку Вставка, затем в группе Текст выберем инструмент Надпись, и нажимаем Нарисовать надпись, при этом указатель мыши примет форму «плюса».
Чтобы вставить надпись стандартного размера просто щёлкните в документе.
Если размер надписи нужно изменить поднесите мышку к любому из маркеров в прямоугольнике и растяните до нужного размера.
Перетащим надпись на нужное место.
Если надпись окружена рамкой, уберём рамку. Нажимаем Формат – Контуры фигуры – Нет контура.
Аналогично подпишем остальные планеты солнечной системы.
Сохраним результат работы в своей рабочей папке под именем Солнечная система надписи.
2-e задание. Поездка в автобусе.
1. Открыть текстовый документ «Поездка в автобусе.docx».
2. Дорисовать схему отношений при поездке в автобусе и подписать их названия с помощью глаголов.
3. Сохранить документ под именем «Поездка в автобусе граф».
Открываем файл Поездка в автобусе.docx в своей рабочей папке. Здесь мы видим незаконченную схему отношений при поездке в автобусе, дорисуем её и подпишем отношения с помощью глаголов. Для этого:
Смотрим на схему. Водитель ведёт автобус.
Выбираем вкладку Вставка, в группе Иллюстрации нажимает на Фигуры. Здесь нам нужна стрелка. Соединяем вершины графа Водитель – Автобус стрелкой и, также как в первом задании, добавляем надпись.
Аналогично достраиваем всю схему.
Сохраним результат работы в своей рабочей папке под именем Поездка в автобусе граф.
Третье задание называется Арифметические выражения.
1. Открыть текстовый документ «Арифметические выражения.docx».
2. По данному образцу построить дерево для арифметического выражения.
3. Сохранить документ под именем «Выражение дерево».
Открываем файл Арифметические выражения.docx в своей рабочей папке. Здесь мы видим образец дерева для арифметического выражения. С помощью вкладки Вставка – Автофигуры построим дерево для нашего арифметического выражения.
Листьями данного дерева являются числа, а остальные вершины – это арифметические операции. Листья связаны с вершинами рёбрами.
Практикум
Практическая работа №1.1. Модели систем
Цель работы: формирование навыков системного анализа, построения структурных схем и графов классификаций.
Задание 1. Выполните проектные задания на анализ систем
Уровень 2
Вариант 1. Используя текстовый редактор, подготовьте небольшой отчет на тему «Модель "черного ящика"». Опишите проблему множественности вариантов модели «черного ящика» для одной и той же системы на примерах знакомых вам систем: радиоприемник, автомобиль, компьютер, столовая, школа и пр. (вы можете продолжить этот список).
Перечислите при этом нежелательные входы и выходы. Установите, как можно устранить недостатки системы (нежелательные связи с внешней средой). Описание представьте в табличной форме.
Вариант 2. Используя текстовый редактор, подготовьте небольшой отчет на тему «Модель состава системы». Изобразите графическими средствами модели состава систем, рассмотренных в первом варианте задания. Обоснуйте вашу модель с точки зрения ее назначения.
Отметьте, какие составляющие системы в этой модели рассматриваются в качестве элементов, а какие — в качестве подсистем.
Задание 2. Постройте структурную схему сложной системы
Уровень 1
Вариант 1. Используя графические средства, воспроизведите схему, отражающую состав и структуру танкового батальона. Подсчитайте количество танков в роте и общее количество танков в батальоне.
Уровень 2
Вариант 2. Постройте граф, отображающий состав и структуру мотопехотного батальона (армия ФРГ образца 1970 г.) по следующему описанию.
Батальон на БМП (боевых машинах пехоты) имел численность 764 человека. Во главе батальона стоял командир, которому подчинялись штаб и 5 рот: штабная и снабжения, минометная и три мотопехотные. Рота штабная и снабжения состояла из управления и трех взводов: штабного, связи и снабжения. В штабном взводе было четыре отделения: штабное, мотоциклистов, транспортное и разведывательное. Во взводе связи было три отделения радиосвязи и два отделения проводной связи. Во взводе снабжения было четыре отделения: материально-технического обеспече-ния, продовольственного снабжения, транспортное и санитарное.
Минометная рота состояла из управления, двух отделений передового наблюдения, отделения обеспечения и шести расчетов 120-мм минометов.
Каждая мотопехотная рота (163 чел.) имела в своем составе три мотопехотных взвода по 48 чел. Каждый взвод состоял из группы управления и четырех мотопехотных отделений по 10 чел. Отделение делилось на две группы: первая — командир машины, наводчик-оператор (БМП «Мардер» оснащался пушкой калибра 20 мм и двумя пулеметами) и механик-водитель; вторая — командир отделения, пулеметчик, гранатометчик, огнемет- чик и три стрелка.
Задание 3. Построение графов классификаций
Уровень 1
Вариант 1. Используя графические средства, воспроизведите схему, отражающую классификацию геометрических объектов.
Уровень 2
Вариант 2. Постройте граф классификации биологической системы по следующему описанию.
Согласно биологической классификации, выделяют три империи (надцарства): археобактерии, эукариоты и прокариоты. К империи эукариотов относятся царства грибов, растений и животных. К царству животных относятся типы членистоногих, моллюсков, иглокожих, кишечнополостных, хордовых и др. К типу хордовых относятся классы рыб, амфибий, рептилий, млекопитающих, птиц. К классу млекопитающих относятся отряды китов, ластоногих, хищных, грызунов, копытных и др. К отряду хищных относятся семейства медвежьих, енотовых, псовых, виверровых, кошачьих и др. К семейству псовых относятся роды лисиц, енотовидных собак, собак, фенеков, песцов и др. К роду собак относятся виды собак домашних, волков, шакалов, койотов. К виду собак домашних относятся овчарки, спаниели, водолазы, сенбер-нары, доги, болонки и др.
Вариант 3. Постройте граф классификации в русском языке по следующему описанию.
Предложения в русском языке классифицируются по составу, по интонации и по цели высказывания. По составу предложения делятся на нераспространенные и распространенные. Нераспространенные предложения состоят только из двух членов: подлежащего и сказуемого. Пример нераспространенного предложения: «Птицы прилетели». Распространенные предложения состоят из подлежащего, сказуемого и второстепенных членов предложения. Пример распространенного предложения: «Ранней весной прилетели первые птицы».
По интонации предложения делятся на восклицательные («Пришла весна!») и невосклицательные («Пришла весна.»).
По цели высказывания предложения делятся на повествовательные, вопросительные и побудительные. Повествовательное предложение: «Мы собрали много грибов и ягод.». Вопросительное предложение: «Вы собрали много грибов и ягод?». Побудительное предложение: «Собирайте грибы и ягоды!».
Цель работы: формирование навыков системного анализа, построения структурных схем и графов классификаций.
Задание 1. Выполните проектные задания на анализ систем
Уровень 2
Вариант 1. Используя текстовый редактор, подготовьте небольшой отчет на тему «Модель "черного ящика"». Опишите проблему множественности вариантов модели «черного ящика» для одной и той же системы на примерах знакомых вам систем: радиоприемник, автомобиль, компьютер, столовая, школа и пр. (вы можете продолжить этот список).
Перечислите при этом нежелательные входы и выходы. Установите, как можно устранить недостатки системы (нежелательные связи с внешней средой). Описание представьте в табличной форме.
Вариант 2. Используя текстовый редактор, подготовьте небольшой отчет на тему «Модель состава системы». Изобразите графическими средствами модели состава систем, рассмотренных в первом варианте задания. Обоснуйте вашу модель с точки зрения ее назначения.
Отметьте, какие составляющие системы в этой модели рассматриваются в качестве элементов, а какие — в качестве подсистем.
Задание 2. Постройте структурную схему сложной системы
Уровень 1
Вариант 1. Используя графические средства, воспроизведите схему, отражающую состав и структуру танкового батальона. Подсчитайте количество танков в роте и общее количество танков в батальоне.
Уровень 2
Вариант 2. Постройте граф, отображающий состав и структуру мотопехотного батальона (армия ФРГ образца 1970 г.) по следующему описанию.
Батальон на БМП (боевых машинах пехоты) имел численность 764 человека. Во главе батальона стоял командир, которому подчинялись штаб и 5 рот: штабная и снабжения, минометная и три мотопехотные. Рота штабная и снабжения состояла из управления и трех взводов: штабного, связи и снабжения. В штабном взводе было четыре отделения: штабное, мотоциклистов, транспортное и разведывательное. Во взводе связи было три отделения радиосвязи и два отделения проводной связи. Во взводе снабжения было четыре отделения: материально-технического обеспече-ния, продовольственного снабжения, транспортное и санитарное.
Минометная рота состояла из управления, двух отделений передового наблюдения, отделения обеспечения и шести расчетов 120-мм минометов.
Каждая мотопехотная рота (163 чел.) имела в своем составе три мотопехотных взвода по 48 чел. Каждый взвод состоял из группы управления и четырех мотопехотных отделений по 10 чел. Отделение делилось на две группы: первая — командир машины, наводчик-оператор (БМП «Мардер» оснащался пушкой калибра 20 мм и двумя пулеметами) и механик-водитель; вторая — командир отделения, пулеметчик, гранатометчик, огнемет- чик и три стрелка.
Задание 3. Построение графов классификаций
Уровень 1
Вариант 1. Используя графические средства, воспроизведите схему, отражающую классификацию геометрических объектов.
Уровень 2
Вариант 2. Постройте граф классификации биологической системы по следующему описанию.
Согласно биологической классификации, выделяют три империи (надцарства): археобактерии, эукариоты и прокариоты. К империи эукариотов относятся царства грибов, растений и животных. К царству животных относятся типы членистоногих, моллюсков, иглокожих, кишечнополостных, хордовых и др. К типу хордовых относятся классы рыб, амфибий, рептилий, млекопитающих, птиц. К классу млекопитающих относятся отряды китов, ластоногих, хищных, грызунов, копытных и др. К отряду хищных относятся семейства медвежьих, енотовых, псовых, виверровых, кошачьих и др. К семейству псовых относятся роды лисиц, енотовидных собак, собак, фенеков, песцов и др. К роду собак относятся виды собак домашних, волков, шакалов, койотов. К виду собак домашних относятся овчарки, спаниели, водолазы, сенбер-нары, доги, болонки и др.
Вариант 3. Постройте граф классификации в русском языке по следующему описанию.
Предложения в русском языке классифицируются по составу, по интонации и по цели высказывания. По составу предложения делятся на нераспространенные и распространенные. Нераспространенные предложения состоят только из двух членов: подлежащего и сказуемого. Пример нераспространенного предложения: «Птицы прилетели». Распространенные предложения состоят из подлежащего, сказуемого и второстепенных членов предложения. Пример распространенного предложения: «Ранней весной прилетели первые птицы».
По интонации предложения делятся на восклицательные («Пришла весна!») и невосклицательные («Пришла весна.»).
По цели высказывания предложения делятся на повествовательные, вопросительные и побудительные. Повествовательное предложение: «Мы собрали много грибов и ягод.». Вопросительное предложение: «Вы собрали много грибов и ягод?». Побудительное предложение: «Собирайте грибы и ягоды!».
Практическая работа №10
«Схемы, графы и деревья» (задания 6 - 8).
Проверочная работа
Деревья
Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами (системами с иерархической структурой).
Например, иерархическую структуру имеет школа, потому что в ней установлены следующие отношения подчиненности: директор — заместители директора – учителя — ученики.
Иерархическую структуру имеют системы, элементы которых связаны отношением «входит в состав».
На рисунке ниже изображен граф иерархической системы, представляющий состав прикладного программного обеспечения (ПО) компьютера.
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.
Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка — обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один ко многим». Вершины, не имеющие порожденных вершин, называются листьями.
Древовидными являются схемы отношений «является разновидностью», используемые для наглядного представления классификации объектов:
Иерархию легко изобразить «лесенкой» — в виде многоуровневого списка. Объекты одного уровня иерархии располагаются на одном уровне в списке. Чем ниже уровень иерархии, тем правее находится соответствующий уровень списка:
Родственные связи между членами семьи удобно изображать с помощью схемы, называемой генеалогическим или родословным деревом. На рисунке ниже показана родословная Романовых. Здесь корень дерева находится снизу. Изображать дерево отношений можно в любом направлении — это дело вкуса разработчика модели.
По иерархическому принципу организована система хранения файлов во внешней памяти.
Вы знаете, что по определенному признаку (принадлежность, назначение, содержимое, время создания и т. д.) файлы целесообразно объединять в папки. Папки, в свою очередь, могут вкладываться в другие папки и т. д. Главная (корневая) вершина этой иерархии соответствует определенному устройству внешней памяти.
Для того чтобы найти файл в иерархической файловой структуре, можно указать путь к файлу. В путь к файлу входят записываемые через разделитель «\» логическое имя диска и последовательность имен вложенных друг в друга папок, в последней из которых находится нужный файл.
Например, пути к файлам можно записать так:
С:\Проекты\История\
С:\Проекты\Информатика\
С:\Рисунки\
Путь к файлу вместе с именем файла называют полным именем файла.
Примеры полных имен файлов:
С:\Проекты\История\Эпоха Возрождения.doc
С:\Проекты\Информатика\Интернет.doc
С:\Проекты\Информатика\Компьютерные вирусы.doc
С:\Рисунки\Закат.jpg
С:\Рисунки\ Зима.ipg
Операционная система позволяет получить на экране компьютера изображение файловой системы в виде дерева:
Использование графов при решении задач
Графы удобно использовать при решении некоторых классов задач.
Задача 1
Сколькими способами можно рассадить в ряд на три стула трех учеников? Выписать все возможные случаи.
Решение этой задачи удобнее всего представить в виде дерева. За его корневую вершину возьмем произвольную точку плоскости О.
На первый стул можно посадить любого из трех учеников — обозначим их А, В и С. На схеме это соответствует трем ветвям, исходящим из точки О:
Посадив на первый стул ученика А, на второй стул можно посадить ученика В или С. Если же на первый стул сядет ученик В, то на второй можно посадить А или С. А если на первый стул сядет С, то на второй можно будет посадить А или В. Это соответствует на схеме двум ветвям, исходящим из каждой вершины первого уровня:
Очевидно, что третий стул в каждом случае займет оставшийся ученик. Это соответствует одной ветви дерева, которая «вырастает» на из предыдущих ветвей.
Выпишем все пути от вершин первого уровня к вершинам третьего уровня: А-В-С, А-С-В, В-А-С, В-С-А, С-А-В, С-В-А. Каждый из выписанных путей определяет один из вариантов рассаживания учеников на стулья. Так как других путей нет, то искомое число способов — 6.
Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их число. В этом случае рассуждать нужно так: на первый стул можно усадить одного из трех человек, на второй — одного из двух оставшихся, на третий — одного оставшегося: 3 * 2 * 1 = 6.
Задача 2
Чтобы принести Царю-батюшке молодильные яблоки, должен Иван-царевич найти единственный верный путь к волшебному саду. Встретил Иван-царевич на развилке трех дорог старого ворона и вот какие советы от него услышал:
1. иди сейчас по правой тропинке;
2. на следующей развилке не выбирай правую тропинку;
3. на третьей развилке не ходи по левой тропинке.
Пролетавший мимо голубь шепнул Ивану-царевичу, что только один совет ворона верный и что обязательно надо пройти по тропинкам разных направлений. Наш герой выполнил задание и попал в волшебный сад. Каким маршрутом он воспользовался?
Обозначим левую, среднюю и правую тропинки соответственно Л, С и П. Возможные маршруты представим в виде графа. При этом подсказки ворона отметим более «жирными» ребрами. Так как только один совет ворона верен, то на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро. Этот маршрут обозначен дополнительной пунктирной линией:
Коротко о главном
Наглядным средством представления состава и структуры системы является граф. Граф состоит из вершин, связанных линиями. Направленная линия называется дугой, ненаправленная — ребром. Линия, выходящая из некоторой вершины и входящая в нее же, называется петлей. Граф называется взвешенным, если его вершины или ребра (дуги) характеризуются некоторой дополнительной информацией — весом вершины или ребра (дуги).
Путь по вершинам и ребрам графа, включающий любое ребро графа не более одного раза, называется цепью. Цепь, начальная и конечная вершины которой совпадают, называется циклом. Разновидность графа, содержащая циклы, называется сетью.
Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами (системами с иерархической структурой).
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Деревья не содержат циклов и петель.
Вопросы и задания
1. Определите сказку, для которой следующий граф определяет отношения между персонажами.
(Курочка Ряба)
2. С разных сторон на холм поднимаются три тропинки и сходятся на вершине. Перечислите множество маршрутов, по которым можно подняться на холм и спуститься с него. Решите ту же задачу, если вверх и вниз надо идти по разным тропинкам.
(Решение:
а) Вверх можно подняться по 3-м тропинкам (3 варианта), спуститься также по 3-м (3 варианта). В итоге имеем: 3 • 3 = 9 вариантов.
б) Вверх можно подняться по 3-м тропинкам (3 варианта), спуститься только по оставшимся 2-м (2 варианта). В итоге имеем: 3 • 2 = 6 вариантов)
3. Сколько трехзначных чисел можно записать с помощью цифр 1, 3, 5 и 7 при условии, что в записи числа не должно быть одинаковых цифр?
(Решение:
Число размещений 4-х элементов по 3: A = 4 • (4-1) • (4-2) • (4-3) = 4 • 3 • 3 • 1 = 24
Ответ: 24 чисел)
4. Для составления цепочек используются бусины, помеченные буквами: А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором — любая гласная, если первая буква согласная, и любая согласная, если первая гласная.
На третьем месте – одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?
(Решение:
а) Первая бусинка А, тогда на втором месте может быть 3 варианта бусинок и на третьем месте тоже 3 варианта. Получаем 3 • 3 = 9 вариантов;
б) Первая бусинка С, тогда на втором месте возможны 2 варианта (2 гласные) и на третьем тоже 2 варианта (Д, Е). Получаем 2 • 2 = 4 варианта;
в) Первая бусинка Е, тогда на втором месте возможны 3 варианта (3 согласные), а на третьем место — 2 варианта (С, Д) Получаем 3 • 2 = 6 вариантов;
В итоге получаем: 9 + 4 + 6 = 19 вариантов
Ответ: 19 вариантов)
5. В центре дальнего леса находилась большая поляна — самое удивительное место в Стране малышей. На ней были три колодца: один — с газировкой, второй — с молоком, третий — с морсом. Когда-то три друга Фантик, Грибок и Дружок — построили на поляне домики и целое лето жили в лесу. Другим малышам нравилось приходить к ним в гости, попить молока, газировки или морса, погулять по лесным тропинкам. Но однажды бывшие друзья поссорились, и каждый из них решил проложить собственные дорожки к колодцам так, чтобы они не пересекались с дорожками соседей.
Подумайте, почему Знайка, к которому коротышки обратились за помощью, предложил им помириться.
(Задача не имеет решения. Нельзя провести тропинки так, чтобы они не пересекались).
Проверочная работа
Вариант 1
1. Решите задачу табличным способом.
В кафе встретились три друга: художник Черняев, рыбак Беленьков и таксист Рыжиков. «Замечательно, что у одного из нас белые, у другого черные, а у третьего рыжие волосы, но ни у кого цвет волос не соответствует фамилии», – заметил черноволосый. «Ты прав», – сказал Рыжиков. Какого цвета волосы у каждого из друзей.
2. Пользуясь диаграммой работоспособности в течение рабочей недели, отметьте только истинные высказывания:
1. самая высокая работоспособность в понедельник;
2. работоспособность в среду ниже работоспособности в четверг;
3. работоспособность во вторник и четверг одинакова;
4. самый непродуктивный день — суббота;
5. работоспособность заметно снижается в пятницу;
6. самая высокая работоспособность в среду;
7. пик работоспособности – в пятницу;
8. всю неделю работоспособность одинаковая.
3. Для выполнения задания постройте дерево.
Запишите все возможные двузначные числа, при записи которых используются цифры 2, 8 и 5.
4. Какое число получится в результате работы этой блок-схемы, если
А) вводится число 4.
Б) вводится число 5
Вариант 2
1. Решите задачу табличным способом.
Три ученицы – Липкина, Яблонева и Черемухина – посадили около школы три дерева: черемуху, яблоню и липу. Причем не одна из них не посадила то дерево, от которого произошла ее фамилия. Узнайте, какое дерево посадила каждая из девочек, если известно, что Липкина посадила не яблоню.
2. Пользуясь диаграммой работоспособности в течение рабочей недели, отметьте только ложные высказывания:
1. самая высокая работоспособность в понедельник;
2. работоспособность в среду ниже работоспособности в четверг;
3. работоспособность во вторник и четверг одинакова;
4. самый непродуктивный день — суббота;
5. работоспособность заметно снижается в пятницу;
6. самая высокая работоспособность в среду;
7. пик работоспособности – в пятницу;
8. всю неделю работоспособность одинаковая.
3. Для выполнения задания постройте дерево.
Запишите все возможные двузначные числа, при записи которых используются цифры 1, 7 и 4.
4. Какое число получится в результате работы этой блок-схемы, если
А) вводится число 6.
Б) вводится число 5
Практическая работа №10
«Схемы, графы и деревья» (задания 6 - 8)
Задание 6. Наши конкурсы
Работы участников школьных конкурсов по информационным технологиям записаны на диске, файловая структура которого имеет вид:
Средствами текстового процессора Word создайте соответствующую схему.
Сохраните результат работы в собственной папке в файле с именем Конкурсы.
Задание 7. Царство животных
1. Составьте схему но следующему описанию:
Близкие виды объединяются в один род. Например: ворона, ворон, галка и грач объединены в род Ворон. Близкие роды объединяются в семейства: род Ворон, род Сорока, род Сойка, род Кедровка объединены в семейство Вороновые. В свою очередь, близкие семейства объединяются в отряды. Так, семейство Синицевые, семейство Вороновые, семейство Ласточковые принадлежат отряду Воробьинообразные. Близкие отряды составляют класс. Так, отряд Воробьинообразные, отряд Совообразные, отряд Гусеобразные принадлежат к классу Птицы. Близкие классы объединены в типы. Так, класс Птицы, класс Амфибии, класс Млекопитающие входят в тип Хордовые. В настоящее время выделяют до 25 различных типов животных. Все они объединены в царство Животные.
2. Сохраните результат работы в собственной папке в файле с именем Животные.
Задание 8. Творческое задание
Придумайте сами пример объектов, отношения между которыми можно представить с помощью схемы. Создайте соответствующую схему в программе Microsoft Word. Сохраните результат работы в собственной папке в файле с именем Идея5.
Читайте также: