Задания ЕГЭ В-3 и В-15. Моделирование


Чтобы посмотреть презентацию с оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов:

В3:весовые матрицы графов(решение заданий с разбором)МоделированиеЕГЭ: demo версия 2016 г.по К. ПоляковуВремя выполнения базового уровня – 3 минВыполнила учитель первой квалификационной категории информатики и ИКТ МБОУ СОШ №1 г. АзоваБаламутова И.А.2015г. тест «Проверь себя»1. Что такое модель?а) Модель — это некий новый объект, который отражает существенные особенности изучаемого объекта, явления или процесса.б) Модель — это некий объект, который отражает некоторые особенности изучаемого объекта, явления или процесса.в) Модель — это простой объект, который отражает особые признаки изучаемого объекта, явления или процесса.2МБОУ СОШ №1 г. Азова - Баламутова И.А.

тест «Проверь себя»2. Что такое моделирование?а) Моделирование — это метод познания, состоящий в создании и исследовании моделей.б) Моделирование — это способ изучения окружающего мира через создание моделей.в) Моделирование — это способ изучения человека и всего, что с ним связано.3МБОУ СОШ №1 г. Азова - Баламутова И.А.

Элементы моделированияГраф – это средство для наглядного представления состава и структуры системыГраф состоит из вершин, связанных дугами или ребрамиАБВГребро (без стрелки)дуга (со стрелкой)Взвешенный граф, где с каждым ребром связано некоторое число. Оно может обозначать, например, расстояние между городами или стоимость перевозки4МБОУ СОШ №1 г. Азова - Баламутова И.А.







Элементы моделированияВесомая матрица – это таблица с данными к графамABCDЕA31B42C342D1Е22П1П2П3П4П5П6П7П14510П2454055П31560П410402035П51555П65560205545П735455МБОУ СОШ №1 г. Азова - Баламутова И.А. Задача 1.В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.ABCDA45B436C3D561)2)3)4)6МБОУ СОШ №1 г. Азова - Баламутова И.А. РешениеАПерепишем таблицу в следующем виде:пара соседних станций – стоимость перевозок между нимиПоскольку стоимость перевозок между соседними станциями не зависит от направления, движемся в одном направленииВDС4563Рисуем граф с вершинами, которые соединяются ребрамиАВ – 4 АD – 5 ВD – 6 СВ – 3 Ответ: рисунок 4ABCDA45B436C3D567МБОУ СОШ №1 г. Азова - Баламутова И.А.












Задача 2.Определить длину дороги между В и Е.АБВГДЕК{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1234567145102454055315604104020355155565560205545735458МБОУ СОШ №1 г. Азова - Баламутова И.А. Решение{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}123456714510245405531560410402035515556556020554573545Определим по весомой матрице те вершины, которые имеют максимальное количество выходных лучей{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}123456714510245405531560410402035515556556020554573545АБВГДЕКПо столбцу и строке 4 видно, что лучей будет четыре, а это соответствует точкеЕ{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}123456714510245405531560410402035515556556020554573545По столбцу и строке 6 видно, что лучей будет пять, а это соответствует точкеВАБВГДЕК{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}123456714510245405531560410402035515556556020554573545Ответ: 209МБОУ СОШ №1 г. Азова - Баламутова И.А.










Задача 3.На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.ДАБВГЕК10МБОУ СОШ №1 г. Азова - Баламутова И.А. РешениеП1П2П3П4П5П6П7П1302518П21712П33017233415П4122346П52537П6344618П718153718ДАБВГЕКОпределим степени вершин по весовой матрице и по графу3253234Нас интересуют пункты А и Д3253234Есть три вершины с тремя выходящими лучамиП1, П4 и П6Вершина П1 (на графе это точка Г )Не имеет общих рёбер с вершинами П4 и П6 П1П2П3П4П5П6П7П1302518П21712П33017233415П4122346П52537П6344618П718153718Ответ – это длина ребра между вершинами П4 и П6 П1П2П3П4П5П6П7П1302518П21712П33017233415П4122346П52537П6344618П718153718По количеству вершин видно, что П3 – это вершина В, П7 – это вершина Е11МБОУ СОШ №1 г. Азова - Баламутова И.А.










Задача 4.Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.ABCDEFZA4630B3C1127D4710E48F52Z29Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.12МБОУ СОШ №1 г. Азова - Баламутова И.А. РешениеЧисла в таблице нас не интересуют. Достаточно знать, что между данными пунктами есть дорога.ABCDEFZA4630B3C1127D4710E48F52Z29Нужно найти все пути, которые проходят через 6 и более пунктов, считая начальный и конечный (между А и Z должно быть не менее 4 промежуточных пунктов)Перечислим все маршруты из А, которые проходят через 2 пунктаПо таблице видно, что из A можно ехать в B, C и Z234567ABACAZМаршрут AZ нас не интересует. Он проходит менее, чем через 6 пунктовИщем все маршруты, проходящие через 3 пункта.Из B можно ехать только в C, а из С – в D и Z234567ABABCACACDACZAZДалее из C едем в D и Z, а из D – в E, F и Z234567ABABCABCDABCZACACDACDEACDFACDZACZAZСтроим следующий уровень только для тех маршрутов, которые ещё не пришли в Z234567ABABCABCDABCDEABCDFABCDZABCZACACDACDEACDEFACDEZACDFACDFEACDFZACDZACZAZСледующие два уровня дают «интересные» маршруты, проходящие через 6 или 7 пунктов234567ABABCABCDABCDEABCDEFABCDEFZABCDEZABCDFABCDFEABCDFEZABCDFZABCDZABCZACACDACDEACDEFACDEFEACDEFZACDEZACDFACDFEACDFEFACDFEZACDFZACDZACZAZЗелёным выделены «интересные» маршруты, их всего 6. А красным – запрещенные маршруты.ОТВЕТ: 6 маршрутов13















РешениеAABAСAZABCACDACZABCDABCZACDEACDFACDZABCDEABCDZABCDFACDEFACDEZACDFEACDFZABCDEFABCDEZABCDFEABCDFZACDEFEACDEFZACDFEFACDFEZABCDEFZABCDFEZ123456714МБОУ СОШ №1 г. Азова - Баламутова И.А. Задача 5.15Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)ABCDEFA24B217C4134D33E7432F2Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам)МБОУ СОШ №1 г. Азова - Баламутова И.А. Решение16ABCDEFA24B217C4134D33E7432F2Построим граф, соответствующий этой весовой матрицеИз вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4)АВС24Для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветомНапример, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7)Е71Новые маршруты из С – в D и E (длины путей соответственно 3 и 4)D34Новый маршрут из D – в E (длина пути 3)3Новый маршрут из E – в F (длина пути 2)F2Нужно проехать из А в 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МБОУ СОШ №1 г. Азова - Баламутова И.А.



















Задача 6.17Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними: Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО. {3C2FFA5D-87B4-456A-9821-1D502468CF0F}Аэропорт вылетаАэропорт прилетаВремя вылетаВремя прилетаСОСНОВОКРАСНЫЙ06:2008:35КРАСНЫЙОКТЯБРЬ10:2512:35ОКТЯБРЬКРАСНЫЙ11:4513:30БЕРЕГСОСНОВО12:1514:25СОСНОВООКТЯБРЬ12:4516:35КРАСНЫЙСОСНОВО13:1515:40ОКТЯБРЬСОСНОВО13:4017:25ОКТЯБРЬБЕРЕГ15:3017:15СОСНОВОБЕРЕГ17:3519:30БЕРЕГОКТЯБРЬ19:4021:551) 15:40 2) 16:35 3)17:15 4) 17:25 Решение18Сначала определим, есть ли прямой рейс из аэропорта ОКТЯБРЬ в СОСНОВО. Он в 17:25{3C2FFA5D-87B4-456A-9821-1D502468CF0F}Аэропорт вылетаАэропорт прилетаВремя вылетаВремя прилетаСОСНОВОКРАСНЫЙ06:2008:35КРАСНЫЙОКТЯБРЬ10:2512:35ОКТЯБРЬКРАСНЫЙ11:4513:30БЕРЕГСОСНОВО12:1514:25СОСНОВООКТЯБРЬ12:4516:35КРАСНЫЙСОСНОВО13:1515:40ОКТЯБРЬСОСНОВО13:4017:25ОКТЯБРЬБЕРЕГ15:3017:15СОСНОВОБЕРЕГ17:3519:30БЕРЕГОКТЯБРЬ19:4021:55{3C2FFA5D-87B4-456A-9821-1D502468CF0F}Аэропорт вылетаАэропорт прилетаВремя вылетаВремя прилетаСОСНОВОКРАСНЫЙ06:2008:35КРАСНЫЙОКТЯБРЬ10:2512:35ОКТЯБРЬКРАСНЫЙ11:4513:30БЕРЕГСОСНОВО12:1514:25СОСНОВООКТЯБРЬ12:4516:35КРАСНЫЙСОСНОВО13:1515:40ОКТЯБРЬСОСНОВО13:4017:25ОКТЯБРЬБЕРЕГ15:3017:15СОСНОВОБЕРЕГ17:3519:30БЕРЕГОКТЯБРЬ19:4021:55Посмотрим, сможет ли путешественник оказаться в СОСНОВО раньше этого времени, если полетит через другой аэропорт, с пересадкойМожно лететь, через КРАСНЫЙ, но, как следует из расписанияОктябрь Красный 11:45 13:30Красный Сосново 13:15 15:40Путешественник не успеет на рейс КРАСНЫЙ – СОСНОВО, который улетает в 13:15, то есть на 15 минут раньше, чем в КРАСНЫЙ прилетает самолет ОКТЯБРЬ – КРАСНЫЙМожно лететь через БЕРЕГБерег Сосново 12:15 14:25Октябрь Берег 15:30 17:15Но рейс БЕРЕГ – СОСНОВО вылетает даже раньше, чем рейс ОКТЯБРЬ – БЕРЕГ, то есть, пересадка не получитсяПоскольку даже перелеты с одной пересадкой не стыкуются по времени, проверять варианты с двумя пересадками в данной задаче бессмысленноТаким образом, правильный ответ – 4 (прямой рейс)











Задачи для самостоятельной работы19Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)ABCDEFA24516B23C43D53323E28F1638Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт Е и не проходящего через пункт B(при условии, что передвигаться можно только по построенным дорогам).МБОУ СОШ №1 г. Азова - Баламутова И.А. Задачи для самостоятельной работы20Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нетКурьеру требуется проехать из A в Z, посетив не менее 6 населённых пунктов. Пункты A и Z при подсчёте учитываются, два раза проходить через один пункт нельзя. Какова наименьшая возможная длина маршрута курьера? В ответе запишите натуральное число – длину минимального маршрута.ABCDEFZA4630B38C111027D4310E41F2Z29 В15:графы. поиск количества путей(решение заданий с разбором)МоделированиеЕГЭ: demo версия 2016 г.по К. ПоляковуВремя выполнения повышенного уровня – 3 минМБОУ СОШ №1 г. Азова - Баламутова И.А. Элементы моделирования22Если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то естьгде обозначает число путей из вершины A в некоторую вершину Q Число путей конечно, если в графе нет циклов – замкнутых путейМБОУ СОШ №1 г. Азова - Баламутова И.А. Задача 1.23На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город В?АБГДBЖЕИКММБОУ СОШ №1 г. Азова - Баламутова И.А. Решение24Проведём сечение графа через вершину ВАБГДBЖЕИКМЕсли мы перешли через линию сечения из левой части в правую по ребру ГЕ или через вершину Ж, мы уже никак не попадём в вершину В так, чтобы все вершины, из которых можно попасть в В, оказались слева от линии сеченияВ данном случае выбрасывается вершина Ж, все связанные с ней рёбра, и ребро ГЕАБГДBЕИКМА дальше начинаем считать число входящих путей в каждую вершину от А, через В к М1611134484Ответ: 16














Задача 2.25На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?АБВГДЕЖИКЛМБОУ СОШ №1 г. Азова - Баламутова И.А. Решение26Для города А есть только один маршрут – никуда не двигатьсяНачнем считать количество путей с начала маршрута – с города ААБВГДЕЖИКЛ1111Из А выходим в трёх направлениях Б, В и ГВ эти вершины приходит по одному пути.А дальше считаем пути, встречающиеся в вершинах до точки Л11311113143141144444113













27На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?ГВАДЗБЕЖИКЗадачи для самостоятельной работыМБОУ СОШ №1 г. Азова - Баламутова И.А. 28Задачи для самостоятельной работыНа рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?АБВГЕКЗЖДИ Спасибоза внимание29МБОУ СОШ №1 г. Азова - Баламутова И.А. Верно Неверно Верно Неверно

Приложенные файлы