Модели, таблицы, графы и деревья

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

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

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

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

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

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

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

1. Какие свойства реального объекта нужны для задачи?
2. Сохранила ли их модель?
3. Достаточна ли точность исходных данных?
4. Совпадает ли прогноз модели с известными наблюдениями?

В табличной модели столбец задаёт свойство объекта, а строка описывает один объект. В базе данных строку часто называют записью, столбец — полем. Ключ однозначно отличает запись от остальных: например, номер читательского билета.

Поле Код подходит на роль ключа, потому что значения не повторяются.

Фильтр оставляет записи, которые удовлетворяют условию. Для условия «класс 9 и балл не меньше 70» логическая запись имеет вид

В таблице подходят Алина и Глеб. Если заменить «и» на «или», в результат ошибочно попадёт Борис: его балл не меньше $70$, хотя он учится в восьмом классе.

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

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

Для графа с вершинами $A$, $B$, $C$, где длины дорог $AB=4$, $AC=9$, $BC=3$, таблица весов выглядит так:

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

Вес пути равен сумме весов его рёбер. Из $A$ в $C$ можно пройти напрямую с весом $9$ или через $B$:

Кратчайший путь проходит через $B$ и имеет длину $7$. Нельзя выбирать самое лёгкое отдельное ребро: сравнивают суммы для полных маршрутов.

В ориентированном графе без циклов число путей удобно считать слева направо. Пусть есть дуги $A\to B$, $A\to C$, $B\to D$, $B\to E$, $C\to D$, $D\to F$, $E\to F$. В начальной вершине считаем один пустой путь:

Для каждой следующей вершины складываем числа путей во всех её непосредственных предшественниках:

Значит, из $A$ в $F$ ведут три пути. Этот способ нельзя без изменения применять к графу с циклами: обход цикла может породить бесконечно много маршрутов.

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

Если у дерева $n$ вершин, то в нём $n-1$ рёбер:

Например, дерево из семи вершин содержит шесть рёбер.

Файловая система — пример иерархии: диск служит корнем, папки — внутренними вершинами, файлы — листьями. Дерево также помогает перебрать варианты. Если пароль состоит из двух символов, а на каждой позиции разрешены A, B, C, из корня выходят три ветви, затем каждая снова делится на три. Число листьев равно

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

Компьютерную сеть можно представить графом: устройства становятся вершинами, линии связи — рёбрами, а задержка или пропускная способность — весами. Понятия сайта, страницы, IP-адреса, URL и поиска разобраны в статье о файловой системе и поиске. В теме 2.11 сеть рассматривают именно как графовую модель.

• Соответствует ли модель цели задачи?
• Не перепутаны ли строка-запись и столбец-поле?
• Учтены ли направление и вес каждого ребра?
• Для маршрута сложены все веса?
• При подсчёте путей сложены значения всех предшественников?
• В дереве нет цикла и к каждой вершине от корня ведёт единственный путь?

Содержание тем 2.9–2.12 сверено с проектом кодификатора ОГЭ-2027 ФИПИ. Таблицы, графы и примеры составлены FastLearn.