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

Моделирование
§ 13. Модели и моделирование

Что такое модель?
модели чего?
автомобиль
Земля
кристаллическая решётка
корабль
дом
оригиналы
объекты (самолет, дом, ядро атома, галактика) процессы (изменение климата, развитие экономики)
явления природы (землетрясения, цунами)
Оригиналы:

Что такое модель?
оригинал не существует
древний Египет
последствия ядерной войны (Н.Н. Моисеев, 1966) исследование оригинала дорого или опасно
управление ядерным реактором (Чернобыль, 1986)
испытание нового скафандра для космонавтов
разработка нового самолета или корабля
оригинал сложно исследовать
Солнечная система, галактика (большие размеры)
атом, нейтрон (маленькие размеры)
процессы в двигателе внутреннего сгорания (очень быстрые)
геологические явления (очень медленные)
интересуют только отдельные свойства
проверка краски для фюзеляжа самолета
Нужно решить задачу, связанную с оригиналом, но:

Модели и оригиналы
оригинал
задача
модель
материальная точка
модели человека

Модели и моделирование
Модель – это объект, который обладает существенными свойствами другого объекта, процесса или явления (оригинала) и используется вместо него.
Моделирование – это создание и исследование моделей с целью изучения оригиналов.
Задачи моделирования:
исследование оригинала
анализ («что будет, если …»)
синтез («как сделать, чтобы …»)
оптимизация («как сделать лучше всего …»)

Виды моделей (по природе)
материальные
вербальные
модели
знаковые
информационные

Виды моделей (по фактору времени)
статические – описывают оригинал в заданный момент времени
силы, действующие на тело в состоянии покоя
результаты осмотра врача
фотография
…
динамические
модель движения тела
явления природы (молния, землетрясение, цунами)
история болезни
видеозапись события
…

Виды динамических моделей
непрерывные – описывают оригинал в любой момент времени на заданном интервале
y = 2t + 5
дискретные – описывают оригинал только в отдельные моменты времени (через 1 сек, час, год, …)
yi = 2ti + 5
yi = 5yi–1 + 5

Виды моделей (по характеру связей)
детерминированные – при одинаковых исходных данных всегда получается тот же результат
расчёт по формулам
движение корабля на спокойной воде
…
вероятностные – учитывают случайность событий
броуновское движение частиц
полета самолёта с учетом ветра
движения корабля на волнении
поведение человека
…

Имитационные модели
нельзя заранее вычислить или предсказать поведение системы, но можно имитировать её реакцию на внешние воздействия
максимальный учет всех факторов
только численные результаты
Примеры:
испытания лекарств на мышах, обезьянах, …
математическое моделирование биологических систем
модели систем массового обслуживания
модели процесса обучения
кросс-программирование
…

Игровые модели
экономические ситуации
военные действия
спортивные игры
тренинги персонала
Игровые модели учитывают действия противников.

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

Пересчёт «модель-оригинал»
7,6 см
М 1:500000
7,6 см ⋅ 500000
= 38 км
В более сложных случаях используют теорию подобия.

Моделирование
§ 14. Математическое моделирование

I. Постановка задачи
Хорошо поставленная задача:
описаны все связи между исходными данными и результатом
известны все исходные данные
решение существует
задача имеет единственное решение
Примеры плохо поставленных задач:
Уроки в школе начинаются в 830. В 1000 к школе подъехал красный автомобиль. Определите, когда Шурик выйдет играть в футбол?
Мальчик Вася в синей кепке бросает белый мяч со скоростью 12 м/с. Когда мяч впервые ударится о землю?
Решить уравнение sin x = 4 (нет решений).
Найти функцию, которая проходит через точки (0,1) и (1,0) (бесконечно много решений).

I. Постановка задачи
Мальчик Вася в синей кепке бросает белый мяч со скоростью 12 м/с. Когда мяч впервые ударится о землю?

II. Разработка математической модели
выделить существенные исходные данные:
начальная скорость 12 м/с
бросок вертикально вверх
ускорение свободного падения 9,81 м/с2
2) построить математическую модель

II. Разработка математической модели
Формализация:
Мяч упал:
Ещё допущения:
мяч – материальная точка
нет сопротивления воздуха

III. Тестирование модели
Тестирование – это проверка модели на простых исходных данных с известным результатом.
• при t = 0 ⇒ y = h0 (в начальной точке)
• при v0 = 0 ⇒ падение вниз

IV. Построение компьютерной модели
алг Полёт
нач
вещ h0=1.5, v0=12, g=9.81
вещ a, b, c, D, t1, t2
a:= -g/2
b:= v0
c:= h0
D:= b*b - 4*a*c
t1:= (-b+sqrt(D))/(2*a)
t2:= (-b-sqrt(D))/(2*a)
вывод t1, нс, t2
кон
Кумир

IV. Построение компьютерной модели
program Polet;
var h0, v0, g: real;
a, b, c, D, t1, t2: real;
begin
h0:= 1.5; v0:= 12; g:= 9.81;
a:= -g/2; b:= v0; c:= h0;
D:= b*b - 4*a*c;
t1:= (-b+sqrt(D))/(2*a);
t2:= (-b-sqrt(D))/(2*a);
writeln(t1);
writeln(t2);
end.
Паскаль

IV. Построение компьютерной модели
from math import sqrt
h0 = 1.5
v0 = 12
g = 9.81
a = -g/2
b = v0
c = h0
D = b*b - 4*a*c
t1 = (-b+sqrt(D))/(2*a)
t2 = (-b-sqrt(D))/(2*a)
print( t1 )
print( t2 )
Python

IV. Построение компьютерной модели
#include
#include
using namespace std;
int main()
{
float h0, v0, g, a, b, c, D, t1, t2;
h0 = 1.5; v0 = 12; g = 9.81;
a = -g/2; b = v0; c = h0;
D = b*b - 4*a*c;
t1 = (-b+sqrt(D))/(2*a);
t2 = (-b-sqrt(D))/(2*a);
cout << t1 << endl << t2;
}
C++

Компьютерная имитационная модель
если нельзя просто решить уравнение…
Дискретизация задачи:
моменты времени:
0, Δt, 2Δt, 3Δt, …,
интервал дискретизации
ti = i⋅ Δt
Знаем yi и vi при t = ti
⇒ получить yi+1 и vi+1 при t = ti +1
yi+1 = yi + vi ⋅ Δt
vi+1 = vi – g ⋅ Δt

Компьютерная имитационная модель
алг Полёт-2
нач
вещ h0=1.5, v0=12, g=9.81
вещ y, v, t, dt=0.01
y:= h0; v:= v0; t:= 0
нц пока y >= 0
y:= y + v*dt
v:= v - g*dt
t:= t + dt
кц
вывод t
кон
Кумир

Компьютерная имитационная модель
program Polet_2;
var h0, v0, g: real;
y, v, t, dt: real;
begin
h0:= 1.5; v0:= 12; g:= 9.81;
dt:= 0.01;
y:= h0; v:= v0; t:= 0;
while y>=0 do begin
y:= y + v*dt;
v:= v - g*dt;
t:= t + dt;
end;
writeln(t);
end.
Паскаль

Компьютерная имитационная модель
h0 = 1.5
v0 = 12
g = 9.81
dt = 0.01
y = h0; v = v0; t = 0
while y>=0:
y = y + v*dt
v = v - g*dt
t = t + dt
print( t )
Python

Компьютерная имитационная модель
#include
using namespace std;
int main()
{
float h0, y, v0, v, g, dt, t;
h0 = 1.5; v0 = 12;
g = 9.81; dt = 0.01;
y = h0; v = v0; t = 0;
while( y>=0 ) {
y = y + v*dt;
v = v - g*dt;
t = t + dt;
}
cout << t;
}
С++

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

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

Моделирование
§ 15. Табличные модели. Диаграммы

Таблицы
Свойства объектов:

Таблицы
Связи между объектами:

Таблицы
Изменение свойств:

Оптимальный маршрут
Березовое: 8:00
Полевое
Б
16:00
07:30
11:50
14:00
14:40
16:10

Анализ диаграмм

Анализ диаграмм
а) все «Форды» могут принадлежать менеджерам
б) все охранники могут ездить на «Ауди»
в) все «Тойоты» могут принадлежать рабочим
г) все рабочие могут ездить на «Фордах»
10 + 40 + 30 + 20 = 100
25
25
50

Моделирование
§ 16. Списки и деревья

Что такое список?
Список – последовательность элементов, в которой важен порядок их расположения.
['Amicus', 'Socrates', 'sed', 'magis', 'amica', 'veritas']
Список как модель:
слово = список букв, текст = список абзацев
Запись:

Операции со списком
замена элемента
удаление элемента
вставка нового элемента
КРАН → КОАН → КОРН → КОРО → КОРОН → КОРОНА

Что такое дерево?
Дерево – это структура данных, которая служит моделью многоуровневой структуры (иерархии).
Лес – это несколько деревьев.

Из чего состоит дерево?
A –
D, E, F, G –
корень
листья
B, C –
промежуточные
узлы
Путь — это последовательность узлов, где каждый следующий связан с предыдущим.
Высота дерева — это количество уровней.
Поддерево — это часть дерева, которая тоже представляет собой дерево.
левое
поддерево
правое
поддерево

Родители и дети
B – родитель для D и E
D и E – сыновья для B
Предок – потомок: между ними есть путь.
A и B – предки для D и E
B, D и E – потомки для A
Родитель – сын: между ними есть ребро.

Генеалогическое дерево
Иванов А.Б.
Иванова Д.А.
Семёнова М.А.
Иванов К.А.
Семёнов C.C.
Семёнов А.C.
Иванов C.К.

Классификации
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2. Кошкоообразные 2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые

Файловая система

Арифметические выражения
Двоичное (бинарное) дерево – это дерево, в котором каждый узел может иметь не более двух сыновей.

Перебор вариантов
Составить все двухбуквенные слова, которые можно записать с помощью алфавита {A, Б, В}.
Б
Б
A
В
Б
В
Б
A
В
A
A
В
пустое дерево
БВ

Перебор вариантов
Разведчик выяснил, что ключ к замку от сейфа состоит из трёх символов, причём могут использоваться буквы из алфавита {A, B, C, D}. Две одинаковые буквы не могут стоять рядом. Рядом с буквой D обязательно должна стоять буква A. Если в ключе есть буква B, то там не может быть буквы C.
14

Дерево для двоичного кода
Г
Д
Б
В
А
0
1
1
0
0
1
0
1
Условие Фано: ни одно из кодовых слов не совпадет с началом другого кодового слова.
тогда однозначно декодируется!

Моделирование
§ 17. Графы

Графы
«От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и Ягодное. Между Солнцевым и Грибным и между Грибным и Ягодным также есть дороги. Кроме того, есть дорога, которая идет из Грибного в лес и возвращается обратно в Грибное».

Графы
Граф – это набор вершин (узлов) и связей между ними (рёбер).

Матрица и список смежности
петля
Матрица смежности
Степень вершины – это количество связанных с ней рёбер (петля считается дважды!).
2
3
5
2

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

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

Нарисуйте граф

Нарисуйте граф

Нарисуйте граф

Связность графа

Дерево – это граф?
дерево
ABC ABDC
BCD CCC…

Взвешенные графы
12
8
2
5
4
6
Весовая матрица:
вес ребра

Постройте весовую матрицу

Постройте весовую матрицу

Нарисуйте граф

Нарисуйте граф

Нарисуйте граф

Кратчайший путь (перебор)
A
B
С
E
С
D
С
D
E
D
2
4
6
2
4
6
1
3
1
3
9
7
5
8
4
1
3
7
дерево возможных путей
Определите кратчайший путь между пунктами A и D.

Кратчайший путь
Определите кратчайший путь между пунктами A и E.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра называю дугами.

Нарисуйте орграф

Нарисуйте орграф

Количество путей из А в Ж
1
1
1
1+1+1=3
1
1+1+1+1+3=7
1

Количество путей из А в К

Количество путей из А в К

Количество путей из А в К

Количество путей из А в К

Моделирование
§ 18. Игровые стратегии

Что такое игровая модель?
Игровая модель — это модель, которая описывает соперничество двух (или более) сторон, каждая из которых преследует свою цель.
Стратегия — это алгоритм игры, который позволяет добиться цели в игре в предположении, что соперники играют безошибочно.
Теория игр: как играть, чтобы получить наибольший выигрыш?
Игры с полной информацией: нет случайностей:
крестики-нолики
шашки
шахматы
…

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

Выигрышные и проигрышные позиции
ходят нолики

Выигрышные и проигрышные позиции
позиция, из которой все возможные ходы ведут в выигрышные позиции, — проигрышная
позиция, из которой хотя бы один из возможных ходов ведёт в проигрышную позицию, — выигрышная
при этом выигрышная стратегия состоит в том, чтобы перевести игру в эту проигрышную (для соперника) позицию.
Ходят нолики:
выигрышная
проигрышная
выигрышная

Дерево перебора вариантов
Два игрока, куча из S камней. За один ход игрок может взять один или два камня. Тот, кто возьмёт последний камень, проигрывает.
4
П:
В:
П:
В:
Первый
Второй
2
2
1
1
1
3
4

Неполное дерево игры
Цель – доказать выигрыш.
4
все возможные ходы того, кто проигрывает
достаточно одного хода того, кто выигрывает

Таблица позиций
П1
В1
В1
П2
В2
В2
П3
В3
В3
П4
Нужно оставлять сопернику N = 3⋅k + 1 камней.

Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
[email protected]