A10 (базовый уровень, время – 2 мин)

Тема: Использование информационных моделей (таблицы, диаграммы, графики).
Перебор вариантов, выбор лучшего по какому-то признаку.

Что нужно знать:

· в принципе, особых дополнительных знаний, кроме здравого смысла и умения перебирать варианты (не пропустив ни одного!) здесь, как правило, не требуется

· полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания

· чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки

· рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет

	A	B	C	D	Е
A
B
C
D
Е

· обратите внимание, что граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее

· в приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так)

· желательно научиться быстро (и правильно) строить граф по весовой матрице и наоборот

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

Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

Аэропорт вылета Аэропорт прилета Время вылета Время прилета

СОСНОВО КРАСНЫЙ 06:20 08:35

КРАСНЫЙ ОКТЯБРЬ 10:25 12:35

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

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

СОСНОВО ОКТЯБРЬ 12:45 16:35

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

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

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

СОСНОВО БЕРЕГ 17:35 19:30

БЕРЕГ ОКТЯБРЬ 19:40 21:55

Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО.

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

Решение:

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

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

2) посмотрим, сможет ли путешественник оказаться в СОСНОВО раньше этого времени, если полетит через другой аэропорт, с пересадкой

3) можно лететь, через КРАСНЫЙ, но, как следует из расписания,

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

…

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

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

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

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

…

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

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

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

6) таким образом, правильный ответ – 4 (прямой рейс).

Возможные ловушки и проблемы: · можно не заметить, что путешественник не успеет на пересадку в КРАСНОМ (неверный ответ 15:40) · можно перепутать аэропорты вылета и прилета (неверный ответ 16:35)

Еще пример задания:

Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. При этом длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час.

1) 1 час 2) 1,5 часа 3)3,5 часа 4) 4 часа

Решение:

1) нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе):

2) разделив числитель на знаменатель, получим время движения по каждой дороге

3) ехать из А в B можно

· напрямую, это займет 4 часа, или …

· через пункт C, это займет 1 час по шоссе (из А в С) и 2,5 часа по грунтовой дороге
(из В в С), всего 1 + 2,5 = 3,5 часа

4) таким образом, правильный ответ – 3.

Возможные ловушки и проблемы: · можно не заметить, что требуется найти минимальное время поездки именно в В, а не в С (неверный ответ 1 час) · можно ограничиться рассмотрением только прямого пути из А в В и таким образом получить неверный ответ 4 часа · можно неправильно нарисовать схему

Еще пример задания:

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

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D	Е
A
B
C
D
Е

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

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

2) рассмотрим таблицу 1:

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

	A	B	C	D	Е
A

· предположим, что мы повезли через C; тогда из третьей строки видим, что из C можно ехать в В, и стоимость равна 4

	A	B	C	D	Е
C

· таким образом общая стоимость перевозки из А через С в В равна 3 + 4 = 7

· кроме того, из С можно ехать не сразу в В, а сначала в Е:

	A	B	C	D	Е
C

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

	A	B	C	D	Е
Е

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

· теперь предположим, что мы поехали из А в D (стоимость 1); из четвертой строки таблицы видим, что из D можно ехать только обратно в А, поэтому этим путем в В никак не попасть:

	A	B	C	D	Е
D

· таким образом, для первой таблицы минимальная стоимость перевозки между А и В равна 7; заданное условие «не больше 6» не выполняется

3) аналогично рассмотрим вторую схему; возможные маршруты из А в В:

· , стоимость 7

· таким образом, минимальная стоимость 7, условие не выполняется

4) для третьей таблицы:

· , стоимость 7

· , стоимость 6

· , стоимость 7

· таким образом, минимальная стоимость 6, условие выполняется

5) для четвертой:

· , стоимость 9

· , стоимость 8

· минимальная стоимость 8, условие не выполняется

6) условие «не больше 6» выполняется только для таблицы 3

7) таким образом, правильный ответ – 3.

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

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

1) для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D	Е
A
B
C
D
Е

2) теперь по схемам определяем кратчайшие маршруты для каждой таблицы:

1: или , стоимость 7

2: или , стоимость 7

3: , стоимость 6

4: , стоимость 8

8) условие «не больше 6» выполняется только для таблицы 3

9) таким образом, правильный ответ – 3.

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

Задачи для тренировки[1]:

	A	B	C	D
A
B
C
D

1) В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

1)	2)	3)	4)

2) В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не соединены автомагистралями. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 5». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом любой населенный пункт должен встречаться на маршруте не более одного раза.

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

3) В таблице приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите таблицу, для которой выполняется условие «Минимальная стоимость перевозки грузов от пункта А до пункта В не больше 3».

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D	Е
A
B
C
D
Е

	A	B	C	D
A
B
C
D

4) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую.

1)	2)	3)	4)

5) В таблицах приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 5».

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

6) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.

1)	2)	3)	4)

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

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

	A	B	C	D
A
B
C
D

[1] Источники заданий:

1. Демонстрационные варианты ЕГЭ 2004-2009 гг.

2. Гусева И.Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. — СПб: Тригон, 2009.