Данный раздел курса требует умения устанавливать соответствие между разными типами данных, основными из которых являются таблицы и графы. В задачах этого раздела необходимо уметь преобразовывать таблицы в графы и наоборот.
Граф, взвешенный граф.
Граф (или сетевая модель данных) представляет собой набор вершин, соединенных ребрами, и обычно описывается в виде таблицы, например, матрицы смежности или весовой матрицы.
Взвешенный граф – это граф, в котором каждому ребру присвоен вес, который может обозначать, например, расстояние между городами или стоимость перевозки.
Первичный анализ графов для решения задания №1 ЕГЭ
Во многих задачах, вес ребра указывает на длину пути между двумя вершинами. Степень вершины в графе отображает количество ребер, связанных с ней.
Чтобы определить степень вершины по заданной таблице (например, матрице весов), нужно подсчитать количество ненулевых ячеек в соответствующей строке или столбце.
Например, степень вершины A равна 2, так как в строке A (выделена голубым) есть две ненулевые ячейки со значениями 6 и 9. В некоторых задачах матрица расстояний является симметричной, что означает, что расстояние от вершины A до B равно расстоянию от вершины B до A. Однако, есть задачи, в которых матрица несимметрична.
Типы заданий
- Поиск оптимального маршрута по таблице.
- Однозначное соотнесение таблицы и графа.
- Неоднозначное соотнесение таблицы и графа.
Поиск оптимального маршрута по таблице
Пример типового задания
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Перед решением задания необходимо построить дерево маршрутов, где вершинами являются населенные пункты, а ветвями - расстояния между ними.
Из таблицы следует, что единственный маршрут из пункта A в B имеет длину 4.
Из B можно попасть в C, D, и E.
От В в C - расстояние 6, в D - 3, а в E - 6.
Из C и D можно добраться только в E.
Из E можно дойти до F.
Всего есть 3 маршрута:
- ABCEF (длина 19),
- ABDEF (длина 14)
- и ABEF (длина 15).
Самый короткий маршрут ABDEF имеет длину 14.
Ответ: 14.
Однозначное соотнесение таблицы и графа
Особенность данных заданий в том, что необходимо по данным таблицы и графа, соотнести строки и столбцы таблицы с вершинами графа (сетевой модели). Здесь можно точно определить, для каждой вершины графа конкретную строку и столбец в таблице.
Типовое задание
На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Укажите номера, которые могут соответствовать пунктам Г и Д. В ответе запишите эти номера в порядке возрастания без пробелов и знаков препинания.
Для удобства расчетов и пометок, можно скопировать таблицу из задания в Excel вместе с рисунком графа.
Для подсчета связности вершин, замените символы * на 1 и используйте функцию СЧЕТ, которая позволяет посчитать количество непустых ячеек в указанном диапазоне.
Например, для подсчета связности строки П1, введите в ячейку K3 формулу: =СЧЁТ(B3:J3), и затем размножьте ее для других строк таблицы. Для этого наведите курсор мыши на угол ячейки K3, где находится исходная формула, зажмите левую клавишу мыши и тяните вниз до последней строки.
Мы замечаем, что три вершины имеют связность 2, а именно П1, П4 и П9 (выделены зеленым). А также, что шесть вершин имеют связность 3 (выделены красным).
Обратимся к схеме графа и заметим, что Б, И, Ж имеют связность два. Следовательно, в таблице первая строка соответствует вершине Б, а оставшиеся две вершины степени 2 — это связанные между собой И и Ж.
Мы ищем, какие ячейки в таблице соответствуют Б, И и Ж. Смотрим на схему графа и замечаем, что Б связана с А и В, что соответствует П5 и П6 в таблице.
Далее, И и Ж связаны с Е и К соответственно, что соответствует П2 и П8 в таблице.
Оставшиеся две вершины Г и Д соответствуют П3 и П7. В ответе необходимо записать только их номера: 3 и 7.
Итак, ответ: 37.
Неоднозначное соотнесение таблицы и графа.
Здесь, также как и в предыдущем задании, необходимо определить соответствие вершин графа на рисунке и в таблице. Но, особенность в том, что для многих вершин — это невозможно сделать. Однако, есть вспомогательные условия, помогающие ответить на вопросы заданий.
Пример задания
На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Решение
Для решения задания нужно скопировать таблицу и граф в Excel и заменить звездочки на единицы.
Затем можно использовать функцию СЧЁТ, чтобы посчитать степени вершин графа в таблице.
Из графа можно определить, что вершина F имеет степень 6 и отметить ее в таблице.
Далее, две вершины со степенью 2 (C и E) связаны с F, а также с вершинами D и B.
В таблице это соответствует номерам 1 и 2.
Оставшиеся ячейки под цифрами 6 и 7 соответствуют вершинам G и A.
Ответ: 67.
Высокие результаты ЕГЭ по информатике
Для успешной сдачи ЕГЭ по информатике на высокие баллы необходимы следующие навыки:
- Понимание общей теории информации, такой как системы счисления, измерение и представление информации, передача информации, логические операции, теория множеств и динамическое программирование.
- Умение работать в электронных таблицах, таких как Excel или аналоги.
- Умение работать с текстовыми редакторами, такими как Word или Notepad.
- Компетентное владение одним языком программирования, включая знание основных конструкций, умение составлять алгоритмы и реализовывать их на алгоритмическом языке.
- Умение работать с файлами, понимание того, как они хранятся на диске, а также знание, что такое путь, имя и расширение.
Если вам нужна помощь в подготовке к компьютерному ЕГЭ по информатике, наша школа предлагает небольшие мини-группы до 5 человек, индивидуальный подход и удобный темп освоения материала. У нас также большой опыт в подготовке новичков с нулевыми навыками программирования. Запишитесь сейчас, связавшись со мной в Телеграм, ВКонтакте или оставив заявку на сайте!
(c) Подготовлено по материалам нашей статьи: https://victor-komlev.ru/zadanie-1-ege-po-informatike-informatsionnye-modeli/
