
МЕТОДЫ ВЫЧИСЛЕНИЙ
ТЕМА 3. ОПТИМИЗАЦИЯ
<номер>
© М.Е. Никитин, 2015-2016

<номер>
Оптимизация
Оптимизация – это поиск оптимального (наилучшего) варианта в заданных условиях.
Оптимальное решение – такое, при котором некоторая заданная функция (целевая функция) достигает минимума или максимума.
Постановка задачи:
целевая функция
ограничения, которые делают задачу осмысленной
(расходы, потери, ошибки)
(доходы, приобретения)
Задача без ограничений: построить дом
при минимальных затратах.
Решение: не строить дом вообще.

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

<номер>
Поиск минимума функции
1. Строим график функции (диаграмма «Точечная»)
2. Подготовка данных
начальное приближение
Зачем нужен
график?
?
начальное приближение
целевая
ячейка
Изменение E2 должно влиять на F2!
!

<номер>
Поиск минимума функции
3. Надстройка «Поиск решения»
изменяемые ячейки:
E2
D2:D6
D2:D6; C5:C8
целевая
ячейка
ограничения
A1 <= 20
B2:B8 >= 5
A1 = целое

<номер>
Параметры оптимизации

<номер>
Оптимизация
Подбор параметра – это оптимизация?
?
Надстройка «Поиск решения» позволяет:
искать минимум и максимум функции
использовать несколько изменяемых ячеек и диапазонов
вводить ограничения (<=, >=, целое, двоичное)
Как влияет ограничение «A1-целое» на
сложность решения задачи?
?

МЕТОДЫ ВЫЧИСЛЕНИЙ
ТЕМА 4. ВОССТАНОВЛЕНИЕ
ЗАВИСИМОСТЕЙ
<номер>
© М.Е. Никитин, 2015-2016

<номер>
Восстановление зависимостей
Пары значений (аргумент-функция):
задают некоторую неизвестную функцию
Зачем:
найти в промежу-точных точках
(интерполяция)
найти вне диапазона измерений
(экстраполяция,
прогнозирование)
какую?

<номер>
Какое решение нам нужно?
Через заданный набор точек проходит
бесконечно много разных кривых!
!
Вывод: задача некорректна, поскольку решение
неединственно.

<номер>
Восстановление зависимостей
Корректная задача: найти функцию заданного вида,
которая лучше всего соответствует данным.
Примеры:
линейная
полиномиальная
степенная
экспоненциальная
логарифмическая
График функции не
обязательно проходит
через заданные точки!
!
Как выбрать
функцию?
?

<номер>
Что значит «лучше всего соответствует»?
заданные пары значений
Метод наименьших квадратов (МНК):
Зачем возведение в квадрат?
?
чтобы складывать положительные значения
решение сводится к системе линейных уравнений (просто решать!)

<номер>
МНК для линейной функции
неизвестно!
a
-b
c

<номер>
Сопротивление проводника
a
-b
Закон Ома
R
U
A
I
?
Точки на линии:
?

<номер>
Обработка результатов эксперимента
Задача. В файле mnk.txt записаны в столбик 10 пар чисел (напряжение, ток), полученные в результате эксперимента с одним резистором. Найти (приближенно) его сопротивление по методу наименьших квадратов.
Этапы решения:
Прочитать данные из файла в массивы U и I.
Вычислить и .
Вычислить R*.

<номер>
Работа с файлами: принцип сэндвича
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 переходом на нов.строку }

<номер>
Обработка результатов эксперимента
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;
Какие переменные и массивы
надо объявить?
?

<номер>
Обработка результатов эксперимента
var UU: real;
...
UU := 0;
for k:=1 to 10 do begin
UU := UU + U[k]*U[k];
end;
Вычисления:
Что вычисляем?
?
Как найти ?
?
Как найти R*?
?

<номер>
Задания
«4»: Используя метод наименьших квадратов, найти приближенное значение сопротивления по данным файла mnk.txt.
«5»: Сделать то же самое, предполагая, что в файле неизвестное количество пар значений, но не более 100. Цикл ввода должен выглядеть так:
while not eof(f) do begin
{ читаем U[k] и I[k] }
{ тут еще что-то надо сделать }
end;
not eof(f)
пока не достигнут конец файла (eof = end of file)

<номер>
Коэффициент достоверности (Excel)
заданные пары значений
Крайние случаи:
если график проходит через точки:
если считаем, что y не меняется и :
– среднее значение
Фактически – метод наименьших квадратов!
!

<номер>
Восстановление зависимостей
Диаграмма «График»:
ПКМ

<номер>
Восстановление зависимостей
тип функции

<номер>
Восстановление зависимостей
Насколько хорошо выбрана функция?
?
Что такое ?
?
В диаграмме «График»
для первой точки,
для второй и т.д.
!

<номер>
Восстановление зависимостей
Сложные случаи (нестандартная функция):
Что делать?
?
Алгоритм:
выделить ячейки для хранения
построить ряд для тех же
построить на одной диаграмме ряды и
попытаться подобрать так, чтобы
два графика были близки
вычислить в отдельной ячейке
функции: СУММКВРАЗН – сумма квадратов разностей рядов
ДИСПР – дисперсия
Поиск решения:
Это задача оптимизации!
!

МЕТОДЫ ВЫЧИСЛЕНИЙ
ТЕМА 5. СТАТИСТИКА
<номер>
© М.Е. Никитин, 2015-2016

<номер>
Ряд данных и его свойства
Ряд данных – это упорядоченный набор значений
Основные свойства (ряд A1:A20):
количество элементов =СЧЕТ(A1:A20)
количество элементов, удовлетворяющих некоторому условию:
= СЧЕТЕСЛИ(A1:A20;"<5")
минимальное значение =МИН(A1:A20)
максимальное значение =МАКС(A1:A20)
сумма элементов =СУММ(A1:A20)
среднее значение =СРЗНАЧ(A1:A20)

<номер>
Дисперсия
Для этих рядов одинаковы МИН, МАКС, СРЗНАЧ
В чем различие?
?
Дисперсия («разброс») – это величина, которая характеризует разброс данных относительно среднего значения.

<номер>
Дисперсия
среднее арифметическое
квадрат отклонения от среднего
средний квадрат отклонения от среднего значения

<номер>
Дисперсия и СКВО
Стандартная функция
=ДИСПР(A1:A20)
Что неудобно:
если измеряется в метрах,
то – в м2
Функции – Другие – Статистические
СКВО = среднеквадратическое отклонение
=СТАНДОТКЛОНП(A1:A20)
В каких
единицах
измеряется?
?

<номер>
Взаимосвязь рядов данных
Два ряда одинаковой длины:
Вопросы:
есть ли связь между этими рядами (соответствуют ли пары какой-нибудь зависимости )
насколько сильна эта связь?

<номер>
Взаимосвязь рядов данных
Ковариация:
Если и – один и тот же ряд?
?
Как понимать это число?
если
если
если
увеличение приводит к увеличению
в среднем!
увеличение приводит к уменьшению
связь обнаружить не удалось
Что плохо?
единицы измерения: если в метрах, в литрах,
то – в мл
зависит от абсолютных значений и , поэтому ничего не говорит о том, насколько сильна связь

<номер>
Взаимосвязь рядов данных
Коэффициент корреляции:
– СКВО рядов и
Какова размерность?
?
безразмерный!
Как понимать это число?
если : увеличение приводит к увеличению
если : увеличение приводит к уменьшению
если : связь обнаружить не удалось
=КОРРЕЛ(A1:A20;B1:B20)

<номер>
Взаимосвязь рядов данных
Как понимать коэффициент корреляции?
: очень слабая корреляция
: слабая
: средняя
: сильная
: очень сильная
: линейная зависимость
: линейная зависимость
Если , то связи нет?
?
Метод для определения линейной зависимости!
!

МЕТОДЫ ВЫЧИСЛЕНИЙ
ТЕМА 6. МОДЕЛИРОВАНИЕ
<номер>
© М.Е. Никитин, 2015-2016
(по мотивам учебника А.Г. Гейна и др., Информатика и ИКТ,
10 класс, М.: Просвещение, 2008)

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

<номер>
– коэффициент рождаемости
– коэффициент смертности
Особенности модели:
не учитывается влияние численности N и внешней среды на K
не учитывается влияние других видов на K
Коэффициент
прироста
прирост
Модель неограниченного роста (T. Мальтус)

<номер>
Модель ограниченного роста (П. Ферхюльст)
L – предельная численность животных
Идеи:
коэффициент прироста KL зависит от численности N
при N=0 должно быть KL=K (начальное значение)
при N=L должно быть KL=0 (достигнут предел)
Модель адекватна,
если ошибка < 10%!
!

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

<номер>
Модель эпидемии гриппа
L – всего жителей Ni – больных в i-ый день
Zi – заболевших в i-ый день Vi – выздоровевших
Wi – всего выздоровевших за i дней
Основное уравнение:
Ограниченный рост:
болели и выздоровели
Выздоровление
(через 7 дней):

<номер>
Влияние других видов
Ni – численность белок, Mi – численность бурундуков
K2, K4 – взаимное влияние
если K2 >K1 или K4 >K3 – враждующие виды
Откуда видно
влияние?
?

<номер>
Моделирование двух популяций
Как скопировать формулы «вниз»?
?

<номер>
Модель системы «хищник-жертва»
Модель – не-система:
караси
щуки
вымирают без еды
Модель – система:
число встреч пропорционально NiZi
«эффект» пропорционален числу встреч
численность уменьшается
численность увеличивается

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

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

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

<номер>
Случайные числа на компьютере
Электронный генератор
нужно специальное устройство
нельзя воспроизвести результаты
318458191041
564321
209938992481
458191
938992
малый период
(последовательность повторяется через 106 чисел)
Метод середины квадрата (Дж. фон Нейман)
в квадрате
Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.

<номер>
Случайные числа на компьютере
Линейный конгруэнтный метод
a, c, m - целые числа
простое число
230-1
период m
Какой период?
?
остаток от деления
«Вихрь Мерсенна»: период 219937-1

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

<номер>
Распределение случайных чисел
Особенности:
распределение – это характеристика всей последовательности, а не одного числа
равномерное распределение одно, компьютерные датчики (псевдо)случайных чисел дают равномерное распределение
неравномерных – много
любое неравномерное можно получить с помощью равномерного
a
b
a
b
равномерное распределение

<номер>
Вычисление площади (метод Монте-Карло)
Вписываем сложную фигуру в другую фигуру, для которой легко вычислить площадь (прямоугольник, круг, …).
Равномерно N точек со случайными координатами внутри прямоугольника.
Подсчитываем количество точек, попавших на фигуру: M.
4. Вычисляем площадь:
Всего N точек
На фигуре M точек
Метод приближенный.
Распределение должно быть равномерным.
Чем больше точек, тем точнее.
Точность ограничена датчиком случайных чисел.
!

<номер>
Вычисление площади
Когда точка внутри круга?
(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;
Как найти число ?
?

<номер>
Задания
«4»: Вычислите площади кругов c радиусами
R = 1, 2, 3, 4, 5.
Используя электронные таблицы, найдите приближенную формулу для вычисления площади круга.
«5»: Вычислите объем шаров c радиусами
R = 1, 2, 3, 4, 5.
Используя электронные таблицы, найдите приближенную формулу для вычисления объема шара.

<номер>
Броуновское движение
Случайный шаг:
Случайное направление (в рад):
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;

<номер>
Графика (АЛГО)
Задать цвет линии:
Начальное положение частицы:
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

Задания
<номер>
«4»: Постройте траектории движения двух частиц в течение 200 шагов. Частицы должны двигаться одновременно.
«5»: Постройте траектории движения 10 частиц в течение 200 шагов. Частицы должны двигаться одновременно. Используйте массивы для хранения координат частиц.

<номер>
Системы массового обслуживания
Примеры:
звонки на телефонной станции
вызовы «скорой помощи»
обслуживание клиентов в банке
сколько бригад?
сколько линий?
сколько операторов?
Особенности:
клиенты (запросы на обслуживание) поступают постоянно, но через случайные интервалы времени
время обслуживание каждого клиента – случайная величина
Нужно знать характеристики
(распределения) «случайностей»!
!

<номер>
Клиенты в банке
Вход клиентов:
за 1 минуту – до Imax человек
равномерное распределение
Обслуживание:
от Tmin до Tmax минут
равномерное распределение
Сколько нужно касс, чтобы клиенты
стояли в очереди не более М минут?
?

<номер>
Клиенты в банке
Число клиентов в помещении банка:
N := N + in - out;
было
пришли
ушли
Допущение: клиенты распределены по
кассам равномерно!
!
Количество касс: K
Средняя длина очереди:
Допустимая длина очереди:
Q – длина очереди
Время ожидания:

<номер>
Клиенты в банке
Пришли за очередную минуту:
in := round(inMax*random);
округление
Обслужены за очередную минуту и выходят:
Случайное время обслуживания:
T := Tmin + (Tmax – Tmin)*random;
Каждый оператор за эту минуту обслужит
клиентов!
!
out := round(K / T);

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