IT "Понятно"
Обучение для начинающих
c 8 лет и до бесконечности
c 8 лет и до бесконечности
Задание №1 ЕГЭ по информатике направлено на проверку навыков учащихся представлять, считывать и анализировать данные в разных типах информационных моделей.
Решается ручным способом, хотя есть и программный методНо возможно и программное решение части этого задания. Программное решение значительно упрощает работу с анализом графа.
Информационные модели могут быть разными: схемы, карты, таблицы, графики или формулы. В заданиях ЕГЭ в качестве информационной модели используются графы.
В заданиях данного типа нужно проанализировать представленный рисунок графа и таблицу к нему. Иногда в задании нам предоставляют только таблицу и граф необходимо составить самостоятельно. Далее, однозначно соотнести значения в таблице с информацией, представленной на графе.
Информационные модели — это упрощённые представления реальных объектов, процессов или явлений, которые используются для анализа, прогнозирования и принятия решений. Они позволяют структурировать информацию, выделяя ключевые свойства и взаимосвязи, и представлять её в удобной для обработки форме. Информационные модели широко применяются в информатике, математике, физике, экономике и других областях.
Основная цель информационной модели — описать объект или систему с помощью данных, которые можно обрабатывать с помощью компьютера. Для этого используются различные способы структурирования информации, такие как линейные списки, таблицы, деревья и графы. Рассмотрим эти понятия подробнее.
Давайте определим, что такое структурирование информации. Можно сказать, что это некоторый процесс организации данных в определённом порядке. Такой процесс позволяет эффективно хранить, обрабатывать и анализировать информацию.
Пример иерархической структуры данных — дерево.
Дерево — это иерархическая структура данных, в которой каждый элемент (узел) имеет одного родителя и может иметь несколько потомков. Корневой узел — это вершина дерева, а листья — узлы, не имеющие потомков
С деревьями, в частности бинарными, мы встретимся, в задании 4 ЕГЭ по информатике.
Но, порой, отношения между объектами информационной модели могут быть очень сложными и запутанными. В таком случае можно использовать не деревья, а графы.
Граф — это математическая абстракция, состоящая из двух основных компонентов:
Рёбра могут быть ориентированными (иметь направление) или неориентированными (без направления). Также граф может быть взвешенным, если каждому ребру присвоено числовое значение (вес).
Вершина — это основной элемент графа, который представляет объект или сущность. Вершины могут быть пронумерованы или иметь буквенные метки для идентификации. В графическом представлении вершины обычно изображаются точками или кружками.
Ребро — это связь между двумя вершинами. Ребро может быть направленным (иметь направление, обозначается стрелкой) или ненаправленным (не имеет направления, обозначается линией).
Логично предположить, что дороги между населёнными пунктами имеют какую-то протяжённость, которую было бы неплохо добавить к графу. Например, можно записать длину каждой дороги в виде таблицы:
Такая таблица называется весовой матрицей графа. Весовая матрица — это квадратная матрица, где элементы указывают вес ребра между вершинами. Если ребра между вершинами нет, то в матрице может быть указано бесконечное значение или нуль.
В задании №1 мы часто будем работать с весовыми матрицами.
Помимо весовой матрицы, вам также может встретиться матрица смежности. Она во многом похожа на весовую, только вместо веса рёбер в неё находятся единицы, если ребро между вершинами существует и 0 — если ребра не существует. Вместо единиц и нулей могут быть и другие условные обозначения, например, звёзды.
И последний термин, которым мы будем пользоваться при решении задания №1 — это степень вершины. Степенью вершины называется количество рёбер, которые выходят из данной вершины.
У задания 1 ЕГЭ по информатике существует 3 разных типа формулировок. Во всех вариантах вам даётся схема дорог какого-либо района, изображённая в виде графа. Рядом со схемой располагается таблица. Это может быть либо весовая матрица, либо матрица смежности. Как их определить?
В весовой матрице расположены числа, обозначающие протяжённость дороги — длина ребра графа. В матрице смежности расположены только звезды, которые обозначают наличие дороги между двумя населёнными пунктами — вершинами графа.
Типы заданий разделяются по сложности, а равно и по времени и объёму выполнения задания.
1 тип заданий. Даётся матрица смежности и требуется однозначно сопоставить номер пункта в таблице с его обозначением на графе.
2 тип заданий. Требует не только сопоставить номер с обозначением, но и подсчитать сумму протяжённостей дорог между некоторыми пунктами.
3 тип заданий. Включает в себя действия из двух предыдущих типов. То есть сначала нужно сопоставить номера с обозначениями, затем расставить протяжённость каждой дороги. А в ответ же требуется дать длину кратчайшего пути между двумя пунктами.