ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Асимптотический анализ Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных.

Презентация:



Advertisements
Похожие презентации
Предел и непрерывность функции одной переменной. Бесконечно малые функции Пусть функция определена в окрестности точки a, кроме, быть может, самой точки.
Advertisements

Практическое занятие Приближенные вычисления Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»
Бер Л.М. Введение в анализ ГОУ ВПО НИ ТПУ Рег.282 от Предел функции по Гейне Пусть функция у = f(x) определена в окрестности точки x 0. В самой.
Лектор Пахомова Е.Г г. Математический анализ Раздел: Введение в анализ Тема: Предел функции (свойства пределов, бесконечно большие и их свойства,
Ведение в Математический анализ – часть математики, в которой функции и их обобщения изучаются с помощью пределов. § Понятие функции Основные понятия Пусть.
Предел функции Лекция 1. Ведение в Математический анализ – часть математики, в которой функции и их обобщения изучаются с помощью пределов. § Понятие.
Содержание Понятие числовой последовательности Примеры числовых последовательностей Способы задания последовательностей Ограниченность числовых последовательностей.
Лектор Белов В.М г. Математический анализ Раздел: Введение в анализ Тема: Бесконечно большие последовательности Предел функции (определение и свойства.
1. Алгебраические методы решения Если исходить из определения неравенства, в котором в обеих частях записаны выражения с переменной, то при решении неравенств.
Практическое занятие ОПЕРАЦИИ (сравнение) Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»
Ребята, мы продолжаем изучать логарифмы, и все что с ними связано. На сегодняшнем занятии мы рассмотрим, какими свойствами обладают операции над логарифмами.
Основы высшей математики и математической статистики.
ОСНОВЫ ПРОГРАММИРОВАНИЯ Раздел 2. Математические основы программирования Логические алгоритмы Старший преподаватель Кафедры ВС, к.т.н. Поляков Артем Юрьевич.
Лектор Янущик О.В г. Математический анализ Раздел: Введение в анализ Тема: Числовые последовательности (основные определения, предел последовательности,
Непрерывность функции Рассмотрим функцию f(x), определенную в некоторой окрестности точки Функция f(x) называется 1) она имеет предел в точке если 2) этот.
3 ноября 2012 г.3 ноября 2012 г.3 ноября 2012 г.3 ноября 2012 г. Лекция 3. Предел функции 3-1 Предел последовательности 3-2 Предел функции 3-3 Бесконечно.
Предел последовательности и предел функции. Предел последовательности Рассмотрим две числовые последовательности (у n ) и (х n ) и изобразим их члены.
Введение в теорию пределов. Последовательность Опр. Числовой последовательностью называется функция, заданная на множестве N натуральных чисел. Кратко.
Последовательность. Арифметическая прогрессия.. Последовательностью называется функция заданная на множестве N натуральных чисел или на множестве n первых.
Свойства пределов. 1. Ограниченность функции, имеющей предел. –Определение. –Функция называется ограниченной на множестве D, если –Теорема. Пример. Функция.
Транксрипт:

ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Асимптотический анализ Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ОСНОВЫ ПРОГРАММИРОВАНИЯ

Математический аппарат © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 Для упрощения сумм можно воспользоваться следующими формулами ( где А, B и C – независящая от i константы):

Математический аппарат © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3 Задача 1.1 Типичный калькулятор умеет вычислять натуральные логарифмы (по основанию e) и логарифмы по основанию 10. Как с помощью этих операций вычислить log 27 59, log 15 40? a) b) c) d) e) f) Задача 1.2 Найдите эквивалентное представление следующих выражений, не содержащее знака суммы:

Асимптотические соотношения © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 Пусть f и g– положительные функции от n.Тогда: 1. f(n) = O(g(n)) g(n) = Ω(f(n)). 2. f(n) = Θ(g(n)) g(n) = Θ(f(n)). 3. f(n) = Θ(g(n)) [ f(n) = O(g(n)) и f(n) = Ω(g(n)) ]. 4.f(n) = o(g(n)) g(n) = ω(f(n) ). 5.f(n) = o(g(n)) 6.f(n) = ω(g(n)) 7. f(n) = o(g(n)) f(n) = O(g(n)), обратное не верно. 8.f(n) = ω(g(n)) f(n) = Ω(g(n)), обратное не верно. 9.f(n) ограничено сверху и снизу положительными константами тогда и только тогда, когда f(n) = Θ(1).

Асимптотические соотношения. (пример 1) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 Докажем следующее асимптотическое соотношение: f(n) = O(g(n)) g(n) = Ω(f(n)). Дано: f(n) = O(g(n)). Доказательство: По определению из того, что f(n) = O(g(n)) следует, что: Данное неравенство можем переписать в виде: Отсюда, обозначив, получаем: Дано: g(n) = Ω(f (n)). Доказательство: По определению из того, что g(n) = Ω(f(n)) следует, что: Аналогично предыдущему доказательству, обозначим через, тогда

Асимптотические соотношения. (пример 2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 Докажем следующее асимптотическое соотношение: f(n) = o(g(n)) Дано: f (n) = o(g(n)). Доказательство: По определению из того, что f (n) = o(g(n)) следует, что: Отсюда перейдем к следующему предельному соотношению: Чем больше значение константы c, тем больше вероятность того, что найдется такое n 0,при котором неравенство (*) выполняется. Таким образом, интерес представляют малые значения c. Перепишем последний предел в виде:

Асимптотические соотношения. (пример 2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Докажем следующее асимптотическое соотношение: f (n) = o(g(n)) Дано: Доказательство: Поскольку предел функции h(n)= f (n)/g(n) равен 0, значит эта функция является бесконечно малой. То есть f (n) растет медленнее, чем g(n), а значит найдется такое положительное n 0, что для любой положительной константы c, будет выполняться неравенство:

Визуально определить асимптотические отношения между функциями © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 Задача 2.1 а) f 1 (n) = lg n, f 2 (n) = n

Визуально определить асимптотические отношения между функциями © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 Задача 2.1 b) f 1 (n) = n, f 2 (n) = nsin(n)

Визуально определить асимптотические отношения между функциями © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 Задача 2.1 c) f 1 (n) = n lg c, f 2 (n) = n lgn

Визуально определить асимптотические отношения между функциями © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 Задача 2.1 d) f 1 (n) = n!, f 2 (n) = n n

Правило Лопиталя © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 12 Теорема Лопиталя если f (x) и g(x) удовлетворяют следующим условиям: 1. f (x) и g(x) дифференцируемы в окрестности a за исключением, быть может, самой точки a (в проколотой окрестности a). 2. g'(x) 0 в проколотой окрестности a На практике данная теорема полезна при вычислении пределов с логарифмами: т.к. [ln(x)]' = 1/x., то логарифм легко свести к полиному, для которых пределы вычислять значительно проще.

Определение асимптотических соотношений с помощью пределов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 a) b) c) d) e) f) Задача 2.2 Для каждой из приведенных ниже пар функций f и g выполняется одно из неравенств: либо f = O(g), либо g= O( f ), но не оба сразу. При помощи пределов определите, какой из случаев имеет место.

Определение асимптотических соотношений с помощью пределов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 f1(n)f1(n)f2(n)f2(n)OΩΘ nn2n2 lg nn 2n2n 2 n/2 n lg c n lg n n!n!n nn sin n lg(n!)lg(n n ) ax 2 +bxx2x2 lg n = log 2 n n! = 123 … n Задача 2.3 Заполнить таблицу

Определение асимптотических соотношений с помощью пределов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 15 Расположите по возрастанию : a) log n, log(log n), n b) n!, (1/3) n, log 2 n c) 4, (1/3) n, d), log 2 n, (3/2) n e) 4, (1/3) n, (3/2) n Задача 2.4

Определение асимптотических соотношений с помощью пределов* © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 16 Задача 2.5 Используйте O, o, ω, и Θ для описания отношений между следующими парами функций: a)log k n, n, где k >0 - константа b)n k, c n, где k >0, с>1 – константы c) 2 n, 2 n/2 * Дополнительные задания

Доказательство асимптотических соотношений © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 17 Задача 3.1 a) Докажите, что 17n 1/6 = O(n 1/5 ) Задача 3.2* Докажите или опровергните каждое из следующих утверждений: a) f (n) = O(g(n)) g(n) = o(f (n)). b) f(n) + g(n) = (max(f(n), g(n)). c) f (n) = O(f 2 (n)). d) f (n) = O(g(n)) Ω(f (n)) * Дополнительные задания

Литература © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 18 1.(CLRS) Кормен Т., Лейзерсон Ч., Ривест Р. Штайн К. Алгоритмы: построение и анализ, 2-е изд.: Пер. с англ. – М.: Издательский дом "Вильямс", – 1296 с.: ил. – Парал. тит. англ. ISBN 978–5–8459–0857–5. 2.Дж. Макконнел Анализ алгоритмов. Активный обучающий подход (3-е дополненное издание). – М.: Техносфера, – 416 с. 3.Миллер Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер; Пер. с англ. – М.: БИНОМ. Лаборатория знаний, – 406 с.