Поиск путей в графе егэ по информатике

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

Поиск путей в
графе

Разбор заданий № 15 ЕГЭ (11 кл)

 

Проверяемые элементы содержания​: Умение представлять и считывать данные в разных типах информационных
моделей (схемы, карты, таблицы, графики и формулы). (повышенный уровень, время – 3
мин)  

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

Теория графов[1] — раздел дискретной математики, изучающий свойства графов.

Граф представляется как множество вершин (узлов), соединённых рёбрами.

Теория графов находит применение, например, в геоинформационных системах

(ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п.

рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии

электропередачи и т. п. — как рёбра. Применение различных вычислений,

производимых на таком графе, позволяет, например, найти кратчайший объездной

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

Графы[2] используют во всех отраслях нашей жизни. Знание основ теории графов

необходимо    в    управлении    производством,    бизнесе,    при    построении    путей

транспортировки и доставки, решении задач.

Графы используют в связи с развитием теории вероятности, математической логики

и информационных технологий.

Граф3 — множество ​V вершин и набор ​Е неупорядоченных и упорядоченных пар

вершин; обозначается граф через ​G(V, Е)​. ​Неупорядоченная пара вершин называется

ребром​, ​упорядоченная пара — ​дугой​. Граф, содержащий только ​рёбра​, называется

неориентированным​; граф, содержащий только ​дуги​,— ​ориентированным​. Пара

вершин может соединяться двумя или более рёбрами (дугами одного направления),

такие рёбра (дуги) называются ​кратными​. Дуга (или ребро) может начинаться и

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

соединённые ребром или дугой, называются ​смежными​. Рёбра, имеющие общую

вершину, также называются смежными. Ребро (дуга) и любая из его двух вершин

называется инцидентными. Говорят, что ребро ​(u, v) соединяет вершины ​u ​и ​v​, а дуга

(u, v)​ начинается в вершине ​u​ и кончается в вершине v​​.

Маршрут на графике — это последовательность ребер 𝑎​1,​𝑎​2,…,​ 𝑎​𝑛 , в которой конец

одного ребра служит началом другого.

​

Информационные
ресурсы:

1.    
Теория:​ ​Способы представления графов​, 

2.    
Задания для тренировки: ​https://inf-ege.sdamgia.ru/test?a=catlistwstat 

a.      
Графы, содержащие
более или менее десяти вершин ​просмотреть

b.     
Графы, содержащие
десять вершин ​просмотреть

3.    
Онлайн-тесты Константина Полякова для подготовки к ЕГЭ: http://kpolyakov.spb.ru/school/egetest/b15.htm  

За​да​ние № 15 (​ДЕМО
ФИПИ ЕГЭ-2020​)

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З,

И, К, Л, М. По каждой дороге можно двигаться только в одном направлении,

указанном стрелкой.​ Сколько существует различных путей ​из города А в город М,

проходящих через город Ж​?

 

Решение:

1.     Из
заданного графа ​исключим​ дуги, которые, при составлении ​маршрута из города А в город М​,
позволяют обойти ​город Ж​:

 

2.     Посчитаем
последовательно количество путей до каждого из городов:

a.      Начало
маршрута ​А = 1;​

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

Д ​= А = 1; ​Г​ =А + Д = 2; ​В​ = А
+ Г = 3; ​Б​ = А + В = 4; ​Е​ = Б
= 4; 

З​ = Д + Г + В = 6; ​Ж​ = З + В + Б + Е = 17; ​И​
= Ж =17; ​К​ = И =17; ​Л​ = И
= 17; М​ = Л + И + К = 51.

c.      Подсчет
количества путей можно отобразить на графе:

 

Ответ: 51.

За​да​ние № 15 (​ДЕМО
ФИПИ ЕГЭ-2019​)

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З,
И, К, Л, М. По каждой дороге можно двигаться только в одном направлении,
указанном стрелкой. ​Сколько существует различных путей ​из города А в город М​,
проходящих через город Л​?

Решение:

1.     Из
заданного графа ​исключим​ дуги, которые, при составлении ​маршрута из города А в город М​,
позволяют обойти ​город Л​:

 

2.     Посчитаем
последовательно количество путей до каждого из городов и отобразим это на
графе:

 

Ответ: 28.

За​да​ние № 15 (​ДЕМО
ФИПИ ЕГЭ-2018​)

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З,
И, К, Л, М. По каждой дороге можно двигаться только в одном направлении,
указанном стрелкой. ​Сколько существует различных путей ​из города А в город М,
проходящих через город Ж​?
Решение:

1.     Из
заданного графа ​исключим​ дуги, которые, при составлении ​маршрута из города А в город М​,
позволяют обойти ​город Ж​:

 

2.     Посчитаем
последовательно количество путей до каждого из городов и отобразим это на
графе:

 

Ответ: 20.

Разбор заданий № 1. ​СтатГрад. Подготовка к ЕГЭ 2019^[3]

Вариант №1

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р,
Т. По каждой дороге можно двигаться только в одном направлении, указанном
стрелкой.
Сколько существует различных путей ​из города А в город Т​?

Решение:

Посчитаем последовательно количество
путей до каждого из городов: 1. Начало маршрута ​А
= 1​;

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

Д ​= А = 1; ​Г​ =А + Д = 2; ​Б​ = А
= 1; ​В​ = А + Б = 2; ​Е​ = А
+ Б + В + Г + Д = 7;  Л ​=
Е = 7; ​К​ = Е = 7; М = К + Е + Л = 21; ​Н​
= К + Л + М = 35; ​П​ = М = 35; Р​ = М + П = 70; ​Т​ = П
+ Р = 105.

3.     Подсчет
количества путей можно отобразить на графе:

 

Ответ: 105.

Вариант №2

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р,
Т. По каждой дороге можно двигаться только в одном направлении, указанном
стрелкой.
Сколько существует различных путей ​из города А в город Т​?

Решение:

Посчитаем последовательно количество путей до каждого
из городов: 1. Начало маршрута ​А
= 1​;

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

Д ​= А = 1; ​Б​ = А = 1; ​Г =А + Б = 2; ​ ​В​ = А + Б = 2; ​Е​ = А
+ Б + В + Г + Д = 7;  К​ =
Е = 7; ​Л ​= Е = 7; ​М​ = Е + К +  Л = 21; ​Н​
= К + М + Л = 35;  П​ = Н =
35; ​Р​ = Н = 35; ​Т​ = П
+ Р = 70.

3.     Подсчет
количества путей можно отобразить на графе:

 

Ответ: 70.

Вариант №3

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П, Р,
С, Т. По каждой дороге можно двигаться только в одном направлении, указанном
стрелкой. ​Сколько существует различных путей ​из города А в город Т, проходящих
через город Л​?

Решение:

1.     Из
заданного графа ​исключим​ дуги, которые, при составлении ​маршрута из города А в город Т​,
позволяют обойти ​город Л​:

 

4.     Рассматривая
соседние (связанные) вершины, посчитаем последовательно количество путей до
каждого из городов, результат отобразим на графе (​А = 1)​:

 

Ответ: 64.

Вариант №4

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П, Р,
С, Т. По каждой дороге можно двигаться только в одном направлении, указанном
стрелкой. ​Сколько существует различных путей ​из города А в город Т, проходящих
через город Н​?

Решение:

1.     Из
заданного графа ​исключим​ дуги, которые, при составлении ​маршрута из города А в город Т​,
позволяют обойти ​город Н​:

 

2.     Рассматривая​ соседние (связанные) вершины,
посчитаем последовательно количество путей до каждого из городов, результат
отобразим на графе (​А = 1)​:

 

Ответ: 32.

Вариант №5

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П, Р,
С, Т. По каждой дороге можно двигаться только в одном направлении, указанном
стрелкой. ​Сколько существует различных путей ​из города А в город Т, проходящих
через город Е​?

Решение:

1.     Из
заданного графа ​исключим​ дуги, которые, при составлении ​маршрута из города А в город Т​,
позволяют обойти ​город Е​:

 

2.     Рассматривая​ соседние (связанные) вершины,
посчитаем последовательно количество путей до каждого из городов, результат
отобразим на графе (​А = 1)​:

 

Ответ: 63.

Вариант №6

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П, Р,
С, Т. По каждой дороге можно двигаться только в одном направлении, указанном
стрелкой. ​Сколько существует различных путей ​из города А в город Т, проходящих
через город В​?

Решение:

1.     Из
заданного графа ​исключим​ дуги, которые, при составлении ​маршрута из города А в город Т​,
позволяют обойти ​город В​:

 

2.     Рассматривая​ соседние (связанные) вершины,
посчитаем последовательно количество путей до каждого из городов, результат
отобразим на графе (​А = 1)​:

 

Ответ: 42.

Разбор заданий № 18. ​ЕГЭ 2020. Ушаков Д.М. 10 тренировочных
вариантов^[4]

Вариант 1

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К​?

Решение:

Рассмотрим​
соседние (связанные) вершины и последовательно посчитаем  количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):

 

Ответ: 30. Вариант 2

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К​?

Решение:

Рассмотрим​
соседние (связанные) вершины и последовательно посчитаем  количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):

 

Ответ: 41.

Вариант 3

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К​?

Решение:

Рассмотрим​
соседние (связанные) вершины и последовательно посчитаем  количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):

 

Ответ: 25

Вариант 4

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К​?

Решение:

Рассмотрим​
соседние (связанные) вершины и последовательно посчитаем  количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):

 

Ответ: 32

Вариант 5

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К​?

Решение:

Рассмотрим​
соседние (связанные) вершины и последовательно посчитаем  количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):

 

Ответ: 24

Вариант 6

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К​?

Решение:

Рассмотрим​
соседние (связанные) вершины и последовательно посчитаем  количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):

 

Ответ: 12

Вариант 7

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К​?

Решение:

Рассмотрим​
соседние (связанные) вершины и последовательно посчитаем  количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):

 

Ответ: 18

Вариант 8

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К​?

Решение:

Рассмотрим​
соседние (связанные) вершины и последовательно посчитаем  количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):

 

Ответ: 30

Вариант 9

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К​?

Решение:

Рассмотрим​
соседние (связанные) вершины и последовательно посчитаем  количество путей до
каждого из городов, результат отобразим на графе (причем, А = 1):

 

Ответ: 19

Вариант 10

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей ​из города А в город К, ​проходящих через город
Е?

Сегодня разберём одно из самых лёгких заданий из ЕГЭ по информатике — задание 13. Вы с похожим типом задач могли встретится на экзамене в 9 классе по информатике.

Приступим к практическим тренировкам решения 13 задания ЕГЭ по информатике 2022.

Задача (Стандартная)

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение:

Нужно подсчитать количество путей от начальной точки А до конечной точки К.

Будем использовать специальную технику для решения 13 задания из ЕГЭ по информатике 2022

Техника:

Ставим 1 (единицу) возле начальной точки A. Далее, просматриваем ближайшие точки и анализируем, сколько входит стрелок в эти точки. В точку Б «перетекает» 1 из точки А. В точку Г тоже входит одна стрелка из точки А. Значит, тоже в эту точку «перетекает» 1 из А.

В точку В входят две стрелки. Значит, в точку В «втекает» сумма двух точек, из которых выходят эти стрелки! Получается 1 + 1 = 2.

И продолжаем в том же духе.

Число в конечной точке показывает правильный ответ!

Ответ: 17

Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е,
Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном
направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих
через город Ж?

Решение:

Отличие этой задачи от предыдущей заключается в том, что пути, которые будем засчитывать, обязательно должны проходить через пункт Ж. Чтобы выполнить это условие, зачеркнём стрелку из пункта Е в пункт И. Так же зачеркнём стрелку из пункта З в пункт И. По этим стрелкам ходить нельзя, т.к. если мы по ним пойдём, не будет пройден пункт Ж.

Основная техника же решения будет такой же, как и в прошлой задаче.

Ответ: 51

Продолжаем отработку 13 задания ЕГЭ по информатике 2022

Задача (Избегаемая вершина)

На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П

Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?

Решение:

Такая же задача, как и предыдущие две, только здесь, при построении путей, мы не должны проходить через точку E.

Зачеркнём те дороги, которые поведут наши пути через пункт E.

Далее, применим старый метод, который использовали ранее.

Получается ответ 27.

Ответ: 27

Рассмотрим задачу, которая была на реальном экзамене по информатике в этом году.

Задача (ЕГЭ по информатике, 2020, Москва)

На рисунке — схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По каждой дороге можно двигаться в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М ?

Решение:

В этой задаче отличается вопрос от привычного нахождения количества путей. Здесь нужно найти наибольшую длину пути из начального пункта в конечный.

Возле начальной точки ставим число 0.

Смотрим сколько входит в узел стрелок. Выбираем стрелку, которая идёт из узла с наибольшим числом. При переходе по стрелочке добавляем 1.

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

Ответ: 7

Моделирование и компьютерный эксперимент

Общая структура деятельности по созданию компьютерных моделей

Объект (лат. objectum — предмет) — это некоторая часть окружающего мира, рассматриваемая как единое целое. Все, что человек изучает, использует, производит, является объектом. Каждый объект имеет имя, что позволяет отличить один объект от другого (например, стол, атом, город Москва, ураган Катрин и т. п.). Конкретизировать объект можно с помощью параметров. Параметры — это признаки, которые характеризуют какое-либо свойство объекта. Они могут быть количественные (рост, вес, возраст, размер и т. п.) и качественные (форма, материал, цвет, запах, вкус и т. п.). Очень часто можно наблюдать смену состояний объекта в течение времени и, как результат, изменение параметров объекта. Говорят, что происходит некоторый процесс. Переход объекта из одного состояния в другое происходит при воздействии на него других объектов.

Модель (лат. modulus — мера; франц. modele — образец) — искусственно созданный объект в виде схем, чертежей, логико-математических знаковых формул, компьютерной программы, физической конструкции, который, будучи аналогичен (подобен, сходен) исследуемому объекту (явлению, процессу, устройству, сооружению, механизму, конструкции), отображает и воспроизводит в более простом, уменьшенном виде структуру, свойства, взаимосвязи и отношения между элементами исследуемого объекта, непосредственное изучение которого связано с какими-либо трудностями, большими затратами средств и энергии или просто недоступно, и тем самым облегчает процесс изучения информации об интересующем нас предмете.

Исследуемый объект по отношению к модели является оригиналом (образцом, прототипом). Модели могут создаваться как из однородного с оригиналом материала (например, макет деревянного сооружения можно сделать тоже из дерева), так и из материала, совершенно отличного от материала оригинала (например, бумажная модель самолета). Кроме того, модели могут быть нематериальными, или абстрактными (например, математическая модель самолета, компьютерная модель электрической сети).

Моделирование — это исследование каких-либо объектов (конкретных или абстрактных) на моделях. Объектом моделирования может быть объект, явление или процесс.

При создании модели стараются отразить наиболее существенные свойства объекта, а несущественные свойства отбрасываются. Например, на глобус наносятся океаны и моря, материки и крупные острова, а маленькие озера и островки на него не попадают: в масштабе глобуса они будут просто не видны.

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

Кроме материальных (предметных) моделей (игрушки, глобуса, макета дома…), существуют нематериальные — абстрактные модели: описания, формулы, изображения, схемы, чертежи, графики и т. д. С помощью математических формул описываются, например, арифметические операции, соотношения геометрии, законы движения и взаимодействия тел (S = Vt, F = mа) и многое другое. Химические формулы помогают представить молекулярный состав химических веществ и реакции, в которые они вступают. Пользуясь таблицами, графиками, диаграммами можно отображать различные закономерности и зависимости реального мира.

Все абстрактные модели не имеют физического воплощения. Абстрактные модели, которые можно представить с помощью набора знаков (геометрических фигур, символов, фрагментов текста), — это знаковые модели. Любую знаковую модель можно изобразить на бумаге. Чтобы построить знаковую модель, нужно представлять значение знаков и знать правила их преобразования. Абстрактная модель, прежде чем оформиться в виде знаковой модели, сначала рождается в голове человека. Она может передаваться человека к человеку в устной форме. В таких случаях модель еще не является знаковым образом, поскольку не имеет вида чертежа, формулы, текста. Модель в голове человека существует в форме мысленных представлений (мысленная модель). Модели, полученные в результате умозаключений, называются вербальными (лат. verbalis — устный). Вербальными называются также модели, изложенные в разговорной форме. Таким образом, все абстрактные модели можно разделить на знаковые и вербальные.

Представленная классификация моделей самая простая. Она основана на делении моделей по способу представления. Возможны и другие классификации, — например, по предметному признаку: физические, химические модели, модели строительных конструкций, различных механизмов и т. д.

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

Компьютерные модели обычно различают по программному обеспечению, которое применяется при создании и работе с моделью. Для обработки компьютерных моделей используются существующие программные приложения (математические пакеты, электронные таблицы, графические редакторы и т. д.) либо разрабатываются оригинальные программы с помощью языков программирования (Ваsic, Раsсаl, Dеlpi, С++ и др.).

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

Этапы создания модели

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

Моделирование, в том числе компьютерное, начинается с постановки задачи. На этом этапе формулируется задача и требования, которые предъявляются к решению. Постановка задачи заключается, прежде всего, в ее описании. Задача может быть описана на обыденном языке — например, в форме вопроса «что будет, если… ?» или «как сделать, чтобы… ?». Математическую задачу описывают с помощью формул и знаков, а инженерная, экономическая задача может быть описана с помощью различных схем, графиков.

При постановке задачи нужно отразить (или хотя бы понять) цель или мотив создания модели. Одни модели создаются, чтобы разобраться в устройстве или составе того или иного объекта. Другие модели направлены на изучение возможностей управления объектом. Третьи модели ставят целью предсказать поведение объекта (задачи прогнозирования). На этапе постановки задачи полезным оказывается предварительный анализ объекта. Разложение объекта на составляющие, выяснение связей между ними позволяет уточнить постановку задачи.

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

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

При разработке компьютерной модели весьма существенным будет выбор программного обеспечения, с помощью которого выполняется моделирование. Программное обеспечение должно позволять эффективно решать задачи, подобные той, которая рассматривается. Например, для создания рисунка на компьютере нужно выбрать тот или иной графический редактор (какой именно — зависит от требуемого формата файла и приемов, которые необходимо применять при рисовании). Чтобы решить систему уравнений, нужно воспользоваться языками программирования Basic, Pascal или каким-либо другим или же использовать для решения математические пакеты. Программная среда должна соответствовать поставленной задаче — только в этом случае задача может быть успешно решена. Выбор программного обеспечения и составление алгоритма — это взаимосвязанные действия. Возможно, что для решения поставленной задачи придется разработать собственную компьютерную программу.

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

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

После выполнения тестирования и отладки можно приступать непосредственно к моделированию. Технология моделирования может заключаться в расчете модели при различных наборах входных данных, различных параметрах.

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

Этапы компьютерного моделирования можно представить в виде таблицы.

1. ПОСТАНОВКА ЗАДАЧИ	Описание
Мотивация
Предварительный анализ

2. РАЗРАБОТКА МОДЕЛИ	Выделение существенных факторов
Составление алгоритма
Выбор программного обеспечения
Программирование

3. КОМПЬЮТЕРНЫЙ ЭКСПЕРИМЕНТ	Тестирование модели
Отладка модели
Расчет модели при различных входных данных

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

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

Информационная модель — это целенаправленно отобранная информация об объекте, представленная в некоторой форме.

Простейшими примерами информационных моделей являются различные загадки, в которых описываются свойства, по которым нужно угадать название объекта («Летом серый, зимой белый»; «Зимой и летом одним цветом»). К информационным моделям можно отнести тексты справочных изданий, энциклопедий.

Формы представления информационных моделей могут быть различными. Наиболее известны следующие формы:

• в виде сигналов;
• устная, словесная;
• символьная (числа, текст, символы);
• табличная;
• схемы, карты;
• графики.

Один и тот же объект, в зависимости от поставленной цели, можно представить несколькими информационными моделями, отличающимися набором параметров и способом их представления. Рассмотрим примеры анализа информации для модели, представленной в табличной форме.

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

1. 
2. 
3. 

Решение. Прежде всего, нужно отметить, что данные в таблицах симметричны относительно главной диагонали, т. е. проезд из А в В стоит столько же, сколько и из В в А.

Рассмотрим первую таблицу. Выберем все возможные варианты проезда из А в В и соответственно подсчитаем стоимости: AC(3) + CB(4); AC(3) + CE(2) + EB(2)

Примечание. В скобках указана стоимость проезда.

Стоимость, как первого, так и второго варианта маршрута равна 7.

Аналогично поступим для второй таблицы: AC(3) + CB(4); AE(1) + EC(2) + CB(4).

Как и в случае с предыдущей таблицей, стоимость как первого, так и второго варианта маршрута равна 7.

Выписываем все варианты для третьей таблицы: AC(3) + CB(4); AC(3) + CE(2) + EB(1).

Стоимость последнего варианта маршрута равна 6.

Ответ: таблица номер 3 содержит маршрут из А в В, стоимость которого не превышает 6.

Пример 2. Для заданной информационной модели, записанной в форме таблицы, построить модель в виде схемы. В ячейках на пересечении строк и столбцов таблицы указана стоимость проезда между соседними станциями. Пустые ячейки означают, что станции не являются соседними.

Решение. Отметим точку A, она должна быть соединена с C и D. Отмечаем точки C и D и соединяем их с точкой А дугами; над каждой дугой указываем стоимость проезда. Точка С должна быть соединена, кроме А, с точками В и Е. Точка D является соседней только с А. Точка В должна быть соединена, кроме С, с точкой Е. В результате можно получить следующую схему:

Математические модели (графики, исследование функций)

Знаковые модели принято делить на математические и информационные.

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

Над элементами математической модели можно выполнять определенные математические преобразования. Например, в модели нахождения наименьшего числа выполняются операции сравнения, а в модели вычисления корня уравнения — различные арифметические операции. С помощью математических моделей описываются решения различных инженерных задач, многие физические процессы (движение планет, автомобиля и т. п.); технологические процессы (сварка, плавление металла и т. п.). Графики, таблицы, диаграммы позволяют отображать различные закономерности и зависимости реального мира. Например, модель развития эпидемии можно описать как с помощью формул, так и с помощью графика. Полет снаряда, выпущенного из орудия, можно математически смоделировать с помощью известных формул движения, затем построить график движения снаряда — баллистическую кривую, которая отображает реальный полет снаряда. Математически изменяя параметры снаряда или характеристики движения, можно изучать, например, вопросы увеличения дальности или высоты полета и т. п.

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

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

• в несколько раз сократить время проведения исследований;
• уменьшить количество участников эксперимента;
• повысить точность и достоверность эксперимента, а следовательно, увеличить контроль;
• за счет средств графической визуализации, например анимации, получить реальную «картинку»;
• повысить качество и информативность эксперимента за счет увеличения числа контролируемых параметров и более точной обработки данных. На экране компьютера возможно, например, формирование целой системы приборов, которые будут отслеживать изменение параметров объекта.

Построение и использование информационных моделей реальных процессов (физических, химических, биологических, экономических)

Моделирование занимает центральное место в исследовании объекта. Компьютеры дают широкие возможности для постановки компьютерных экспериментов. Компьютерное моделирование позволяет воссоздать явления, которые в реальных условиях воспроизвести невозможно. Это, например, движение материков, эффекты землетрясений и наводнений, рождение сверхновых звезд, изменение направлений морских подводных течений и т. д. При изучении этих явлений на помощь приходят компьютеры и компьютерные программы, причем последние составляются квалифицированными программистами совместно с различными специалистами: физиками, географами, биологами, медиками и др.

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

Построение моделей позволяет осознанно принимать решения по усовершенствованию имеющихся объектов и созданию новых, изменению процессов управления ими. И, как следствие, наблюдается изменение окружающего нас мира.

Примеры информационных компьютерных моделей для различных отраслей знаний приведены в таблице.

Физика	Моделирование движения на плоскости и в пространстве, моделирование различного вида колебаний, процесса расщепления атомного ядра; моделирование работы двигателя, турбины и т. п.; моделирование магнитных, электрических явлений и т. д.
Химия	Моделирование строения молекул; моделирование процесса взаимодействия веществ; моделирование отдельных этапов химического производства; моделирование процессов нагревания или остывания различных тел и т. п.
Биология	Моделирование развития биологического объекта в зависимости от условий (например, климатических); моделирование побочных действий лекарственных препаратов; моделирование процесса распространения эпидемий; моделирование при решении задач генетики; различные модели изменения численности популяций и т. д.
Экономика	Моделирование работы предприятия, банка, отрасли экономики или экономики в целом; моделирование процесса миграции трудовых ресурсов, кризисных явлений в экономике и т. д.

ЕГЭ-2015 задание 15.

Поиск количества путей в графе

Теория

Если в город S можно приехать только из городов X, Y, и Z, то число различных путей из города A в город S равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть

N_S = N_X + N_Y + N_Z ,

где N_M обозначает число путей из вершины A в некоторую вершину M

Число путей конечно, если в графе нет циклов — замкнутых путей

Задача

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Решение

Будем обозначать через N_X количество различных путей из города А в город X. Для города А есть только один маршрут – никуда не двигаться, поэтому N_A = 1. Для любого города X количество маршрутов N_X можно вычислить как

N_X = N_Y + … + N_Z

где сумма взята по всем вершинам, из которых есть прямой путь в вершину X; например, 

N_Л = N_Д + N_И + N_Ж + N_К

Составим таблицу, в которой около каждого города будем записывать количество прямых путей в этот город. Начнем считать количество путей с начала маршрута – с города А: 

В пункты Б и В ведут единственные дороги из А. В пункт В можно попасть из пунктов А, Б, и Г, т.е. N_В = N_А + N_Б + N_Г = 3.

А	Б	В	Г	Д	Е	Ж	И	К	Л
1	1	3	1

В пункт Е можно попасть только из Г, количество путей равно количеству путей в пункт Г. В пункт Ж ведут прямые пути из пунктов Е и В, т.е. N_Ж = N_В + N_Е = 4. В пункт Д ведут прямые пути из пунктов Б и В, т.е. N_Д = N_В + N_Б = 4.

А	Б	В	Г	Д	Е	Ж	И	К	Л
1	1	3	1	4	1	4

В пункт И можно попасть только из Д, количество путей равно количеству путей в пункт Д = 4. В пункт К ведет путь только из пункта Е, т.е. N_К = N_Е = 1. В пункт Л ведут прямые пути из пунктов Д, И, Ж и К, т.е. N_Л = N_Д + N_И + N_Ж + N_К = 13.

А	Б	В	Г	Д	Е	Ж	И	К	Л
1	1	3	1	4	1	4	4	1	13

Ответ

13