Similar presentations:
Последовательности и их пределы. Введение в математический анализ
1.
Последовательности иих пределы
Введение в математический анализ
2.
Домашнее задание3.
Что будетна уроке
1. Последовательности:
определение;
примеры.
1. Сходимость
последовательностей
(вычисление пределов)
4.
Последовательность — это пронумерованныйнабор каких-либо объектов, среди которых
допускаются повторения, причём порядок
объектов имеет значение.
Примеры элементов последовательности:
дни недели, времена года, наше расписание
занятий; распорядок дня (с оговоркой, что
порядок выполнения задач строгий).
5.
Предмет нашего занятия – числовыепоследовательности, пронумерованные
натуральными числами.
В качестве обозначения последовательности
обычно используют строчные латинские
буквы в кавычках
6.
67.
1a
2
6 … n
3
4
5
b
c
7
8.
89.
Два способа заданиячисловой
последовательности
явный
неявный
10.
Явный.В этом случае есть конкретная формула для
получения n-го члена последовательности. Эту
формулу называют общим (главным) членом
последовательности.
10
11.
Неявный.Каждый член последовательности зависит не от
номера, а от других элементов последовательности.
(но упорядоченность элементов сохраняется)
Пример - последовательность Фибоначчи.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
11
12.
Арифметическая игеометрическая прогрессия
(последовательность)
12
13.
Пример геометрическойпоследовательности
13
14.
Пример геометрическойпоследовательности
14
15.
Пример геометрическойпоследовательности
15
16.
Реализация на PythonОткрываем ноутбук
16
17.
Сходимостьпоследовательностей
(пределы)
18.
1819.
1920.
2021.
2122.
2223.
2324.
2425.
• Выяснить тип неопределённости.• Если в выражении дробь вида «многочлен делить на многочлен»
поделить старшую степень.
• Поделить на n в этой степени числитель и знаменатель.
25
26.
2627.
Какая будет старшая степень?27
28.
2829.
2930.
3031.
3132.
3233.
Правила вычисления пределов, если в числителеи знаменателе степенные функции
• если максимальная степень числителя меньше
максимальной степени знаменателя, то предел
равен 0;
• если максимальная степень числителя больше
максимальной степени знаменателя, то предел
равен ±∞;
• если максимальная степень числителя равна
максимальной степени знаменателя, то предел
равен коэффициентам при этих степенях.
33
34.
3435.
3536.
3637.
3738.
Задача (практическое применениетеории пределов)
Понять какой из алгоритмов быстрее для сортировки.
Есть 3 алгоритма:
1) O(n^2)
2) O(n*log(n))
3) O(n).
Фраза «сложность алгоритма есть O(f(n))» означает, что с
ростом n время работы алгоритма будет возрастать не
быстрее, чем С*f(n),
где n - количество результатов поиска, в которых есть
искомая строка в какой-то форме,
С – некоторая константа.
38
39.
Задача (практическое применениетеории пределов)
Ход решения – найти пределы частных.
Например
(решить этот предел можно по правилу Лопиталя или просто оценить: на
бесконечности степенная функция растёт быстрее логарифма).
Значит O(n*log(n)) быстрее, чем O(n^2).
Исходя только из теории пределов, правильный ответ - O(n).
Может возникнуть такая ситуация: O(n) означает, что f(n) <= C*n, но C может
быть настолько велика, что даже на имеющихся миллиардах строк выдачи С >
n), а в алгоритмах O(n^2) и O(n log n) эта константа обычно порядка единиц,
максимум десятков, но никак не миллиардов.
И тогда правильный ответ - O(n*log(n)).
39
40.
Выводы (правила)40
41.
4142.
4243.
4344.
4445.
Сумма членов геометрическойпрогрессии
45
46.
4647.
4748.
Ваши вопросы!Спасибо за внимание!
48