Задание 1 ЕГЭ по информатике. Информационные модели

В заданиях этого раздела курса требуется установить соответствие между разными форматами данных, основными из которых являются таблицы и графы.

При решении задач на эту тему необходимо уметь преобразовывать таблицы в схемы и наоборот.

Граф (сетевая модель данных)

Граф представляет собой набор вершин, соединенных ребрами, и чаще всего описывается в виде таблицы, например, матрицы смежности или весовой матрицы.

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

Особенности анализа графов в решении задания №1 ЕГЭ

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

Степень вершины в графе представляет собой количество ребер, соединенных с ней.

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

Например, степень вершины А равна 2, так как в строке А (выделена голубым) есть две ненулевые ячейки со значениями 6 и 9

В данном примере, матрица расстояний симметрична. То есть, расстояние из пункта F в G равно расстоянию из G в F (11). Но, имеются задания с несимметричной матрицей.

Типы заданий

1. Поиск оптимального маршрута по таблице.
2. Однозначное соотнесение таблицы и графа.
3. Неоднозначное соотнесение таблицы и графа.

Поиск оптимального маршрута по таблице

Пример типового задания

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение задания

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

Исходя из данных таблицы, из пункта А в пункт В есть единственный маршрут длиной 4.

Из пункта B можно вернуться в A (что не имеет смысла, так как это удлинит маршрут), а также добраться до C, D, E. Из B в C, расстояние 6, в D — 3, а в E — 6.

Из пунктов C и D можно добраться только в E:

Из пункта E можно добраться в пункт F

Получилось 3 маршрута: ABCEF (длина 19), ABDEF (длина 14) и ABEF (15). Самый короткий маршрут — ABDEF длиной 14.

Ответ: 14.

Однозначное соотнесение таблицы и графа

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

Типовое задание

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

Решение

Скопируем таблицу из задания в Excel вместе с рисунком графа. Это поможет нам быстро посчитать связность вершин, делать пометки (называть вершины) и выделять цветом промежуточные вычисления.

Чтобы посчитать связность вершин в таблице, заменим символы * на 1. Для этого, выделим таблицу (обязательно без названий строк и столбцов!!!) нажмем Ctrl+H и сделаем замену (жмем «Заменить всё»):

Теперь вместо символов *, у нас стоят 1, и мы можем приступать к подсчету связности вершин. Для этого, будем использовать функцию СЧЕТ.

Функция СЧЕТ (ДИАПАЗОН1; ДИАПАЗОН2; ДИАПАЗОН3…), позволяет посчитать количество непустых ячеек в указанных диапазонах.

Посчитаем связность для строки П1. Для этого введем в ячейку K3 формулу: =СЧЁТ(B3:J3)

Размножим данную формулу для других строк таблицы. Для этого необходимо навести курсор мыши на угол ячейки K3 (где находится исходная формула).

Курсор сменится на значок черного крестика (как на рисунке)

После этого, зажимаем левую клавишу мыши и не отпуская, тянем вниз до самой последней строки (ячейки K11).

Результат подсчетов можно посмотреть на рисунке ниже:

Видим, что три вершины имеют связность 2 (выделены зеленым). Это П1, П4 и П9. И шесть вершин имеют связность 3 (выделены красным).

Посмотрим на нашу схему графа. По ней четко видно, что три вершины, имеющие связность два — это Б, И, Ж

Отметим это в таблице:

Еще раз посмотрим на схему графа. Можно увидеть, что вершины Ж и И вязаны друг с другом. Найдем в таблице, какие из ячеек Б, И, Ж связаны друг с другом.

Следовательно, вершина в первой строке таблицы — это Б, а оставшиеся вершины степени 2 — это связанные между собой И и Ж. Отмечаем это в таблице

Снова смотрим на граф, и с какими вершинами связана Б. Это А и В. В таблице — это ячейки П5 и П6. Исправляем их название.

Смотрим на графе, с какими вершинами связаны И и Ж. Это Е и К. В таблице  — это П2 и П8. Исправляем.

Очевидно, что две оставшиеся до сих пор неизвестными вершины Г и Д, соответствуют данным П3 и П7 таблицы. В ответе необходимо записать только их номера: 3 и 7:

Ответ: 37

Неоднозначное соотнесение таблицы и графа.

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

Пример задания

На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Решение задания

Копируем таблицу и граф в Excel, делаем замену звездочек на символы «1». Как это сделать, описано в предыдущем решении.

Считаем степени вершин графов в таблице через функцию СЧЁТ.

Одна из вершин имеет степень 6 (выделена красным). По рисунку, определяем, что это вершина F. Отмечаем ее в таблице:

Две вершины (4 и 5) имеют степень 2. На графе мы видим, что  — это C и E.

Обе эти вершины (C, E) соединены с вершиной F, а также с вершинами D, B.

В таблице, им соответствуют номера 1 и 2.

Оставшиеся ячейки, которые идут под цифрами 6 и 7 таблицы — это G и A.

Это и есть ответ на задачу. Вершинам A, G соответствуют ячейки 6 и 7 таблицы.

Ответ: 67

Видеорешение задачи 1 ЕГЭ по информатике

Для тех, кто не любит читать, видео с нашего канала. Подписывайтесь!

Подготовиться к ЕГЭ с репетитором

Чтобы сдать ЕГЭ по информатике на высокие баллы, нужно владеть следующими навыками:

1. Общая теория информации: системы счисления, измерение информации, представление информации, передача информации, логические операции, теория множеств, динамическое программирование.
2. Уметь работать в электронных таблицах: Excel или аналоги
3. Уметь работать с текстовыми редакторами: Word, Notepad
4. Уверенно владеть одним языком программирования: знать основные конструкции, уметь составлять алгоритмы и реализовывать их на алгоритмическом языке.
5. Уметь работать с файлами, представлять как они хранятся на диске, понимать что такое путь, имя и расширение.

Наша школа готова помочь вам с подготовкой к компьютерному ЕГЭ по информатике. Небольшие мини-группы по 5 человек, индивидуальный подход и темп освоения материала. У нас большой опыт подготовки новичков с нулевыми навыками программирования. Записывайся:

• Пиши мне в Телеграм
• Вконтакте
• Или оставляй заявку на сайте!