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

Сентябрь 3, 2022

Главная
Алгебра
Моделирование.pptx

Содержание

2. Модели в нашей жизни
3. Что такое модель? Модель – это объект, который обладает некоторыми свойствами другого объекта (оригинала) и используется
4. Что можно моделировать? Модели объектов: уменьшенные копии зданий, кораблей, самолетов, … модели ядра атома, кристаллических решеток
5. Моделирование Моделирование – это создание и использование моделей для изучения оригиналов. Когда используют моделирование: оригинал не
6. Цели моделирования исследование оригинала изучение сущности объекта или явления «Наука есть удовлетворение собственного любопытства за казенный
7. Один оригинал – одна модель? материальная точка
8. Зачем нужно много моделей? изучение строения тела примерка одежды изучение наследственности тренировка спасателей учет граждан страны
9. Природа моделей материальные (физические, предметные) модели: информационные модели представляют собой информацию о свойствах и состоянии объекта,
10. Классификация моделей
11. 1. Модели по области применения учебные (в т.ч. тренажеры) опытные – при создании новых технических средств
12. 2. Модели по фактору времени статические – описывают оригинал в заданный момент времени силы, действующие на
13. 3. Модели по характеру связей детерминированные связи между входными и выходными величинами жестко заданы при одинаковых
14. 4. Модели по структуре табличные модели (пары соответствия) иерархические (многоуровневые) модели сетевые модели (графы)
15. Типы моделей
16. Словесные модели Словесные модели - это описания предметов, явлений, событий, процессов на естественных языках Роман Словесная
17. Компьютерные математические модели Компьютерными математическими моделями называются математические модели, реализованные с помощью систем программирования, электронных таблиц,
18. Имитационные модели нельзя заранее вычислить или предсказать поведение системы, но можно имитировать её реакцию на внешние
19. Билетная касса Торговое предприятие Ремонтная мастерская Служба скорой помощи Управление транспортными потоками Системы массового обслуживания Имитационные
20. Игровые модели игровые – учитывающие действия противника Примеры: модели экономических ситуаций модели военных действий спортивные игры
21. Адекватность Адекватность – это совпадение существенных свойств модели и оригинала в данной задаче. Модель всегда отличается
22. Пересчёт «модель-оригинал» 7,6 см М 1:500000 7,6 см  500000 = 38 км В более сложных
23. © К.Ю. Поляков, 2007-2011 Тема 2. Этапы моделирования
24. I. Постановка задачи Хорошо поставленная задача: описаны все связи между исходными данными и результатом известны все
25. II. Разработка модели выбрать тип модели определить существенные свойства оригинала, которые нужно включить в модель, отбросить
26. III. Тестирование модели Тестирование – это проверка модели на простых исходных данных с известным результатом. Примеры:
27. IV. Эксперимент c моделью Эксперимент – это исследование модели в интересующих нас условиях. Примеры: устройство для
28. V. Проверка практикой, анализ результатов Возможные выводы: задача решена, модель адекватна необходимо изменить алгоритм или условия
29. Пример. Задача. Обезьяна хочет сбить бананы на пальме. Как ей надо кинуть кокос, чтобы попасть им
30. I. Постановка задачи Допущения: кокос и банан считаем материальными точками расстояние до пальмы известно рост обезьяны
31. II. Разработка модели Графическая модель h Формальная (математическая) модель Задача: найти t, , при которых
32. III. Тестирование модели при нулевой скорости кокос падает вертикально вниз при t=0 координаты равны (0,h) при
33. IV. Эксперимент Метод I. Меняем угол . Для выбранного угла  строим траекторию полета ореха. Если
34. V. Анализ результатов Всегда ли обезьяна может сбить банан? Что изменится, если обезьяна может бросать кокос
35. Математическое моделирование Моделирование
36. I. Постановка задачи Мальчик Вася в синей кепке бросает белый мяч со скоростью 12 м/с. Когда
37. II. Разработка математической модели выделить существенные исходные данные: начальная скорость 12 м/с бросок вертикально вверх ускорение
38. II. Разработка математической модели Формализация: Мяч упал: Ещё допущения: мяч – материальная точка нет сопротивления воздуха
39. III. Тестирование модели Тестирование – это проверка модели на простых исходных данных с известным результатом. •
40. IV. Построение компьютерной модели program Polet; var h0, v0, g: real; a, b, c, D, t1,
41. Компьютерная имитационная модель если нельзя просто решить уравнение… Дискретизация задачи: моменты времени: 0, t, 2t, 3t,
42. Компьютерная имитационная модель алг Полёт-2 нач вещ h0=1.5, v0=12, g=9.81 вещ y, v, t, dt=0.01 y:=
43. Компьютерная имитационная модель program Polet_2; var h0, v0, g: real; y, v, t, dt: real; begin
44. V. Эксперимент с моделью Эксперимент – это исследование модели при тех исходных данных, которые нас интересуют
45. VI. Анализ результатов Возможные выводы: задача решена, модель адекватна необходимо изменить алгоритм или условия моделирования необходимо
46. Системный подход
47. Системный подход Система – группа объектов и связей между ними, выделенных из среды и рассматриваемых как
48. Системный подход Модель-система: Модель-не-система: 1-я линия: Пр. Ветеранов Ленинский пр. Автово Кировский завод Нарвская … 2-я
49. Системный подход Граф – это набор вершин и соединяющих их ребер. 1 2 3 4 5
50. Семантическая (смысловая) модель предложения: «Выхожу один я на дорогу…» выхожу я на дорогу один что делаю?
51. Списки и деревья
52. Что такое список? Список – последовательность элементов, в которой важен порядок их расположения. ['Amicus', 'Socrates', 'sed',
53. Операции со списком замена элемента удаление элемента вставка нового элемента КРАН  КОАН  КОРН 
54. Что такое дерево? Дерево – это структура данных, которая служит моделью многоуровневой структуры (иерархии). Лес –
55. Из чего состоит дерево? A – D, E, F, G – корень листья B, C –
56. Родители и дети B – родитель для D и E D и E – сыновья для
57. Генеалогическое дерево Иванов А.Б. Иванова Д.А. Семёнова М.А. Иванов К.А. Семёнов C.C. Семёнов А.C. Иванов C.К.
58. Классификации Глава 1. Псообразные 1.1. Псовые 1.2. Енотовые 1.3. Медвежьи … Глава 2. Кошкоообразные 2.1. Кошачьи
59. Файловая система
60. Арифметические выражения Двоичное (бинарное) дерево – это дерево, в котором каждый узел может иметь не более
61. Перебор вариантов Составить все двухбуквенные слова, которые можно записать с помощью алфавита {A, B, C}. Б
62. Перебор вариантов Разведчик выяснил, что ключ к замку от сейфа состоит из трёх символов, причём могут
63. Дерево для двоичного кода Г Д Б В А 0 1 1 0 0 1 0
64. Графы «От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и Ягодное. Между Солнцевым и
65. Графы Граф – это набор вершин (узлов) и связей между ними (рёбер).
66. Матрица и список смежности петля Матрица смежности Степень вершины – это количество связанных с ней рёбер
67. Постройте матрицу смежности
68. Постройте матрицу смежности
69. Нарисуйте граф
70. Нарисуйте граф
71. Нарисуйте граф
72. Связность графа
73. Дерево – это граф? дерево ABC ABDC BCD CCC…
74. Взвешенные графы 12 8 2 5 4 6 Весовая матрица: вес ребра
75. Постройте весовую матрицу
76. Постройте весовую матрицу
77. Нарисуйте граф
78. Нарисуйте граф
79. Нарисуйте граф
80. Кратчайший путь (перебор) A B С E С D С D E D 2 4 6
81. Кратчайший путь Определите кратчайший путь между пунктами A и E.
82. Кратчайший путь Определите кратчайший путь между пунктами A и B.
83. Кратчайший путь Определите кратчайший путь между пунктами A и B.
84. Кратчайший путь Определите кратчайший путь между пунктами A и B.
85. Кратчайший путь Определите кратчайший путь между пунктами A и B.
86. Ориентированные графы (орграфы) Рёбра имеют направление (начало и конец), рёбра называю дугами.
87. Нарисуйте орграф
88. Нарисуйте орграф
89. Количество путей из А в Ж 1 1 1 1+1+1=3 1 1+1+1+1+3=7 1
90. Количество путей из А в К
91. Количество путей из А в К
92. Количество путей из А в К
93. Количество путей из А в К
94. Игровые стратегии
95. Что такое игровая модель? Игровая модель — это модель, которая описывает соперничество двух (или более) сторон,
96. Выигрышные и проигрышные позиции игра без ничьих… Выигрышная позиция — это такая позиция, в которой игрок,
97. Выигрышные и проигрышные позиции ходят нолики
98. Выигрышные и проигрышные позиции позиция, из которой все возможные ходы ведут в выигрышные позиции, — проигрышная
99. Дерево перебора вариантов Два игрока, куча из S камней. За один ход игрок может взять один
100. Неполное дерево игры Цель – доказать выигрыш. 4 все возможные ходы того, кто проигрывает достаточно одного
101. Таблица позиций П1 В1 В1 П2 В2 В2 П3 В3 В3 П4 Нужно оставлять сопернику N
102. Моделирование Табличные модели. Диаграммы
103. Таблицы Свойства объектов:
104. Таблицы Связи между объектами:
105. Таблицы Изменение свойств:
106. Оптимальный маршрут Березовое: 8:00 Полевое Б 16:00 07:30 11:50 14:00 14:40 16:10
107. Анализ диаграмм
108. Анализ диаграмм а) все «Форды» могут принадлежать менеджерам б) все охранники могут ездить на «Ауди» в)
109. Модели и моделирование © К.Ю. Поляков, 2007-2011 Тема 3. Модели биологических систем (по мотивам учебника А.Г.
110. – начальная численность – после 1 цикла деления – после 2-х циклов Особенности модели: не учитывается
111. – коэффициент рождаемости – коэффициент смертности Особенности модели: не учитывается влияние численности N и внешней среды
112. Модель ограниченного роста (П. Ферхюльст) L – предельная численность животных Идеи: коэффициент прироста KL зависит от
113. Модель с отловом Примеры: рыбоводческое хозяйство, разведение пушных зверей и т.п.
114. Модель эпидемии гриппа L – всего жителей Ni – больных в i-ый день Zi – заболевших
115. Модель системы «хищник-жертва» Модель – не-система: Модель – система: число встреч пропорционально NiZi «эффект» пропорционален числу
116. Модель системы «хищник-жертва» Хищники вымирают: Равновесие: караси щуки караси щуки
118. Модель системы «хищник-жертва» Колебания:
119. Модели и моделирование © К.Ю. Поляков, 2007-2011 Тема 4. Моделирование случайных процессов (по мотивам учебника А.Г.
120. Случайные процессы Случайно… встретить друга на улице разбить тарелку найти 10 рублей выиграть в лотерею Случайный
121. Случайные числа на компьютере Электронный генератор нужно специальное устройство нельзя воспроизвести результаты 318458191041 564321 209938992481 458191
122. Случайные числа на компьютере Линейный конгруэнтный метод a, c, m - целые числа простое число 230-1
123. Распределение случайных чисел Модель: снежинки падают на отрезок [a,b] распределение равномерное неравномерное
124. Распределение случайных чисел Особенности: распределение – это характеристика всей последовательности, а не одного числа равномерное распределение
125. Вычисление площади (метод Монте-Карло) Вписываем сложную фигуру в другую фигуру, для которой легко вычислить площадь (прямоугольник,
126. Вычисление площади Когда точка внутри круга? (x,y) Случайные координаты: x := R*random; y := R*random; Программа:
127. Броуновское движение Случайный шаг: Случайное направление (в рад): alpha := 2*pi*random; h := hMax*random; Программа: for
128. Системы массового обслуживания Примеры: звонки на телефонной станции вызовы «скорой помощи» обслуживание клиентов в банке сколько
129. Клиенты в банке Вход клиентов: за 1 минуту – до N человек равномерное распределение Обслуживание: от
130. Клиенты в банке Число клиентов в помещении банка: N := N + in - out; было
131. Клиенты в банке Пришли за очередную минуту: in := round(N*random); округление Обслужены за очередную минуту и
132. Клиенты в банке (программа) count := 0; { счетчик «плохих» минут } for i:=1 to L
134. Скачать презентацию

Слайд 2

Модели в нашей жизни

Слайд 3

Что такое модель?
Модель – это объект, который обладает некоторыми свойствами другого

объекта (оригинала) и используется вместо него.
Оригиналы и модели

Первый линейный русский корабль «Гото Предестинация»

Слайд 4

Что можно моделировать?
Модели объектов:
уменьшенные копии зданий, кораблей, самолетов, …
модели ядра атома,

кристаллических решеток
чертежи
…
Модели процессов:
изменение экологической обстановки
экономические модели
исторические модели
…
Модели явлений:
землетрясение
солнечное затмение
цунами
…

Слайд 5

Моделирование
Моделирование – это создание и использование моделей для изучения оригиналов.
Когда используют

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

Слайд 6

Цели моделирования
исследование оригинала
изучение сущности объекта или явления
«Наука есть удовлетворение собственного любопытства

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

Слайд 7

Один оригинал – одна модель?
материальная точка

Слайд 8

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

Слайд 9

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

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

Слайд 10

Классификация моделей

Слайд 11

1. Модели по области применения
учебные (в т.ч. тренажеры)
опытные – при создании

новых технических средств
научно-технические

аэродинамическая труба

испытания в опытовом бассейне

имитатор солнечного излучения

вакуумная камера в Институте космических исследований

вибростенд НПО «Энергия»

Слайд 12

2. Модели по фактору времени
статические – описывают оригинал в заданный момент

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

Слайд 13

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

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

Слайд 14

4. Модели по структуре
табличные модели (пары соответствия)
иерархические (многоуровневые) модели
сетевые модели (графы)

Слайд 15

Типы моделей

Слайд 16

Словесные модели
Словесные модели - это описания предметов, явлений, событий, процессов на

естественных языках

Роман

Словесная
модель

Исторические
события

Географические
объекты

Учебник

Художественная
литература

Перенос отношений
между людьми на отношения
между персонажами басни

Басня

Слайд 17

Компьютерные математические модели
Компьютерными математическими моделями называются математические модели, реализованные с помощью

систем программирования, электронных таблиц, специализированных математических пакетов и программных средств для моделирования.

Математическая модель

Слайд 18

Имитационные модели
нельзя заранее вычислить или предсказать поведение системы, но можно имитировать

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

Слайд 19

Билетная
касса
Торговое
предприятие
Ремонтная
мастерская
Служба
скорой помощи
Управление
транспортными
потоками
Системы
массового
обслуживания
Имитационные модели воспроизводят поведение сложных систем, элементы которых

могут вести себя случайным образом.

Имитационная модель

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

Слайд 20

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

спортивные игры
тренинги персонала

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

Слайд 21

Адекватность
Адекватность – это совпадение существенных свойств модели и оригинала в данной

задаче.

Модель всегда отличается от оригинала

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

Слайд 22

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

случаях используют теорию подобия.

Слайд 23

© К.Ю. Поляков, 2007-2011
Тема 2. Этапы моделирования

Слайд 24

I. Постановка задачи
Хорошо поставленная задача:
описаны все связи между исходными данными и

результатом
известны все исходные данные
решение существует
задача имеет единственное решение
Примеры плохо поставленных задач:
Винни Пух и Пятачок построили ловушку для слонопотама. Удастся ли его поймать?
Малыш и Карлсон решили по–братски разделить два орешка – большой и маленький. Как это сделать?
Найти максимальное значение функции y = x2 (нет решений).
Найти функцию, которая проходит через точки (0,1) и (1,0) (неединственное решение).

Слайд 25

II. Разработка модели
выбрать тип модели
определить существенные свойства оригинала, которые нужно включить

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

Слайд 26

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

с известным результатом.
Примеры:
устройство для сложения многозначных чисел – проверка на однозначных числах
модель движения корабля – если руль стоит ровно, курс не должен меняться; если руль повернуть влево, корабль должен идти вправо
модель накопления денег в банке – при ставке 0% сумма не должна изменяться

Слайд 27

IV. Эксперимент c моделью
Эксперимент – это исследование модели в интересующих нас

условиях.
Примеры:
устройство для сложения чисел – работа с многозначными числами
модель движения корабля – исследование в условиях морского волнения
модель накопления денег в банке – расчеты при ненулевой ставке

Слайд 28

V. Проверка практикой, анализ результатов
Возможные выводы:
задача решена, модель адекватна
необходимо изменить алгоритм

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

Слайд 29

Пример.
Задача. Обезьяна хочет сбить бананы на пальме. Как ей надо

кинуть кокос, чтобы попасть им в бананы.
Анализ задачи:
все ли исходные данные известны?
есть ли решение?
единственно ли решение?

Слайд 30

I. Постановка задачи
Допущения:
кокос и банан считаем материальными точками
расстояние до пальмы известно
рост

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

Слайд 31

II. Разработка модели
Графическая модель
h
Формальная (математическая) модель
Задача: найти t, , при которых

Слайд 32

III. Тестирование модели
при нулевой скорости кокос падает вертикально вниз
при t=0 координаты

равны (0,h)
при броске вертикально вверх (=90o) координата x не меняется
при некотором t координата y начинает уменьшаться (ветви параболы вниз)

Математическая модель

Слайд 33

IV. Эксперимент
Метод I.
Меняем угол . Для выбранного угла  строим траекторию

полета ореха. Если она проходит выше банана, уменьшаем угол, если ниже – увеличиваем.
Метод II.
Из первого равенства выражаем время полета:
Меняем угол . Для выбранного угла  считаем t, а затем – значение y при этом t. Если оно больше H, уменьшаем угол, если меньше – увеличиваем.

не надо строить всю траекторию для каждого 

Слайд 34

V. Анализ результатов
Всегда ли обезьяна может сбить банан?
Что изменится, если обезьяна

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

Слайд 35

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

Слайд 36

I. Постановка задачи
Мальчик Вася в синей кепке бросает белый мяч со

скоростью 12 м/с. Когда мяч впервые ударится о землю?

Слайд 37

II. Разработка математической модели
выделить существенные исходные данные:
начальная скорость 12 м/с
бросок вертикально

вверх
ускорение свободного падения 9,81 м/с2
2) построить математическую модель

Слайд 38

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

Слайд 39

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

с известным результатом.

• при t = 0  y = h0 (в начальной точке)
• при v0 = 0  падение вниз

Слайд 40

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.

Слайд 41

Компьютерная имитационная модель
если нельзя просто решить уравнение…
Дискретизация задачи:
моменты времени:
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

Слайд 42

Компьютерная имитационная модель
алг Полёт-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
кон

Слайд 43

Компьютерная имитационная модель
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.

Слайд 44

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

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

Слайд 45

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

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

Слайд 46

Системный подход

Слайд 47

Системный подход
Система – группа объектов и связей между ними, выделенных из

среды и рассматриваемых как одно целое.

Примеры:
семья
экологическая система
компьютер
техническая система
общество

среда

Слайд 48

Системный подход
Модель-система:
Модель-не-система:
1-я линия:
Пр. Ветеранов
Ленинский пр.
Автово
Кировский завод
Нарвская
…
2-я линия:
Купчино
Звездная
Московская
Парк Победы
Электросила
…

Слайд 49

Системный подход
Граф – это набор вершин и соединяющих их ребер.
1
2
3
4
5
вершина
ребро
23
18
20
15
14
5
вес ребра

(взвешенный граф)

ориентированный граф (орграф) –ребра имеют направление

Слайд 50

Семантическая (смысловая) модель предложения:
«Выхожу один я на дорогу…»
выхожу
я
на дорогу
один
что делаю?
кто?
сколько?
куда?
граф

Слайд 51

Списки и деревья

Слайд 52

Что такое список?
Список – последовательность элементов, в которой важен порядок их

расположения.

['Amicus', 'Socrates', 'sed', 'magis', 'amica', 'veritas']

Список как модель:

слово = список букв, текст = список абзацев

Запись:

Слайд 53

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

 КОРО  КОРОН  КОРОНА

Слайд 54

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

структуры (иерархии).

Лес – это несколько деревьев.

Слайд 55

Из чего состоит дерево?
A –
D, E, F, G –
корень
листья
B,

C –

промежуточные
узлы

Путь — это последовательность узлов, где каждый следующий связан с предыдущим.

Высота дерева — это наибольшая длина пути от корня дерева к листу.

Поддерево — это часть дерева, которая тоже представляет собой дерево.

Слайд 56

Родители и дети
B – родитель для D и E
D и E

– сыновья для B

Предок – потомок: между ними есть путь.

A и B – предки для D и E
B, D и E – потомки для A

Родитель – сын: между ними есть ребро.

Слайд 57

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

Слайд 58

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

Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые

Слайд 59

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

Слайд 60

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

может иметь не более двух сыновей.

Слайд 61

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

{A, B, C}.

пустое дерево

БВ

Слайд 62

Перебор вариантов
Разведчик выяснил, что ключ к замку от сейфа состоит из

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

Слайд 63

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

совпадет с началом другого кодового слова.

тогда однозначно декодируется!

Слайд 64

Графы
«От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и

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

Слайд 65

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

Слайд 66

Матрица и список смежности
петля
Матрица смежности
Степень вершины – это количество связанных с

ней рёбер (петля считается дважды!).

Слайд 67

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

Слайд 68

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

Слайд 69

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

Слайд 70

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

Слайд 71

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

Слайд 72

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

Слайд 73

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

Слайд 74

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

Слайд 75

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

Слайд 76

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

Слайд 77

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

Слайд 78

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

Слайд 79

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

Слайд 80

Кратчайший путь (перебор)
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 и

Слайд 81

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

Слайд 82

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

Слайд 83

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

Слайд 84

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

Слайд 85

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

Слайд 86

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

Слайд 87

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

Слайд 88

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

Слайд 89

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

Слайд 90

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

Слайд 91

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

Слайд 92

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

Слайд 93

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

Слайд 94

Игровые стратегии

Слайд 95

Что такое игровая модель?
Игровая модель — это модель, которая описывает соперничество

двух (или более) сторон, каждая из которых преследует свою цель.

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

Теория игр: как играть, чтобы получить наибольший выигрыш?

Игры с полной информацией: нет случайностей:
крестики-нолики
шашки
шахматы
…

Слайд 96

Выигрышные и проигрышные позиции
игра без ничьих…
Выигрышная позиция — это такая позиция,

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

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

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

Нет выигрышной стратегии…

Слайд 97

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

Слайд 98

Выигрышные и проигрышные позиции
позиция, из которой все возможные ходы ведут в

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

Ходят нолики:

выигрышная

проигрышная

выигрышная

Слайд 99

Дерево перебора вариантов
Два игрока, куча из S камней. За один ход

игрок может взять один или два камня. Тот, кто возьмёт последний камень, проигрывает.

П:

В:

П:

В:

Первый

Второй

Слайд 100

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

проигрывает

достаточно одного хода того, кто выигрывает

Слайд 101

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

Слайд 102

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

Слайд 103

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

Слайд 104

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

Слайд 105

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

Слайд 106

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

Слайд 107

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

Слайд 108

Анализ диаграмм
а) все «Форды» могут принадлежать менеджерам
б) все охранники могут ездить

на «Ауди»
в) все «Тойоты» могут принадлежать рабочим
г) все рабочие могут ездить на «Фордах»

10 + 40 + 30 + 20 = 100

Слайд 109

учебника А.Г. Гейна и др., Информатика и ИКТ, 10 класс, М.: Просвещение, 2008)

Слайд 110

– начальная численность
– после 1 цикла деления
– после 2-х циклов
Особенности модели:
не

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

Модель деления

Слайд 111

– коэффициент рождаемости
– коэффициент смертности
Особенности модели:
не учитывается влияние численности N и

внешней среды на K
не учитывается влияние других видов на K

Коэффициент прироста

прирост

Модель неограниченного роста (T. Мальтус)

Слайд 112

Модель ограниченного роста (П. Ферхюльст)
L – предельная численность животных
Идеи:
коэффициент прироста KL

зависит от численности N
при N=0 должно быть KL=K (начальное значение)
при N=L должно быть KL=0 (достигнут предел)

Слайд 113

Модель с отловом
Примеры: рыбоводческое хозяйство, разведение пушных зверей и т.п.

Слайд 114

Модель эпидемии гриппа
L – всего жителей Ni – больных в i-ый день
Zi

– заболевших в i-ый день Vi – выздоровевших
Wi – всего выздоровевших за i дней

Основное уравнение:

Ограниченный рост:

Выздоровление (через 7 дней):

Слайд 115

Модель системы «хищник-жертва»
Модель – не-система:
Модель – система:
число встреч пропорционально NiZi
«эффект»

пропорционален числу встреч

Слайд 116

Модель системы «хищник-жертва»
Хищники вымирают:
Равновесие:
караси
щуки
караси
щуки

Слайд 117

Слайд 118

Модель системы «хищник-жертва»
Колебания:

Слайд 119

учебника А.Г. Гейна и др., Информатика и ИКТ, 10 класс, М.: Просвещение, 2008)

Слайд 120

Случайные процессы
Случайно…
встретить друга на улице
разбить тарелку
найти 10 рублей
выиграть в лотерею
Случайный выбор:
жеребьевка

на соревнованиях
выигравшие номера в лотерее

Как получить случайность?

Слайд 121

Случайные числа на компьютере
Электронный генератор
нужно специальное устройство
нельзя воспроизвести результаты
318458191041
564321
209938992481
458191
938992
малый период (последовательность

повторяется через 106 чисел)

Метод середины квадрата (Дж. фон Нейман)

в квадрате

Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.

Слайд 122

Случайные числа на компьютере
Линейный конгруэнтный метод
a, c, m - целые числа
простое

число

230-1

период m

остаток от деления

«Вихрь Мерсенна»: период 219937-1

Слайд 123

Распределение случайных чисел
Модель: снежинки падают на отрезок [a,b]
распределение
равномерное
неравномерное

Слайд 124

Распределение случайных чисел
Особенности:
распределение – это характеристика всей последовательности, а не

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

Слайд 125

Вычисление площади (метод Монте-Карло)
Вписываем сложную фигуру в другую фигуру, для которой

легко вычислить площадь (прямоугольник, круг, …).
Равномерно N точек со случайными координатами внутри прямоугольника.
Подсчитываем количество точек, попавших на фигуру: M.
4. Вычисляем площадь:

Всего N точек

На фигуре M точек

Метод приближенный.
Распределение должно быть равномерным.
Чем больше точек, тем точнее.
Точность ограничена датчиком случайных чисел.

Слайд 126

Вычисление площади
Когда точка внутри круга?
(x,y)
Случайные координаты:
x := Rrandom;
y := Rrandom;
Программа:
for i:=1

to N do begin
{ найти случайные координаты }
if x*x + y*y <= R*R then M := M+1;
end;
S := 4*R*R*M / N;

Слайд 127

Броуновское движение
Случайный шаг:
Случайное направление (в рад):
alpha := 2pirandom;
h := hMax*random;
Программа:
for i:=1

to N do begin
{ найти случайное направление и шаг }
x := x + h*cos(alpha);
y := y + h*sin(alpha);
end;

Слайд 128

Системы массового обслуживания
Примеры:
звонки на телефонной станции
вызовы «скорой помощи»
обслуживание клиентов в банке
сколько

бригад?

сколько линий?

сколько операторов?

Особенности:
клиенты (запросы на обслуживание) поступают постоянно, но через случайные интервалы времени
время обслуживание каждого клиента – случайная величина

Слайд 129

Клиенты в банке
Вход клиентов:
за 1 минуту – до N человек
равномерное распределение
Обслуживание:
от

Tmin до Tmax минут
равномерное распределение

Слайд 130

Клиенты в банке
Число клиентов в помещении банка:
N := N + in

- out;

было

пришли

ушли

Количество касс: K

Средняя длина очереди:

Допустимая длина очереди:

Слайд 131

Клиенты в банке
Пришли за очередную минуту:
in := round(N*random);
округление
Обслужены за очередную минуту

и выходят:

Случайное время обслуживания:

T := Tmin + (Tmax – Tmin)*random;

out := K / T;

Слайд 132

Клиенты в банке (программа)
count := 0; { счетчик «плохих» минут }
for

i:=1 to L do begin
in := { случайное число входящих }
out := { случайное число обслуженных }
N := N + in – out;
if N > Q*K then
count := count + 1;
end;
writeln(count/L:0:2);

период моделирования L минут

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

Содержание

Модели в нашей жизни

Что такое модель?Модель – это объект, который обладает некоторыми свойствами другого

Что можно моделировать?Модели объектов:уменьшенные копии зданий, кораблей, самолетов, …модели ядра атома,

МоделированиеМоделирование – это создание и использование моделей для изучения оригиналов.Когда используют

Цели моделированияисследование оригиналаизучение сущности объекта или явления«Наука есть удовлетворение собственного любопытства

Один оригинал – одна модель? материальная точка

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

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

Классификация моделей

1. Модели по области примененияучебные (в т.ч. тренажеры)опытные – при создании

2. Модели по фактору временистатические – описывают оригинал в заданный момент

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

4. Модели по структуретабличные модели (пары соответствия)иерархические (многоуровневые) моделисетевые модели (графы)

Типы моделей

Словесные моделиСловесные модели - это описания предметов, явлений, событий, процессов на

Компьютерные математические моделиКомпьютерными математическими моделями называются математические модели, реализованные с помощью

Имитационные моделинельзя заранее вычислить или предсказать поведение системы, но можно имитировать

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

АдекватностьАдекватность – это совпадение существенных свойств модели и оригинала в данной

Пересчёт «модель-оригинал»7,6 смМ 1:5000007,6 см  500000= 38 кмВ более сложных

© К.Ю. Поляков, 2007-2011Тема 2. Этапы моделирования

I. Постановка задачиХорошо поставленная задача:описаны все связи между исходными данными и

II. Разработка моделивыбрать тип моделиопределить существенные свойства оригинала, которые нужно включить

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

IV. Эксперимент c модельюЭксперимент – это исследование модели в интересующих нас

V. Проверка практикой, анализ результатовВозможные выводы:задача решена, модель адекватнанеобходимо изменить алгоритм

Пример. Задача. Обезьяна хочет сбить бананы на пальме. Как ей надо

I. Постановка задачиДопущения:кокос и банан считаем материальными точкамирасстояние до пальмы известнорост

II. Разработка моделиГрафическая модельhФормальная (математическая) модельЗадача: найти t, , при которых

III. Тестирование моделипри нулевой скорости кокос падает вертикально внизпри t=0 координаты

IV. ЭкспериментМетод I.Меняем угол . Для выбранного угла  строим траекторию

V. Анализ результатовВсегда ли обезьяна может сбить банан?Что изменится, если обезьяна

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

I. Постановка задачиМальчик Вася в синей кепке бросает белый мяч со

II. Разработка математической моделивыделить существенные исходные данные:начальная скорость 12 м/сбросок вертикально

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

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

IV. Построение компьютерной моделиprogram Polet;var h0, v0, g: real; a, b,

Компьютерная имитационная модельесли нельзя просто решить уравнение… Дискретизация задачи:моменты времени:0, t,

Компьютерная имитационная модельалг Полёт-2нач вещ h0=1.5, v0=12, g=9.81 вещ y, v,

Компьютерная имитационная модельprogram Polet_2;var h0, v0, g: real; y, v, t,

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

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

Системный подход

Системный подходСистема – группа объектов и связей между ними, выделенных из

Системный подходГраф – это набор вершин и соединяющих их ребер.12345вершинаребро23182015145вес ребра

Семантическая (смысловая) модель предложения:«Выхожу один я на дорогу…»выхожуяна дорогуодинчто делаю?кто?сколько?куда?граф

Списки и деревья

Что такое список?Список – последовательность элементов, в которой важен порядок их

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

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

Из чего состоит дерево?A – D, E, F, G – кореньлистьяB,

Родители и детиB – родитель для D и ED и E

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

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

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

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

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

Перебор вариантовРазведчик выяснил, что ключ к замку от сейфа состоит из

Дерево для двоичного кодаГДБВА01100101Условие Фано: ни одно из кодовых слов не

Графы«От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и

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

Матрица и список смежностипетляМатрица смежностиСтепень вершины – это количество связанных с

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

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

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

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

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

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

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

Взвешенные графы1282546Весовая матрица:вес ребра

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

Что такое модель?
Модель – это объект, который обладает некоторыми свойствами другого

Что можно моделировать?
Модели объектов:
уменьшенные копии зданий, кораблей, самолетов, …
модели ядра атома,

Моделирование
Моделирование – это создание и использование моделей для изучения оригиналов.
Когда используют

Цели моделирования
исследование оригинала
изучение сущности объекта или явления
«Наука есть удовлетворение собственного любопытства

Один оригинал – одна модель?
материальная точка

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

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

1. Модели по области применения
учебные (в т.ч. тренажеры)
опытные – при создании

2. Модели по фактору времени
статические – описывают оригинал в заданный момент

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

4. Модели по структуре
табличные модели (пары соответствия)
иерархические (многоуровневые) модели
сетевые модели (графы)

Словесные модели
Словесные модели - это описания предметов, явлений, событий, процессов на

Компьютерные математические модели
Компьютерными математическими моделями называются математические модели, реализованные с помощью

Имитационные модели
нельзя заранее вычислить или предсказать поведение системы, но можно имитировать

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

Адекватность
Адекватность – это совпадение существенных свойств модели и оригинала в данной

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

© К.Ю. Поляков, 2007-2011
Тема 2. Этапы моделирования

I. Постановка задачи
Хорошо поставленная задача:
описаны все связи между исходными данными и

II. Разработка модели
выбрать тип модели
определить существенные свойства оригинала, которые нужно включить

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

IV. Эксперимент c моделью
Эксперимент – это исследование модели в интересующих нас

V. Проверка практикой, анализ результатов
Возможные выводы:
задача решена, модель адекватна
необходимо изменить алгоритм

Пример.
Задача. Обезьяна хочет сбить бананы на пальме. Как ей надо

I. Постановка задачи
Допущения:
кокос и банан считаем материальными точками
расстояние до пальмы известно
рост

II. Разработка модели
Графическая модель
h
Формальная (математическая) модель
Задача: найти t, , при которых

III. Тестирование модели
при нулевой скорости кокос падает вертикально вниз
при t=0 координаты

IV. Эксперимент
Метод I.
Меняем угол . Для выбранного угла  строим траекторию

V. Анализ результатов
Всегда ли обезьяна может сбить банан?
Что изменится, если обезьяна

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

I. Постановка задачи
Мальчик Вася в синей кепке бросает белый мяч со

II. Разработка математической модели
выделить существенные исходные данные:
начальная скорость 12 м/с
бросок вертикально

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

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

IV. Построение компьютерной модели
program Polet;
var h0, v0, g: real;
a, b,

Компьютерная имитационная модель
если нельзя просто решить уравнение…
Дискретизация задачи:
моменты времени:
0, t,

Компьютерная имитационная модель
алг Полёт-2
нач
вещ h0=1.5, v0=12, g=9.81
вещ y, v,

Компьютерная имитационная модель
program Polet_2;
var h0, v0, g: real;
y, v, t,

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

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

Системный подход
Система – группа объектов и связей между ними, выделенных из

Системный подход
Граф – это набор вершин и соединяющих их ребер.
1
2
3
4
5
вершина
ребро
23
18
20
15
14
5
вес ребра

Семантическая (смысловая) модель предложения:
«Выхожу один я на дорогу…»
выхожу
я
на дорогу
один
что делаю?
кто?
сколько?
куда?
граф

Что такое список?
Список – последовательность элементов, в которой важен порядок их

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

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

Из чего состоит дерево?
A –
D, E, F, G –
корень
листья
B,

Родители и дети
B – родитель для D и E
D и E

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

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

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

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

Перебор вариантов
Разведчик выяснил, что ключ к замку от сейфа состоит из

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

Графы
«От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и

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

Матрица и список смежности
петля
Матрица смежности
Степень вершины – это количество связанных с

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

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