Краткое содержание: Параграф § 13 / Информатика 6 класс

Многообразие и понятие схемы

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

Схема — это представление некоторого объекта, отражающее его основные черты с помощью условных обозначений. С помощью схем можно отобразить как внешний вид объекта, так и его внутреннюю структуру. Например, на рисунке 47 (страница 104) представлена схема зрительного зала, а на рисунке 48 (страница 105) — план квартиры.

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

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

Для наглядного представления состава и структуры систем широко используются графы.

Граф состоит из вершин (объектов) и связывающих их линий. Линия, направленная (со стрелкой), называется дугой, а ненаправленная (без стрелки) — ребром.

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

Если объекты системы представлены вершинами, а связи между ними — линиями, то граф становится информационным представлением этой системы. Ранее рассматривались графы, отображающие отношения между объектами. Например, граф на рисунке 51 (страница 107) показывает отношение «переписываются» между детьми.

Ребро — это ненаправленная связь (например, отношение «пишут письма друг другу»), отражающая симметричное отношение. Граф называется неориентированным, если его вершины соединены ребрами.

Дуга — это направленная связь (например, отношение «переписывает»), отражающая асимметричное отношение. Граф называется ориентированным, если его вершины соединены дугами (рисунок 52).

Взвешенный граф — это граф, у которого вершины или ребра (дуги) несут дополнительную информацию — вес вершины или ребра. Например, на рисунке 53 (страница 108) показан взвешенный граф городов Золотого кольца, где вес вершин — год основания города, а вес ребер — расстояние в километрах между городами.

Цепь — это путь по вершинам и ребрам графа, включающий любое ребро графа не более одного раза.

Цикл — это цепь, у которой начальная и конечная вершины совпадают (например, Аня — Коля — Витя — Аня на рисунке 52).

Граф с циклами называется сетью.

Семантическая сеть — это граф, представляющий информационную модель, в которой вершины обозначают объекты (понятия), а дуги — связи (отношения) между ними. Например, семантическая сеть на рисунке 54 (страница 109) иллюстрирует информационную модель сказки «Царевна-лягушка».

Деревья и иерархия

Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых связаны отношением «является разновидностью», называются иерархическими системами.

Дерево — это граф иерархической системы (рисунок 55, страница 110). Отличительная особенность дерева: между любыми двумя вершинами существует единственный путь, и оно не содержит циклов и петель.

В дереве выделяется одна главная вершина, называемая корнем.

Любая вершина дерева (кроме корня) имеет только одного предка (объект верхнего уровня) и может порождать несколько потомков (вершин нижнего уровня).

Вершины, не имеющие порождённых вершин, называются листьями.

Отношение связи в такой системе называется «один ко многим».

Древовидная схема — это схема отношений «является разновидностью», используемая для наглядного представления классификации объектов (например, классификация рептилий на рисунке 56).

Иерархия также легко представляется в виде многоуровневого списка, где объекты одного уровня иерархии расположены на одной строке, а более низкий уровень соответствует отступу (рисунок 57, а).

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

Использование деревьев для решения задач

Деревья удобно применять при решении комбинаторных задач.

Задача 1 (Распределение учеников): Сколькими способами можно рассадить в ряд трёх учеников (А, В, С) на три стула?

Решение: Используется дерево вариантов. Корень (точка O) — начало выбора.

На первый стул можно посадить любого из трёх (А, В или С) — это три ветви первого уровня.

Если на первый стул сел А, то на второй стул можно посадить В или С (две ветви второго уровня).

Если на первый стул сел А, на второй — В, то на третий стул можно посадить только С (одна ветвь третьего уровня).

Общее количество способов — это количество «листьев» дерева (путей от корня к третьему уровню). Пути: А-В-С, А-С-В, В-А-С, В-С-А, С-А-В, С-В-А. Всего \( 3 \times 2 \times 1 = 6 \) способов. (рисунок 58, 59, 60).

Задача 2 (Путь Ивана-царевича): Иван-царевич встречает ворона, который говорит, что единственный верный путь в волшебный сад: 1) немедленно по правой тропинке; 2) на следующей развилке не выбирать правую тропинку; 3) на третьей развилке не идти по левой тропинке. Ворон намекает, что только один совет верен. Пролетающий мимо голубь шепчет: «Нужно обязательно пройти по тропинкам разных направлений». Каким маршрутом воспользовался Иван-царевич?

Решение: Из трёх советов ворона верен только один. Голубь: обязательно пройти по тропинкам разных направлений (Право, Лево, Прямо). Это означает, что маршрут должен включать все три направления, каждое по одному разу. Верный маршрут: Лево - Право - Прямо (Л-П-Т). Это согласуется с графом вариантов и условием, что только совет 3 верен. (рисунок 61)

Самое главное (Резюме)

Схема — это представление объекта в общих, главных чертах с помощью условных обозначений. Схемы могут отражать внешний вид, структуру и даже поведение (рисунок 61) .

Граф — наглядное средство для отображения состава и структуры системы, состоит из связанных линиями вершин.

Иерархия — расположение элементов от высшего к низшему, где элементы связаны отношениями «является разновидностью», «входит в состав» или другими отношениями подчинения. Системы с иерархической структурой называются иерархическими системами.

Дерево — граф иерархической системы. Его ключевая особенность — наличие единственного пути между любыми двумя вершинами.