Теория графов информатика егэ

Использование теории графов для решения заданий ЕГЭ

1. Между населенными пунктами A,B,C,D,E,Fпостроены дороги, протяженность которых приведена в таблице(отсутствие числа означает, что прямой дороги нет). Определить длину кратчайшего пути между пунктами E и F. (Передвигаться можно только по построенным дорогам). A B C D E F A 2 4 B 2 1 7 C 4 1 3 4 D 3 3 E 7 4 3 2 F 2 Решение: В этом задании исходные данные представлены в виде таблицы, которую можно рассматривать как матрицу неориентированного взвешенного графа. Вершинами данного графа являются населенные пункты A,B,C,D,E,F. Элементы данной матрицы показывают, какие населенные пункты связаны дорогами и какова их длина. Для более наглядного представления изобразим данные таблицы в виде графа. Для этого в произвольном порядке изображаем вершины, затем соединяем их ребрами и указываем вес каждого ребра. Нам надо указать длину кратчайшего пути из пункта А в пункт F.  Нарисуем этот путь с конца.

Сначала изобразим конечный пункт F. В этот пункт можно попасть только из пункта Е. Соединяем пункты Е и F  дугой и указываем вес этой дуги. Он равен двум, то есть расстоянию между пунктами  Е и F. Соответственно по графу можно увидеть, что в пункт Е можно попасть  из пунктов B, C и D. В пункт В можно попасть из А. В пункт С – из В и А. В  пункт D – из С. В пункт В попадаем из А. В пункт С – из В и А. И в пункт В из А.

Данную схему можно рассматривать как ориентированный взвешенный граф, который наглядно показывает, что есть 5 путей из пункта А в пункт F. Подсчитываем длину каждого пути 
1 путь: 2+7+2=11;
2 путь: 2+1+4+2=9;
3 путь: 4+4+2=10;
4 путь2+1+3+3+2=11;
5 путь: 4+3+3+2=12. 
Так как нам надо определить длину кратчайшего пути, то выбираем второй путь, длина которого равна 9. Данный ответ находится под цифрой 1. Поэтому в ответе надо поставить крестик в клеточке, соответствующей первому ответу.

2. У исполнителя Утроитель две команды, которым присвоены номера
1. Прибавь 1;
2. Умножь на 3.
Запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд.
Решение:
Для решения данного задания используем метод от обратного, то есть будем преобразовывать число 22 в 1. Соответственно команды исполнителя заменим командами антагонистами, то есть команду «Прибавь 1» заменим командой «Вычти 1», а «Умножь на 3» заменим командой «Раздели на 3». Ход выполнения команд можно изобразить в виде  дерева, каждая вершина которого имеет две ветки, соответствующие командам 1 и 2. Корнем этого дерева является число 22. Это дерево будет иметь 5 ярусов, так как программа должна содержать не более 5 команд. Но здесь нужно учесть один момент. Если число  делится на 3, то вершина будет иметь 2 потомка, а если нет, то одного (то есть делить на 3 мы не можем, а можем только вычитать 1). Получаем следующее дерево.

  

 Инвертируем теперь команды и преобразуем число 1 в 22.
    1+1*3+1*3+1=22.
   Учитывая номера команд, записываем программу решения данной задачи в виде  последовательности соответствующих команд. Ответ: 12121

 
Решение: (1 способ)
Условие данного задания представлено в виде ориентированного графа, вершинами которого являются названия городов, а дороги, соединяющие эти города, являются дугами графа. Для того, чтобы решить данную задачу, построим еще один ориентированный граф, но с  учетом того, по каким дорогам можно будет попасть в пункт Л.

 По графу легко подсчитать количество дорог, ведущих из города А в город Л.
 

3.У Исполнителя Кузнечик 2 команды:
1. Прибавь 3;
2. Вычти 2.
Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд. 
Решение:
Оформим решение данной задачи в виде дерева, вершинами которого будут являться числа, соответствующие промежуточным значениям. Данное дерево будет иметь корень, равный 1 и 5 ярусов, так как у нас должно быть ровно 5 команд.

 

 4. У исполнителя Устроитель две команды, которым присвоены номера:
1. Прибавь 1;
2. Умножь на 3.
Программа для Устроителя – это последовательность команд. 
Сколько есть программ, которые преобразуют 1 в число 29?

  При решении данной задачи следует учитывать, что если число больше 9, то умножать на 3 мы не можем, так как получится число, большее 29, следовательно, вершины с числами большими 9 будут иметь только одну ветвь, соответствующую команде +1.

  
 

   

5.Даны три кучи камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой-нибудь куче, или добавить по 2 камня в каждую из всех трех куч. Выигрывает тот, после чьего хода в какой-нибудь куче становится больше или равно 15 камней или во всех трех кучах суммарно становится больше либо равно 25 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок? 
Решение:    В разумной партии каждый игрок должен стараться следовать общему правилу – всегда оставлять противнику проигрышную позицию. В ходе решения задач можно заметить, что в одной партии в Камешки только один из игроков может следовать этому правилу – тот, кто первым может занять выигрышную позицию (имеет выигрышную стратегию). Если он будет ей следовать, а, значит, делать только разумные ходы и оставлять противнику только проигрышные позиции, то выиграет при любой игре противника. Если начальная позиция выигрышная, то выигрышную стратегию имеет Первый, если проигрышная – Второй.  
Изобразим решение данной задачи в виде графа.

Ответ:  при правильной стратегии игры выигрывает первый игрок. При этом первый его ход должен быть 2, 3, 4                 4, 5, 6.

Литература: 
ФИПИ (открытый банк данных)
Материалы демонстрационных вариантов ЕГЭ по информатике  2016, 2015 года
Материалы диагностической работы 2015 года.

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

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

Объект (лат. 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 является соседней только с А. Точка В должна быть соединена, кроме С, с точкой Е. В результате можно получить следующую схему:

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

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

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

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

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

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

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

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

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

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

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

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

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

Цель: подготовка к ЕГЭ по информатике и ИКТ.

Задачи:

• дать основные понятия теории графов;
• разобрать задачи встречающиеся в ЕГЭ по
  информатике и ИКТ.

Тип мастер-класса: Комбинированный.

Метод обучения:
объяснительно-иллюстративный.

Оборудование: компьютер, проектор, Презентация1.ppt,
дидактический материал «Задачи» (Приложение1).

Время проведения: 60 минут.

Структура мастер-класса:

1. Орг. момент (2 мин).
2. Изложение нового материала (48 мин).
3. Дискуссия по результатам выполняемых заданий (10
   мин).

Ход мастер-класса

1. Оргмомент.

2. Изложение нового материала.

Графы — это отличный инструмент для наглядного
решения широкого круга задач. Этот мастер класс
наглядно демонстрирует, что владея таким
надежным инструментом, как теория графов,
возможно, создать выигрышную стратегию игры, т.е.
решить задачу ЕГЭ из части С3.

Основные понятия теории графов. (Слайд №1.)

Закрепление основных понятий теории графов.
(Слайд №2.)

Область применения графов. (Слайд №3.)

Отыскание пути в графе. (Слайд №4-5.)

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

Матрицы графов. (Слайд №7.)

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

Задачи из ЕГЭ.

Слайд №8 — A10 (базовый уровень, время — 2 мин)

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

Слайд №9 — C3 (высокий уровень, время — 30 мин)

Тема: «Дерево игры. Поиск выигрышной
стратегии».

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

Используемая литература.

1. Л. Ю. Березина Графы и их применение: Пособие для
   учителей.- Москва: Просвещение, 1979 г.