WWW.DOCX.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет материалы
 

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ МОСКОВСКОЙ ОБЛАСТИ Государственное образовательное учреждение высшего профессионального образования МОСКОВСКИЙ ГОСУДАРСТВННЫЙ ОБЛАСТНОЙ УНИВЕРСИТЕТ (МГОУ) ...»

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

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

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

(МГОУ)

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

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

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

МОСКВА 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

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

1х = о() и 2х = о()

1х + 2х = о()

1х = о() т.е. limхa1(x)=0 2х = о() т.е. limхa2(x)=0limхa1x2x=limхa1(x)±limхa2(x)=0

__________________________________________________________________

Свойство 3

= о(С) limхaС=0, С0, С=о()-?

limхaСС=СlimхaС=0 ;( limхa=0)- ?Умножение и деление на С0limхaСС=1С limхaСlimхaС=0 С=о__________________________________________________________________

Свойство 4

Cо=о, С-const 0=Co ; =o-?

С=o ; (limхa=0)-?

limхaС=0; limхa=limхaСС=(limхaС (limхaСС=0)Свойство 5

о(n)=o(k), n2 nN, k=1,2,…, n-1.=o(n); (=o(k)) - ?

limхan=0;( limхak=0)- ?limхan=limхakkn=limхa(k)·limхank =olimхank=o

__________________________________________________________________

Свойство 6

(o())n=o(n) nN

=olimхa=0

n=o(n)limхank=0-?

limхank=lim(хann)=(limхa)n=0

Пример:

(sinx)xn-3 (предположим sin x= o(x1-e), 0<t<1

(sinx)xn-3= o(x1-e)n)xn-3= o(xn-1)xn-3=o(xn-1)xn-3=св-во 8=o(xn-1-(n-3))=0(x2)__________________________________________________________________

8 свойство

o(n)=o(n-1);n2, nN=nlimхan=0

=on-1-?

limхankт-1=limхan-1=limхan=0

__________________________________________________________________

9 свойство

limхak=1nCk kk=1nCk n=limхak=1nCkkk=1nCk k=0limxak=1nCk k=0limxaC11+ C22…Ck n=0limxaC1+ C2+C32…Ck n = 0

__________________________________________________________________

10 свойство

o(o())=o(); =o()=o(o()limхao()=0 ; limхa=0-?limхa=limхao()o1= limхao()limхao()=0

__________________________________________________________________

11 свойство

o(+o())=o()=o+o; =o-?; limхa=0- ?

limхa=limхa(+o())(+o()=limхa+o()limхao()=0limхao()=0(limхa1+limхao()=0(+limхao()=0__________________________________________________________________

12 свойство

=o; =o()

=; =o-?; limхa=0-?

limхa=limхa=limхa=0

__________________________________________________________________

13 свойство

~

-=o

-=o

limхa=1

limхa-=limхa-limхa1=1-1=0

__________________________________________________________________

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

1 свойство

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

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

(x)Agx, limхag(x)f(x)=0

gconst=A

limхag(x)f(x)=0, limхa(x)f(x)=0-?

limхa(x)f(x)=limхag(x)(x)f(x)g(x)=0

__________________________________________________________________

2 свойство

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

g(x)=O(f(x)) limхa(x)g(x)=0,

x=o(g(x)xAgx

limхa(x)g(x)=0-?

limхa(x)g(x)=limхa(x)g(x)g(x)f(x)=0

__________________________________________________________________

3 свойство

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

g(x)=O(f(x))g(x)Af(x)x=O(gx)(x)A2 g(x)

(x)A2 gxA2A1fx=Af(x)

__________________________________________________________________

5 свойство

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

g(x) = o(f(x) = 0 g(x)f(x)A1 -const0,g(x)A1f(x)

x=Of(x)(x)A2f(x)

x+g(x)x+gxA1fx+A2fx=Af(x)

__________________________________________________________________

Пример:

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

limx0sinx-xx=0-?

limx0sinx-xx=limx0(sinxx-1)=0

2) cos x – 1 + x22=ox2-?limx0cosx-1+x22x2=limx0-2sinx2x2+limx0x22x2=limx0-2sin2x2(x2)24+12=0

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

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

Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x  0 формула  обозначает, что , где  — функция, о которой известно только то, что она принадлежит множеству . Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,      — содержит только одну функцию из класса .

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

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

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

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

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

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

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

 при .

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

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

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

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

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

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

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

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

.

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

Литература

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

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

http://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%B5http://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




Похожие работы:

«Классный час по теме: "День народного единства"Цель: формировать чувство гражданственности и патриотизма; формировать ответственность за судьбу Родины; дать общее представление об истории возникновения праздника и событиях, связанных с 1612г.; расширять кругозор учащихся; развивать умение делать в...»

«Приложение № 1 к Порядку проведения в Московской области в 2015 году отборочного этапа олимпиады школьников Союзного государства "Россия и Беларусь: историческая и духовная общность" Задания для отборочного этапа олимпиады Тексты для написания отзыва А.Т. ТвардовскийПРИЗНАНИЕ Я не пишу дав...»

«ПРИТЧА О СТРАХЕ БОЖИЕМДействующие лица: Ведущий Сережа Аня Действие происходит у них дома. Из окна виден соседский дом.Ведущий: Я расскажу для вас историю вот эту: Она случилась, верно, прошлым летом, А может, и сто лет тому назад. Но поученье нынче можно взять, Как поступать, одним оставшись дома. Вот так, как сказано, иль к...»

«Муниципальное бюджетное общеобразовательное учреждение средняя общеобразовательная школа пос. Славинска муниципального образования "Гвардейский район" Калининградской области 238222, Калининградская область, Гвардейский район, поселок Славинск, ул. Ст...»

«Муниципальное бюджетное общеобразовательное учреждение основная общеобразовательная школа № 3 г. Бикина Бикинского муниципального района Хабаровского краяКраеведческий конкурс: "Был город фронт, была блокада."Номинация: "Творческая краеведческая работа" Сазонова Кр...»

«Диктатура, которая спасла Россию и весь мир Ю.БЕЛОВ. "Правда" № 57 (30119) 30 мая – 2 июня 2014 года. Вопрос, к которому автор настоящей статьи желает привлечь внимание всех, кто намерен овладеть основами марксизма-ле...»

«РАЗРАБОТКА ВЕБ-САЙТА ИНСТИТУТА МАТЕМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ВОЛГУ, ОСНОВАННОГО НА CMS DRUPAL И CSS-ФРЕЙМВОРКЕ BOOTSTRAPDEVELOPMENT OF VOLSU INSTITUTE OF MATHEMATICS AND INFORMATION TECHNOLOGIES WEBSITE...»

«Министерство образования и науки РФ Министерство здравоохранения и социального развития РФ Государственное образовательное учреждение высшего профессионального образования Сама...»







 
2017 www.docx.lib-i.ru - «Бесплатная электронная библиотека - интернет материалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.