Урок для старших классов "О символика"

Скачать материал

МИНИСТЕРСТВО ОБРАЗОВАНИЯ МОСКОВСКОЙ ОБЛАСТИ

Государственное образовательное учреждение высшего профессионального образования

МОСКОВСКИЙ ГОСУДАРСТВННЫЙ ОБЛАСТНОЙ УНИВЕРСИТЕТ

(МГОУ)

Факультет Физико-математический

«О-символика»

Луценко Евгения Сергеевна

МОСКВА 2014

Содержание

1. Введение

2. Обозначения «О-символики»

3. История вопроса

4. Доказательства свойств «о-малое» и «О-большое»

5. Асимптотика

6. Литература

Введение.

«O» большое и «o» малое (О и о) — математические обозначения для сравнения асимптотического поведения функций.

o(f) «о малое от » обозначает «бесконечно малое относительно », пренебрежимо малую величину при рассмотрении . Смысл термина

O(f) «О большое» зависит от его области применения, но всегда растёт не быстрее, чем , «O большое от »

В частности:

· фраза «сложность алгоритма есть » означает, что с увеличением параметра , характеризующего количество входной информации алгоритма, время работы алгоритма не может быть ограничено величиной, которая растет медленнее, чем n!;

· фраза «функция является „о“ малым от функции в окрестности точки » означает, что с приближением к уменьшается быстрее, чем (отношение $\left |f(x)\right |/\left |g(x)\right |$ стремится к нулю).

Актуальность данной курсовой работы заключается в том, что тема «О-символика» используется в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов.

Цели работы: расскрыть более подробно смысл и значение символов

«О-символики», обозначить и доказать их свойства, уменьшить сложность понимания темы.

Обозначения.

Для функций f(n) и g(n) при $n \to n_0$ используются следующие обозначения:

Обозначение	Интуитивное объяснение	Определение
$f(n) \in O(g(n))$	f ограничена сверху функцией g (с точностью до постоянного множителя) асимптотически	$\exists (C>0), U : \forall (n \in U) \; \|f(n)\| \leq C\|g(n)\|$
$f(n) \in \Omega(g(n))$	f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически	$\exists (C>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\|$
$f(n) \in \Theta(g(n))$	f ограничена снизу и сверху функцией g асимптотически	$\exists (C>0), (C'>0), U : \forall (n \in U) \; C\|g(n)\| \leq \|f(n)\| \leq C'\|g(n)\|$
$f(n) \in o(g(n))$	g доминирует над f асимптотически	$\forall (C>0) ,\exists U : \forall(n \in U) \; \|f(n)\| < C\|g(n)\|$
$f(n) \in \omega(g(n))$	доминирует над g асимптотически	$\forall (C>0) ,\exists U : \forall(n \in U) \; C\|g(n)\| < \|f(n)\|$
$f(n) ~\sim~ g(n)$	эквивалентна g асимптотически	$\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1$

где — проколотая окрестность точки .

История вопроса.

Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом (англ.) во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, Эдмундом Ландау в 1909 году.

Эдмунд Георг Герман (Иезекииль) Ландау (14 февраля 1877, Берлин — 19 февраля 1938, Берлин) — немецкий математик родился в семье преуспевающего берлинского врача-еврея, профессора Леопольда Ландау, мать Йоханна Якоби происходила из известного банкирского дома Якоби. До 16 лет учился в берлинской Французской гимназии, который успешно закончил на 2 года раньше положенного.

В 1899 году под руководством Фробениуса подготовил и защитил диссертацию по теории чисел. В 1901 году защитил докторскую о рядах Дирихле в аналитической теории чисел. В 1909 году, после смерти Минковского, занимает его кафедру и становится профессором математики Гёттингенского университета. В конце 1920-х годов посетил Палестину. Был избран профессором Еврейского университета в Иерусалиме.

В 1934 году, под давлением нацистов, Ландау был вынужден уйти в отставку. Он не захотел покинуть Германию и продолжал жить в Берлине. С 1935 преподавал в Кембриджском, в 1937—1938 — в Брюссельском университетах.

Скончался в 1938 году от сердечного приступа.

Основные открытия Ландау относятся к аналитической теории чисел и комплексному анализу. Часть работ касается оснований математики.

Он исследовал распределение простых чисел и в 1909 году выпустил двухтомную монографию с первым систематическим изложением этой теории. Ландау сумел связать закон распределения простых чисел и распределение простых идеалов алгебраического числового тела. Ландау внёс существенный вклад в исследование функции Римана. В 1930 году опубликовал книгу «Основания анализа», которая считается классическим изложением предмета и в наши дни.

Имя Ландау носит доказанная им теорема об особых точках целых функций. Так же с работами его связана и популяризация обоих обозначений о-малое и О-большое, в связи с чем их также называют символами Ландау. Обозначение пошло от немецкого слова «Ordnung» (порядок).

В честь Эдмунда Ландау названа также функция Ландау. В 1924 году Ландау был избран почётным членом Лондонского математического общества. Избран иностранным членом многих европейских Академий, в том числе иностранным членом - корреспондентом Российской академии наук (1924) и иностранным почётным членом АН СССР (1932).

Основные свойства:

Транзитивность

$\begin{matrix}f(n)=\Theta(g(n)) \land g(n)=\Theta(h(n)) & \Rightarrow & f(n) = \Theta (h(n)) \\ f(n)=O(g(n)) \land g(n)=O (h(n)) & \Rightarrow & f(n) = O (h(n)) \\ f(n)=\Omega(g(n)) \land g(n)=\Omega(h(n)) & \Rightarrow & f(n) = \Omega(h(n)) \\ f(n)=o(g(n)) \land g(n)= o (h(n)) & \Rightarrow & f(n) = o (h(n)) \\ f(n)=\omega(g(n)) \land g(n)=\omega(h(n)) & \Rightarrow & f(n) = \omega(h(n))\end{matrix}$

Рефлексивность

· $f(n)=\Theta(f(n))$

· $f(n)=\Omega(f(n))$

Симметричность

· $f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n))$

Перестановочная симметрия

$\begin{matrix} f(n)= O(g(n)) & \Leftrightarrow & g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) & \Leftrightarrow & g(n)=\omega(f(n)) \end{matrix}$

Дополнительные свойства символов о-малое и О-большое

1. $C \cdot o(f) = o(f)$

$C \cdot O(f) = O(f)$

2. $o(C \cdot f) = o(f)$

$O(C \cdot f) = O(f)$

как следствия:

4. $O(f) \cdot O(g) = O(fg)$

$o(f) \cdot O(g) = o(f) \cdot o(g) = o(fg)$

Свойство 1 и 2

Пусть и – бесконечно малые функции при ха.

= о(β) и = о(β)

+ = о(β)

= о(β) т.е. = о(β) т.е.

__________________________________________________________________

Свойство 3

α= о(Сβ) , С0, С=о(β)-?

;(

Умножение и деление на С

__________________________________________________________________

Свойство 4

;

Свойство 5

о(, n

); )) - ?

;(

= =o=o

__________________________________________________________________

Свойство 6

(o(=o( nN

Пример:

(предположим sin x= o(, 0<t<1

= = ==св-во 8=o((

__________________________________________________________________

8 свойство

=o(

__________________________________________________________________

9 свойство

= 0

__________________________________________________________________

10 свойство

o(o(;

;

__________________________________________________________________

11 свойство

__________________________________________________________________

12 свойство

__________________________________________________________________

13 свойство

__________________________________________________________________

Cвойства «O – большое»

1 свойство

O(o(f(x))=o(f(x))

µ(x) = O(o(f(x)), g(x) = o(f)

__________________________________________________________________

2 свойство

o(O(f)x))) = o(f(x))

g(x)=O(f(x)) ,

__________________________________________________________________

3 свойство

O(o(f(x)) = O(f(x)

g(x)=O(f(x))

__________________________________________________________________

5 свойство

O(f(x)) + o(f(x) – O(f(x))

g(x) = o(f(x) = 0

__________________________________________________________________

Пример:

1)Sin x-x=o(x) -?

2) cos x – 1 +

Асимптотические обозначения в уравнениях

· Если в правой части уравнения находится только асимптотическое обозначение (например n = O(n²)), то знак равенства обозначает принадлежность множеству (n ∈ O(n²)).

· Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула обозначает, что , где — функция, о которой известно только то, что она принадлежит множеству . Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, $\sum_{i=0}^nO(n_i^2)$ — содержит только одну функцию из класса .

· Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.

Например, запись $f(x)\in o(x)$ обозначает, что для любой функции , существует некоторая функция g(x) такая, что выражение x+ f(x) = g(x) — верно для всех .

· Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с правилом.
Например: $4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)$ . Отметим, что такая интерпретация подразумевает выполнение соотношения $4n^4+4n^2+1=\Theta(n^4)$ .

Приведенная интерпретация подразумевает выполнение соотношения:

$\left. \begin{matrix}A = B \\ B = C \end{matrix} \right\} \Rightarrow A = C$ , где A, B, C — выражения, которые могут содержать асимптотические обозначения.

Примеры использования: $e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + ... + \frac{x^n}{n!} + ... = 1 + x + \frac{x^2}{2} + O(x^3)$ при $x \rightarrow 0$

$n! = O\left(\left(\frac{n}{e}\right)^{n + \frac{1}{2}}\right)$ при $n \rightarrow \infty$ (следует из формулы Стирлинга: Формула Стирлинга является первым приближением при разложении факториала в ряд Стирлинга:

при $n \rightarrow \infty$ .

При $n \geq 1$ выполнено неравенство .

Поэтому положим .

Отметим, что нельзя положить , так как и, следовательно, это значение при любой константе больше $c \cdot 0^2=0$ .

Функция при $n \rightarrow \infty$ имеет степень роста .

Чтобы это показать, надо положить и . Можно, конечно, сказать, что имеет порядок , но это более слабое утверждение, чем то, что .

Докажем, что функция при $n \rightarrow \infty$ не может иметь порядок .

Предположим, что существуют константы и такие, что для всех $n \geq n_0$ выполняется неравенство $3^n \leq c \cdot 2^n$ .

Тогда $c \geq \left( \frac{3}{2} \right)^n$ для всех $n \geq n_0$ . Но $\left( \frac{3}{2} \right)^n$ принимает любое, как угодно большое, значение при достаточно большом , поэтому не существует такой константы , которая могла бы мажорировать $\left( \frac{3}{2} \right)^n$ для всех больших некоторого .

$T(n)=n^3+2n^2 = \Omega(n^3), n \rightarrow \infty$ .

Для проверки достаточно положить . Тогда $T(n) \geq cn^3$ для

Литература

· В. Н. Крупский Введение в сложность вычислений.

· Бугров, Никольский Высшая математика, том 2.

Скачать материал

Скачать материал "Урок для старших классов "О символика""

Как учитель может зарабатывать на Инфоуроке?

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 665 188 материалов в базе

Найти материалы

Скачать материал

Другие материалы

docx

Разноуровневая самостоятельная работа по теме "Разность квадратов"

12.10.2015
24742
2395

pptx

Урок по математике "Задачи с параметрами и методы их решений"

12.10.2015
3551
6

docx

«Взаимное расположение прямых и плоскостей в пространстве»

Рейтинг: 5 из 5

12.10.2015
9759
27

pptx

Презентация по математике 5 класс

12.10.2015
4209
10

docx

Доклад на тему "Ошибки в геометрических доказательствах"

12.10.2015
2559
15

docx

МАТЕМАТИКАНЫ ОҚЫТУДА ЖАҢА ИННОВАЦИЯЛЫҚ ӘДІСТЕРДІ ҚОЛДАНУ

Рейтинг: 1 из 5

12.10.2015
4771
53

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Скачать материал
- 12.10.2015 8245
- DOCX 116.2 кбайт
- 10 скачиваний
- Оцените материал:
Настоящий материал опубликован пользователем Луценко Елена Александровна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Автор материала

Луценко Елена Александровна
- На сайте: 8 лет и 6 месяцев
- Подписчики: 1
- Всего просмотров: 28676
- Всего материалов: 11