Погода
Календарь
Январь 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123456
78910111213
14151617181920
21222324252627
28293031  
Страницы сайта

Анализ информационных моделей.

Структурирование информации — это установление главных элементов в информационных сообщениях и установление связей между ними.

Структурирование выполняется с целью облегчения восприятия и поиска информации.

Структурирование возможно при помощи следующих структур (информационных моделей):

множество:

перечисление элементов, собранных по характерному признаку;

Вася, Петя, Коля
1, 17, 22, 55

В множестве упорядочивание элементов не обязательно, т. е. порядок следования не важен.

линейный список, для решения 3 задания ЕГЭ

линейный список

Важна упорядоченность следования элементов.

таблица

таблица

В таблицах выделяются объекты (отдельные записи таблиц) и свойства (названия столбцов или названия строк):
дерево или иерархия объектов

 Уровни в дереве

Уровни в дереве

Рассмотрим родственные отношения в дереве:

дерево

«Сыновья» А: B, C.
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G.
«Предки» F: A, C.

Корень – узел без предков (A).
Лист – узел без потомков (D, E, F, G).
Высота – наибольшее расстояние от корня до листа (количество уровней).

файловая система

файловая система (иерархия)

Допустим, на жестком диске компьютера имеются следующие папки (каталоги) с файлами:

Получим дерево:

дерево файлов


Графы

Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. Тогда можно использовать графы:

Граф – это набор вершин и связей между ними, называющихся рёбрами:

Граф

Граф, отображающий дороги между поселками матрица и список смежности

матрица и список смежностей

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

Связный граф

Связный граф
Дерево – это связный граф без циклов (замкнутых участков).

Дерево - связный граф без циклов

Дерево — связный граф без циклов

взвешенные графы и весовая матрица

У взвешенных графов указан «вес ребра»:

взвешенный граф


Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.

Весовая матрица

Весовая матрица

ПОИСК КРАТЧАЙШЕГО ПУТИ (ПЕРЕБОР)

кратчайший путь

Определение кратчайшего пути между пунктами A и D

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

Решение заданий:

Задание 1. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.  Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

Решение:

  1. для того чтобы определить нужные нам вершины В и Е в весовой матрице, легче всего подсчитать степени вершин, то есть для каждой вершины найти количество рёбер, с которыми она связана (петля – ребро, которое соединяет вершину саму с собой, как кольцевая дорога, считается дважды)
  2. в весовой матрице степень вершины – это количество непустых клеток в соответствующей строке (показаны справа от таблицы на жёлтом фоне), а для изображения графа- количество пересечений небольшой окружности, проведённой около вершины, со всеми рёбрами:
  • по изображению графа находим, что вершина В имеет степень 5, а вершина Е – степень 4
  • в таблице есть ровно одна вершина, степень которой 5 (это П6) и одна вершина, степень которой – 4 (П4), их соединяет ребро длиной 20 (эти ячейки выделены в весовой  матрице фиолетовым фоном).

Ответ:  20.

Попытаемся теперь определить, как обозначены остальные вершины в таблице. Каждая из вершин Д (степени 2)  и Г (степени 3)  соединена с уже известными вершинами В и Е, по таблице находим, что вершина Д – это П7, а вершина Г – это П2. Тогда вершина К соединяется с Е (П4) и Г (П2), то есть К – это П1. А вот различить вершины А и Б по этим данным не удаётся.

Задание 2. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.

Решение:

  1. определим степени вершин по весовой матрице и по изображению графа (как в предыдущей задаче):
  • по изображению графа находим, что обе интересующих нас вершины, А и Д, имеют степени 3; кроме того, степень 3 имеет еще и вершина Г
  • в таблице тоже есть три вершины со степенью 3 (это П1, П4 и П6), но вершина П1 (это вершина Г на рисунке!) не имеет общих ребёр с вершинами П4 и П6 (а это А и Д!);
  • таким образом, ответ – это длина ребра между вершинами П4 и П6 (эти ячейки выделены в весовой  матрице фиолетовым фоном).

Ответ:  46.

Определим вершины В и Е, имеющие степени 5 и 4, это П3 и П7; с вершиной Г (П1) связана ещё вершина К, имеющая степень 2 – это П5; с Е связана ещё вершина Д – это П6; тогда П4 – это А, а П2 – это Б.

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

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.

      Решение:

  1. поскольку нас интересуют только маршруты, НЕ проходящие через пункт В, столбец и строку, соответствующие этому пункту, можно удалить из таблицы:
  • дальше действуем так же, как показано при решении следующих далее разобранных задач; причем из всех маршрутов нужно оставить только те, которые проходят через пункт Е
  • первый шаг от А (в скобках указаны длины маршрутов):

АС (4), AD (8)

прямой маршрут AF не рассматриваем, потому что он не проходит через пункт E

  • второй шаг

ACD (7), ADC (11), ADE (13)

маршрут ADF не рассматриваем, потому что он не проходит через пункт E

  • третий шаг:

ACDE (12), ADEF (18)

маршрут ADEF дошел до пункта назначения;

маршрут ADC продолжать не имеет смысла, потому что из C можно проехать только в пункты A и D, где мы уже были;

маршрут ACDF не рассматриваем, потому что он не проходит через пункт E

  • четвертый шаг:

ACDEF(17)

  • этот маршрут тоже дошел до пункта назначения, его длина меньше, чем для предыдущего, его и выбираем

Ответ: 17.

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

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение (вариант 1, использование схемы):

  1. построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):
  • для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее
  • например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):
  • новые маршруты из С – в D и E (длины путей соответственно 3 и 4):
  • новый маршрут из D – в E (длина пути 3):
  • новый маршрут из E – в F (длина пути 2):
  • нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E
  • попробуем перечислить возможные маршруты из А в Е:

А – В – Е       длина 9

А – В – С – Е      длина 7

А – В – C – D – Е        длина 9

А –C – Е        длина 8

А –C – B – Е       длина 12

А –C – D – Е      длина 10

  • из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9
  • таким образом, правильный ответ – 9.

Задание 5. На рисунке справа схема дорог Н-ского района изображена в виде графа. В таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).

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

Решение: Строке П5 должна соответствовать вершина из которой выходит 4 дуги. Такой вершиной является В
П5 — В

Строке П6 должна соответствовать вершина из которой выходит 2 дуги.

Такой вершиной является А
П6 — А

Дороги из пункта А ведут в пункт Б и пункт В. Очевидно что из пункта А в пункт В протяженность 7 км, следовательно в пункт Б – 5 км.

Значит строке П1 соответствует вершина Б.
П1 — Б

В задании требуется определить длину дороги из пункта Б в пункт В.
По таблице определяем что путь из Б в В равен 8.

Ответ: 8

Решение 1: Проанализируем граф и таблицу:

  • Единственная вершина в графе имеет 4 дороги — это В. В таблице — это П5, т.к. только у этой вершины есть 4 связи.
  • Единственная вершина имеет две дороги — это А, а в таблице — это П6.
  • Пункты П1, П2, П4 имеют по 3 дороги, один из этих пунктов — Б. Так как из этих трёх пунктов, только П1 связан с П6 (вершиной А), то это и есть вершина Б.
  • Расстояние между вершинами Б(П1) и В(П5) равно 8. Ответ: 8

1) 15:40       2) 16:35             3)17:15           4) 17:25

Решение:

  1. сначала заметим, что есть прямой рейс из аэропорта ОКТЯБРЬ в СОСНОВО с прибытием в 17:25:

          ОКТЯБРЬ          СОСНОВО                13:40               17:25

  • посмотрим, сможет ли путешественник оказаться в СОСНОВО раньше этого времени, если полетит через другой аэропорт, с пересадкой
  • можно лететь, через КРАСНЫЙ, но, как следует из расписания,

          ОКТЯБРЬ          КРАСНЫЙ                11:45               13:30

                 …

         КРАСНЫЙ         СОСНОВО                13:15               15:40

путешественник не успеет на рейс КРАСНЫЙ – СОСНОВО, который улетает в 13:15, то есть на 15 минут раньше, чем в КРАСНЫЙ прилетает самолет ОКТЯБРЬ – КРАСНЫЙ

  • можно лететь через БЕРЕГ,

             БЕРЕГ             СОСНОВО                12:15               14:25

                 …

          ОКТЯБРЬ              БЕРЕГ                    15:30               17:15

но рейс БЕРЕГ – СОСНОВО вылетает даже раньше, чем рейс ОКТЯБРЬ – БЕРЕГ, то есть, пересадка не получится

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

Решение (вариант 2, граф):

  1. для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ
  2. из аэропорта ОКТЯБРЬ есть три рейса:

          ОКТЯБРЬ          СОСНОВО                13:40               17:25

          ОКТЯБРЬ          КРАСНЫЙ                11:45               13:30

          ОКТЯБРЬ              БЕРЕГ                    15:30               17:15

  • построим граф, около каждого пункта запишем время прибытия
  • проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс  «БЕРЕГ-СОСНОВО», вылетающий в 12:15
  • таким образом, правильный ответ – 4 (прямой рейс).

Задание 7. Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда  из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими  соседними станциями.

Решение (вариант 1):

  1. нужно рассматривать все маршруты из А в В, как напрямую, так и через другие станции
  2. рассмотрим таблицу 1:

из верхней строки таблицы следует, что из А в В напрямую везти нельзя, только через C (стоимость перевозки А-С равна 3) или через D (стоимость перевозки из А в D равна 1)

  • предположим, что мы повезли через C; тогда из третьей строки видим, что из C можно ехать в В, и стоимость равна 4
  • таким образом общая стоимость перевозки из А через С в В равна 3 + 4 = 7
  • кроме того, из С можно ехать не сразу в В, а сначала в Е:

а затем из Е – в В (стоимость также 2),

так что общая стоимость этого маршрута равна 3  + 2 + 2 = 7

  • теперь предположим, что мы поехали из А в D (стоимость 1); из четвертой строки таблицы видим, что из D можно ехать только обратно в А, поэтому этим путем в В никак не попасть:
  • таким образом, для первой таблицы минимальная стоимость перевозки между А и В равна 7; заданное условие «не больше 6» не выполняется
  • аналогично рассмотрим вторую схему; возможные маршруты из А в В:
  • , стоимость 7
  • , стоимость 7
  • таким образом, минимальная стоимость 7, условие не выполняется
  • для третьей таблицы:
  • , стоимость 7
  • , стоимость 6
  • , стоимость 7
  • таким образом, минимальная стоимость 6, условие выполняется
  • для четвертой:
  • , стоимость 9
  • , стоимость 8
  • минимальная стоимость 8, условие не выполняется
  • условие «не больше 6» выполняется только для таблицы 3
  • таким образом, правильный ответ – 3.

     Решение (вариант 2, с рисованием графа):

За­да­ние 8. Пу­те­ше­ствен­ник при­шел в 08:00 на ав­то­стан­цию по­сел­ка

ЛЕС­НОЕ и уви­дел сле­ду­ю­щее рас­пи­са­ние ав­то­бу­сов:

От­прав­ле­ние из При­бы­тие в Время от­прав­ле­ния Время при­бы­тия
Лес­ное Озер­ное 07:45 08:55
Лу­го­вое Лес­ное 08:00 09:10
По­ле­вое Лес­ное 08:55 11:25
По­ле­вое Лу­го­вое 09:10 10:10
Лес­ное По­ле­вое 09:15 11:45
Озер­ное По­ле­вое 09:15 10:30
Лес­ное Лу­го­вое 09:20 10:30
Озер­ное Лес­ное 09:25 10:35
Лу­го­вое По­ле­вое 10:40 11:40
По­ле­вое Озер­ное 10:45 12:00

Опре­де­ли­те самое ран­нее время, когда пу­те­ше­ствен­ник смо­жет ока­зать­ся в пунк­те ПО­ЛЕ­ВОЕ со­глас­но этому рас­пи­са­нию.

1) 10:30                2) 11:25             3) 11:40            4) 11:45

По­яс­не­ние.

Пу­те­ше­ствен­ник не может уехать рань­ше того, как он пришёл, т. е. рань­ше 8-00. За­ме­тим, что есть пря­мой рейс из посёлка ЛЕС­НОЕ в ПО­ЛЕ­ВОЕ с при­бы­ти­ем в 11:45.

Но можно по­ехать с пе­ре­сад­кой: ЛЕС­НОЕ-ЛУ­ГО­ВОЕ (9-20 — 10-30), затем ЛУ­ГО­ВОЕ-ПО­ЛЕ­ВОЕ (10-40 — 11-40), причём на пе­ре­сад­ку у пу­те­ше­ствен­ни­ка есть 10 минут. Ответ: 3

За­да­ние 9. Транс­порт­ная фирма осу­ществ­ля­ет гру­зо­пе­ре­воз­ки раз­ны­ми ви­да­ми транс­пор­та между че­тырь­мя го­ро­да­ми: ЧЕ­РЕ­ПО­ВЕЦ, МОСКВА, КУРСК, ПЕРМЬ. Сто­и­мость до­став­ки гру­зов и время в пути ука­за­ны в таб­ли­це:

Пункт от­прав­ле­ния Пункт на­зна­че­ния Сто­и­мость (у. е.) Время в пути
Москва Пермь 100 70
Москва Курск 30 10
Москва Че­ре­по­вец 50 15
Пермь Москва 100 69
Че­ре­по­вец Пермь 140 80
Че­ре­по­вец Москва 50 15
Че­ре­по­вец Курск 100 80
Курск Пермь 60 40
Курск Москва 30 10
Курск Че­ре­по­вец 100 80
Курск Че­ре­по­вец 90 100

Опре­де­ли­те марш­рут наи­бо­лее де­ше­во­го ва­ри­ан­та до­став­ки груза из ЧЕ­РЕ­ПОВ­ЦА в ПЕРМЬ. Если таких марш­ру­тов не­сколь­ко, в от­ве­те ука­жи­те наи­бо­лее вы­год­ный по вре­ме­ни ва­ри­ант.

1) ЧЕ­РЕ­ПО­ВЕЦ – ПЕРМЬ

2) ЧЕ­РЕ­ПО­ВЕЦ – КУРСК – ПЕРМЬ

3) ЧЕ­РЕ­ПО­ВЕЦ – МОСКВА – ПЕРМЬ

4) ЧЕ­РЕ­ПО­ВЕЦ – МОСКВА – КУРСК – ПЕРМЬ

По­яс­не­ние.

1) ЧЕ­РЕ­ПО­ВЕЦ – ПЕРМЬ: сто­и­мость 140, время 80

2) ЧЕ­РЕ­ПО­ВЕЦ – КУРСК – ПЕРМЬ: сто­и­мость 100 + 60 = 160, время 80 + 40 = 120

3) ЧЕ­РЕ­ПО­ВЕЦ – МОСКВА – ПЕРМЬ: сто­и­мость 50 + 100 = 150, время 15 + 70 =85

4) ЧЕ­РЕ­ПО­ВЕЦ – МОСКВА – КУРСК – ПЕРМЬ: сто­и­мость 50 + 30 + 60 = 140, время 15 + 10 + 40 = 65

Ва­ри­ан­ты 1 и 4 имеют оди­на­ко­во ми­ни­маль­ную сто­и­мость 140 (140 < 150 < 160), но ва­ри­ант 4 более вы­го­ден по вре­ме­ни 65 < 80.

Ответ: 4

Top