АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Базовые теоремы

Читайте также:
  1. Б) Базовые учебники
  2. Базовые алгоритмы
  3. Базовые архитектуры компьютерных сетей
  4. БАЗОВЫЕ ДОЗИМЕТРИЧЕСКИЕ ВЕЛИЧИНЫ
  5. Базовые знания, умения, навыки необходимые для изучения темы
  6. Базовые идеи анархизма, национализма, фашизма, пацифизма, феминизма, глобализма, антиглобализма, религиозного фуендаментализма.
  7. Базовые компетентности педагога
  8. Базовые конструкции алгоритмов
  9. Базовые концепции и гипотезы финансового менеджмента
  10. Базовые концепции финансового менеджмента
  11. Базовые концепции финансового менеджмента
  12. Базовые концепции финансового менеджмента

 

Теорема 1

Если Pm(n) - функция сложности, представленная полиномом порядка m относительно n, то Pm(n) = Q(nm).

Доказательство

Так как полином

Pm(n) = amn m + am-1n m-1 +... + a0

есть функция сложности алгоритма, то он монотонно не убывает с ростом n для n>0. Отсюда следует, что am>0. Требуется доказать, что $ c1, c2 >0 и такое n0, что для любого n > n0 будут выполняться неравенства:

c1 nm £ Pm(n) £ c2 nm. (1)

Разделим оба неравенства на nm:

c1 £ am + R(n) £ c2 , (2)

где

R(n) = am-1n-1 + am-2n-2 +... + a0n-m.

Т.к. , то существует такое n0, что . Выберем , а . Тогда для любого n > n0 неравенства (2) и, следовательно, (1) будут выполнены.

 

Теорема 2

(3)

Доказательство

Сумма слева есть арифметическая прогрессия, отсюда

.

Тогда справедливость (3) прямо следует из теоремы 1.

 

Теорема 3

. (4)

Доказательство

Доказывется также, как и теорема 2. Известно, что [2]

.

Из теоремы 1 следует справедливость (4).

 

Теорема 4

. (5)

Доказательство

¨Известно, что сумма слева связана с многочленами и числами Бернулли следующим соотношением:

. (6)

где Bm(n) - многочлен Бернулли:

, (7)

а bk - числа Бернулли. Это рациональные числа, приведем первые из них: b0 = 1, b1 = -1/2, b2 = 1/6, b3 = 0, b4 = -1/30.

Из (6) и (7) следует, что

.

При этом коэффициент первого (старшего) члена суммы положителен:

.

Отсюда следует справедливость теоремы.

¨

 

Полезное равенство:

.

Доказать предлагается самостоятельно.

 

 


1 | 2 | 3 | 4 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)