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

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

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

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

(МГОУ)

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

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

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

МОСКВА 2014

Содержание

1. Введение

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

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

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

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

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

Введение.

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

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

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

В частности:

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

• фраза «функция является "о" малым от функции в окрестности точки » означает, что с приближением к уменьшается быстрее, чем (отношение стремится к нулю).

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

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

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

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

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

Обозначение

Интуитивное объяснение

Определение

f ограничена сверху функцией g (с точностью до постоянного множителя) асимптотически

f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически

f ограничена снизу и сверху функцией g асимптотически

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

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

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

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

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

Обозначение «"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).

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

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

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

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

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

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

1.

2.

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

3.

4.

5.

Свойство 1 и 2

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

= о(β) и = о(β)

+ = о(β)

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

__________________________________________________________________

Свойство 3

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

;(

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

__________________________________________________________________

Свойство 4

C

;

Свойство 5

о(, n

); )) - ?

;(

= =o=o

__________________________________________________________________

Свойство 6

(o(=o( nN

Пример:

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

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

__________________________________________________________________

8 свойство

=o(

__________________________________________________________________

9 свойство

= 0

__________________________________________________________________

10 свойство

o(o(;

;

__________________________________________________________________

11 свойство

o(

+

__________________________________________________________________

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 формула обозначает, что , где - функция, о которой известно только то, что она принадлежит множеству . Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, - содержит только одну функцию из класса .

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

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

• Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с правилом.
  Например: . Отметим, что такая интерпретация подразумевает выполнение соотношения .

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

, где A, B, C - выражения, которые могут содержать асимптотические обозначения.

Примеры использования: при

при (следует из формулы Стирлинга: Формула Стирлинга является первым приближением при разложении факториала в ряд Стирлинга:

при .

При выполнено неравенство .

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

Отметим, что нельзя положить , так как и, следовательно, это значение при любой константе больше .

Функция при имеет степень роста .

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

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

Предположим, что существуют константы и такие, что для всех выполняется неравенство .

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

.

Для проверки достаточно положить . Тогда для

Литература

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

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

• ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5

• ru.math.wikia.com/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5