Слайд 2
Методы вычислений
Тема 1. Алгоритм Евклида
Слайд 3
Вычисление НОД
НОД = наибольший общий делитель двух
натуральных чисел – это наибольшее
число, на которое оба исходных числа
делятся без остатка.
Перебор:
Записать в переменную k минимальное из двух чисел.
Если a и b без остатка делятся на k, то стоп.
Уменьшить k на 1.
Перейти к шагу 2.
это цикл с условием!
Слайд 4
Вычисление НОД (перебор)
k := a; { или k
:= b; }
while (a mod k 0) or
(b mod k <> 0) do
k := k - 1;
writeln ('НОД(', a, ',', b, ')=', k);
много операций для больших чисел
ИЛИ
Слайд 5
Алгоритм Евклида
Евклид
(365-300 до. н. э.)
НОД(a,b)= НОД(a-b, b)
= НОД(a, b-a)
Заменяем большее из
двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.
НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)
Пример:
= НОД (7, 7) = 7
Слайд 6
Реализация алгоритма Евклида
пока a ≠ b делай
если
a > b, то
a
:= a - b
иначе b := b - a;
НОД (1998, 2) = НОД (1996, 2) = … = 2
много шагов при большой разнице чисел:
Слайд 7
Модифицированный алгоритм Евклида
НОД(a,b)= НОД(a mod b, b)
= НОД(a, b mod a)
Заменяем большее
из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД.
НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7
Пример:
Еще один вариант:
НОД(2·a,2·b)= 2·НОД(a, b)
НОД(2·a,b)= НОД(a, b) // при нечетном b
Слайд 8
Задания
«4»: Составить программу для вычисления НОД и заполнить
таблицу:
«5»: То же самое, но сравнить для всех пар
число шагов обычного и модифицированного алгоритмов (добавить в таблицу еще две строчки).
Слайд 9
Методы вычислений
Тема 2. Решение уравнений
Слайд 10
Методы решения уравнений
f (x) = 0
Точные (аналитические)
Приближенные
графические
численные
(методы последовательного
приближения):
по графику найти интервал [a, b], в котором находится
x* (или одно начальное приближение x0)
по некоторому алгоритму уточнить решение, сужая интервал, в котором находится x*
повторять шаг 2, пока не достигнута требуемая точность:
b – a < ε
Слайд 11
Численные методы
Применение: используются тогда, когда точное (аналитическое) решение
неизвестно или очень трудоемко.
дают хотя бы какое-то решение
во многих
случаях можно оценить ошибку и найти решение с заданной точностью
решение всегда приближенное, неточное
Слайд 12
Метод прямого перебора
Задача: найти решение уравнения f (x)
= 0 на интервале [a, b] с заданной точностью
ε (чтобы найденное решение отличалось от истинного не более, чем на ε).
Алгоритм:
разбить интервал [a, b] на полосы шириной ε
найти полосу [a*, b*], в которой находится x*
решение – a* или b*
Слайд 13
Есть ли решение на [a, b]?
есть решение
нет решения
нет
решения
Слайд 14
Метод прямого перебора
eps := 0.001; { точность решения
}
x := a;
ответ := x;
пока f(x)*f(x+eps) > 0 делай
x := x + eps; { к следующему интервалу}
конец
eps := 0.001; { точность решения }
x := a;
x := x + eps/2;
while f(x)*f(x+eps) > 0 do begin
x := x + eps; { к следующему интервалу}
end;
Слайд 15
Метод прямого перебора
program qq;
var ...: real;
begin
{ основная
программа }
end.
function f(x: real): real;
begin
f := -x;
end;
Слайд 16
Задания
«4»: Найти все решения уравнения
на интервале [-5,5]
и вывести их на экран.
«5»: Сделать то же самое
с помощью только одного цикла.
Слайд 17
Метод дихотомии (деление пополам)
Найти середину отрезка [a,b]:
c = (a + b) / 2;
Если f(c)*f(a)
сдвинуть правую границу интервала
b = c;
Если f(c)*f(a)≥ 0, сдвинуть левую границу интервала
a = c;
Повторять шаги 1-3, пока не будет b – a ≤ ε.
Слайд 18
Метод дихотомии (деления пополам)
простота
можно получить решение с любой
заданной точностью
нужно знать интервал [a, b]
на интервале [a, b]
должно быть только одно решение
большое число шагов для достижения высокой точности
только для функций одной переменной
Слайд 19
Метод дихотомии (в программе)
пока b - a >
eps делай
c := (a + b) / 2;
если f(a)*f(c) < 0 то
b := c
иначе a := c;
конец
ответ := (a + b) / 2;
Слайд 20
Задания
«4»: Найти все решения уравнения
на интервале [-5,5]
методом дихотомии и вывести их на экран.
«5»: Сделать задачу
на «4» и сравнить число шагов цикла при использовании метода перебора и метода дихотомии.
Слайд 21
Решение уравнений в Exсel
Задача: найти все решения уравнения
на
интервале [-5,5]
Методы решения уравнений:
аналитические: решение в виде формулы
численные: приближенное решение, число
выбрать начальное приближение «рядом» с решением
по некоторому алгоритму вычисляют первое приближение, затем – второе и т.д.
вычисления прекращают, когда значение меняется очень мало (метод сходится)
Слайд 22
Решение уравнения
1. Таблица значений функций на интервале [-5,5]
2.
Графики функций (диаграмма «Точечная»)
2 решения:
начальные приближения
Слайд 23
Решение уравнения
3. Подготовка данных
начальное приближение
целевая ячейка
Цель: H2=0
Слайд 24
Решение уравнения
4. Подбор параметра
ошибка
решение уравнения
Слайд 25
Плавающее бревно
На сколько погрузится бревно радиуса R, брошенное
в воду, если плотность дерева ρд = 700 кг/м3.
Плотность воды ρв = 1000 кг/м3?
H
L
Слайд 26
Плавающее бревно: силы
Сила тяжести
Сила Архимеда
FA
Fg
объем погруженной части
площадь сечения
погруженной
части
полный объем
площадь сечения
Слайд 27
Плавающее бревно: равновесие
Сила тяжести
Сила Архимеда
FA
Fg
неизвестно
Слайд 28
Плавающее бревно: площадь сечения
S1
Слайд 29
Плавающее бревно: уравнение
найти α
Слайд 30
Методы вычислений
Тема 3. Оптимизация
Слайд 31
Оптимизация
Оптимизация – это поиск оптимального (наилучшего) варианта в
заданных условиях.
Оптимальное решение – такое, при котором некоторая заданная
функция (целевая функция) достигает минимума или максимума.
Постановка задачи:
целевая функция
ограничения, которые делают задачу осмысленной
(расходы, потери, ошибки)
(доходы, приобретения)
Задача без ограничений: построить дом
при минимальных затратах.
Решение: не строить дом вообще.
Слайд 32
Оптимизация
локальный минимум
глобальныйминимум
обычно нужно найти глобальный минимум
большинство численных методов
находят только локальный минимум
минимум, который найдет Excel, зависит от
выбора начального приближения («шарик на горке скатится в ближайшую ямку»)
Слайд 33
Поиск минимума функции
1. Строим график функции (диаграмма «Точечная»)
2.
Подготовка данных
начальное приближение
начальное приближение
целевая
ячейка
Слайд 34
Поиск минимума функции
3. Надстройка «Поиск решения»
изменяемые ячейки:
E2
D2:D6
D2:D6; C5:C8
целевая
ячейка
ограничения
A1
= 5
A1 = целое
Слайд 36
Оптимизация
Надстройка «Поиск решения» позволяет:
искать минимум и максимум функции
использовать
несколько изменяемых ячеек и диапазонов
вводить ограничения (=, целое,
двоичное)
Слайд 37
Методы вычислений
Тема 4. Восстановление
зависимостей
Слайд 38
Восстановление зависимостей
Пары значений (аргумент-функция):
задают некоторую неизвестную функцию
Зачем:
найти
в промежу-точных точках
(интерполяция)
найти вне диапазона
измерений
(экстраполяция,
прогнозирование)
какую?
Слайд 39
Какое решение нам нужно?
Вывод: задача некорректна, поскольку решение
неединственно.
Слайд 40
Восстановление зависимостей
Корректная задача: найти функцию заданного вида,
которая
лучше всего соответствует данным.
Примеры:
линейная
полиномиальная
степенная
экспоненциальная
логарифмическая
Слайд 41
Что значит «лучше всего соответствует»?
заданные пары значений
Метод наименьших
квадратов (МНК):
чтобы складывать положительные значения
решение сводится к системе линейных
уравнений (просто решать!)
Слайд 42
МНК для линейной функции
неизвестно!
a
-b
c
Слайд 43
Сопротивление проводника
a
-b
Закон Ома
R
U
A
I
?
Точки на линии:
?
Слайд 44
Обработка результатов эксперимента
Задача. В файле mnk.txt записаны в
столбик 10 пар чисел (напряжение, ток), полученные в результате
эксперимента с одним резистором. Найти (приближенно) его сопротивление по методу наименьших квадратов.
Этапы решения:
Прочитать данные из файла в массивы U и I.
Вычислить и .
Вычислить R*.
Слайд 45
Работа с файлами: принцип сэндвича
I этап. открыть файл
:
связать переменную f с файлом
открыть файл (сделать его
активным,
приготовить к работе)
Assign(f, 'mnk.txt');
Reset(f); {для чтения}
Rewrite(f); {для записи}
II этап: работа с файлом
Переменная типа «текстовый файл»:
var f: text;
III этап: закрыть файл
Close(f);
Read ( f, n ); { ввести значение n }
Write ( f, n ); { записать значение n }
Writeln ( f, n );{c переходом на нов.строку }
Слайд 46
Обработка результатов эксперимента
var f: text;
...
begin
Assign(f, 'mnk.txt');
Reset(f);
for k:=1 to 10 do begin
Read(f, U[k],
I[k]);
Writeln(U[k]:0:3, ' ', I[k]:0:3);
end;
Close(f);
end.
Чтение данных:
U, I: array[1..10] of real;
k: integer;
Слайд 47
Обработка результатов эксперимента
var UU: real;
...
UU := 0;
for k:=1
to 10 do begin
UU := UU + U[k]*U[k];
end;
Вычисления:
Слайд 48
Задания
«4»: Используя метод наименьших квадратов, найти приближенное значение
сопротивления по данным файла mnk.txt.
«5»: Сделать то же самое,
предполагая, что в файле неизвестное количество пар значений, но не более 100. Цикл ввода должен выглядеть так:
while not eof(f) do begin
{ читаем U[k] и I[k] }
{ тут еще что-то надо сделать }
end;
not eof(f)
пока не достигнут конец файла (eof = end of file)
Слайд 49
Коэффициент достоверности (Excel)
заданные пары значений
Крайние случаи:
если график проходит
через точки:
если считаем, что y не меняется и
:
– среднее значение
Слайд 50
Восстановление зависимостей
Диаграмма «График»:
ПКМ
Слайд 53
Восстановление зависимостей
Сложные случаи (нестандартная функция):
Алгоритм:
выделить ячейки для хранения
построить
ряд
для тех же
построить на одной диаграмме ряды и
попытаться подобрать так, чтобы
два графика были близки
вычислить в отдельной ячейке
функции: СУММКВРАЗН – сумма квадратов разностей рядов
ДИСПР – дисперсия
Поиск решения:
Слайд 54
Методы вычислений
Тема 5. Статистика
Слайд 55
Ряд данных и его свойства
Ряд данных – это
упорядоченный набор значений
Основные свойства (ряд A1:A20):
количество элементов =СЧЕТ(A1:A20)
количество элементов,
удовлетворяющих некоторому условию:
= СЧЕТЕСЛИ(A1:A20;"<5")
минимальное значение =МИН(A1:A20)
максимальное значение =МАКС(A1:A20)
сумма элементов =СУММ(A1:A20)
среднее значение =СРЗНАЧ(A1:A20)
Слайд 56
Дисперсия
Для этих рядов одинаковы МИН, МАКС, СРЗНАЧ
Дисперсия («разброс»)
– это величина, которая характеризует разброс данных относительно среднего
значения.
Слайд 57
Дисперсия
среднее арифметическое
квадрат отклонения от среднего
средний квадрат отклонения от
среднего значения
Слайд 58
Дисперсия и СКВО
Стандартная функция
=ДИСПР(A1:A20)
Что неудобно:
если измеряется
в метрах,
то – в
м2
Функции – Другие – Статистические
СКВО = среднеквадратическое отклонение
=СТАНДОТКЛОНП(A1:A20)
Слайд 59
Взаимосвязь рядов данных
Два ряда одинаковой длины:
Вопросы:
есть ли связь
между этими рядами (соответствуют ли пары
какой-нибудь зависимости )
насколько сильна эта связь?
Слайд 60
Взаимосвязь рядов данных
Ковариация:
Как понимать это число?
если
если
если
увеличение приводит к увеличению
в
среднем!
увеличение приводит к уменьшению
связь обнаружить не удалось
Что плохо?
единицы измерения: если в метрах, в литрах,
то – в м⋅л
зависит от абсолютных значений и , поэтому ничего не говорит о том, насколько сильна связь
Слайд 61
Взаимосвязь рядов данных
Коэффициент корреляции:
– СКВО рядов
и
безразмерный!
Как понимать это число?
если
: увеличение приводит к увеличению
если : увеличение приводит к уменьшению
если : связь обнаружить не удалось
=КОРРЕЛ(A1:A20;B1:B20)
Слайд 62
Взаимосвязь рядов данных
Как понимать коэффициент корреляции?
: очень
слабая корреляция
: слабая
: средняя
: сильная
: очень сильная
: линейная зависимость
: линейная зависимость
Слайд 63
Методы вычислений
Тема 6. Моделирование
(по мотивам учебника А.Г. Гейна
и др., Информатика и ИКТ,
10 класс, М.: Просвещение,
2008)
Слайд 64
– начальная численность
– после 1 цикла деления
– после
2-х циклов
Особенности модели:
не учитывается смертность
не учитывается влияние внешней среды
не
учитывается влияние других видов
Модель деления
Слайд 65
– коэффициент рождаемости
– коэффициент смертности
Особенности модели:
не учитывается влияние
численности N и внешней среды на K
не учитывается влияние
других видов на K
Коэффициент
прироста
прирост
Модель неограниченного роста (T. Мальтус)
Слайд 66
Модель ограниченного роста (П. Ферхюльст)
L – предельная численность
животных
Идеи:
коэффициент прироста KL зависит от численности N
при N=0
должно быть KL=K (начальное значение)
при N=L должно быть KL=0 (достигнут предел)
Слайд 67
Модель с отловом
Примеры: рыбоводческое хозяйство, разведение пушных зверей
и т.п.
Слайд 68
Модель эпидемии гриппа
L – всего жителей Ni – больных
в i-ый день
Zi – заболевших в i-ый день Vi –
выздоровевших
Wi – всего выздоровевших за i дней
Основное уравнение:
Ограниченный рост:
Выздоровление
(через 7 дней):
Слайд 69
Влияние других видов
Ni – численность белок, Mi –
численность бурундуков
K2, K4 – взаимное влияние
если K2 >K1 или
K4 >K3 – враждующие виды
Слайд 71
Модель системы «хищник-жертва»
Модель – не-система:
Модель – система:
число встреч
пропорционально Ni⋅Zi
«эффект» пропорционален числу встреч
Слайд 72
Модель системы «хищник-жертва»
Хищники вымирают:
Равновесие:
караси
щуки
Слайд 73
Модель системы «хищник-жертва»
Колебания:
Слайд 74
Случайные процессы
Случайно…
встретить друга на улице
разбить тарелку
найти 10 рублей
выиграть
в лотерею
Случайный выбор:
жеребьевка на
соревнованиях
выигравшие номера
в лотерее
Как получить
случайность?
Слайд 75
Случайные числа на компьютере
Электронный генератор
нужно специальное устройство
нельзя воспроизвести
результаты
318458191041
564321
209938992481
458191
938992
малый период
(последовательность повторяется через 106 чисел)
Метод середины квадрата
(Дж. фон Нейман)
в квадрате
Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.
Слайд 76
Случайные числа на компьютере
Линейный конгруэнтный метод
a, c, m
- целые числа
простое число
230-1
период m
остаток от деления
«Вихрь Мерсенна»: период
219937-1
Слайд 77
Распределение случайных чисел
Модель: снежинки падают на отрезок [a,b]
распределение
равномерное
неравномерное
Слайд 78
Распределение случайных чисел
Особенности:
распределение – это характеристика всей
последовательности, а не одного числа
равномерное распределение одно, компьютерные датчики
(псевдо)случайных чисел дают равномерное распределение
неравномерных – много
любое неравномерное можно получить с помощью равномерного
a
b
a
b
Слайд 79
Вычисление площади (метод Монте-Карло)
Вписываем сложную фигуру в другую
фигуру, для которой легко вычислить площадь (прямоугольник, круг, …).
Равномерно N точек со случайными координатами внутри прямоугольника.
Подсчитываем количество точек, попавших на фигуру: M.
4. Вычисляем площадь:
Всего N точек
На фигуре M точек
Метод приближенный.
Распределение должно быть равномерным.
Чем больше точек, тем точнее.
Точность ограничена датчиком случайных чисел.
!
Слайд 80
Вычисление площади
Когда точка внутри круга?
(x,y)
Случайные координаты:
x := R*random;
y
:= R*random;
Программа:
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;
Слайд 81
Задания
«4»: Вычислите площади кругов c радиусами
R
= 1, 2, 3, 4, 5.
Используя электронные таблицы,
найдите приближенную формулу для вычисления площади круга.
«5»: Вычислите объем шаров c радиусами
R = 1, 2, 3, 4, 5.
Используя электронные таблицы, найдите приближенную формулу для вычисления объема шара.
Слайд 82
Броуновское движение
Случайный шаг:
Случайное направление (в рад):
alpha := 2*pi*random;
h
:= hMax*random;
Программа:
for i:=1 to N do begin
{ найти
случайное направление и шаг }
x := x + h*cos(alpha);
y := y + h*sin(alpha);
end;
Слайд 83
Графика (АЛГО)
Задать цвет линии:
Начальное положение частицы:
x:= 200; y:=
250;
MoveTo(round(x), round(y));
Pen(1, 0, 255, 0);
Движение частицы:
for i:=1 to
N do begin
{ определить новые координаты }
LineTo(round(x), round(y));
end;
толщина линии
R(red)
0..255
G(green)
0..255
B(blue)
0..255
Слайд 84
Задания
«4»: Постройте траектории движения двух частиц в течение
200 шагов. Частицы должны двигаться одновременно.
«5»: Постройте траектории
движения 10 частиц в течение 200 шагов. Частицы должны двигаться одновременно. Используйте массивы для хранения координат частиц.
Слайд 85
Системы массового обслуживания
Примеры:
звонки на телефонной станции
вызовы «скорой помощи»
обслуживание
клиентов в банке
сколько бригад?
сколько линий?
сколько операторов?
Особенности:
клиенты (запросы на обслуживание)
поступают постоянно, но через случайные интервалы времени
время обслуживание каждого клиента – случайная величина
Слайд 86
Клиенты в банке
Вход клиентов:
за 1 минуту – до
Imax человек
равномерное распределение
Обслуживание:
от Tmin до Tmax минут
равномерное распределение
Слайд 87
Клиенты в банке
Число клиентов в помещении банка:
N :=
N + in - out;
было
пришли
ушли
Количество касс: K
Средняя длина очереди:
Допустимая
длина очереди:
Q – длина очереди
Время ожидания:
Слайд 88
Клиенты в банке
Пришли за очередную минуту:
in := round(inMax*random);
округление
Обслужены
за очередную минуту и выходят:
Случайное время обслуживания:
T := Tmin
+ (Tmax – Tmin)*random;
out := round(K / T);
Слайд 89
Клиенты в банке (программа)
count := 0; { счетчик
«плохих» минут }
for i:=1 to L do begin
in
:= { случайное число входящих }
out := { случайное число обслуженных }
N := N + in – out;
if N/K > Qmax then
count := count + 1;
end;
writeln(count/L:10:2);
период моделирования L минут
Слайд 90
Клиенты в банке (исходные данные)
inMax := 10; {
max число входящих за 1 мин }
Tmin :=
1; { min время обслуживания }
Tmax := 5; { max время обслуживания }
L := 1000; { период моделирования в минутах }
M := 10; { допустимое время ожидания }
Задача: найти минимальное K, при котором время ожидания в 90% случаев не больше M минут.
![Есть ли решение на [a, b]?есть решениенет решениянет решения](/img/tmb/7/625265/c4feab82bfb5f6f2d61ad86b7fea9eef-720x.jpg "Методы вычислений")
![Задания«4»: Найти все решения уравнения на интервале [-5,5] и вывести их](/img/tmb/7/625265/7a4723d38e974473749f6f40d2e21424-720x.jpg "Методы вычислений")
![Метод дихотомии (деление пополам)Найти середину отрезка [a,b]: c =](/img/tmb/7/625265/9fdb334a96e5c73541043cc76bf79b8d-720x.jpg "Методы вычислений")
![Задания«4»: Найти все решения уравнения на интервале [-5,5] методом дихотомии и](/img/tmb/7/625265/6042191d8f0d182b30263b4a5c4bd4ce-720x.jpg "Методы вычислений")
![Решение уравнения1. Таблица значений функций на интервале [-5,5]2. Графики функций (диаграмма «Точечная»)2 решения: начальные приближения](/img/tmb/7/625265/3fc6a0d3a0c3b21c15b41671c6627e37-720x.jpg "Методы вычислений")
![Распределение случайных чиселМодель: снежинки падают на отрезок [a,b]распределениеравномерноенеравномерное](/img/tmb/7/625265/6c93be1693b2ec23a66bca3d5776626a-720x.jpg "Методы вычислений")
