Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Урок для старших классов "О символика"

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

  • Математика

Поделитесь материалом с коллегами:

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

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

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

(МГОУ)

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









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











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



МОСКВА 2014



Содержание



1. Введение

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

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

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

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

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

































Введение.

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

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

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

В частности:

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

  • фраза «функция f(x) является „о“ малым от функции g(x) в окрестности точки p» означает, что с приближением x к p f(x) уменьшается быстрее, чем g(x) (отношение \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))

f доминирует над g асимптотически

\forall (C>0) ,\exists U : \forall(n \in U) \; C|g(n)| < |f(n)|

f(n) ~\sim~ g(n)

f эквивалентна g асимптотически

\lim_{n \to n_0} \frac{f(n)}{g(n)} = 1

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

























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

Обозначение «„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)=O(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)

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

o(-f) = o(f)

O(-f) = O(f)

3. o(f) + o(f) = o(f)

o(f) + O(f) = O(f) + O(f) = O(f)

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

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

5. O(O(f)) = O(f)

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





Свойство 1 и 2

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

hello_html_m19b018ad.gif= о(β) и hello_html_467a68eb.gif = о(β)

hello_html_m19b018ad.gif+ hello_html_467a68eb.gif = о(β)

hello_html_m19b018ad.gif= о(β) т.е. hello_html_m19b54388.gif hello_html_467a68eb.gif = о(β) т.е. hello_html_m5301e1a6.gif

hello_html_m3e7d974.gif

__________________________________________________________________

Свойство 3

α= о(Сβ)hello_html_m3853c312.gif , Сhello_html_m2bc03806.gif0, С=о(β)-?

hello_html_12f8c031.gif;( hello_html_m662bd267.gif

Умножение и деление на Сhello_html_47f4e8d2.gif

hello_html_4b05108.gifhello_html_m3498d00e.gif

__________________________________________________________________

Свойство 4

Chello_html_m7037f5b8.gif

hello_html_m43f5bb2f.gif

hello_html_54725bc6.gif

hello_html_m107a9c81.gif; hello_html_m628e677d.gif



Свойство 5

о(hello_html_m1cd378e9.gif, nhello_html_57fa22e1.gif

hello_html_m6b60f6d.gif); hello_html_426e83a2.gif)) - ?

hello_html_591a6159.gif;( hello_html_22bee0e6.gif

hello_html_m24d4e231.gif=hello_html_31166339.gif =ohello_html_43902a30.gif=o

__________________________________________________________________





Свойство 6

(o(hello_html_m7c7ffb7d.gif=o(hello_html_4f4f09d5.gif nhello_html_m2e28bbd1.gifN

hello_html_m63ab3a5f.gif

hello_html_m15532b6f.gif

hello_html_58ab3cc.gif

Пример:

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

hello_html_58578cd2.gif= hello_html_5fb48b0f.gif= hello_html_m3b04b560.gif=hello_html_m3b04b560.gif=св-во 8=o(hello_html_e47ecec.gif(hello_html_1d7723b7.gif

__________________________________________________________________





8 свойство

hello_html_708e38d0.gif=o(hello_html_m153a4073.gif

hello_html_64f91f90.gif

hello_html_20d54a15.gif

hello_html_m464c681.gif

__________________________________________________________________

9 свойство

hello_html_61af23f7.gif= 0

__________________________________________________________________

10 свойство

o(o(hello_html_6e9e268c.gif; hello_html_m3a3527b.gif

hello_html_m1598a40b.gif; hello_html_m1ebb404.gif

hello_html_m7dae6c88.gif

__________________________________________________________________







11 свойство

o(hello_html_m4887f44b.gif

hello_html_m4b2b1ad9.gif

hello_html_m4cbe9808.gif+hello_html_m4a17e084.gif

__________________________________________________________________

12 свойство

hello_html_m2c20424e.gif

hello_html_m1d9f7b70.gif

hello_html_5ea24d28.gif

__________________________________________________________________

13 свойство

hello_html_m7d471794.gif

hello_html_m3d5a823.gif

hello_html_m13ab7cea.gif

hello_html_691f506.gif

hello_html_m1aa1db84.gif

__________________________________________________________________



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

1 свойство

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

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

hello_html_m70d03136.gif

hello_html_61900bee.gif

hello_html_m6ce3fc3e.gif

hello_html_m3217d12f.gif

__________________________________________________________________

2 свойство

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

g(x)=O(f(x)) hello_html_m25978010.gif,

hello_html_133476e7.gif

hello_html_m716a1201.gif

hello_html_32caf151.gif

__________________________________________________________________





3 свойство

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

g(x)=O(f(x))hello_html_25304ac7.gif

hello_html_m7614b779.gif

hello_html_m62ab45ff.gif

__________________________________________________________________

5 свойство

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

g(x) = o(f(x) = 0 hello_html_1df291ca.gif

hello_html_m5fc9d5a7.gif

hello_html_m47c5920f.gif

hello_html_m316531fb.gif

__________________________________________________________________

Пример:

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

hello_html_m667e009b.gif

hello_html_572be28a.gif

2) cos x – 1 + hello_html_m265024a5.gif

hello_html_m2c773516.gif



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

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

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

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

Например, запись f(x)\in o(x)x+o(x)=O(x) обозначает, что для любой функции , существует некоторая функция g(x)hello_html_3da6c2dd.gif такая, что выражение x+ f(x) = g(x) — верно для всех 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 (следует из формулы Стирлинга:81615c3ffac15032bbea4074c1a29765.png Формула Стирлинга является первым приближением при разложении факториала в ряд Стирлинга: 831fdf97c5fa6d4ba7762616b667d739.png

T(n)=(n+1)^2=O(n^2) при n \rightarrow \infty.



При n \geq 1 выполнено неравенство (n+1)^2<4n^2.

Поэтому положим n_0=1, c=4.

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

Функция O(n^3)T(n)=3n^3+2n^2 при n \rightarrow \infty имеет степень роста .

Чтобы это показать, надо положить n_0=0 и c=5. Можно, конечно, сказать, что T(n) имеет порядок O(n^4), но это более слабое утверждение, чем то, что T(n) = O(n^3).

Докажем, что функция 3^n при n \rightarrow \infty не может иметь порядок O(2^n).

Предположим, что существуют константы c и n_0 такие, что для всех 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 принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы c, которая могла бы мажорировать \left( \frac{3}{2} \right)^n для всех n больших некоторого n_0.

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

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





























Литература





Выберите курс повышения квалификации со скидкой 50%:

Автор
Дата добавления 12.10.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров1414
Номер материала ДВ-055285
Получить свидетельство о публикации

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх