Информационные модели: графы, таблицы, базы данных
Ты научишься читать графы и таблицы, связывать данные по ключам и выбирать подходящий способ решения.
Зачем на экзамене
Информационная модель помогает представить объекты, их свойства и связи в удобной форме. На экзамене нужно не просто прочитать схему, а восстановить отношения между объектами, проверить ограничения и получить числовой ответ. В нумерации проекта КИМ 2027 тема связана с заданиями 1, 3 и 23.
Что нужно уметь
- выделять вершины и ребра графа, учитывать направления и веса;
- сопоставлять граф со списком ребер или таблицей смежности;
- находить маршрут и вычислять его длину;
- различать записи, поля, первичные и внешние ключи;
- соединять данные из нескольких таблиц;
- проверять условия отбора без пропуска подходящих строк;
- строить граф по данным файла и считать оптимальные пути или число путей.
База
Информационная модель
Информационная модель описывает важные для задачи свойства объекта. Один и тот же набор данных можно представить графом, обычной таблицей или набором связанных таблиц базы данных. Выбор формы зависит от того, что нужно увидеть: связи, значения свойств или отношения между записями.
Граф
Граф состоит из вершин и ребер. Вершины обозначают объекты, а ребра показывают связи между ними. Например, города можно представить вершинами, а дороги между ними обозначить ребрами.
В неориентированном графе ребро можно пройти в обе стороны. В ориентированном графе у ребра есть направление. Такое ребро называют дугой. Если возле ребра указано число, граф является взвешенным. Вес может обозначать расстояние, стоимость или время.
Путь является последовательностью вершин, в которой каждые две соседние вершины соединены ребром нужного направления. Длина пути во взвешенном графе равна сумме весов его ребер. Степень вершины в неориентированном графе равна числу ребер, которые к ней подходят. В ориентированном графе отдельно считают входящие и исходящие дуги.
Табличные представления графа
Граф можно хранить без рисунка. При чтении таблицы сначала выясни, что означают строки, столбцы и пустые ячейки.
| Представление | Что хранится | Как читать |
|---|---|---|
| Список ребер | Пары связанных вершин | Каждая строка задает одно ребро |
| Таблица смежности | Связи между всеми парами вершин | Ячейка показывает наличие или вес ребра |
| Таблица объектов | Свойства вершин | Строка описывает один объект |
Таблица смежности неориентированного графа симметрична относительно главной диагонали. Для ориентированного графа симметрии может не быть. Ноль или пустая ячейка часто означают отсутствие ребра, но точный смысл нужно брать из условия.
Подсчет путей в ациклическом графе
В ориентированном ациклическом графе нет пути, возвращающегося в исходную вершину. Его вершины можно расположить в топологическом порядке: начало каждой дуги идет раньше ее конца. Номера вершин сами по себе такой порядок не гарантируют.
Для числа путей поставь начальной вершине 1, остальным 0. Последовательно передавай число путей из обработанной вершины каждому ее соседу по исходящей дуге. Если несколько дуг задают разные допустимые переходы, учитывай каждую согласно условию.
C(s)=1,\qquad C(v)=\sum_{u \to v} C(u)Если требуется кратчайший или самый длинный путь в ациклическом графе, в том же порядке выбирай минимум или максимум суммы предыдущего результата и веса дуги. Недостижимая вершина отличается от вершины с расстоянием 0.
Реляционная база данных
Реляционная база данных хранит данные в связанных таблицах. Строка таблицы называется записью, а столбец называется полем. Поле id часто служит первичным ключом и однозначно определяет запись.
Внешний ключ хранит идентификатор записи из другой таблицы. Например, поле city_id в таблице школ может указывать на поле id таблицы городов. Чтобы получить название города, нужно сопоставить равные значения этих полей.
При отборе записей проверяй логические связки. Для условия "А и Б" запись должна удовлетворять обеим частям. Для условия "А или Б" достаточно хотя бы одной части. Если требуется количество записей, считай строки после отбора. Если требуется сумма, складывай значения нужного поля только в отобранных строках.
Как решать
Если даны граф и таблица
- Определи тип графа: ориентированный или неориентированный, взвешенный или невзвешенный.
- Выпиши степени вершин или число входящих и исходящих дуг.
- Сравни эти признаки со строками таблицы. Начинай с уникальных вершин: тупиков, вершин с наибольшей степенью или редким набором соседей.
- Зафиксируй найденное соответствие и проверь соседей. Одна угаданная вершина без проверки не дает надежного ответа.
- Если нужен путь, следи за направлением каждого ребра. Для взвешенного графа складывай веса, а не количество ребер.
Если граф задан в файле
- Прочитай описание формата: заголовок, число вершин и дуг, порядок полей и правила направления.
- Построй списки соседей. Для неориентированного ребра добавь оба направления, для дуги только указанное.
- Уточни, нужен оптимальный путь или количество путей. Не заменяй одну величину другой.
- Для ациклического графа найди топологический порядок; затем считай значения после всех предшественников.
- Для кратчайшего пути с неотрицательными весами подойдет алгоритм Дейкстры. Для отрицательных весов он неприменим без дополнительных условий.
- Проверь старт, финиш, недостижимые вершины и каждое ограничение на маршрут из условия.
Если даны связанные таблицы
- Определи, что обозначает одна строка каждой таблицы.
- Найди первичные и внешние ключи. Не соединяй строки только по похожим названиям.
- Переведи условие в последовательность действий: соединение таблиц, отбор строк, затем подсчет или сумма.
- Проверяй сложное условие по частям. Удобно отмечать выполнение каждой части отдельно.
- Перед ответом уточни, что требуется считать: записи, разные объекты или значение числового поля.
Для поиска кратчайшего пути при неотрицательных весах можно ставить вершинам временные расстояния. Начальной вершине поставь 0, остальным: неизвестное большое значение. Выбирай необработанную вершину с наименьшей отметкой и проверяй, можно ли улучшить расстояния до ее соседей. Остановись после окончательной обработки конечной вершины.
Частые ошибки
- Ошибка: считать ребра вместо их весов. Как избежать: отдельно запиши маршрут и сумму весов.
- Ошибка: идти против направления дуги. Как избежать: проверяй стрелку при каждом переходе.
- Ошибка: считать пустую ячейку ребром с нулевым весом. Как избежать: сначала прочитай правило заполнения таблицы.
- Ошибка: соединять записи по номеру строки. Как избежать: используй только указанные ключевые поля.
- Ошибка: заменять условие "и" условием "или". Как избежать: проверяй каждую часть условия отдельно.
- Ошибка: считать разные значения вместо строк. Как избежать: уточни, требуется ли устранять повторы.
Проверь себя
- В графе есть ребра АБ, АВ, БВ и ВГ. Какова степень вершины В?
- Что означает симметричная таблица смежности для неориентированного графа?
- Какое поле связывает запись одной таблицы с первичным ключом другой?
- В поле записаны значения 7, 12, 12 и 20. Сколько строк удовлетворяет условию "значение не меньше 12"?
Ответы: 1) 3; 2) связь между двумя вершинами одинаково отражена по обе стороны главной диагонали; 3) внешний ключ; 4) 3 строки.
Связь с заданиями
В задании 1 сопоставляют граф и табличную модель, в задании 3 связывают и отбирают записи таблиц. В задании 23 по проекту КИМ 2027 анализируют граф: находят оптимальный путь или количество путей в ориентированном ациклическом графе. Формат файла, направления, веса и ограничения на маршрут всегда берутся из условия. Подсчет программ числового исполнителя относится к заданию 13 и разобран в отдельной теме.