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

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

1
Моделирование
§ 13. Модели и моделирование
§ 14. Математическое моделирование
§ 15. Табличные модели. Диаграммы
§ 16. Списки и деревья
§ 17. Графы
§ 18. Игровые стратегии
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

2
Моделирование
§ 13. Модели и моделирование
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Что такое модель?

Моделирование, 9 класс
3
Что такое модель?
модели чего?
автомобиль
!
Земля
кристаллическая
решётка
корабль
Моделей без оригинала не существует!
дом
оригиналы
Оригиналы:
• объекты (самолет, дом, ядро атома, галактика)
• процессы (изменение климата, развитие экономики)
• явления природы (землетрясения, цунами)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

4. Что такое модель?

Моделирование, 9 класс
4
Что такое модель?
?
Зачем нужны модели?
Нужно решить задачу, связанную с оригиналом, но:
• оригинал не существует
- древний Египет
- последствия ядерной войны (Н.Н. Моисеев, 1966)
• исследование оригинала дорого или опасно
- управление ядерным реактором (Чернобыль, 1986)
- испытание нового скафандра для космонавтов
- разработка нового самолета или корабля
• оригинал сложно исследовать
-
Солнечная система, галактика (большие размеры)
атом, нейтрон (маленькие размеры)
процессы в двигателе внутреннего сгорания (очень быстрые)
геологические явления (очень медленные)
• интересуют только отдельные свойства
- проверка краски для фюзеляжа самолета
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Модели и оригиналы

Моделирование, 9 класс
5
Модели и оригиналы
оригинал
задача
модели человека
К.Ю. Поляков, Е.А. Ерёмин, 2018
модель
материальная точка
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
6
Модели и моделирование
Модель – это объект, который обладает существенными
свойствами другого объекта, процесса или явления
(оригинала) и используется вместо него.
Моделирование – это создание и исследование моделей
с целью изучения оригиналов.
Задачи моделирования:
• исследование оригинала
• анализ («что будет, если …»)
• синтез («как сделать, чтобы …»)
• оптимизация («как сделать лучше всего …»)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

7. Виды моделей (по природе)

Моделирование, 9 класс
7
Виды моделей (по природе)
модели
материальные
информационные
знаковые
вербальные
графические
табличные
математические
логические
специальные
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

8. Виды моделей (по фактору времени)

Моделирование, 9 класс
8
Виды моделей (по фактору времени)
• статические – описывают оригинал в заданный
момент времени
силы, действующие на тело в состоянии покоя
результаты осмотра врача
фотография
…
• динамические
модель движения тела
явления природы (молния, землетрясение, цунами)
история болезни
видеозапись события
…
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

9. Виды динамических моделей

Моделирование, 9 класс
9
Виды динамических моделей
• непрерывные – описывают оригинал в любой момент
времени на заданном интервале
y
y = 2t + 5
t
• дискретные – описывают оригинал только в отдельные
моменты времени (через 1 сек, час, год, …)
yi = 2ti + 5
y
y1 y2 y3
yi = 5yi–1 + 5
y4
y0
t
t0 t1 t2 t3 t4
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

10. Виды моделей (по характеру связей)

Моделирование, 9 класс
10
Виды моделей (по характеру связей)
• детерминированные – при одинаковых исходных
данных всегда получается тот же результат
расчёт по формулам
движение корабля на спокойной воде
…
• вероятностные – учитывают случайность событий
броуновское движение частиц
полета самолёта с учетом ветра
движения корабля на волнении
поведение человека
…
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

11. Имитационные модели

Моделирование, 9 класс
11
Имитационные модели
• нельзя заранее вычислить или предсказать поведение
системы, но можно имитировать её реакцию на внешние
воздействия
• максимальный учет всех факторов
• только численные результаты
!
Задача – найти лучшее решение методом
проб и ошибок (многократные эксперименты)!
Примеры:
• испытания лекарств на мышах, обезьянах, …
• математическое моделирование биологических систем
• модели систем массового обслуживания
• модели процесса обучения
• кросс-программирование
•…
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

12. Игровые модели

Моделирование, 9 класс
12
Игровые модели
Игровые модели учитывают действия противников.
экономические ситуации
военные действия
спортивные игры
тренинги персонала
!
Задача – найти лучший вариант действий в
самом худшем случае!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

13. Адекватность

Моделирование, 9 класс
13
Адекватность
Адекватность – это совпадение существенных свойств
модели и оригинала в данной задаче.
результаты моделирования согласуются с выводами
теории (законы сохранения и т.п.)
X – моделирование
X* - эксперимент
подтверждаются экспериментом
относительная ошибка X
!
X X*
X*
100% < 10%
Адекватность модели можно доказать только
экспериментом!
Модель всегда отличается от оригинала
!
Любая модель адекватна только при
определенных условиях!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

14. Пересчёт «модель-оригинал»

Моделирование, 9 класс
14
Пересчёт «модель-оригинал»
?
7,6 см
Сколько на местности?
7,6 см 500000
100 1000
= 38 км
М 1:500000
В более сложных случаях используют теорию подобия.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

15
Моделирование
§ 14. Математическое
моделирование
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

Моделирование, 9 класс
17
I. Постановка задачи
Мальчик Вася в синей кепке бросает белый мяч со
скоростью 12 м/с. Когда мяч впервые ударится о землю?
?
Хорошо поставлена?
Допущения:
• Вася бросает мяч вертикально вверх.
• В момент броска мяч находится на высоте 1,5 м.
? Всегда ли есть решение?
? Решение единственно?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

18. II. Разработка математической модели

Моделирование, 9 класс
18
II. Разработка математической модели
1) выделить существенные исходные данные:
• начальная скорость 12 м/с
• бросок вертикально вверх
• ускорение свободного падения 9,81 м/с2
2) построить математическую модель
Графическая модель:
y
v0
h0, v0
исходные данные
?
модель
tп
результаты
Такой модели достаточно?
h0
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

19. II. Разработка математической модели

Моделирование, 9 класс
19
II. Разработка математической модели
Ещё допущения:
• мяч – материальная точка
• нет сопротивления воздуха
Формализация:
h0
v0
t
где
g t
y h0 v0 t
2
– начальная высота
– начальная скорость
– время
Мяч упал:
!
2
g t
0 h0 v0 tn
2
2
n
Связали исходные данные и результат!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

20. III. Тестирование модели

Моделирование, 9 класс
20
III. Тестирование модели
Тестирование – это проверка модели на простых
исходных данных с известным результатом.
g t
y h0 v0 t
2
2
• при t = 0 y = h0 (в начальной точке)
• при v0 = 0 падение вниз
?
Доказывает ли успешное тестирование
правильность модели?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

21. IV. Построение компьютерной модели

Моделирование, 9 класс
21
IV. Построение компьютерной модели
g tn2
0 h0 v0 tn
2
?
алг Полёт
нач
вещ 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
кон
К.Ю. Поляков, Е.А. Ерёмин, 2018
Что такое a, b, c, D?
Кумир
http://kpolyakov.spb.ru

22. IV. Построение компьютерной модели

Моделирование, 9 класс
22
IV. Построение компьютерной модели
?
g tn2
Что такое a, b, c, D?
0 h0 v0 tn
2
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.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

23. IV. Построение компьютерной модели

Моделирование, 9 класс
23
IV. Построение компьютерной модели
?
g tn2
0 h0 v0 tn
2
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 )
К.Ю. Поляков, Е.А. Ерёмин, 2018
Что такое a, b, c, D?
Python
http://kpolyakov.spb.ru

24. IV. Построение компьютерной модели

Моделирование, 9 класс
24
IV. Построение компьютерной модели
?
g tn2
Что такое a, b, c, D?
0 h0 v0 tn
2
#include <iostream>
C++
#include <cmath>
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;
}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

25. Компьютерная имитационная модель

Моделирование, 9 класс
25
Компьютерная имитационная модель
если нельзя просто решить уравнение…
интервал
дискретизации
Дискретизация задачи:
моменты времени: 0, t, 2 t, 3 t, …, ti = i t
y
0 t
t
Рассматриваем [ti, ti+1]
Знаем yi и vi при t = ti получить yi+1 и vi+1 при t = ti +1
!
Считаем, что скорость
меняется скачком!
К.Ю. Поляков, Е.А. Ерёмин, 2018
yi+1 = yi + vi t
vi+1 = vi – g t
http://kpolyakov.spb.ru

26. Компьютерная имитационная модель

Моделирование, 9 класс
26
Компьютерная имитационная модель
алг Полёт-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
Что такое y, v, t, dt?
v:= v - g*dt
t:= t + dt
кц
вывод t
кон
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

27. Компьютерная имитационная модель

Моделирование, 9 класс
27
Компьютерная имитационная модель
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;
Что такое y, v, t, dt?
t:= t + dt;
end;
writeln(t);
end.
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

28. Компьютерная имитационная модель

Моделирование, 9 класс
28
Компьютерная имитационная модель
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 )
К.Ю. Поляков, Е.А. Ерёмин, 2018
Python
?
Что такое y, v, t, dt?
http://kpolyakov.spb.ru

29. Компьютерная имитационная модель

Моделирование, 9 класс
29
Компьютерная имитационная модель
#include <iostream>
С++
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;
Что такое y, v, t, dt?
v = v - g*dt;
t = t + dt;
}
cout << t;
}
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

30. V. Эксперимент с моделью

Моделирование, 9 класс
30
V. Эксперимент с моделью
Эксперимент – это исследование модели при тех
исходных данных, которые нас интересуют (результат
заранее неизвестен).
!
Можно ли верить результатам?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
31
VI. Анализ результатов
!
Необходима проверка на оригинале!
Возможные выводы:
• задача решена, модель адекватна
• необходимо изменить алгоритм или условия
моделирования
• необходимо изменить модель (учесть
дополнительные свойства)
• необходимо изменить постановку задачи
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

32
Моделирование
§ 15. Табличные модели.
Диаграммы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

33. Таблицы

Моделирование, 9 класс
33
Таблицы
Свойства объектов:
Фамилия
Иванов
Кузьмин
Сидоров
Имя
Кузьма
Сидор
Иван
Год
рождения
1955
1978
1990
Место отдыха
о. Валаам
о. Ольхон
о. Кипр
Лада
Приора
Лада
Калина
Мощность
двигателя, л.с.
98
89
79
70
Максимальная
скорость, км/ч
183
165
165
156
Время разгона
до 100 км/ч, с
11,5
12,5
14
15
Марка
К.Ю. Поляков, Е.А. Ерёмин, 2018
ВАЗ 2110 ВАЗ 21099
http://kpolyakov.spb.ru

34. Таблицы

Моделирование, 9 класс
34
Таблицы
Связи между объектами:
Лада
Москва
Санкт-Петербург
Пермь
520
430
120
Петя
Барнаул
Хабаровск
Владивосток
Магадан
К.Ю. Поляков, Е.А. Ерёмин, 2018
УАЗ
Тойота
Форд
210
350
200
805
260
150
370
410
230
Вася
Маша
Даша
http://kpolyakov.spb.ru

35. Таблицы

Моделирование, 9 класс
35
Таблицы
Изменение свойств:
День
1
2
3
4
5
6
7
Температура, C
15
18
20
17
23
16
19
Давление, мм. рт. ст.
750 748 760 755 770 743 756
Скорость ветра, м/с
К.Ю. Поляков, Е.А. Ерёмин, 2018
5
7
2
9
3
6
4
http://kpolyakov.spb.ru

36. Оптимальный маршрут

Моделирование, 9 класс
36
Оптимальный маршрут
Из
Березовое
Березовое
Лесное
Полевое
Осиновое
Лесное
Осиновое
Березовое
Лесное
Полевое
В
Лесное
Осиновое
Березовое
Лесное
Полевое
Осиновое
Лесное
Полевое
Полевое
Осиновое
Отправл.
07:30
11:50
12:50
13:20
14:00
14:20
14:40
16:00
16:10
17:40
Прибытие
10:00
14:10
15:20
14:40
17:15
15:30
15:50
17:50
17:30
19:55
Березовое: 8:00
Полевое
17:50 П
16:00
Б 07:30
11:50
10:00 Л
14:00
14:10 О
14:40
К.Ю. Поляков, Е.А. Ерёмин, 2018
17:15 П
15:50 Л 16:10
17:30 П
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
37
Анализ диаграмм
а)
30
25
лоси
белки
зайцы
20
15
лоси
белки
10
5
0
зайцы
б)
I участок II участок III участок
зайцы
лоси
лоси
белки
зайцы
всего
I участок
15
30
10
II участок
30
20
15
III участок
15
10
15
всего
60
60
40
160
белки
в)
зайцы
лоси
белки
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
38
Анализ диаграмм
1)
10 + 40 + 30 + 20 = 100
2)
25
40
менеджеры
30
50
рабочие
20
охрана
10
0
«Лада» «Форд» «Тойота» «Ауди»
25
а) все «Форды» могут принадлежать менеджерам
б) все охранники могут ездить на «Ауди»
в) все «Тойоты» могут принадлежать рабочим
г) все рабочие могут ездить на «Фордах»
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

39
Моделирование
§ 16. Списки и деревья
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

40. Что такое список?

Моделирование, 9 класс
40
Что такое список?
Список – последовательность элементов, в которой
важен порядок их расположения.
П
О
Л
И
предыдущий
Г
Л
О
Т
следующий
Список как модель:
слово = список букв, текст = список абзацев
Запись:
['Amicus', 'Socrates', 'sed', 'magis', 'amica', 'veritas']
?
Что это значит?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

41. Операции со списком

Моделирование, 9 класс
41
Операции со списком
• замена элемента
• удаление элемента
• вставка нового элемента
?
Какие операции на
каждом шаге?
КРАН КОАН КОРН КОРО КОРОН КОРОНА
?
Более короткие варианты?
Операция
Замена гласной буквы на гласную или
согласной на согласную.
Замена гласной на согласную или согласной
на гласную.
Вставка или удаление буквы.
?
Цена
1
2
5
СКАНЕР ПРИНТЕР с наименьшей стоимостью?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

42. Что такое дерево?

Моделирование, 9 класс
42
Что такое дерево?
директор
Уровень 1
Уровень 2
Уровень 3
главный инженер
Петров
Иванов
Фомин
Дерево – это структура
данных, которая служит
моделью многоуровневой
структуры (иерархии).
главный бухгалтер
Алексеева
Сидорова
лист лист
лист
лист
лист
Лес – это несколько деревьев.
корень
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

43. Из чего состоит дерево?

Моделирование, 9 класс
43
Из чего состоит дерево?
левое
поддерево
B
D
A
правое
поддерево
рёбра
C
E
F
A – корень
D, E, F, G – листья
B, C – промежуточные
узлы
G
Путь — это последовательность узлов, где каждый
следующий связан с предыдущим.
Высота дерева — это количество уровней.
Поддерево — это часть дерева, которая тоже
представляет собой дерево.
?
Какие есть поддеревья?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

44. Родители и дети

Моделирование, 9 класс
44
Родители и дети
Родитель – сын: между ними есть ребро.
B – родитель для D и E
D и E – сыновья для B
A
B
D
C
E
F
G
? Если нет родителей?
? Если нет сыновей?
Предок – потомок: между ними есть путь.
A и B – предки для D и E
B, D и E – потомки для A
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

45. Генеалогическое дерево

Моделирование, 9 класс
45
Генеалогическое дерево
Иванов А.Б.
Иванова Д.А.
внуки
Иванов К.А.
Иванов C.К.
К.Ю. Поляков, Е.А. Ерёмин, 2018
Семёнова М.А.
Семёнов C.C.
дети
Семёнов А.C.
http://kpolyakov.spb.ru

46. Классификации

Моделирование, 9 класс
46
Классификации
Хищные
Псообразные
Псовые
Енотовые
Медвежьи
Кошкообразные
Кошачьи
Гиеновые
Мангустовые
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2. Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
47
Файловая система
Документы
Тексты
Фотографии
Доходы.doc Расходы.odt Отдых.txt Папа.jpg
Мама.gif
Документы
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Фотографии
Папа.jpg
Мама.gif
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

48. Арифметические выражения

Моделирование, 9 класс
48
Арифметические выражения
-
(a+3)*5-2*b*c
*
+
a
*
5
3
2
*
b
c
Двоичное (бинарное) дерево – это дерево, в котором
каждый узел может иметь не более двух сыновей.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

49. Перебор вариантов

Моделирование, 9 класс
49
Перебор вариантов
Составить все двухбуквенные слова, которые можно
записать с помощью алфавита {A, Б, В}.
пустое дерево
Б
A
В
БВ
A
Б
В
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
Б
В
A
Б
В
http://kpolyakov.spb.ru

50. Перебор вариантов

Моделирование, 9 класс
50
Перебор вариантов
Разведчик выяснил, что ключ к замку от сейфа
состоит из трёх символов, причём могут
использоваться буквы из алфавита {A, B, C, D}. Две
одинаковые буквы не могут стоять рядом. Рядом с
буквой D обязательно должна стоять буква A. Если в
ключе есть буква B, то там не может быть буквы C.
?
Сколько возможных ключей?
К.Ю. Поляков, Е.А. Ерёмин, 2018
14
http://kpolyakov.spb.ru

51. Дерево для двоичного кода

Моделирование, 9 класс
51
Дерево для двоичного кода
А
0
?
Б
11
В
Г
Д
101 110 111
Можно однозначно
декодировать?
0
А
0
0
Условие Фано: ни одно из
кодовых слов не совпадет
с началом другого
кодового слова.
!
1
1
В
1
Б
0
Г
1
Д
тогда однозначно
декодируется!
Все буквы должны быть в листьях!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

52
Моделирование
§ 17. Графы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

53. Графы

Моделирование, 9 класс
53
Графы
«От посёлка Васюки три дороги идут в
посёлки Солнцево, Грибное и Ягодное.
Между Солнцевым и Грибным и между
Грибным и Ягодным также есть дороги.
Кроме того, есть дорога, которая идет
из Грибного в лес и возвращается
обратно в Грибное».
?
Как структурировать?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

54. Графы

Моделирование, 9 класс
54
Графы
Солнцево
A
C
B
D
Грибное
Васюки
Ягодное
Граф – это набор вершин (узлов) и связей между ними
(рёбер).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

55. Матрица и список смежности

Моделирование, 9 класс
55
Матрица и список смежности
Матрица смежности
A
B
C
D
A
B
C
D
A
0
1
1
0
B
1
0
1
1
C
1
1
1
1
D
0
1
1
0
2
3
5
2
петля
Степень вершины – это количество связанных с ней
рёбер (петля считается дважды!).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
56
Постройте матрицу смежности
A
A
D
C
B
A
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
B
D
D
C
A
B
C
D
A
B
C
D
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
57
Постройте матрицу смежности
A
A
D
D
B
C
B
A
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
C
D
A
B
C
D
A
B
C
D
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
58
Нарисуйте граф
A
A
B
C
D
0
1
1
B
0
1
0
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
1
1
0
D
1
0
0
A
A
B
C
D
1
0
1
B
1
1
0
C
0
1
D
1
0
1
1
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
59
Нарисуйте граф
A
B
C
D
E
A B
0
0
1 1
1 0
0 1
C D E
1 1 0
1 0 1
0 1
0
0
1 0
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A B
0
0
1 1
1 0
1 0
C D E
1 1 1
1 0 0
0 1
0
0
1 0
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
60
Нарисуйте граф
A
B
C
D
E
A B
0
0
1 1
1 0
1 1
C D E
1 1 1
1 0 1
0 1
0
0
1 0
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A B
0
0
0 1
1 0
0 1
C D E
0 1 0
1 0 1
1 1
1
0
1 0
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
61
Связность графа
A
C
B
D
!
Связный граф – это
граф, между любыми
вершинами которого
существует путь.
Солнцево
A
C
B
D
Грибное
Васюки
Ягодное
компоненты связности
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

62. Дерево – это граф?

Моделирование, 9 класс
62
Дерево – это граф?
!
Дерево – это связный граф без
циклов (замкнутых путей).
A
A
C
B
D
B
ABC
BCD
D
ABDC
CCC…
К.Ю. Поляков, Е.А. Ерёмин, 2018
H
C
E
F
G
J
дерево
http://kpolyakov.spb.ru

63. Взвешенные графы

Моделирование, 9 класс
63
Взвешенные графы
2
Солнцево
8
A
Грибное
12
5
B
Ягодное
Васюки
2
C
5
12
4
8
4
6
D
6
вес ребра
Весовая матрица:
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
A
B
C
D
12
8
B
12
5
6
C
8
5
2
4
D
6
4
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
64
Постройте весовую матрицу
A
A
4
1
3
B
3
1
A
C
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
2
C
D
D
1
2
B
C
4
A
B
D
C
D
A
B
C
D
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
65
Постройте весовую матрицу
2
A
D
1
3
A
4
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
C
1
D
2
1
B
1
B
A
C
A
B
D
4
C
D
A
B
C
D
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
66
Нарисуйте граф
A
A
B
C
D
B
4
C
3
4
3
D
2
6
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
6
A
B
C
D
A
B
C
2
2
3
4
5
D
3
4
5
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
67
Нарисуйте граф
A
B
C
D
E
A B
4
4
3
2
7
C D E
3
7
2
6
6
1
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A B
2
2
5
3
6
C D E
5
6
3
1
1
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
68
Нарисуйте граф
A B
A
B
C 2
D 2
E 6
2
C D E
2 2 6
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A B
5
5
2
5
6
C D E
2
6
5
2
2
3
3
http://kpolyakov.spb.ru

69. Кратчайший путь (перебор)

Моделирование, 9 класс
69
Кратчайший путь (перебор)
A B
2
A
B 2
C 4 1
D
E 6
C D E
4
6
1
5 1
5
3
1 3
Определите кратчайший путь
между пунктами A и D.
A
2
B
4
С
2
6
E
4
1
С
5
D
8
1
С
3
6
3
7
D
9
1
E
4
3
дерево возможных
путей
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
7
http://kpolyakov.spb.ru

70. Кратчайший путь

Моделирование, 9 класс
70
Кратчайший путь
A B
2
A
B 2
C 4 1
D
7
E
C D E
4
1
7
3 5
3
3
5 3
К.Ю. Поляков, Е.А. Ерёмин, 2018
Определите кратчайший
путь между пунктами A и E.
http://kpolyakov.spb.ru

71. Кратчайший путь

Моделирование, 9 класс
71
Кратчайший путь
A B
A
B
C 3
D 1
E
4
C D E
3 1
4
2
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
Определите кратчайший
путь между пунктами A и B.
http://kpolyakov.spb.ru

72. Кратчайший путь

Моделирование, 9 класс
72
Кратчайший путь
A B
A
B
C 3
D 1
E 1
4
C D E
3 1 1
4
2
Определите кратчайший
путь между пунктами A и B.
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

73. Кратчайший путь

Моделирование, 9 класс
73
Кратчайший путь
A B
A
B
C 3
D 1
E 4
4
C D E
3 1 4
4
2
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
Определите кратчайший
путь между пунктами A и B.
http://kpolyakov.spb.ru

74. Кратчайший путь

Моделирование, 9 класс
74
Кратчайший путь
A B
A
B
C
D 1
E
4
1
C D E
1
4
1
4 2
4
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
Определите кратчайший
путь между пунктами A и B.
http://kpolyakov.spb.ru

75. Ориентированные графы (орграфы)

Моделирование, 9 класс
75
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец),
рёбра называю дугами.
Солнцево
12
8
Грибное
5
Ягодное
6
!
Весовая матрица
может быть
несимметрична!
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
A
A
B
C
D
12
C
5
12
4
Васюки
8
4
D
6
B
12
C
8
5
D
6
4
4
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
76
Нарисуйте орграф
A B
A
B 2
C 3
D 1
E
C D E
3 1
4
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
A B
A
B
C 3
D
E
4
2
C D E
5 1
6 4
3
3
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
77
Нарисуйте орграф
A B
A
B
C
D
E 4
4
C D E
3 1 4
4
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
A B
A
B
C 3
D 1
E 1
4
2
1
C D E
1
4
1
4 2
4
2
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
78
Количество путей из А в Ж
Б
1
Д
1+1+1=3
1
А
1
1+1+1+1+3=7
Ж
Г
В
!
1
Е 1
NЖ= NД + NБ + NГ + NВ + NЕ
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
79
Количество путей из А в К
Д
Б
B
З
Е
А
К
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
Ж
И
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
80
Количество путей из А в К
Д
Б
B
З
Е
А
К
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
Ж
И
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
81
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
И
http://kpolyakov.spb.ru

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

Моделирование, 9 класс
82
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
И
http://kpolyakov.spb.ru

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

83
Моделирование
§ 18. Игровые стратегии
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

84. Что такое игровая модель?

Моделирование, 9 класс
84
Что такое игровая модель?
Игровая модель — это модель, которая описывает
соперничество двух (или более) сторон, каждая из
которых преследует свою цель.
Теория игр: как играть, чтобы получить наибольший
выигрыш?
Стратегия — это алгоритм игры, который позволяет
добиться цели в игре в предположении, что соперники
играют безошибочно.
Игры с полной информацией: нет случайностей:
• крестики-нолики
Какие игры с неполной
• шашки
информацией?
• шахматы
• …
!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

85. Выигрышные и проигрышные позиции

Моделирование, 9 класс
85
Выигрышные и проигрышные позиции
игра без ничьих…
Выигрышная позиция — это такая позиция, в которой
игрок, делающий первый ход, может гарантированно
выиграть при любой игре соперника, если не сделает
ошибку.
Есть выигрышная стратегия — алгоритм выбора
очередного хода, позволяющий выиграть.
Проигрышная позиция — это такая позиция, в которой
игрок, делающий первый ход, обязательно проиграет,
если его соперник не сделает ошибку.
Нет выигрышной стратегии…
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

86. Выигрышные и проигрышные позиции

Моделирование, 9 класс
86
Выигрышные и проигрышные позиции
ходят нолики
а) ×
×
б) ×
×
×
д) ×
×
×
е) ×
К.Ю. Поляков, Е.А. Ерёмин, 2018
×
в)
×
×
×
ж) ×
×
×
×
г) × ×
×
з) ×
×
http://kpolyakov.spb.ru

87. Выигрышные и проигрышные позиции

Моделирование, 9 класс
87
Выигрышные и проигрышные позиции
• позиция, из которой все возможные ходы ведут в
выигрышные позиции, — проигрышная
• позиция, из которой хотя бы один из возможных ходов
ведёт в проигрышную позицию, — выигрышная
при этом выигрышная стратегия состоит в том,
чтобы перевести игру в эту проигрышную (для
соперника) позицию.
Ходят нолики:
×
×
×
×
×
×
выигрышная
×
× ×
проигрышная выигрышная
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

88. Дерево перебора вариантов

Моделирование, 9 класс
88
Дерево перебора вариантов
Два игрока, куча из S камней. За один ход игрок может
взять один или два камня. Тот, кто возьмёт последний
камень, проигрывает.
Первый
Второй
4
-1
П:
3
-1
В:
П:
-2
1
0
-1
В:
К.Ю. Поляков, Е.А. Ерёмин, 2018
0
-1
-2
1
1
0
-1
-1
0
?
2
-2
2
-1
-2
0
Какие выигрышные?
http://kpolyakov.spb.ru

89. Неполное дерево игры

Моделирование, 9 класс
89
Неполное дерево игры
Цель – доказать выигрыш.
-1
П:
4
-2
3
2
-2
В:
1
-1
1
0
К.Ю. Поляков, Е.А. Ерёмин, 2018
достаточно одного хода
того, кто выигрывает
-1
-1
П:
все возможные ходы
того, кто проигрывает
0
http://kpolyakov.spb.ru

90. Таблица позиций

Моделирование, 9 класс
90
Таблица позиций
S
10
П4
?
9
В3
8
В3
7
П3
6
В2
5
В2
4
П2
3
В1
2
В1
1
П1
Какова стратегия?
Нужно оставлять сопернику N = 3 k + 1 камней.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

91. Конец фильма

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

92. Источники иллюстраций

Моделирование, 9 класс
92
Источники иллюстраций
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
loadmap.net
pilotrc.ru
www.ship268.com
www.globusy.ru
infourok.ru
alkhimikov.net
redcross-mosuvao.ru
studopedia.info
portalsystem.ru
biographera.net
tylove.ru
lms.101xp.com
mbofsantarosa.com
bumblebee.org
ru.wikipedia.org
иллюстрации художников издательства «Бином»
авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru