informaticsSimilar presentations:
Моделирование. Модели и моделирование
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. Разработка математической модели
Ещё допущения:
• мяч – материальная точка
• нет сопротивления воздуха
Формализация:
g t
y h0 v0 t
2
2
h0 – начальная высота
v0 – начальная скорость
t – время
где
Мяч упал:
!
g t
0 h0 v0 t n
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 t n2
0 h0 v0 t n
2
? Что такое a, b, c, D?
алг Полёт
нач
вещ 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
Кумир
http://kpolyakov.spb.ru
22. IV. Построение компьютерной модели
Моделирование, 9 класс22
IV. Построение компьютерной модели
?
g t n2
Что такое a, b, c, D?
0 h0 v0 t n
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. Построение компьютерной модели
? Что такое a, b, c, D?
g t n2
0 h0 v0 t n
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
Python
http://kpolyakov.spb.ru
24. IV. Построение компьютерной модели
Моделирование, 9 класс24
IV. Построение компьютерной модели
?
g t n2
Что такое a, b, c, D?
0 h0 v0 t n
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
Таблицы
Связи между объектами:
Лада
УАЗ
Тойота
Форд
Москва
Санкт-Петербург
Пермь
210
350
200
805
260
150
370
410
230
Вася
Маша
Даша
520
430
120
Петя
Барнаул
Хабаровск
Владивосток
Магадан
К.Ю. Поляков, Е.А. Ерёмин, 2018
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
Скорость ветра, м/с
5
К.Ю. Поляков, Е.А. Ерёмин, 2018
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
А
1
0
1
декодировать?
0
Условие Фано: ни одно из
кодовых слов не совпадет
с началом другого
кодового слова.
Б
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
B
C
D
A
0
0
1
1
B
0
0
1
0
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
1
1
0
0
D
1
0
0
0
A
B
C
D
A
0
1
0
1
B
1
0
1
0
C
0
1
0
1
D
1
0
1
0
http://kpolyakov.spb.ru
59. Нарисуйте граф
Моделирование, 9 класс59
Нарисуйте граф
A
B
C
D
E
A
0
0
1
1
0
B
0
0
1
0
1
C D E
1 1 0
1 0 1
0 0 1
0 0 0
1 0 0
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A
0
0
1
1
1
B
0
0
1
0
0
C D E
1 1 1
1 0 0
0 0 1
0 0 0
1 0 0
http://kpolyakov.spb.ru
60. Нарисуйте граф
Моделирование, 9 класс60
Нарисуйте граф
A
B
C
D
E
A
0
0
1
1
1
B
0
0
1
0
1
C D E
1 1 1
1 0 1
0 0 1
0 0 0
1 0 0
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A
0
0
0
1
0
B
0
0
1
0
1
C D E
0 1 0
1 0 1
0 1 1
1 0 0
1 0 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
A
D
C
4
B
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
2
-2
-1
-2
1
1
0
2
-1
-2
-1
-1
0
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. loadmap.net
2. pilotrc.ru
3. www.ship268.com
4. www.globusy.ru
5. infourok.ru
6. alkhimikov.net
7. redcross-mosuvao.ru
8. studopedia.info
9. portalsystem.ru
10. biographera.net
11. tylove.ru
12. lms.101xp.com
13. mbofsantarosa.com
14. bumblebee.org
15. ru.wikipedia.org
16. иллюстрации художников издательства «Бином»
17. авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru