Теперь любой учитель или репетитор может отслеживать результаты своих учеников по всей группе или классу.
Для этого нажмите ниже на кнопку «Создать класс», а затем отправьте приглашение всем заинтересованным.
Ознакомьтесь с подробной видеоинструкцией по использованию модуля.
На уроке рассматривается решение 13 задания ЕГЭ по информатике
13-е задание: «Информационные модели»
Требуется использование специализированного программного обеспечения
Примерное время выполнения
— 3 минуты.
Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)
До ЕГЭ 2021 года — это было задание № 15 и № _ ЕГЭ
Типичные ошибки и рекомендации по их предотвращению:
«Игнорирование указаний в условии задания, что путь должен включать (или не включать) заданные промежуточные вершины»
ФГБНУ «Федеральный институт педагогических измерений»
Графы. Поиск количества путей
NR = NX + NY + NZ
Решение заданий 13 ЕГЭ по информатике
Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?
М = И + Е + К
——
И = Е
Е = Г + Ж
Г = Б + А + Д = 1 + 1 + 1 = 3
Ж = Г = 3
К = Е + Ж
Теперь возвращаемся, подставляя найденные значения: ↑
Е = Г + Ж = 3 + 3 = 6
Ж = Г = 3
И = Е = 6 (получили из последующих шагов)
К = Е + Ж = 6 + 3 = 9
М = И + Е + К = 6 + 6 + 9 =
Видео ЕГЭ по информатике (аналитическое решение):
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
Сколько существует различных путей, ведущих из города А в город М и не проходящих через город Г?
М = И + Е + К
——
И = В + Е
В = 1
Е = В + Ж
Ж = 1
Теперь возвращаемся, подставляя найденные значения: ↑
Е = В + Ж = 1 + 1 = 2
И = В + Е = 1 + 2 = 3
К = Е = 2
М = И + Е + К = 3 + 2 + 2 =
Подробное решение данного 13 задания в видеоуроке:
13 задание. Демоверсия ЕГЭ 2018 информатика:
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.Какова длина самого длинного пути из города А в город М?
Длиной пути считать количество дорог, составляющих этот путь.
1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения
Простейшие задачи на графы
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Е?
Заметим, что количество путей в город Е является суммой путей в города Ж, Г и Д. Количество путей в город Ж — сумма путей в города Г и Б. Таким образом получаем:
Г = Б + В
Д = Г + В
Ж = Б + Г
Е = Ж + Г + Д
Заметим, что в пункты Б и В можно попасть единственным способом — из города А. Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
Заметим, что количество путей в город Ж является суммой путей в города Д, Г и Е. Количество путей в город Г — сумма путей в город В, Б и Е. Таким образом получаем:
Г = Б + В + Е
Д = В + Г
Ж = Д + Г + Е
Заметим, что в пункты Б, В и Е можно попасть единственным способом — из города А. Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое.
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Найдём все варианты маршрутов из A в E и выберем самый короткий.
Из пункта A можно попасть в пункты B, D.
Из пункта B можно попасть в пункты C, D.
Из пункта C можно попасть в пункты D, E.
A—B—C—E: длина маршрута 7 км.
A—D—B—C—E: длина маршрута 9 км.
A—D—C—E: длина маршрута 6 км.
Самый короткий путь: A—D—C—E. Длина маршрута 6 км.
Геральт спешит выручить Цири из плена Кагыра. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого короткого участка кратчайшего пути от Геральта до Цири (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:
Найдём все варианты маршрутов из И в М и выберем самый короткий.
Из пункта И можно попасть в пункты А, Б, Г, М.
Из пункта Г можно попасть в пункты И, М.
Из пункта В можно попасть в пункты А, Б.
Из пункта Б можно попасть в пункты В, И, М.
И—А—В—Б—М: длина маршрута 7 км.
И—Б—М: длина маршрута 4 км.
И—Г—М: длина маршрута 7 км.
И—М: длина маршрута 8 км.
Самый короткий путь: И—Б—М. Длина маршрута 4 км. Самый короткий участок этого пути равен 1 км.
На схеме нарисованы дороги между четырьмя населёнными пунктами A, B, C, D и указаны протяжённости данных дорог.
Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами.
Заметим, что наиболее удалены друг от друга пункты A и D. Найдём все варианты маршрутов из A в D и выберем самый короткий.
A—B—D: длина маршрута 13 км.
A—C—D: длина маршрута 15 км.
A—B—C—D: длина маршрута 23 км.
A—C—B—D: длина маршрута 17 км.
Заметим, что кратчайшее расстояние между пунктами A и D равняется 13.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Начнем считать количество путей с конца маршрута — с города К. Пусть NX — количество различных путей из города А в город X, N — общее число путей.
В К можно приехать из Е, В, Г или Ж, поэтому N = NК = NЕ + NВ + N Г + NЖ (*).
NЕ = NБ + NВ = 1 + 2 = 3;
NЖ = NД = 1;
NВ = NА + NБ = 1 + 1 = 2;
NГ = NА + NД = 1 + 1 = 2;
NД = NА = 1;
NБ = NА = 1.
Подставим в формулу (*): N = 3 + 2 + 2 + 1 = 8.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Проанализируем некоторые возможные маршруты.
Маршрут B—D—E, длина 11 км.
Маршрут B—C—D—E, длина 10 км.
Маршрут B—С—D—A—E, длина 9 км.
Любые другие маршруты будут длиннее маршрута B—С—D—A—E. Самый короткий путь: B—С—D—A—E. Длина маршрута 9 км.
Курс Глицин. Любовь, друзья, спорт и подготовка к ЕГЭ
Поиск путей в
графе
Разбор заданий № 15 ЕГЭ (11 кл)
Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных
моделей (схемы, карты, таблицы, графики и формулы). (повышенный уровень, время – 3
мин)
Теория: Способы представления графов,
Задания для тренировки:
Графы, содержащие
более или менее десяти вершин
Графы, содержащие
десять вершин
Онлайн-тесты Константина Полякова для подготовки к ЕГЭ:
Ние № 15 (ДЕМО
ФИПИ ЕГЭ-2020
Из
заданного графа исключим дуги, которые, при составлении маршрута из города А в город М,
позволяют обойти город Ж:
Посчитаем
последовательно количество путей до каждого из городов:
Начало
маршрута А = 1;
последовательно
будем рассматривать соседние (связанные) вершины и подсчитывать количество
проходящих через них путей:
Д = А = 1; Г =А + Д = 2; В = А
+ Г = 3; Б = А + В = 4; Е = Б
= 4;
З = Д + Г + В = 6; Ж = З + В + Б + Е = 17; И
= Ж =17; К = И =17; Л = И
= 17; М = Л + И + К = 51.
Подсчет
количества путей можно отобразить на графе:
Ние № 15 (ДЕМО
ФИПИ ЕГЭ-2019
Из
заданного графа исключим дуги, которые, при составлении маршрута из города А в город М,
позволяют обойти город Л:
Посчитаем
последовательно количество путей до каждого из городов и отобразим это на
графе:
Ние № 15 (ДЕМО
ФИПИ ЕГЭ-2018
Посчитаем последовательно количество
путей до каждого из городов: 1. Начало маршрута А
= 1;
Д = А = 1; Г =А + Д = 2; Б = А
= 1; В = А + Б = 2; Е = А
+ Б + В + Г + Д = 7; Л =
Е = 7; К = Е = 7; М = К + Е + Л = 21; Н
= К + Л + М = 35; П = М = 35; Р = М + П = 70; Т = П
+ Р = 105.
Посчитаем последовательно количество путей до каждого
из городов: 1. Начало маршрута А
= 1;
Д = А = 1; Б = А = 1; Г =А + Б = 2; В = А + Б = 2; Е = А
+ Б + В + Г + Д = 7; К =
Е = 7; Л = Е = 7; М = Е + К + Л = 21; Н
= К + М + Л = 35; П = Н =
35; Р = Н = 35; Т = П
+ Р = 70.
Из
заданного графа исключим дуги, которые, при составлении маршрута из города А в город Т,
позволяют обойти город Л:
Рассматривая
соседние (связанные) вершины, посчитаем последовательно количество путей до
каждого из городов, результат отобразим на графе (А = 1):
Из
заданного графа исключим дуги, которые, при составлении маршрута из города А в город Т,
позволяют обойти город Н:
Рассматривая соседние (связанные) вершины,
посчитаем последовательно количество путей до каждого из городов, результат
отобразим на графе (А = 1):
Из
заданного графа исключим дуги, которые, при составлении маршрута из города А в город Т,
позволяют обойти город Е:
Из
заданного графа исключим дуги, которые, при составлении маршрута из города А в город Т,
позволяют обойти город В:
Разбор заданий № 18.
Рассмотрим
соседние (связанные) вершины и последовательно посчитаем количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):
Сегодня разберём одно из самых лёгких заданий из ЕГЭ по информатике — задание 13. Вы с похожим типом задач могли встретится на экзамене в 9 классе по информатике.
Приступим к практическим тренировкам решения 13 задания ЕГЭ по информатике 2022.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Нужно подсчитать количество путей от начальной точки А до конечной точки К.
Будем использовать специальную технику для решения 13 задания из ЕГЭ по информатике 2022
Ставим 1 (единицу) возле начальной точки A. Далее, просматриваем ближайшие точки и анализируем, сколько входит стрелок в эти точки. В точку Б «перетекает» 1 из точки А. В точку Г тоже входит одна стрелка из точки А. Значит, тоже в эту точку «перетекает» 1 из А.
В точку В входят две стрелки. Значит, в точку В «втекает» сумма двух точек, из которых выходят эти стрелки! Получается 1 + 1 = 2.
И продолжаем в том же духе.
Число в конечной точке показывает правильный ответ!
Ответ: 17
Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е,
Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном
направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих
через город Ж?
Отличие этой задачи от предыдущей заключается в том, что пути, которые будем засчитывать, обязательно должны проходить через пункт Ж. Чтобы выполнить это условие, зачеркнём стрелку из пункта Е в пункт И. Так же зачеркнём стрелку из пункта З в пункт И. По этим стрелкам ходить нельзя, т.к. если мы по ним пойдём, не будет пройден пункт Ж.
Основная техника же решения будет такой же, как и в прошлой задаче.
Продолжаем отработку 13 задания ЕГЭ по информатике 2022
Задача (Избегаемая вершина)
На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П
Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?
Такая же задача, как и предыдущие две, только здесь, при построении путей, мы не должны проходить через точку E.
Зачеркнём те дороги, которые поведут наши пути через пункт E.
Далее, применим старый метод, который использовали ранее.
Получается ответ 27.
Ответ: 27
Рассмотрим задачу, которая была на реальном экзамене по информатике в этом году.
Задача (ЕГЭ по информатике, 2020, Москва)
На рисунке — схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По каждой дороге можно двигаться в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М ?
В этой задаче отличается вопрос от привычного нахождения количества путей. Здесь нужно найти наибольшую длину пути из начального пункта в конечный.
Возле начальной точки ставим число 0.
Смотрим сколько входит в узел стрелок. Выбираем стрелку, которая идёт из узла с наибольшим числом. При переходе по стрелочке добавляем 1.
Число, которое получится возле конечной точки и будет ответом. В этой задачке стрелок получилось 7, это и будет ответ.
Задачи на графы для подготовки к ЕГЭ. Использовался сайт Константина Полякова (
Пример задания 1:
Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:
СОСНОВО КРАСНЫЙ 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
путешественник не успеет на рейс КРАСНЫЙ – СОСНОВО, который улетает в 13:15, то есть на 15 минут раньше, чем в КРАСНЫЙ прилетает самолет ОКТЯБРЬ – КРАСНЫЙ
но рейс БЕРЕГ – СОСНОВО вылетает даже раньше, чем рейс ОКТЯБРЬ – БЕРЕГ, то есть, пересадка не получится
Возможные ловушки и проблемы
Решение (вариант 2, граф):
Еще пример задания 2:
Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. При этом длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час.
1) 1 час 2) 1,5 часа 3)3,5 часа 4) 4 часа
Еще пример задания:
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
Решение (вариант 2, с рисованием схемы):
, стоимость 7
, стоимость 8
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
1) 9 2) 10 3) 11 4) 12
Решение (вариант 1, использование схемы):
А – В – Е длина 9
А – В – С – Е длина 7
А – В – C – D – Е длина 9
А –C – Е длина 8
А –C – B – Е длина 12
А –C – D – Е длина 10
Между четырьмя местными аэропортами: ВОСТОРГ, ЗАРЯ, ОЗЕРНЫЙ и ГОРКА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:
ВОСТОРГ ГОРКА 16:15 18:30
ОЗЕРНЫЙ ЗАРЯ 13:40 15:50
ОЗЕРНЫЙ ВОСТОРГ 14:10 16:20
ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20
ЗАРЯ ОЗЕРНЫЙ 16:20 18:25
ВОСТОРГ ЗАРЯ 14:00 16:15
ГОРКА ЗАРЯ 14:10 16:25
ОЗЕРНЫЙ ГОРКА 18:35 19:50
Путешественник оказался в аэропорту ВОСТОРГ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ГОРКА.
1) 16:15 2) 18:15 3)18:30 4) 19:50
Решение («обратный ход»):
Определите длину кратчайшего пути между пунктами B и D (при условии, что передвигаться можно только по построенным дорогам).
1) 8 2) 9 3) 10
Сдай ЕГЭ! Бесплатные материалы для
подготовки каждую неделю!
Нажимая на кнопку, вы даете согласие на обработку своих персональных
данных согласно 152-ФЗ. Подробнее
Программа ЕГЭ по информатике — Разбор задач и материалы
Онлайн-курсы по информатике
New: Повторяем основные формулы и понятия
New: ЕГЭ по информатике 2021
New: Как сдать ЕГЭ по информатике на 90+ баллов?
New: Актуальные видео по информатике
Статьи
Спасибо за то, что пользуйтесь нашими статьями.
Информация на странице «Программа ЕГЭ по информатике u0026#8212; Разбор задач и материалы» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ.
Чтобы успешно сдать нужные и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из данного раздела.
Публикация обновлена:
08.05.2023
Мы используем файлы cookie, чтобы персонализировать контент, адаптировать и оценивать результативность рекламы, а также обеспечить безопасность. Перейдя на сайт, вы соглашаетесь с использованием файлов cookie.
