1 Метод Монте-КарлоМонте-Карло Метод приближенного нахождения площадей фигур А.Г. Гейн, и др. Информатика. Учебник для 8-9 классов. Москва, «Просвещение», - презентация

1 1 Метод Монте-КарлоМонте-Карло Метод приближенного нахождения площадей фигур А.Г. Гейн, и др. Информатика. Учебник для 8-9 классов. Москва, «Просвещение», 1997

2 2 Монте-Карло – город, где расположена знаменитая рулетка, которую можно рассматривать как генератор случайных чисел.

3 3 Для решения математических задач также строят математические модели… Задача. Вычислить площадь фигуры. Для простейших фигур: прямоугольник, многоугольник, круг и т.п. все просто – в известные формулы надо подставить исходные данные. Но как быть, если фигура имеет сложную форму?

4 4 Задача. Дана фигура сложной формы. Вычислить ее площадь. Возможные модели для решения задачи: С помощью палетки (на фигуру накладывается клетчатая прозрачная бумага (палетка) и подсчитывается количество квадратиков, попавших в фигуру. Предполагается, что чем меньше клетки, тем точнее будет результат независимо от того, каким образом наложить палетку на фигуру; «физическая» модель: скопировать фигуру на картон, аккуратно вырезать его, взвесить и поделить на вес единичного квадрата из этого же картона; с помощью интегралов. Однако эти модели не для расчетов на ЭВМ.

5 5 Математическая модель метода Монте-Карло Поместим данную фигуру в квадрат. Будем наугад (случайным образом) бросать точки в этот квадрат. Естественно предположить, что чем больше площадь фигуры, тем чаще в нее будут попадать точки. Представим себе квадратный дворик и в нем детскую площадку. Ясно, что во время снегопада количество снежинок, попавших на детскую площадку, пропорционально ее площади. Т.о., можно сделать допущение: при большом числе точек, наугад выбранных внутри квадрата, доля точек, содержащихся в данной фигуре, приближенно равна отношению площади этой фигуры к площади квадрата.

6 6 Исходные данные: F – данная фигура. a – сторона квадрата, содержащего фигуру F. N – количество точек, которые мы будем случайным образом выбирать внутри квадрата Результат: S – площадь фигуры F. М – число точек, которые содержатся в фигуре F. Связи между исходными данными и результатами: S a 2 M/N математические соотношения позволяющие определить попала ли точка в фигуру F; S a2a2 M N

7 7 Проверим данную модель для приближенного нахождения площади круга радиуса R. Формула площади круга: S = πR 2. Однако, эта формула дана нам без доказательства. Проверим ее с помощью ЭВМ. x y 1 1 Пусть R = 1; а = 2. Выбрать точку – значит задать ее координаты: числа x и y. Точка принадлежит квадрату, если -1 x 1 и -1 y 1. Теорема Пифагора подсказывает : если x 2 + y 2 1, то точка попадет в круг F, иначе она вне круга. Это и есть математическое соотношение, позволяющее для каждой точки определить, лежит ли она в F.

8 8 Ввести N – количество точек N – количество точек -Количество точек в круге М = 0 -i будет последовательно принимать значения 1, 2, 3, …, N -Стандартная функция Random вырабатывает случайные числа в интервале [0,1) -Если точка попадет в круг – значение М увеличим на 1 -Присвоим S примерное значение площади. -Для каждого i печатаем очередное S M = 0 N i = 1, N X = Random Y = Random X 2 +Y 2 1 M:=M+1 S = 4M / i i,,S да нет Проследить, как изменяется S с увеличением количества генерируемых точек i. Алгоритм

9 9 Количество точек (N) Число точек надо брать достаточно большим – не менее 300 Выполнив несколько раз программу для одного и того же N мы получим разные результаты ( в отличии от решения предыдущих задач, когда для одних и тех же исходных данных получался всегда один и тот же результат). Причина: в данной модели используются случайные числа. Такая модель называется вероятностной. Раздел математики – теория вероятностей – доказывает, что такой метод достаточно точен.

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

11 11 Составить алгоритм нахождения площадей следующих фигур методом Монте-Карло 1 x y x y y = x 2 y = x САМОСТОЯТЕЛЬНАЯ РАБОТА

12 12 Решение задач 1.Ученик пишет квадратные уравнения x 2 + px + q = 0, выбирая коэффициенты p и q случайным образом из отрезка [-1; 1]. С какой частотой он будет писать уравнения, имеющие действительные корни? 2. Учитель хочет проверить знание учащимися таблицы умножения, задавая сомножители случайным образом. Напишите программу, которая поможет учителю.

13 13 Решение задач 3.Завод, стоящий на берегу реки, сбрасывает в нее ежедневно случайным образом от 0 до 30 кг вредных веществ. За каждый килограмм сверх 15 завод обязан заплатить штраф 100 тыс. руб. Прибыль завода от реализации продукции 700 тыс. руб. в день. Как часто в течение пятилетки штраф превзойдет прибыль? Рентабелен ли такой завод?