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

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

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

Таблица и граф
Пример соответствия между таблицей и графом

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

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

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

Пример взвешенного графа

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

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

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

Граф со связанными вершинами
Граф со связанными вершинами

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

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

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

Связанная с графом таблица
Связанная с графом таблица

Типы заданий

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

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

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

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

Пример задания 1. Расчет кратчайшего расстояния по таблице

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

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

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

Анализ таблицы шаг 1

Из пункта A в B
Дерево маршрутов из A в B

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

Маршруты из пункта B

Из пункта B
Маршруты из пункта B

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

Маршруты из C и D

Из пунктов C D E

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

Маршрут из E

Дерево решений определения кратчайших расстояний
Дерево решений определения кратчайших расстояний

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

Ответ: 14.

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

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

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

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

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

Решение

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

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

 

Замена в таблице расстояний

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

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

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

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

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

Вид курсора при копировании формулы

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

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

Подсчет связности вершин графа

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

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

Связность вершин на графе

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

Отмечаем вершины в таблице 1

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

Связанные вершины графа

Определение связных вершин в таблице

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

Вторая итерация определения вершин

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

Связи вершины Б

Третья итерация определения вершин графа

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

Связи вершин ЖИ

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

Последняя итерация

Ответ: 37

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

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

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

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

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

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

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

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

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

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

Неоднозначное соотнесение таблицы и графа. Итерация 2. СЧЕТ

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

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

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

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

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

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

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

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

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

Ответ: 67

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

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

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

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

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

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

 

Понравилась статья? Поделиться с друзьями:
Школа Виктора Комлева
Комментарии: 6
  1. Александр

    В задаче на «Однозначное соотнесение таблицы и графа» не ошибка — ли в ответе? Не 27 вместо 37? :?:
    Благодарю за ответ.

  2. Александр

    Виноват! 28 вместо 37. :oops:

  3. Александр

    Приношу свои извинения. Я был неправ: Ваш ответ верен. С уважением, Александр.

Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.