презентация. Графы. Моделирование Использование графов

• Название: Моделирование Использование графов
• Анкор: презентация
• Дата: 09.12.2021
• Размер: 156.84 Kb.
• Имя файла: Графы.pptx
• Тип: Документы; #297677

Моделирование

Использование графов

Виды моделей

Иерархические модели

Деревья
Описывают многоуровневую структуру

Задачи:

Игровые стратегии
Кодирование информации
Поиск оптимального решения

Сетевые модели

Графы
Каждый узел может быть связан со всеми другими

Задачи

Весовые и матрицы смежности
Поиск оптимального пути

Игровые стратегии (основные понятия)

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

Задачи

Постройте матрицы смежности и весовые матрицы

Задачи

Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 1 камень или 10 камней. Например, имея кучу из 7 камней, за один ход можно получить кучу из 8 или 17 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 31. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 31 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 30.

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

Задачи

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

б) Укажите такое значение S. при котором Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы.

2. Укажите два значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Вова. Для указанных значений S опишите выигрышную стратегию Паши. 3. Укажите значение S, при котором у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, однако у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вовы. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.
https://docs.google.com/forms/d/e/1FAIpQLSelZx-QhfFs20MYydKRxjoiC2PRBZs1GGxNWtB-mM1BMxSujA/viewform?usp=sf_link

Моделирование

Этапы моделирования

Постановка задачи

исследование оригинала

изучение сущности объекта или явления

анализ («что будет, если …»)

научиться прогнозировать последствий при различных воздействиях на оригинал

синтез («как сделать, чтобы …»)

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

оптимизация («как сделать лучше»)

выбор наилучшего решения в заданных условиях

Пример: Спортсмен Вася в синей кепке бросает белый мяч со скоростью 12 м/с. Под каким углом к горизонту ему нужно бросить мяч, чтобы попасть в желтую мишень?

Разработка модели

1) Определить существенные исходные данные.

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

2) Выбор типа модели

Графическая
Формальная
компьютерная

Тестирование

Тестирование – это проверка модели на простых исходных данных с известным результатом.

Тестирование математической модели
Тестирование компьютерной модели

Эксперимент

Эксперимент – это исследование модели при тех исходных данных, которые нас интересуют (результат заранее неизвестен).

Виды компьютерного эксперимента 

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

Анализ результатов

Возможные выводы:

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

К основным этапам компьютерного моделирования относятся:

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