Презентация, доклад на тему Моделирование и ГРАФЫ. К. Поляков ЕГЭ и ОГЭ

Содержание

1. Моделирование и ГРАФЫ. К. Поляков ЕГЭ и ОГЭ
2. Модели в нашей жизни
3. Что такое модель?Модель – это объект, который
4. Что можно моделировать?Модели объектов:уменьшенные копии зданий, кораблей,
5. МоделированиеМоделирование – это создание и использование моделей
6. Цели моделированияисследование оригиналаизучение сущности объекта или явления«Наука
7. Один оригинал – одна модель? материальная точка
8. Зачем нужно много моделей?изучение строения телапримерка одеждыизучение наследственноститренировка спасателейучет граждан страны
9. Природа моделейматериальные (физические, предметные) модели:информационные модели представляют
10. Модели по области примененияучебные (в т.ч. тренажеры)опытные
11. Модели по фактору временистатические – описывают оригинал
12. Модели по характеру связейдетерминированные связи между входными
13. Модели по структуретабличные модели (пары соответствия)иерархические (многоуровневые) моделисетевые модели (графы)
14. Специальные виды моделейимитационные нельзя заранее вычислить или
15. Специальные виды моделейигровые – учитывающие действия противника Примеры:модели экономических ситуациймодели военных действий спортивные игрытренинги персонала
16. Адекватность моделиАдекватность – совпадение существенных свойств модели
17. Системный подходСистема – группа объектов и связей
18. Системный подходМодель-система:Модель-не-система:1-я линия:Пр. ВетерановЛенинский пр.Автово Кировский заводНарвская…2-я линия:КупчиноЗвезднаяМосковскаяПарк ПобедыЭлектросила…
19. Системный подходГраф – это набор вершин и
20. Системный подходСемантическая (смысловая) модель предложения:«Выхожу один я на дорогу…»выхожуяна дорогуодинчто делаю?кто?сколько?куда?граф
21. Матрица смежностипетля
22. Матрица смежности
23. Матрица смежности
24. Весовая матрицаВасюкиСолнцевоЯгодное128546Грибное2
25. Весовая матрица
26. Весовая матрица
27. Кратчайшие путиОпределите кратчайший путь между пунктами A и D.ABСEСDСDED246246131397584137дерево возможных маршрутов
28. Кратчайшие путиОпределите кратчайший путь между пунктами A и E.
29. Количество путейСколько существует различных путей из А
30. Количество путейБ←АВ←АЕ←ВД←БГ←АБВЖ←БВГДЕПосле сортировки:Ж←БВГДЕNЖ← NБ + NВ + NГ + NД + NЕБ←АВ←АЕ←ВД←БГ←АБВЖ←БВГДЕЗаполнение таблицы:111137
31. Количество путейБ←АВ←АЕ←ВД←БГ←АБВЖ←БВГДЕФорма записи:111137
32. Количество путейСколько существует различных путей из А в Ж?ЖАБВГДЕ
33. Модели и моделирование© К.Ю. Поляков, 2007-2011Тема 2. Этапы моделирования
34. I. Постановка задачиисследование оригиналаизучение сущности объекта или
35. I. Постановка задачиХорошо поставленная задача:описаны все связи
36. II. Разработка моделивыбрать тип моделиопределить существенные свойства
37. III. Тестирование моделиТестирование – это проверка модели
38. IV. Эксперимент c модельюЭксперимент – это исследование
39. V. Проверка практикой, анализ результатовВозможные выводы:задача решена,
40. Пример. Задача. Обезьяна хочет сбить бананы на
41. I. Постановка задачиДопущения:кокос и банан считаем материальными
42. II. Разработка моделиГрафическая модельhФормальная (математическая) модельЗадача: найти t, α, при которых
43. III. Тестирование моделипри нулевой скорости кокос падает
44. IV. ЭкспериментМетод I.Меняем угол α. Для выбранного
45. V. Анализ результатовВсегда ли обезьяна может сбить
46. Модели и моделирование© К.Ю. Поляков, 2007-2011Тема
47. – начальная численность– после 1 цикла деления–
48. – коэффициент рождаемости– коэффициент смертностиОсобенности модели:не учитывается
49. Модель ограниченного роста (П. Ферхюльст)L – предельная
50. Модель с отловомПримеры: рыбоводческое хозяйство, разведение пушных зверей и т.п.
51. Модель эпидемии гриппаL – всего жителей Ni –
52. Модель системы «хищник-жертва»Модель – не-система:Модель – система:число встреч пропорционально Ni⋅Zi «эффект» пропорционален числу встреч
53. Модель системы «хищник-жертва»Хищники вымирают:Равновесие:карасищукикарасищуки
54. Слайд 54
55. Модель системы «хищник-жертва»Колебания:
56. Модели и моделирование© К.Ю. Поляков, 2007-2011Тема
57. Случайные процессыСлучайно…встретить друга на улицеразбить тарелкунайти 10
58. Случайные числа на компьютереЭлектронный генераторнужно специальное устройствонельзя
59. Случайные числа на компьютереЛинейный конгруэнтный методa, c,
60. Распределение случайных чиселМодель: снежинки падают на отрезок [a,b]распределениеравномерноенеравномерное
61. Распределение случайных чиселОсобенности: распределение – это характеристика
62. Вычисление площади (метод Монте-Карло)Вписываем сложную фигуру в
63. Вычисление площадиКогда точка внутри круга?(x,y)Случайные координаты:x :=
64. Броуновское движениеСлучайный шаг:Случайное направление (в рад):alpha :=
65. Системы массового обслуживанияПримеры:звонки на телефонной станциивызовы «скорой
66. Клиенты в банкеВход клиентов:за 1 минуту – до N человекравномерное распределениеОбслуживание:от Tmin до Tmax минутравномерное распределение
67. Клиенты в банкеЧисло клиентов в помещении банка:N
68. Клиенты в банкеПришли за очередную минуту:in :=
69. Клиенты в банке (программа)count := 0; {
70. Конец фильма

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

Главная
Информатика
Моделирование и ГРАФЫ. К. Поляков ЕГЭ и ОГЭ

Слайд 1Модели и моделирование
© К.Ю. Поляков, 2007-2011
Тема 1. Модели и их типы

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

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

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

Оригиналы и модели

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

Что такое модель?Модель – это объект, который обладает некоторыми свойствами другого объекта (оригинала) и используется вместо него.Оригиналы

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

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

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

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

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

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

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

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

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

Слайд 7Один оригинал – одна модель?

материальная точка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

сетевые модели (графы)

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

можно имитировать её реакцию на внешние воздействия;
максимальный учет всех факторов;
только численные результаты;

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

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

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

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

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

Слайд 16Адекватность модели
Адекватность – совпадение существенных свойств модели и оригинала:
результаты моделирования согласуются

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

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

Адекватность моделиАдекватность – совпадение существенных свойств модели и оригинала:результаты моделирования согласуются с выводами теории (законы сохранения и

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

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

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

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

среда

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

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

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

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

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

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

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

граф

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

Слайд 21Матрица смежности

петля

Слайд 22Матрица смежности

Слайд 23Матрица смежности

Слайд 24Весовая матрица

Васюки
Солнцево
Ягодное

12
8
5
4
6
Грибное

2

Слайд 25Весовая матрица

Слайд 26Весовая матрица

Слайд 27

Кратчайшие пути

Определите кратчайший путь между пунктами A и D.
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
дерево возможных маршрутов

Слайд 28Кратчайшие пути

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

Слайд 29Количество путей

Сколько существует различных путей из А в Ж?
1. Откуда можно

приехать в Ж?

Ж←БВГДЕ

Е←В

Д←Б

Г←АБВ

В←А

Б←А

2. Можно приехать только из А:

Б←А

В←А

3. Можно приехать только из уже отобранных вершин (А, Б и В):

Б←А

В←А

Е←В

Д←Б

Г←АБВ

4. Можно приехать только из уже отобранных вершин:

Б←А

В←А

Е←В

Д←Б

Г←АБВ

Ж←БВГДЕ

Слайд 30Количество путей

Б←А
В←А
Е←В
Д←Б
Г←АБВ
Ж←БВГДЕ
После сортировки:
Ж←БВГДЕ
NЖ← NБ + NВ + NГ + NД +

NЕ

Б←А

В←А

Е←В

Д←Б

Г←АБВ

Ж←БВГДЕ

Заполнение таблицы:

Слайд 31Количество путей

Б←А
В←А
Е←В
Д←Б
Г←АБВ
Ж←БВГДЕ
Форма записи:
1
1
1
1
3
7

Слайд 32Количество путей

Сколько существует различных путей из А в Ж?

Ж
А
Б
В
Г
Д
Е

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

Слайд 34I. Постановка задачи
исследование оригинала
изучение сущности объекта или явления
анализ («что будет, если

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

I. Постановка задачиисследование оригиналаизучение сущности объекта или явленияанализ («что будет, если …»)научиться прогнозировать последствий при различных воздействиях

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

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

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

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

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

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

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

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

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

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

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

IV. Эксперимент c модельюЭксперимент – это исследование модели в интересующих нас условиях.Примеры:устройство для сложения чисел – работа

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

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

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

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

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

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

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

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

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

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

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

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

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

III. Тестирование моделипри нулевой скорости кокос падает вертикально внизпри t=0 координаты равны (0,h)при броске вертикально вверх (α=90o)

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

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

Меняем угол α. Для выбранного угла α считаем t, а затем – значение y при этом t. Если оно больше H, уменьшаем угол, если меньше – увеличиваем.

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

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

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

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

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

Слайд 46Модели и моделирование
© К.Ю. Поляков, 2007-2011
Тема 3. Модели биологических систем
(по мотивам

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

Модели и моделирование© К.Ю. Поляков, 2007-2011Тема 3. Модели биологических систем(по мотивам учебника А.Г. Гейна и др.,

Слайд 47

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

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

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

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

Слайд 48

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

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

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

прирост

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Слайд 54

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

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

Модели и моделирование© К.Ю. Поляков, 2007-2011Тема 4. Моделирование случайных процессов(по мотивам учебника А.Г. Гейна и др.,

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

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

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

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

Слайд 58
Случайные числа на компьютере
Электронный генератор
нужно специальное устройство
нельзя воспроизвести результаты

318458191041
564321
209938992481
458191
938992
малый период (последовательность

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

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

в квадрате

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

Случайные числа на компьютереЭлектронный генераторнужно специальное устройствонельзя воспроизвести результаты318458191041564321209938992481458191938992малый период (последовательность повторяется через 106 чисел)Метод середины

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

число

230-1

период m

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

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

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

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

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

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

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

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

Всего N точек

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

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

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

Слайд 63Вычисление площади

Когда точка внутри круга?
(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;

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

Слайд 64Броуновское движение

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

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

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

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

бригад?

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

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

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

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

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

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

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

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

- out;

было

пришли

ушли

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

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

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

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

и выходят:

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

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

out := K / T;

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

Слайд 69Клиенты в банке (программа)
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 минут

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

Слайд 70Конец фильма

Скачать презентацию

Презентация, доклад на тему Моделирование и ГРАФЫ. К. Поляков ЕГЭ и ОГЭ

Содержание

Слайд 1Модели и моделирование© К.Ю. Поляков, 2007-2011Тема 1. Модели и их типы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Слайд 16Адекватность моделиАдекватность – совпадение существенных свойств модели и оригинала:результаты моделирования согласуются

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

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

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

Слайд 21Матрица смежностипетля

Слайд 22Матрица смежности

Слайд 23Матрица смежности

Слайд 24Весовая матрицаВасюкиСолнцевоЯгодное128546Грибное2

Слайд 25Весовая матрица

Слайд 26Весовая матрица

Слайд 27Кратчайшие путиОпределите кратчайший путь между пунктами A и D.ABСEСDСDED246246131397584137дерево возможных маршрутов

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

Слайд 29Количество путейСколько существует различных путей из А в Ж?1. Откуда можно

Слайд 30Количество путейБ←АВ←АЕ←ВД←БГ←АБВЖ←БВГДЕПосле сортировки:Ж←БВГДЕNЖ← NБ + NВ + NГ + NД +

Слайд 31Количество путейБ←АВ←АЕ←ВД←БГ←АБВЖ←БВГДЕФорма записи:111137

Слайд 32Количество путейСколько существует различных путей из А в Ж?ЖАБВГДЕ

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

Слайд 34I. Постановка задачиисследование оригиналаизучение сущности объекта или явленияанализ («что будет, если

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

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

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

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

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

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

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

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

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

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

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

Слайд 46Модели и моделирование© К.Ю. Поляков, 2007-2011Тема 3. Модели биологических систем(по мотивам

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

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

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

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

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

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

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

Слайд 54

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

Слайд 56Модели и моделирование© К.Ю. Поляков, 2007-2011Тема 4. Моделирование случайных процессов(по мотивам

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

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

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

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

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

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

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

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

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

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

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

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

Слайд 70Конец фильма

Похожие презентации

Что такое shareslide.ru?

Обратная связь

Слайд 1Модели и моделирование
© К.Ю. Поляков, 2007-2011
Тема 1. Модели и их типы

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

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

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

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

Слайд 7Один оригинал – одна модель?

материальная точка

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

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

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

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

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

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

сетевые модели (графы)

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

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

Слайд 16Адекватность модели
Адекватность – совпадение существенных свойств модели и оригинала:
результаты моделирования согласуются

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

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

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

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

граф

Слайд 21Матрица смежности

петля

Слайд 24Весовая матрица

Васюки
Солнцево
Ягодное

12
8
5
4
6
Грибное

2

Слайд 27

Кратчайшие пути

Определите кратчайший путь между пунктами A и D.
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
дерево возможных маршрутов

Слайд 28Кратчайшие пути

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

Слайд 29Количество путей

Сколько существует различных путей из А в Ж?
1. Откуда можно

Слайд 30Количество путей

Б←А
В←А
Е←В
Д←Б
Г←АБВ
Ж←БВГДЕ
После сортировки:
Ж←БВГДЕ
NЖ← NБ + NВ + NГ + NД +

Слайд 31Количество путей

Б←А
В←А
Е←В
Д←Б
Г←АБВ
Ж←БВГДЕ
Форма записи:
1
1
1
1
3
7

Слайд 32Количество путей

Сколько существует различных путей из А в Ж?

Ж
А
Б
В
Г
Д
Е

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

Слайд 34I. Постановка задачи
исследование оригинала
изучение сущности объекта или явления
анализ («что будет, если

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

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

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

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

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

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

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

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

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

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

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

Слайд 46Модели и моделирование
© К.Ю. Поляков, 2007-2011
Тема 3. Модели биологических систем
(по мотивам

Слайд 47

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

Слайд 48

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

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

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

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

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

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

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

Слайд 56Модели и моделирование
© К.Ю. Поляков, 2007-2011
Тема 4. Моделирование случайных процессов
(по мотивам

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

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

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

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

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

Слайд 63Вычисление площади

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

Слайд 64Броуновское движение

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

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

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

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

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

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