Викиконспекты - Вклад участника [ru]

Сортировка слиянием

2012-05-15T17:47:27Z

109.205.255.119:

==Описание==
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
'''Сортировка слиянием''' — алгоритм сортировки, хороший пример использования принципа «разделяй и властвуй». Он был предложен Джоном фон Нейманом в 1945 году.

Это стабильный алгоритм сортировки, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log(n))</tex> времени.

==Принцип работы==
Принцип «разделяй и властвуй» — сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:

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

===Слияние двух массивов===
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]]
 
Алгоритм слияния формально можно записать следующим образом:

<pre>// слияние двух массивов с помощью временного
merge (array a, array b) // a - левая половина (от l до m), b - правая половина (от m + 1 до r)
i = l, j = m + 1, k = 0;
array temp;
while i <= m and j <= r
temp[k++] = (a[j] < b[i]) ? a[j++] : b[i++];
while i <= m
temp[k++] = b[i++];
while j <= r
temp[k++] = a[j++];
for (int t = 0; t != k; t++)
a[t] = temp[t]
// в конце a[1..k] это будет отсортированный массив
</pre>

==Рекурсивный алгоритм==
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером l до элемента с номером r:

<pre>// r и l - правая и левая граница массива, m - середина
m = r / 2 // делим на 2 половины
if m == r // условие выхода - если массив стал состоять из 1 элемента
return
sort a[l..m] // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива
sort a[m+1..r]
merge (a[l..m], a[m+1..r]) // делаем процедуру слияния 2х отсортированных половинок
</pre>

Пример работы алгоритма показан на рисунке:

==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> - время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> 
(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

<tex>T(n)</tex> <tex>=</tex> <tex>2T(n/2)</tex> <tex>+</tex> <tex>O(n)</tex> <tex>=</tex> <tex>4T(n/4)</tex> <tex>+</tex> <tex>2*O(n)</tex> <tex>=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kT(1)</tex> <tex>+</tex> <tex>kO(n).</tex>

Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log(n)</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log(n)O(n)</tex>. Так как <tex>T(1)</tex> - константа, то <tex>T(n)=O(n)+\log(n)O(n)=O(n\log(n))</tex>.

==Ссылки==
*[http://ru.wikipedia.org/wiki/Mergesort Википедия - сортировка слиянием]
*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием]
*[http://www.sorting-a\logorithms.com/merge-sort Сортировка слиянием, анимация и свойства (англ.)]
*[http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC Примеры реализации на различных языках (Википедия)]
*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием в картинках (источник картинок в статье)]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]

Сортировка слиянием

2012-05-15T17:34:47Z

109.205.255.119:

=Описание=
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
'''Сортировка слиянием''' — алгоритм сортировки, хороший пример использования принципа «разделяй и властвуй». Он был предложен Джоном фон Нейманом в 1945 году.

Это стабильный алгоритм сортировки, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log(n))</tex> времени.

=Принцип работы=
Принцип «разделяй и властвуй» — сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:

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

==Слияние двух массивов==
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]]
 
Алгоритм слияния формально можно записать следующим образом:

<pre>// слияние двух массивов с помощью временного
merge (array a, array b) // a - левая половина (от l до m), b - правая половина (от m + 1 до r)
i = l, j = m + 1, k = 0;
array temp;
while i <= m and j <= r
temp[k++] = (a[j] < b[i]) ? a[j++] : b[i++];
while i <= m
temp[k++] = b[i++];
while j <= r
temp[k++] = a[j++];
for (int t = 0; t != k; t++)
a[t] = temp[t]
// в конце a[1..k] это будет отсортированный массив
</pre>

==Рекурсивный алгоритм==
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером l до элемента с номером r:

<pre>// r и l - правая и левая граница массива, m - середина
m = r / 2 // делим на 2 половины
if m == r // условие выхода - если массив стал состоять из 1 элемента
return
sort a[l..m] // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива
sort a[m+1..r]
merge (a[l..m], a[m+1..r]) // делаем процедуру слияния 2х отсортированных половинок
</pre>

Пример работы алгоритма показан на рисунке:

=Время работы=
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> - время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> 
(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

<tex>T(n)</tex> <tex>=</tex> <tex>2T(n/2)</tex> <tex>+</tex> <tex>O(n)</tex> <tex>=</tex> <tex>4T(n/4)</tex> <tex>+</tex> <tex>2*O(n)</tex> <tex>=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kT(1)</tex> <tex>+</tex> <tex>kO(n).</tex>

Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log(n)</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log(n)O(n)</tex>. Так как <tex>T(1)</tex> - константа, то <tex>T(n)=O(n)+\log(n)O(n)=O(n\log(n))</tex>.

=Ссылки=
*[http://ru.wikipedia.org/wiki/Mergesort Википедия - сортировка слиянием]
*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием]
*[http://www.sorting-a\logorithms.com/merge-sort Сортировка слиянием, анимация и свойства (англ.)]
*[http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC Примеры реализации на различных языках (Википедия)]
*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием в картинках (источник картинок в статье)]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]

Сортировка слиянием

2012-05-15T06:59:10Z

109.205.255.119:

=Описание=
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
'''Сортировка слиянием''' — алгоритм сортировки, хороший пример использования принципа «разделяй и властвуй». Он был предложен Джоном фон Нейманом в 1945 году.

Это стабильный алгоритм сортировки, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>log(n))</tex> времени.

=Принцип работы=
Принцип «разделяй и властвуй» — сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:

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

==Слияние двух массивов==
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]]
 
Алгоритм слияния формально можно записать следующим образом:

<pre>// слияние двух массивов с помощью временного
merge (array a, array b) // a - левая половина (от l до m), b - правая половина (от m + 1 до r)
i = l, j = m + 1, k = 0;
array temp;
while i <= m and j <= r
temp[k++] = (a[j] < b[i]) ? a[j++] : b[i++];
while i <= m
temp[k++] = b[i++];
while j <= r
temp[k++] = a[j++];
for (int t = 0; t != k; t++)
a[t] = temp[t]
// в конце a[1..k] это будет отсортированный массив
</pre>

==Рекурсивный алгоритм==
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером l до элемента с номером r:

<pre>// r и l - правая и левая граница массива, m - середина
m = r / 2 // делим на 2 половины
if m == r // условие выхода - если массив стал состоять из 1 элемента
return
sort a[l..m] // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива
sort a[m+1..r]
merge (a[l..m], a[m+1..r]) // делаем процедуру слияния 2х отсортированных половинок
</pre>

Пример работы алгоритма показан на рисунке:

=Время работы=
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> - время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> 
(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

<tex>T(n)</tex> <tex>=</tex> <tex>2T(n/2)</tex> <tex>+</tex> <tex>O(n)</tex> <tex>=</tex> <tex>4T(n/4)</tex> <tex>+</tex> <tex>2*O(n)</tex> <tex>=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kT(1)</tex> <tex>+</tex> <tex>kO(n).</tex>

Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log(n)</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log(n)O(n)</tex>. Так как <tex>T(1)</tex> - константа, то <tex>T(n)=O(n)+\log(n)O(n)=O(n\log(n))</tex>.

=Ссылки=
*[http://ru.wikipedia.org/wiki/Mergesort Википедия - сортировка слиянием]
*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием]
*[http://www.sorting-alogorithms.com/merge-sort Сортировка слиянием, анимация и свойства (англ.)]
*[http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC Примеры реализации на различных языках (Википедия)]
*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием в картинках]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]

Сортировка слиянием

2012-05-14T21:39:33Z

109.205.255.119:

=Сортировка слиянием=
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
'''Сортировка слиянием''' — очень простой алгоритм сортировки. Он был предложен Джоном фон Нейманом в 1945 году.

Это стабильный алгоритм сортировки, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>lg(n))</tex> времени.

=Принцип работы=
Данный алгоритм — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:

1. Разбить имеющиеся элементы массива на пары и осуществить слияние элементов каждой пары, получив отсортированные цепочки длины 2 (кроме, быть может, одного элемента, для которого не нашлось пары).

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

3. Если число отсортированных цепочек больше единицы, перейти к шагу 2.

=Слияние 2-х массивов=
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]]
 
Алгоритм слияния формально можно записать следующим образом:

<pre>// слияние двух массивов с помощью временного
merge (array a, array b) // a - левая половина (от l до m), b - правая половина (от m + 1 до r)
i = l, j = m + 1, k = 0;
array temp;
while i <= m and j <= r
temp[k++] = (a[j] < b[i]) ? a[j++] : b[i++];
while i <= m
temp[k++] = b[i++];
while j <= r
temp[k++] = a[j++];
for (int t = 0; t != k; t++)
a[t] = temp[t]
// в конце a[1..k] это будет отсортированный массив
</pre>

=Рекурсивный алгоритм=
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером a до элемента с номером b:

<pre>// r и l - правая и левая граница массива, m - середина
m = r / 2 // делим на 2 половины
if m == r // условие выхода - если массив стал состоять из 1 элемента
return
sort a[l..m] // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива
sort a[m+1..r]
merge (a[l..m], a[m+1..r]) // делаем процедуру слияния 2х отсортированных половинок
</pre>

Пример работы алгоритма показан на рисунке:

=Время работы=
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> - время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> 
(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

<tex>T(n)</tex> <tex>=</tex> <tex>2T(n/2)</tex> <tex>+</tex> <tex>O(n)</tex> <tex>=</tex> <tex>4T(n/4)</tex> <tex>+</tex> <tex>2*O(n)</tex> <tex>=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kT(1)</tex> <tex>+</tex> <tex>kO(n).</tex>

Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log(n)</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log(n)O(n)</tex>. Так как <tex>T(1)</tex> - константа, то <tex>T(n)=O(n)+\log(n)O(n)=O(n\log(n))</tex>.

=Свойства=
Стабильный.

<tex>O(n)</tex> дополнительной памяти для массива.

<tex>O(lg(n))</tex> дополнительной памяти для связных списков.

<tex>O(n</tex> <tex>lg(n))</tex> времени.

=Ссылки=
*[http://ru.wikipedia.org/wiki/Mergesort Википедия - сортировка слиянием]
*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием]
*[http://www.sorting-algorithms.com/merge-sort Сортировка слиянием, анимация и свойства (англ.)]
*[http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC Примеры реализации на различных языках (Википедия)]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]

Участник:Tiss93

2012-05-13T16:22:35Z

109.205.255.119:

Серока Арсений. Гр 1538

ars.seroka@gmail.com

Участник:Tiss93

2012-05-13T16:22:23Z

109.205.255.119: Новая страница: «Серока Арсений. Гр 1538 ars.seroka@gmail.com»

Серока Арсений. Гр 1538
ars.seroka@gmail.com

Сортировка слиянием

2012-05-13T10:30:47Z

109.205.255.119: /* Сортировка слиянием */

=Сортировка слиянием=
[[Файл:Merge sort animation2.gif|right|380px|thumb|Действие алгоритма на примере сортировки случайных точек.]]
'''Сортировка слиянием''' — Сортировка слиянием — вероятно, один из самых простых алгоритмов сортировки (среди «быстрых» алгоритмов). Особенностью этого алгоритма является то, что он работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями.

Кроме того, сортировка слиянием — чуть ли не единственный алгоритм, который может быть эффективно использован для сортировки таких структур данных, как связанные списки. Последовательная работа с элементами массива значительно увеличивает скорость сортировки в системах с кэшированием.

Сортировка слиянием — стабильный алгоритм сортировки. Это означает, что порядок «равных» элементов не изменяется в результате работы алгоритма. В некоторых задачах это свойство достаточно важно.
Этот алгоритм был предложен Джоном фон Нейманом в 1945 году

=Принцип работы=
Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Для решения задачи сортировки эти три этапа выглядят так:
*Сортируемый массив разбивается на две части примерно одинакового размера;
*Каждая из получившихся частей сортируется отдельно, обычно - рекурсивно, тем же самым алгоритмом;
*Два упорядоченных массива половинного размера соединяются в один.

Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).

=Слияние 2-х массивов=
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|center|500px|thumb|Пример работы процедуры слияния.]]
 
Алгоритм слияния формально можно записать следующим образом:

a = 0; b = 0;
While (a < <tex>n_a</tex>) and (b < <tex>n_b</tex>)
If A[a] <tex>\leqslant</tex> B[b]
C[a + b] = A[a];
a = a + 1;
Else
C[a + b] = B[b];
b = b + 1;
End;
End;
If a < <tex>n_a</tex>
Copy remain part of A
Else
Copy remain part of B
End;

=Рекурсивный алгоритм=
Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером a до элемента с номером b:
Function MergeSort(a,b)
If b = a then Exit;
c = (a + b)/2;
Mergesort(a,c);
MergeSort(c + 1,b);
Merge fragments (a,c) and (c + 1,b);
End

Пример работы алгоритма показан на рисунке:
[[Файл:Merge sort1.png|500px|center|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]

=Время работы=
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> - время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> 
(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

T(n) = 2T(n/2) + O(n) = 4T(n/4) + 2*O(n) = ... = 2^kT(1) + kO(n).

Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log(n)</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log(n)O(n)</tex>. Так как <tex>T(1)</tex> - константа, то <tex>T(n)=O(n)+\log(n)O(n)=O(n\log(n))</tex>.

=Ссылки=
*[http://ru.wikipedia.org/wiki/Mergesort| Википедия - сортировка слиянием]
*[http://iproc.ru/parallel-programming/lection-6/| Сортировка слиянием]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]

Участник:Yulya3102/Матан

2012-04-26T18:20:57Z

109.205.255.119: /* Дифференцирование разложений Тейлора */

== Основные вопросы ==

=== Список ===

* Замечание о представимости функции рядом Тейлора
* Дифференцирование разложений Тейлора
* ''Иррациональность числа e''
* Следствие о точках разрыва производной выпуклой функции
* Теорема о свойствах неопределенного интеграла
* Теорема о разложении рациональной дроби на простейшие
* Предел римановых сумм
* ''Интегрируемость модуля интегрируемой функции''
* ''Интегрируемость произведения''
* ''Интегрируемость частного''
* Ослабленный критерий Лебега. Следствие
* ''Иррациональность числа пи''
* Неравенство Чебышева для функций и конечных последовательностей
* Теорема о формуле трапеций
* Формула Эйлера - Маклорена
* Формула Стирлинга
* ''Свойства несобственного интеграла: аддитивность, линейность, монотонность, интегрирование по частям''
* ''Признак сравнения сходимости несобственного интеграла''

=== Правило Лопиталя ===

==== Правило Лопиталя для неопределенностей вида 0/0 ====
{{Теорема
|id=правило Лопиталя для неопределенностей вида 0/0
|statement=Пусть:

<tex>-\infty \le a ,

функции ''f'' и ''g'' дифференцируемы на ''(a, b)'',

<tex>g'(t) \ne 0</tex> для любого <tex>t \in (a, b)</tex>,

<tex>\underset {x \to a+}{\lim} f(x) = \underset{x \to a+}{lim} g(x) = 0</tex>

и существует предел <tex>\underset{x \to a+}{lim} {{f'(x)} \over {g'(x)}} = A \in \overline{\mathbb{R}}</tex>.

Тогда предел <tex>\underset{x \to a+}{lim} {{f(x)} \over {g(x)}}</tex> также существует и равен ''A''.
|proof=1. Пусть <tex>a \in \mathbb{R}</tex>. Доопределим функции в точке ''a'' нулём: <tex>f(a) = g(a) = 0</tex>. Тогда доопределенные функции ''f'' и ''g'' будут непрерывны на ''[a, b)''. Возьмем последовательность <tex>\{ x_n \} : x_n \in (a, b), x_n \to a</tex>, и докажем, что <tex>{{f(x_n)} \over {g(x_n)}} \to A</tex>. Функции ''f'' и ''g'' удовлетворяют условиям теоремы Коши на каждом отрезке <tex>[a, x_n]</tex>. Поэтому для любого <tex>n \in \mathbb{N}</tex> найдется такая точка <tex>c_n \in (a, x_n)</tex>, что

<tex> {{f(x_n} \over {g(x_n)}} = {{f(x_n) - f(a)} \over {g(x_n) - g(a)}} = {{f'(c_n)} \over {g'(c_n)}}</tex>.

По [[Участник:Katyatitkova/Матан#Теорема о сжатой последовательности|теореме о сжатой последовательности]] <tex>c_n \to a</tex>. По [[Участник:Katyatitkova/Матан#Односторонние пределы|определению правостороннего предела]] на языке последовательностей <tex>{f'(c_n) \over g'(c_n)} \to A</tex>, а тогда в силу произвольности <tex> \{x_n\}</tex> и <tex>{f(x) \over g(x)} \underset{x \to a+}{\to} A</tex>.

2. Пусть <tex>a = -\infty</tex>. В силу локальности предела можно считать, что ''b < 0''. Положим <tex>\phi (t) = f(-{1 \over t}), \psi (t) = g(-{1 \over t}) (t \in (0, - {1 \over b}))</tex>. Тогда

<tex>\phi '(t) = {1 \over t^2} f'(-{1 \over t})</tex>,

<tex>\psi '(t) = {1 \over t^2} g'(-{1 \over t}) \ne 0</tex>,

<tex>\underset {t \to 0+}{lim} \phi (t) = \underset {x \to -\infty}{lim} f(x) = 0</tex>,

<tex>\underset {t \to 0+}{lim} \psi (t)= \underset {x \to -\infty}{lim} g(x) = 0</tex>,

<tex>\underset {t \to 0+}{lim} {\phi '(t) \over \psi '(t)} = \underset{x \to -\infty}{lim} {f'(x) \over g'(x)} = A</tex>.

По доказанному

<tex>\underset {x \to -\infty}{lim} {f(x) \over g(x)} = \underset {t \to 0+}{lim} {\phi (t) \over \psi (t)} = A</tex>.
}}

==== Правило Лопиталя для неопределенностей вида inf/inf ====

{{Теорема
|id=правило Лопиталя для неопределенностей вида inf/inf
|statement=Пусть:

<tex>-\infty \le a ,

функции ''f'' и ''g'' дифференцируемы на ''(a, b)'',

<tex>g'(t) \ne 0</tex> для любого <tex>t \in (a, b)</tex>,

<tex>\underset{x \to a+}{lim} g(x) = \infty</tex>

и существует предел <tex>\underset{x \to a+}{lim} {{f'(x)} \over {g'(x)}} = A \in \overline{\mathbb{R}}</tex>.

Тогда предел <tex>\underset{x \to a+}{lim} {{f(x)} \over {g(x)}}</tex> также существует и равен ''A''.
|proof=1. Пусть <tex>A = 0</tex>. Возьмем последовательность <tex>\{x_n\}</tex> со свойствами: <tex>x_n \in (a, b), x_n \to a</tex>, и докажем, что <tex>{f(x_n) \over g(x_n)} \to 0</tex>. Зафиксируем число <tex>\sigma > 0</tex>. По условию найдется такое <tex>y \in (a, b)</tex>, что для любого <tex>c \in (a, y)</tex> будет <tex>g(c) \ne 0</tex> и <tex>\left\vert {f'(c) \over g'(c)}\right\vert < \sigma</tex>. Начиная с некоторого номера <tex>x_n \in (a, y)</tex>, поэтому можно считать, что <tex>x_n \in (a, y)</tex> для всех ''n''. По теореме Коши для любого ''n'' найдется такое <tex>c_n \in (x_n, y)</tex>, что

<tex>{f(x_n) \over g(x_n)} = {f(x_n) - f(y) \over g(x_n) - g(y)} {g(x_n) - g(y) \over g(x_n)} + {f(y) \over g(x_n)} = {f'(c_n) \over g'(c_n)} \left ( 1 - {g(y) \over g(x_n)} \right ) + {f(y) \over g(x_n)}</tex>.

Учитывая еще, что <tex>g(x_n) \to \infty</tex>, находим

<tex>\left\vert {f(x_n) \over g(x_n)} \right\vert \le \sigma \left ( 1 + \left\vert{g(y) \over g(x_n)}\right\vert \right ) + \left\vert {f(y) \over g(x_n)}\right\vert \underset{n \to \infty}{\to} \sigma</tex>.

Поэтому <tex>\overline{lim} \left\vert {f(x_n) \over g(x_n)} \right\vert \le \sigma</tex>. Но, так как <tex>\sigma</tex> произвольно, <tex>\overline{lim} \left\vert {f(x_n) \over g(x_n)} \right\vert = 0</tex>, а значит, и <tex>lim {f(x_n) \over g(x_n)} = 0</tex>.

2. Пусть <tex>A \in \mathbb{R}</tex> произвольно. Положим <tex>h = f - Ag</tex>. Тогда

<tex>\underset{x \to a+}{lim} {h'(x) \over g'(x)} = \underset{x \to a+}{lim} \left ( {f'(x) \over g'(x)} - A \right ) = 0</tex>.

По доказанному <tex>{h(x) \over g(x)} \underset{x \to a+}{\to} 0</tex>, то есть <tex>{f(x) \over g(x)} \underset{x \to a+}{\to} A</tex>.

3. Случай <tex>A = +\infty</tex> рассматривается аналогично случаю <tex>A = 0</tex>. При этом вместо <tex>\left\vert {f'(c) \over g'(c)}\right\vert < \sigma</tex> используется неравенство <tex>{f'(c) \over g'(c)} > M</tex> и доказывается, что <tex>\underline{lim} {f(x_n) \over g(x_n)} \ge M</tex>. Случай <tex>A = -\infty</tex> разбирается аналогично или сводится к случаю <tex>A = +\infty</tex> переходом к функции <tex>-f</tex>.
}}

=== Замечание о представимости функции рядом Тейлора ===

=== Дифференцирование разложений Тейлора ===
Ну приблизительно:
Типа если мы продифференцируем формулу Тейлора для какой-то функции, то получим формулу Тейлора для её производной

=== Иррациональность числа е ===
Виноградов, том 1, 213

=== Критерий монотонности и строгой монотонности ===
==== Критерий монотонности функции ====
{{Теорема
|id=критерий монотонности функции
|statement=Пусть функция ''f'' непрерывна на <tex>\left \langle a, b\right \rangle</tex> и дифференцируема на <tex>(a, b)</tex>. Тогда ''f'' возрастает (убывает) на <tex>\left \langle a, b\right \rangle</tex> в том и только в том случае, когда <tex>f'(x) \ge 0 \ (f'(x) \le 0) \ \forall x \in (a, b)</tex>.
|proof=1. Необходимость. Пусть ''f'' возрастает. Возьмем <tex>x \in (a, b)</tex>. Тогда <tex>f(y) \ge f(x) \ \forall x \in (a, b \rangle</tex> , поэтому

<tex>f'(x) = f'_+(x) = \underset{y \to x+}{lim}{f(y) - f(x) \over y - x} \ge 0</tex>.

2. Достаточность. Пусть <tex>f'(x) \ge 0 \ \forall x \in \langle a, b\rangle</tex> . Возьмем <tex>x_1, x_2 \in \langle a, b\rangle : x_1 < x_2</tex>, и докажем, что <tex>f(x_1) \le f(x_2)</tex>. По теореме Лагранжа <tex>\exists c \in (x_1, x_2)</tex>:

<tex>f(x_2) - f(x_1) = f'(c)(x_2 - x_1) \ge 0</tex>.

Случай убывающей функции сводится к рассмотренному переходом к функции <tex>-f</tex>.
}}

==== Следствие: критерий постоянства функции ====
{{Теорема
|id=критерий постоянства функции
|statement=Пусть <tex>f: \langle a, b\rangle \to \mathbb{R}</tex>. Тогда ''f'' постоянна на <tex>\langle a, b\rangle</tex> в том и только том случае, когда <tex>f \in C\langle a, b\rangle</tex> и <tex>f'(x) = 0 \ \forall x \in (a, b)</tex>.
|proof=То, что производная постоянной функции равна нулю, известно. Обратно, если <tex>f \in C\langle a, b\rangle</tex> и <tex>f'(x) = 0 \ \forall x \in (a, b)</tex>, то по [[#критерий монотонности функции|критерию монотонности функции]] функция <tex>f</tex> одновременно возрастает и убывает, то есть постоянна на <tex>\langle a, b\rangle</tex>.
}}

==== Критерий строгой монотонности функции ====
{{Теорема
|id=критерий строгой монотонности функции
|statement=Пусть функция ''f'' непрерывна на <tex>\langle a, b\rangle</tex> и дифференцируема на <tex>(a, b)</tex>. Тогда ''f'' строго возрастает на <tex>\langle a, b\rangle</tex> в том и только в том случае, когда:

1) <tex>f'(x) \ge 0 \ \forall x \in (a, b)</tex>;

2) <tex>f'</tex> не обращается в нуль тождественно ни на каком интервале.
|proof=По [[#критерий постоянства функции|критерию постоянства функции]] условие 2) означает, что <tex>f</tex> не постоянна ни на каком интервале. Поэтому из строгого возрастания <tex>f</tex> вытекает утверждение 2), а утверждение 1) верно по [[#критерий монотонности функции|критерию монотонности функции]].

Пусть теперь выполнены утверждения 1) и 2). Из неотрицательности производной следует возрастание <tex>f</tex>. Если возрастание нестрогое, то <tex>\exists x_1, x_2 \in \langle a, b\rangle : x_1 < x_2, f(x_1) = f(x_2)</tex>. Тогда <tex>f</tex> постоянна на <tex>[x_1, x_2]</tex>, что противоречит условию 2).
}}

=== Теорема о необходимом и достаточном условии экстремума ===
{{Теорема
|id=теорема о необходимом условии экстремума
|about=Необходимое условие экстремума
|statement=Пусть <tex>f:\langle a,b\rangle\to\mathbb{R},\ x_0\in(a,b)</tex> - точка экстремума <tex>f,\ f</tex> дифференцируема в точке <tex>x_0</tex>. Тогда <tex>f'(x_0)=0.</tex>
|proof=
По [[#Локальный экстремум|определению точки экстремума]] <tex>\exists\delta>0:\ f(x_0)=\underset{x\in(x_0-\delta,x_0+\delta)}{\max}f(x)</tex> или <tex>f(x_0)=\underset{x\in(x_0-\delta,x_0+\delta)}{\min}f(x).</tex>

Остается применить [[Участник:Katyatitkova/Матан#Теорема Ферма (с леммой)|теорему Ферма]] к функции <tex>f|_{(x_0-\delta,x_0+\delta)}.</tex>
}}

=== Лемма о трех хордах ===
{{Лемма
|id=лемма о трех хордах
|statement=Пусть функция <tex>f</tex> выпукла вниз на <tex>\langle a, b\rangle</tex>, <tex>x_1, x_2, x_3 \in \langle a, b\rangle, x_1 < x_2 < x_3</tex>. Тогда

<tex>{f(x_2) - f(x_1) \over x_2 - x_1} \le {f(x_3) - f(x_1) \over x_3 - x_1} \le {f(x_3) - f(x_2) \over x_3 - x_2}</tex>.
|proof=По [[#определение выпуклости|определению выпуклости]]

<tex>f(x_2) \le tf(x_1) + (1-t)f(x_3)</tex>,

где <tex>t={x_3 - x_2 \over x_3 - x_1}, \ 1-t = {x_2 - x_1 \over x_3 - x_1}</tex>. Преобразуем неравенство двумя способами. С одной стороны,

<tex>f(x_2) \le f(x_1)+(1-t)(f(x_3)-f(x_1))=f(x_1)+(x_2-x_1){f(x_3)-f(x_1)\over x_3-x_1}</tex>,

что равносильно левому неравенству в лемме. С другой стороны,

<tex>f(x_2)\le f(x_3)-t(f(x_3)-f(x_1))=f(x_3)-(x_3-x_2){f(x_3)-f(x_1)\over x_3-x)1}</tex>,

что равносильно правому неравенству в лемме.
}}

=== Теорема об односторонней дифференцируемости выпуклой функции ===
{{Теорема
|id=теорема об односторонней дифференцируемости выпуклой функции
|statement=Пусть функция <tex>f</tex> выпукла вниз на <tex>\langle a, b \rangle</tex>. Тогда для любой точки <tex>x \in (a, b) \ \exists</tex> конечные <tex>f'_-(x), f'_+(x): f'_-(x) \le f'_+(x)</tex>.
|proof=Возьмем <tex>x \in (a, b)</tex> и положим

<tex>g(\xi) = {f(\xi) - f(x) \over \xi - x}, \ \xi \in \langle a, b \rangle \backslash \{x\}</tex>.

По [[#лемма о трех хордах|лемме о трех хордах]] ''g'' возрастает на <tex>\langle a, b \rangle \backslash \{x\}</tex>. Поэтому, если <tex>a < \xi < x < \eta < b</tex>, то <tex>g(\xi) \le g(\eta)</tex>, то есть

<tex>{f(\xi) - f(x) \over \xi - x} \le {f(\eta) - f(x) \over (\eta - x}</tex>.

Следовательно, ''g'' ограничена на <tex>\langle a, x)</tex> сверху, а на <tex>(x, b\rangle</tex> - снизу. По [[Участник:Katyatitkova/Матан#Теорема о пределе монотонной функции|теореме о пределе монотонной функции]] существуют конечные пределы <tex>g(x-)</tex> и <tex>g(x+)</tex>, которые по определению являются односторонними производными <tex>f'_-(x)</tex> и <tex>f'_+(x)</tex>. Устремляя <tex>\xi</tex> к <tex>x</tex> слева, а <tex>\eta</tex> - справа, получаем, что <tex>f'_-(x) \le f'_+(x)</tex>.
}}

=== Следствие о точках разрыва производной выпуклой функции ===

=== Описание выпуклости с помощью касательных ===
{{Теорема
|id=описание выпуклости с помощью касательных
|statement=Пусть функция ''f'' дифференцируема на <tex>\langle a, b\rangle</tex>. Тогда ''f'' выпукла вниз на <tex>\langle a, b\rangle</tex> в том и только том случае, когда график ''f'' лежит не ниже любой своей касательной, то есть <tex>\forall x, x_0 \in \langle a, b\rangle</tex>

<tex>f(x) \ge f(x_0)+f'(x_0)(x-x_0)</tex>.
|proof=1. Необходимость. Пусть ''f'' выпукла вниз, <tex>x, x_0 \in \langle a, b\rangle</tex>.

Если <tex>x > x_0</tex>, то по [[#лемма о трех хордах|лемме о трех хордах]] <tex>\forall \eta \in (x_0, x)</tex>

<tex>{f(\eta) - f(x_0) \over \eta - x_0} \le {f(x)-f(x_0)\over x-x_0}</tex>.

Устремляя <tex>\eta</tex> к <tex>x_0</tex> справа, получаем неравенство

<tex>f'(x_0) \le {f(x) - f(x_0) \over x-x_0}</tex>,

равносильное неравенству в теореме.

Если <tex>x < x_0</tex>, то по [[#лемма о трех хордах|лемме о трех хордах]] <tex>\forall \xi \in (x,x_0)</tex>

<tex>{f(\xi)-f(x_0)\over\xi-x_0}\ge{f(x)-f(x_0)\over x-x_0}</tex>.

Устремляя <tex>\xi</tex> к <tex>x_0</tex> слева, получаем неравенство

<tex>f'(x_0) \ge {f(x)-f(x_0)\over x-x_0}</tex>,

равносильное неравенству в теореме.

2. Достаточность. Пусть <tex>\forall x,x_0 \in \langle a, b\rangle</tex> верно неравенство в теореме. Возьмем <tex>x_1, x_2 \in \langle a, b\rangle : x_1 < x_2, \ x \in (x_1, x_2)</tex>. Применяя данное неравенство дважды: сначала к точкам <tex>x_1</tex> и <tex>x</tex>, а затем - к <tex>x_2</tex> и <tex>x</tex>, получаем

<tex>f(x_1) \ge f(x) + f'(x)(x_1 - x)</tex>,

<tex>f(x_2) \ge f(x) + f'(x)(x_2 - x)</tex>,

что равносильно

<tex>{f(x) - f(x_1)\over x-x_1}\le f'(x)\le{f(x_2)-f(x)\over x_2-x}</tex>.

Крайние части и составляют неравенство, равносильное неравенству из [[#определение выпуклости|определения выпуклости]].
}}

=== Дифференциальный критерий выпуклости ===
{{Теорема
|id=дифференциальные критерии выпуклости
|statement=
1. Пусть функция <tex>f</tex> непрерывна на <tex>\langle a,b\rangle</tex> и дифференцируема на <tex>(a,b)</tex>. Тогда <tex>f</tex> (строго) выпукла вниз на <tex>\langle a,b\rangle</tex> в том и только том случае когда <tex>f'</tex> (строго) возрастает на <tex>(a,b)</tex>.

2. Пусть функция <tex>f</tex> непрерывна на <tex>\langle a,b\rangle</tex> и дважды дифференцируема на <tex>(a,b)</tex>. Тогда <tex>f</tex> выпукла вниз на <tex>\langle a,b\rangle</tex> в том и только том случае, когда <tex>f''(x)\ge0\ \forall x\in(a,b)</tex>.
|proof=
1. Необходимость. Возьмем <tex>x_1,x_2\in(a,b):\ x_1<x_2</tex>. По [[#Теорема об односторонней дифференцируемости выпуклой функции|теореме об односторонней дифференцируемости выпуклой функции]]

<tex>f'(x_1)\le{f(x_2)-f(x_1)\over x_2-x_1}\le f'(x_2)</tex>,

что и означает возрастание <tex>f'</tex>.

Достаточность. Возьмем <tex>x_1,x_2\in\langle a,b\rangle:\ x_1<x_2</tex>, и <tex>x\in(x_1,x_2)</tex>. По [[Участник:Katyatitkova/Матан#Теоремы Лагранжа и Коши. Следствия об оценке приращения и о пределе производной|теореме Лагранжа]] <tex>\exists c_1\in(x_1,x),\ c_2\in(x,x_2):\ {f(x)-f(x_1)\over x-x_1}=f'(c_1),\ {f(x_2)-f(x)\over x_2-x}=f'(c_2).</tex>

Тогда <tex>x_1<c_1<x<c_2<x_2</tex>, а <tex>f'</tex> по условию возрастает, поэтому <tex>f'(c_1)\le f'(c_2)</tex>, то есть

<tex>{f(x)-f(x_1)\over x-x_1}\le{f(x_2)-f(x)\over x_2-x}</tex>,

что равносильно [[#Выпуклая функция|неравенству из определения выпуклости]].

Если <tex>f</tex> строго выпукла вниз, то оба неравенства в доказательстве необходимости строгие. Обратно, если <tex>f'</tex> строго возрастает, то неравенство в доказательстве достаточности строгое, что влечет выпуклость <tex>f</tex>.

2. По пункту 1 выпуклость <tex>f</tex> равносильна возрастанию <tex>f'</tex>, которое по [[#Критерий монотонности функции|критерию монотонности]] равносильно неотрицательности <tex>f''</tex>.
}}

=== Неравенство Йенсена ===
{{Теорема
|id=неравенство Йенсена
|statement=Пусть функция <tex>f</tex> выпукла вниз на <tex>\langle a,b\rangle,\ n\in\mathbb{N}</tex>. Тогда <tex>\forall x_1,...,x_n\in\langle a,b\rangle</tex> и <tex>p_1,...,p_n>0</tex>

<tex>f\left({\underset{k=1}{\overset{n}{\sum}}p_kx_k\over\underset{k=1}{\overset{n}{\sum}}p_k}\right)\le{\underset{k=1}{\overset{n}{\sum}}p_kf(x_k)\over\underset{k=1}{\overset{n}{\sum}}p_k}.</tex>

Замечание 1. Числа <tex>p_k</tex> называются ''весами'', а отношение <tex>{\underset{k=1}{\overset{n}{\sum}}p_kx_k\over\underset{k=1}{\overset{n}{\sum}}p_k}</tex> - ''взвешенным средним'' (арифметическим) чисел <tex>x_1,...,x_n</tex>. Если все <tex>p_k=1</tex>, то взвешенное среднее есть обычное среднее арифметическое <tex>{1\over n}\underset{k=1}{\overset{n}{\sum}}x_k</tex>. Неравенство Йенсена можно сформулировать так: значение выпуклой вниз функции от взвешенного среднего не превосходит взвешенного среднего значений функции.

Замечание 2. Не уменьшая общности, можно считать, что <tex>\underset{k=1}{\overset{n}{\sum}}p_k=1</tex>. При этом условии неравенство Йенсена принимает вид

<tex>f\left(\underset{k=1}{\overset{n}{\sum}}p_kx_k\right)\le\underset{k=1}{\overset{n}{\sum}}p_kf(x_k)</tex>.

Действительно, для произвольных положительных <tex>p_k</tex> положим <tex>q_k={p_k\over\underset{j=1}{\overset{n}{\sum}}p_j}</tex>. Тогда неравенство Йенсена для весов <tex>p_k</tex> и <tex>q_k</tex> выглядит одинаково, а <tex>\underset{k=1}{\overset{n}{\sum}}q_k=1</tex>.
|proof=
Пусть <tex>\underset{k=1}{\overset{n}{\sum}}p_k=1</tex>. Положим <tex>x^*=\underset{k=1}{\overset{n}{\sum}}p_kx_k</tex>.

Сразу отметим, что если <tex>x_1=...=x_n</tex>, то <tex>x^*</tex> с ними совпадает, а неравенство Йенсена обращается в равенство.

Пусть среди чисел <tex>x_1,...,x_n</tex> есть различные.

Проверим, что <tex>x^*\in(a,b)</tex>. Действительно, хоть одно из чисел <tex>x_k</tex> меньше <tex>b</tex>, поэтому

<tex>x^*=\underset{k=1}{\overset{n}{\sum}}p_kx_k<\underset{k=1}{\overset{n}{\sum}}p_kb=b</tex>.

Аналогично доказывается, что <tex>x^*>a</tex>.

В точке <tex>x^*</tex> у функции <tex>f</tex> существует опорная прямая; пусть она задается уравнением <tex>\ell(x)=\alpha x+\beta</tex>. По [[#Опорная прямая|определению опорной прямой]] <tex>\ell(x^*)=f(x^*)</tex> и <tex>\ell(x_k)\le f(x_k)\ \forall k</tex>. Поэтому

<tex>f(x^*)=\ell(x^*)=\alpha\underset{k=1}{\overset{n}{\sum}}p_kx_k+\beta=\underset{k=1}{\overset{n}{\sum}}p_k(\alpha x_k+\beta=\underset{k=1}{\overset{n}{\sum}}p_k\ell(x_k)\le\underset{k=1}{\overset{n}{\sum}}p_kf(x_k).</tex>
}}

=== Неравенство Гельдера ===
{{Теорема
|statement=Пусть <tex>a,b\in\mathbb{R}^n</tex> или <tex>\mathbb{C}^n,\ p>1,\ \frac{1}{p}+\frac{1}{q}=1</tex>. Тогда

<tex>\left\vert\underset{k=1}{\overset{n}{\sum}}a_kb_k\right\vert\le\left(\underset{k=1}{\overset{n}{\sum}}\vert a_k\vert^p\right)^{1/p}\left(\underset{k=1}{\overset{n}{\sum}}\vert b_k\vert^q\right)^{1/q}</tex>.
|proof=Так как <tex>\left\vert\underset{k=1}{\overset{n}{\sum}}a_kb_k\right\vert\le\underset{k=1}{\overset{n}{\sum}}\vert a_kb_k\vert</tex>,

достаточно доказать неравенство Гельдера для чисел <tex>\vert a_k\vert,\ \vert b_k\vert</tex>. Поэтому, не уменьшая общности, можно считать, что <tex>a_k,b_k\in\mathbb{R}_+</tex>. Более того, можно считать, что все <tex>b_k>0</tex>. Действительно, если неравенство Гельдера доказано для положительных чисел <tex>b_k</tex>, то

<tex>\underset{k=1}{\overset{n}{\sum}}a_kb_k=\underset{k:b_k\ne0}{\sum}a_kb_k\le\left(\underset{k:b_k\ne0}{\sum}a_k^p\right)^{1/p}\left(\underset{k:b_k\ne0}{\sum}b_k^q\right)^{1/q}\le\left(\underset{k=1}{\overset{n}{\sum}}a_k^p\right)^{1/p}\left(\underset{k=1}{\overset{n}{\sum}}b_k^q\right)^{1/q}.</tex>

Итак, пусть <tex>a_k\ge0,\ b_k>0\ \forall k</tex>. Функция <tex>f(x)=x^p</tex> строго выпукла вниз на <tex>[0,+\infty)</tex>. Положим <tex>p_k=b_k^q,\ x_k=a_kb_k^{1-q}</tex> и применим [[#Неравенство Йенсена|неравенство Йенсена]]:

<tex>\left({\underset{k=1}{\overset{n}{\sum}}p_kx_k\over\underset{k=1}{\overset{n}{\sum}}p_k}\right)^p\le{\underset{k=1}{\overset{n}{\sum}}p_kx_k^p\over\underset{k=1}{\overset{n}{\sum}}p_k}</tex>.

Учитывая, что <tex>p_kx_k=a_kb_k,\ p_kx_k^p=b_k^qa_k^pb_k^{p(1-q)}=a_k^p,</tex> получаем:

<tex>\left({\underset{k=1}{\overset{n}{\sum}}a_kb_k\over\underset{k=1}{\overset{n}{\sum}}b_k^q}\right)^p\le{\underset{k=1}{\overset{n}{\sum}}a_k^p\over\underset{k=1}{\overset{n}{\sum}}b_k^q},</tex>

<tex>\left(\underset{k=1}{\overset{n}{\sum}} a_kb_k\right)^p\le\left(\underset{k=1}{\overset{n}{\sum}}a_k^p\right)\left(\underset{k=1}{\overset{n}{\sum}}b_k^q\right)^{p-1}.</tex>

Остается возвести обе части неравенства в степень <tex>\frac{1}{p}</tex> и воспользоваться тем, что <tex>1-\frac{1}{p}=\frac{1}{q}.</tex>
}}

=== Неравенство Минковского ===
{{Теорема
|id=неравенство Минковского
|statement=Пусть <tex>a,b\in\mathbb{R}^n</tex> или <tex>\mathbb{C}^n,\ p\ge1</tex>. Тогда

<tex>\left(\underset{k=1}{\overset{n}{\sum}}\vert a_k+b_k\vert^p\right)^{1/p}\le\left(\underset{k=1}{\overset{n}{\sum}}\vert a_k\vert^p\right)^{1/p}+\left(\underset{k=1}{\overset{n}{\sum}}\vert b_k\vert^p\right)^{1/p}</tex>.
|proof=При <tex>p=1</tex> неравенство Минковского сводится к неравенству треугольника для модуля. Пусть <tex>p>1,\ q={p\over p-1}</tex>. Обозначим <tex>C=\underset{k=1}{\overset{n}{\sum}}\vert a_k+b_k\vert^p</tex>. Применим неравенство треугольника, а затем неравенство Гёльдера:

<tex>C=\underset{k=1}{\overset{n}{\sum}}\vert a_k+b_k\vert\vert a_k+b_k\vert^{p-1}\le\underset{k=1}{\overset{n}{\sum}}\vert a_k\vert\vert a_k+b_k\vert^{p-1}+\underset{k=1}{\overset{n}{\sum}}\vert b_k\vert a_k+b_k\vert^{p-1}\le\left(\underset{k=1}{\overset{n}{\sum}}\vert a_k\vert^p\right)^{1/p} \left(\underset{k=1}{\overset{n}{\sum}}\vert a_k+b_k\vert^{(p-1)q}\right)^{1/q}+\left(\underset{k=1}{\overset{n}{\sum}}\vert b_k\vert^p\right)^{1/p} \left(\underset{k=1}{\overset{n}{\sum}}\vert a_k+b_k\vert^{(p-1)q}\right)^{1/q}=\left\{\left(\underset{k=1}{\overset{n}{\sum}}\vert a_k\vert^p\right)^{1/p}+\left(\underset{k=1}{\overset{n}{\sum}}\vert b_k\vert^p\right)^{1/p}\right\}C^{1/q}.</tex>

Если <tex>C=0</tex>, то неравенство Минковского очевидно, а если <tex>C>0</tex>, то, сокращая на <tex>C^{1/q}</tex>, получаем требуемое.
}}

=== Неравенство Коши ===
{{Теорема
|about=Монотонность средних степенных
|statement=Пусть <tex>n\in\mathbb{N},\ r,s\in\mathbb{R},\ r<s,\ a_1,...,a_n\ge0</tex> при <tex>r\ge0,\ a_1,...,a_n>0</tex> при <tex>r<0</tex>. Тогда <tex>M_r(a)\le M_s(a)</tex>, причем равенство имеет место лишь при <tex>a_1=...=a_n</tex>. В частности,

<tex>\sqrt[n]{a_1\cdot...\cdot a_n}\le{a_1+...+a_n\over n}</tex>.

Это неравенство называется '''неравенством Коши''' между средним геометрическим и средним арифметическим.
|proof=1. Пусть <tex>0<r<s</tex>. Поскольку <tex>{s\over r}>1</tex>, функция <tex>f(x)=x^{s/r}</tex> строго выпукла вниз на <tex>[0,+\infty)</tex>. Применим к ней [[#Неравенство Йенсена|неравенство Йенсена]], взяв <tex>p_k=1,\ x_k=a^r_k</tex>. Получим

<tex>\left({1\over n} \underset{k=1}{\overset{n}{\sum}} a_k^r\right)^{s/r}\le{1\over n}\underset{k=1}{\overset{n}{\sum}}a_k^s</tex>,

причем в силу строгой выпуклости равенство достигается лишь при <tex>a_1=...=a_n</tex>. Остается возвести обе части в степень <tex>1\over s</tex>.

2. Пусть <tex>r=0,s=1</tex>, то есть докажем неравенство Коши. Если среди <tex>a_k</tex> есть нуль, то неравенство очевидно выполняется и обращается в равенство лишь если все <tex>a_k</tex> суть нули. Пусть <tex>a_1,...,a_n>0</tex>. Применим [[#Неравенство Йенсена|неравенство Йенсена]] к строго выпуклой вверх функции <tex>\ln</tex>, взяв <tex>p_k=1,\ x_k=a_k</tex>. Получим

<tex>{1\over n} \underset{k=1}{\overset{n}{\sum}} \ln a_k\le \ln\left({1\over n} \underset{k=1}{\overset{n}{\sum}} a_k\right)</tex>,

что равносильно неравенству Коши, причем в силу строгой выпуклости равенство достигается лишь при <tex>a_1=...a_n</tex>.

3. Если <tex>r=0<s</tex>, то по доказанному неравенству Коши

<tex>M_0(a)=M_0^{1/s}(a^s)\le M_1^{1/s}(a^s)=M_s(a).</tex>

4. Если <tex>r<s\le0</tex>, то <tex>0\le-s<-r</tex>, и по доказанному

<tex>M_r(a)={1\over M_{-r}({1\over a})}\le {1\over M_{-s}({1\over a})}=M_s(a).</tex>

5. Если <tex>r<0<s</tex>, то <tex>M_r(a)\le M_0(a)\le M_s(a).</tex>
}}

=== Теорема о свойствах неопределенного интеграла ===
Виноградов, том 1, 254

=== Теорема о разложении рациональной дроби на простейшие ===

=== Лемма о свойствах сумм Дарбу ===
{{Теорема
|id=лемма о свойствах сумм Дарбу
|statement=
1. <tex>S_\tau(f)=\underset{\xi}{\sup}\sigma_\tau(f,\xi),\ s_\tau(f)=\underset{\xi}{\inf}\sigma_\tau(f,\xi)</tex> (грани берутся по всевозможным оснащениям дробления <tex>\tau</tex>).

2. При добавлении новых точек дробления верхняя сумма не увеличится, а нижняя - не уменьшится.

3. Каждая нижняя сумма Дарбу не превосходит каждой верхней (даже отвечающей другому дроблению).
|proof=1. Для определенности докажем утверждение о верхних суммах. Очевидно, что <tex>f(\xi_k)\le M_k\ \forall k\in[0:n-1]</tex> . Умножая эти неравенства на <tex>\Delta x_k</tex> и суммируя по <tex>k</tex>, получаем неравенство <tex>\sigma\le S</tex>, то есть <tex>S</tex> - верхняя граница для интегральных сумм Римана. Докажем, что эта верхняя граница точная.

Пусть <tex>f</tex> ограничена сверху на <tex>[a,b]</tex>. Возьмем <tex>\epsilon>0</tex> и для каждого <tex>k</tex> по [[Участник:Katyatitkova/Матан#Верхняя, нижняя границы; супремум, инфимум|определению верхней грани]] подберем <tex>\xi^*_k\in[x_k,x_{k+1}]:\ f(\xi^*_k)>M_k-{\epsilon\over b-a}</tex>. Тогда

<tex>\sigma^*=\underset{k=0}{\overset{n-1}{\sum}}f(\xi^*_k)\Delta x_k>S={\epsilon\over b-a}\underset{k=0}{\overset{n-1}{\sum}}\Delta x_k=S-\epsilon</tex>.

Так как <tex>\epsilon</tex> произвольно, <tex>S</tex> - точная верхняя граница.

Пусть <tex>f</tex> не ограничена сверху на <tex>[a,b]</tex>. Тогда <tex>\exists \nu:\ f</tex> - не ограничена сверху на <tex>[x_\nu,x_{\nu+1}]</tex>. Возьмем <tex>A>0</tex> и выберем точки <tex>\xi^*_k</tex> при <tex>k\ne\nu</tex> произвольно, а <tex>\xi^*_\nu</tex> - так, чтобы

<tex>f(\xi^*_\nu)>{1\over\Delta x_\nu}\left(A-\underset{k\ne\nu}{\sum}f(\xi^*_k)\Delta x_k\right)</tex>.

Тогда

<tex>\sigma^*=\underset{k=0}{\overset{n-1}{\sum}}f(\xi^*_k)\Delta x_k>A</tex>.

Так как <tex>A</tex> произвольно, <tex>\underset{\xi}{\sup}\sigma=+\infty=S</tex>.

2. Для определенности докажем утверждение о верхних суммах. В силу принципа математической индукции достаточно проверить, что верхняя сумма не увеличится при добавлении одной новой точки дробления. Пусть дробление <tex>T</tex> получено из дробления <tex>\tau=\{x_k\}^n_{k=0}</tex> добавлением точки <tex>c\in(x_\nu,x_{\nu+1})</tex>. Тогда

<tex>S_\tau=\underset{k=0}{\overset{\nu-1}{\sum}}M_k\Delta x_k+M_\nu\Delta x_\nu+\overset{n-1}{\underset{k=\nu+1}{\sum}}M_k\Delta x_k</tex>,

<tex>S_T=\underset{k=0}{\overset{\nu-1}{\sum}}M_k\Delta x_k+M'(c-x_\nu)+M''(x_{\nu+1}-c)+\underset{k=\nu+1}{\overset{n-1}{\sum}}M_k\Delta x_k</tex>,

где <tex>M'=\underset{x\in[x_\nu,c]}{\sup}f(x),\ M''=\underset{x\in[c,x_{\nu+1}]}{\sup}f(x)</tex>. Поскольку при сужении множества его супремум не увеличивается, <tex>M'\le M_\nu</tex> и <tex>M''\le M_\nu</tex>. Поэтому

<tex>S_\tau-S_T=M_\nu\Delta x_\nu - M'(c-x_\nu)-M''(x_{\nu+1}-c)\ge M_\nu(x_{\nu+1}-x_\nu-c+x_\nu+c-x_{\nu+1} = 0.</tex>

3. Неравенство <tex>s_\tau\le S_\tau</tex> между суммами для одного и того же дробления <tex>\tau</tex> тривиально. Пусть <tex>\tau_1</tex> и <tex>\tau_2</tex> - два дробления отрезка <tex>[a,b]</tex>. Докажем, что <tex>s_{\tau_1} \le S_{\tau_2}</tex>. Положим <tex>\tau=\tau_1\cup\tau_2</tex>. Тогда по свойству 2

<tex>s_{\tau_1}\le s_\tau\le S_\tau\le S_{\tau_2}.</tex>
}}

=== Критерий интегрируемости Римана ===
{{Теорема
|id=критерий интегрируемости функции
|about=Критерий интегрируемости функции
|statement=Пусть <tex>f:[a,b]\to\mathbb{R}</tex>. Тогда <tex>f\in R[a,b]</tex> в том и только том случае, когда <tex>S_\tau(f) - s_\tau(f)\underset{\lambda\to0}{\to}0</tex>, то есть

<tex>\forall\epsilon>0\ \exists\delta>0\ \forall\tau:\lambda_\tau<\delta\ S_\tau(f)-s_\tau(f)<\epsilon.</tex>
|proof=1. Необходимость. Пусть <tex>f\in R[a,b]</tex>. Обозначим <tex>I=\int^b_af</tex>. Возьмем <tex>\epsilon>0</tex> и подберем такое <tex>\delta>0</tex> из определения предела интегральных сумм, что для любого оснащенного дробления <tex>(\tau,\xi)</tex>, ранг которого меньше <tex>\delta</tex>,

<tex>I-{\epsilon\over3}<\sigma_\tau(f,\xi)<I+{\epsilon\over3}.</tex>

Переходя к супремуму и инфимуму по <tex>\xi</tex>, в силу [[#лемма о свойствах сумм Дарбу|свойства 1]] получаем:

<tex>I-{\epsilon\over3}\le s_\tau\le S_\tau\le I+{\epsilon\over3}</tex>,

откуда <tex>S_\tau-s_\tau\le{2\epsilon\over3}<\epsilon.</tex>

2. Достаточность. Пусть <tex>S_\tau-s_\tau\underset{\lambda\to0}{\to}0</tex>. Тогда все суммы <tex>S_\tau</tex> и <tex>s_\tau</tex> конечны.

<tex>\forall\tau\ s_\tau\le I_*\le I^*\le S_\tau</tex>,

поэтому <tex>0\le I^*-I_*\le S_\tau-s_\tau.</tex>

Так как правая часть последнего неравенства принимает сколь угодно малые значения, <tex>I_*=I^*</tex>. Обозначим общее значение <tex>I_*</tex> и <tex>I^*</tex> через <tex>I</tex> и докажем, что <tex>I=\underset{\lambda\to0}{\lim}\sigma</tex>. Из неравенств

<tex>s_\tau\le I\le S_\tau,\ s_\tau\le\sigma_\tau\le S_\tau</tex>

следует, что

<tex>\vert\sigma_\tau-I\vert\le S_\tau-s_\tau.</tex>

По <tex>\epsilon>0</tex> можно подобрать такое <tex>\delta>0</tex>, что для любого дробления <tex>\tau</tex>, ранг которого меньше <tex>\delta</tex>, будет <tex>S_\tau-s_\tau<\epsilon</tex>, а тогда для любого оснащения <tex>\xi</tex> такого дробления <tex>\vert\sigma_\tau(f,\xi)-I\vert<\epsilon.</tex>
}}

{{Теорема
|id=критерий интегрируемости Римана
|about=Критерий интегрируемости Римана
|statement=Пусть <tex>f:[a,b]\to\mathbb{R}.</tex> Тогда <tex>f\in R[a,b]</tex> в том и только том случае, когда

<tex>\forall\epsilon>0\ \exists\tau:\ S_\tau(f)-s_\tau(f)<\epsilon.</tex>
}}

=== Интегрируемость на меньшем параллелепипеде ===
{{Теорема
|id=интегрируемость функции и ее сужения
|about=Интегрируемость функции и ее сужения
|statement=1. Если <tex>f\in R[a,b],\ [\alpha,\beta]\subset[a,b]</tex>, то <tex>f\in R[\alpha,\beta].</tex>

2. Если <tex>a<c<b,\ f:[a,b]\to\mathbb{R},\ f</tex> интегрируема на <tex>[a,c]</tex> и на <tex>[c,b]</tex>, то <tex>f\in R[a,b].</tex>
|proof=1. Проверим выполнение условия интегрируемости <tex>f</tex> на отрезке <tex>[\alpha,\beta]</tex>. Возьмем <tex>\varepsilon>0</tex> и подберем <tex>\delta>0</tex> из [[#критерий интегрируемости функции|критерия интегрируемости]] <tex>f</tex> на <tex>[a,b]</tex>: если ранг дробления <tex>\tau</tex> отрезка <tex>[a,b]</tex> меньше <tex>\delta</tex>, то <tex>S_\tau-s_\tau<\varepsilon</tex>. Покажем, что это <tex>\delta</tex> подходит и для критерия интегрируемости <tex>f</tex> на <tex>[\alpha,\beta]</tex>. Пусть <tex>\tau_0</tex> - дробление <tex>[\alpha,\beta],\ \lambda_{\tau_0}<\delta</tex>. Возьмем какие-нибудь дробления отрезков <tex>[a,\alpha]</tex> и <tex>[\beta,b]</tex> (если эти отрезки невырожденные) ранга, меньшего <tex>\delta</tex>, и объединим их с <tex>\tau_0</tex>. Получим дробление <tex>\tau=\{x_k\}^n_{k=0}</tex> отрезка <tex>[a,b]</tex>:

<tex>a=x_0<...<x_\mu=\alpha<x_{\mu+1}<...<x_\nu=\beta<x_{\nu+1}<...<x_n=b,</tex>

причем <tex>\lambda_\tau<\delta</tex>. Тогда

<tex>S_{\tau_0}-s_{\tau_0}=\underset{k=\mu}{\overset{\nu-1}{\sum}}\omega_k(f)\Delta x_k\le\underset{k=0}{\overset{n-1}{\sum}}\omega_k(f)\Delta x_k\le\varepsilon.</tex>

2. Проверим выполнение условия интегрируемости <tex>f</tex> на отрезке <tex>[a,b]</tex>. Не умаляя общности, можно считать, что <tex>f</tex> не постоянна, то есть что <tex>\omega=\omega(f)_{[a,b]}>0</tex>. Возьмем <tex>\varepsilon>0</tex>. По [[#критерий интегрируемости функции|критерию интегрируемости]] подберем такие <tex>\delta_1>0</tex> и <tex>\delta_2>0</tex>, что для любых дроблений <tex>\tau_1</tex> отрезка <tex>[a,c]</tex> и <tex>\tau_2</tex> отрезка <tex>[c,b]</tex>, удовлетворяющих условиям <tex>\lambda_{\tau_1}<\delta_1,\ \lambda_{\tau_2}<\delta_2</tex>, выполняются неравенства

<tex>S_{\tau_1}-s_{\tau_1}<{\varepsilon\over3},\ S_{\tau_2}-s_{\tau_2}<{\varepsilon\over3}.</tex>

Положим <tex>\delta=\min\{\delta_1,\delta_2,{\varepsilon\over3\omega}\}</tex>. Пусть <tex>\tau</tex> - дробление <tex>[a,b],\ \lambda_\tau<\delta</tex>. Точка <tex>c</tex> не обязана принадлежать <tex>\tau</tex>; пусть <tex>c\in[x_\nu,x_{\nu+1}).</tex> Обозначим

<tex>\tau'=\tau\cup\{c\},\ \tau_1=\tau'\cap[a,c],\ \tau_2=\tau'\cap[c,b].</tex>

Тогда по выбору <tex>\delta</tex>

<tex>S_\tau-s_\tau\le S_{\tau_1}-s_{\tau_1}+S_{\tau_2}-s_{\tau_2}+\omega_\nu(f)\delta<\varepsilon.</tex>
}}

=== Аддитивность интеграла ===
{{Теорема
|id=аддитивность интеграла
|about=Аддитивность интеграла по отрезку
|statement=Если <tex>a,b,c\in\mathbb{R},\ f\in R[\min\{a,b,c\},\max\{a,b,c\}]</tex>, то

<tex>\int_a^bf=\int_a^cf+\int_c^bf</tex>.
|proof=Пусть <tex>a<c<b,\ f\in R[a,b]</tex>. Тогда по [[#Интегрируемость на меньшем параллелепипеде|теореме об интегрируемости функции и ее сужения]] <tex>f\in R[a,c]</tex> и <tex>f\in R[c,b]</tex>. Пусть <tex>\{(\bar\tau^{(n)},\bar\xi^{(n)})\}, \{(\bar{\bar\tau}^{(n)},\bar{\bar\xi}^{(n)})\}</tex> - последовательности оснащенных дроблений отрезков <tex>[a,c]</tex> и <tex>[c,b]</tex> на <tex>n</tex> равных частей, <tex>\tau^{(n)}=\bar\tau^{(n)}\cup\bar{\bar\tau}^{(n)},\ \xi^{(n)}=\bar\xi^{(n)}\cup\bar{\bar\xi}^{(n)},\ \bar\sigma_n,\ \bar{\bar\sigma}_n</tex> и <tex>\sigma_n</tex> - соответствующие последовательности интегральных сумм. Тогда

<tex>\sigma_n=\bar\sigma_n+\bar{\bar\sigma}_n.</tex>

Остается перейти к пределу при <tex>n\to+\infty.</tex>

Если <tex>a<b<c</tex>, то по доказанному

<tex>\int_a^bf=\int_a^cf-\int_b^cf=\int_a^cf+\int_c^bf.</tex>

Если <tex>a=b</tex>, то

<tex>\int_a^bf=0=\int_a^cf+\int_c^bf.</tex>

Остальные случаи разбираются аналогично.
}}

=== Предел римановых сумм ===

=== Линейность интеграла ===
{{Теорема
|id=линейность интеграла
|statement=Если <tex>f,g\in R[a,b],\ \alpha,\beta\in\mathbb{R}</tex>, то

<tex>\int_a^b(\alpha f+\beta g)=\alpha\int_a^bf+\beta\int_a^bg.</tex>
|proof=Интегрируемость <tex>\alpha f+\beta g</tex> следует из [[#Интегрируемость модуля интегрируемой функции|теоремы об арифметических действиях над интегрируемыми функциями]]. Остается перейти к пределу в равенстве

<tex>\sigma_\tau(\alpha f+\beta g)=\alpha\sigma_\tau(f)+\beta\sigma_\tau(g).</tex>
}}

=== Монотонность интеграла ===
''//и другие свойства, нужные при доказательстве теорем''
{{Теорема
|about=Монотонность интеграла (свойство 4)
|id=i4
|statement=Если <tex>a<b,\ f,g\in R[a,b],\ f\le g</tex>, то <tex>\int_a^bf\le\int_a^bg</tex>.
|proof=Для доказательства нужно перейти к пределу в неравенстве <tex>\sigma_\tau(f)\le\sigma_\tau(g)</tex>.
}}
{{Теорема
|about=Следствие 1
|id=i4s1
|statement=Пусть <tex>a,b,\ f\in R[a,b].</tex> Если <tex>M\in\mathbb{R},\ f\le M</tex>, то

<tex>\int_a^bf\le M(b-a),</tex>

а если <tex>m\in\mathbb{R},\ f\ge m</tex>, то

<tex>\int_a^bf\ge m(b-a)</tex>.

В частности, если <tex>f\in R[a,b],\ f\ge0</tex>, то

<tex>\int_a^b f\ge0</tex>.
}}

{{Теорема

|about=Свойство 5
|id=i5
|statement=Пусть <tex>a<b,\ f\in R[a,b],\ f\ge0,\ \exists x_0\in[a,b]:f(x_0)>0,\ f</tex> непрерывна в <tex>x_0</tex>. Тогда <tex>\int_a^bf>0.</tex>
|proof=Возьмем <tex>\varepsilon={f(x_0\over2}>0</tex> и по [[Участник:Katyatitkova/Матан#Непрерывное отображение|определению непрерывности]] <tex>f</tex> в точке <tex>x_0</tex> подберем <tex>\delta>0:\ \forall x\in[x_0-\delta,x_0+\delta]\cap[a,b]\ f(x)>f(x_0)-\varepsilon={f(x_0)\over2}</tex>.

Обозначим <tex>[\alpha,\beta]=[x_0-\delta,x_0+\delta]\cap[a,b]</tex>. По [[#i4s1|следствию 1 из свойства монотонности]]

<tex>\int_a^bf=\int_a^\alpha f+\int_\alpha^\beta f+\int_\beta^bf\ge\int_\alpha^\beta f\ge(\beta-\alpha){f(x_0)\over2}>0.</tex>

'''Замечание 1.''' Без условия непрерывности <tex>f</tex> в точке <tex>x_0</tex> утверждение неверно. Контрпримером служит функция, равная 0 всюду, кроме одной точки, в которой она положительна.

'''Замечание 2.''' Аналогичное утверждение справедливо и для двух функций:

''Пусть <tex>a<b,\ f,g\in R[a,b],\ f\le g,\ \exists x_0\in[a,b]:f(x_0)<g(x_0),\ f,g</tex>непрерывны в точке <tex>x_0</tex>. Тогда <tex>\int_a^bf<\int_a^bg</tex>.''

Для доказательства достаточно применить свойство к функции <tex>g-f.</tex>

'''Замечание 3.''' ''Пусть <tex>a<b,\ f\in R[a,b],\ f>0.</tex> Тогда <tex>\int_a^bf>0.</tex> Аналогичное утверждение верно и для двух функций.''

Действительно, из [[#Ослабленный критерий Лебега. Следствие|критерия Лебега]] легко вытекает, что на <tex>[a,b]</tex> есть точки непрерывности <tex>f</tex>.
}}

{{Теорема
|about=Свойство 6
|id=i6
|statement=Пусть <tex>a<b,\ f\in R[a,b]</tex>. Тогда
<tex>\left\vert\int_a^bf\right\vert\le\int_a^b\vert f\vert</tex>.
|proof=Интегрируя неравенство <tex>-\vert f\vert\le f\le\vert f\vert</tex>, получаем:

<tex>-\int_a^b\vert f\vert\le\int_a^bf\le\int_a^b\vert f\vert</tex>,

что равносильно доказываемому.

'''Замечание 4.''' Если отказаться от требования <tex>a<b</tex>, свойство надо изменить так: ''если <tex>f\in R[a,b]</tex>, то <tex>\left\vert\int_a^bf\right\vert\le\left\vert\int_a^b\vert f\vert\right\vert.</tex>''
}}

=== Интегрируемость модуля интегрируемой функции ===

=== Интегрируемость произведения ===

=== Интегрируемость частного ===

=== Ослабленный критерий Лебега. Следствие ===

=== Теорема о среднем. Следствия ===
{{Теорема
|id=t1
|about=Теорема о среднем
|statement=Пусть <tex>f,g\in R[a,b],\ g\ge0</tex> (или <tex>g\le0</tex>), <tex>m,M\in\mathbb{R},\ m\le f\le M</tex>. Тогда <tex>\exists\mu\in[m,M]: \int_a^bfg=\mu\int_a^bg</tex>.
|proof=Для определенности будем полагать, что <tex>a<b,g\ge0</tex>. Тогда <tex>\int_a^bg\ge0</tex> и <tex>mg\le fg\le Mg</tex>.

Проинтегрируем это неравенство и вынесем постоянные множители за знаки интегралов:

<tex>m\int_a^bg\le\int_a^bfg\le M\int_a^bg</tex>.

Отсюда если <tex>\int_a^bg=0</tex>, то и <tex>\int_a^bfg=0</tex>, а тогда подходит любое <tex>\mu</tex>. Если же <tex>\int_a^bg>0</tex>, то следует положить:

<tex>\mu={\int_a^bfg\over\int_a^bg}</tex>.

Условия на <tex>\mu</tex>, очевидно, выполнены.
}}
{{Теорема
|about=Следствие 1
|statement=Пусть <tex>f\in C[a,b],\ g\in R[a,b],\ g\ge0</tex> (или <tex>g\le0</tex>). Тогда <tex>\exists c\int[a,b]:\ \int_a^bfg=f(c)\int_a^bg</tex>.
|proof=По [[Участник:Katyatitkova/Матан#Теорема Вейерштрасса о непрерывном образе компакта. Следствия|теореме Вейерштрасса о непрерывных функциях]] существуют <tex>m=\underset{x\in[a,b]}{\min}f(x)</tex> и <tex>M=\underset{x\in[a,b]}{\max}f(x)</tex>.

Подберем <tex>\mu\in[m,M]</tex> из теоремы о среднем. По [[Участник:Katyatitkova/Матан#Лемма о связности отрезка. Теорема Больцано—Коши о промежуточном значении|теореме Больцано-Коши о промежуточном значении]] найдется <tex>c\in[a,b]:\mu=f(c)</tex>.
}}
{{Теорема
|about=Следствие 2
|statement=Пусть <tex>f\in R[a,b],\ m,M\in\mathbb{R},\ m\le f\le M</tex>. Тогда <tex>\exists\mu\in[m,M]:\int_a^bf=\mu(b-a)</tex>.
|proof=Для доказательства надо положить <tex>g\equiv1</tex> в теореме о среднем.
}}
{{Теорема
|about=Следствие 3
|statement=Пусть <tex>f\in C[a,b]</tex>. Тогда <tex>\exists c\in[a,b]:\int_a^bf=f(c)(b-a)</tex>.
|proof=Для доказательства надо положить <tex>g\equiv1</tex> в следствии 1.
}}

=== Теорема Барроу ===
{{Теорема
|id=теорема об интеграле с переменным верхним пределом
|about=Об интеграле с переменным верхним пределом
|statement=Пусть <tex>E\subset\mathbb{R}</tex> - невырожденный промежуток, <tex>f:E\to\mathbb{R},\ f</tex> интегрируема на каждом отрезке, содержащемся в <tex>E,\ a\in E,\ \Phi(x)=\int_a^xf(x\in E)</tex>. Тогда справедливы следующие утверждения.

1. <tex>\Phi\in C(E).</tex>

2. Если, кроме того, <tex>f</tex> непрерывна в точке <tex>x_0\in E</tex>, то <tex>\Phi</tex> дифференцируема в точке <tex>x_0</tex> и <tex>\Phi'(x_0)=f(x_0)</tex>.

Утверждение 2 часто называют '''теоремой Барроу'''.
|proof=1. Возьмем <tex>x_0\in E</tex> и докажем непрерывность <tex>\Phi</tex> в точке <tex>x_0</tex>. Выберем такое <tex>\delta>0</tex>, что <tex>[x_0-\delta, x_0+\delta]\cap E</tex> есть невырожденный отрезок <tex>[A,B]</tex>. Функция <tex>f</tex> ограничена на <tex>[A,B]</tex> некоторым числом <tex>M</tex>. Пусть <tex>\Delta x</tex> таково, что <tex>x_0+\Delta x\in[A,B]</tex>. Тогда по [[#Аддитивность интеграла|аддитивности интеграла]]

<tex>\Phi(x_0+\Delta x)-\Phi(x_0)=\int_{x_0}^{x_0+\Delta x}f</tex>, по по [[#i4|свойству 4]] и по [[#i6|свойству 6]]

<tex>\vert\Phi(x_0+\Delta x)-\Phi(x_0)\vert\le\left\vert\int_{x_0}^{x_0+\Delta x}\vert f\vert\right\vert\le M\Delta x\underset{\Delta x\to0}{\to}0</tex>.

Это и доказывает непрерывность <tex>\Phi</tex> в точке <tex>x_0</tex>.

2. Проверим, что <tex>{\Phi(x_0+\Delta x)-\Phi(x_0)\over\Delta x}\underset{\Delta x\to0}{\to}f(x_0)</tex>.

Возьмем <tex>\varepsilon>0</tex> и по [[Участник:Katyatitkova/Матан#Непрерывное отображение|определению непрерывности]] подберем <tex>\delta>0:\ \forall t\in E:\ \vert t-x_0\vert<\delta\ \ \vert f(t)-f(x_0)\vert<\varepsilon</tex>. Тогда <tex>\forall\Delta x:x_0+\Delta x\in E,\ 0<\vert\Delta x\vert<\delta</tex>, по [[#i6|свойству 6]] и по [[#i5|свойству 5]] и замечаниям к ним

<tex>\left\vert{\Phi(x_0+\Delta x)-\Phi(x_0)\over\Delta x}-f(x_0)\right\vert=\left\vert{1\over\Delta x}\int_{x_0}^{x_0+\Delta x}(f(t)-f(x_0))dt\right\vert<{1\over\vert\Delta x\vert}\varepsilon\vert\Delta x\vert=\varepsilon</tex>, откуда и следует проверяемое утверждение.
}}

=== Формула Ньютона-Лейбница для кусочно-непрерывных функций ===
{{Теорема
|about=Формула Ньютона-Лейбница
|statement=Пусть <tex>f\in R[a,b],\ F</tex> - первообразная <tex>f</tex> на <tex>[a,b]</tex>. Тогда <tex>\int_a^bf=F(b)-F(a)</tex>.
|proof=<tex>\forall n\in\mathbb{N}</tex> положим <tex>x_k={k(b-a)\over n}</tex>. Тогда

<tex>F(b)-F(a)=\underset{k=0}{\overset{n-1}{\sum}}(F(x_{k+1})-F(x_k)).</tex>

По [[Участник:Katyatitkova/Матан#Теоремы Лагранжа и Коши. Следствия об оценке приращения и о пределе производной|теореме Лагранжа]] <tex>\forall k\in[0:n-1]\ \exists\xi_k^{(n)}\in(x_k,x_{k+1}): F(x_{k+1})-F(x_k)=F'(\xi_k^{(n)})\Delta x_k=f(\xi_k^{(n)})\Delta x_k</tex>.

В силу интегрируемости <tex>f</tex>

<tex>\int_a^b=\underset{n\to\infty}{\lim}\underset{k=0}{\overset{n-1}{\sum}}f(\xi_k^{(n)})\Delta x_k=\underset{n\to\infty}{\lim}(F(b)-F(a))=F(b)-F(a).</tex>
}}

=== Замена переменных и интегрирование по частям в определенном интеграле ===
==== Интегрирование по частям ====
{{Теорема
|statement=
Пусть <tex>f,g</tex> дифференцируемы на <tex>[a,b],\ f',g'\in R[a,b]</tex>. Тогда

<tex>\int_a^bfg'=fg|_a^b-\int_a^bf'g.</tex>
|proof=
Будучи дифференцируемыми, функции <tex>f,\ g</tex> непрерывны и, следовательно, интегрируемы. По теореме об арифметическими действиями над интегрируемыми функциями <tex>f'g,fg'\in R[a,b]</tex>, а тогда и <tex>(fg)'=f'g+fg'\in R[a,b]</tex>. По [[#Формула Ньютона-Лейбница для кусочно-непрерывных функций|формуле Ньютона-Лейбница]]

<tex>\int_a^bfg'+\int_a^bf'g=\int_a^b(fg)'=fg|_a^b.</tex>

Остается перенести второе слагаемое из левой части в правую.
}}
==== Замена переменной ====
{{Теорема
|statement=
Пусть <tex>\varphi:[\alpha,\beta]\to[A,B],\varphi</tex> дифференцируема на <tex>[\alpha,\beta],\varphi'\in R[\alpha,\beta], f\in C[A,B]</tex>. Тогда

<tex>\int_\alpha^\beta(f\circ\varphi)\varphi'=\int_{\varphi(\alpha)}^{\varphi(\beta)}f.</tex>
|proof=
Поскольку <tex>f\circ\varphi\in C[\alpha,\beta]\subset R[\alpha,\beta]</tex>, по теореме об арифметических действиях над интегрируемыми функциями <tex>(f\circ\varphi)\varphi'\in R[\alpha,\beta]</tex>. Также и <tex>f\in R[\varphi(\alpha),\varphi(\beta)]</tex>. Пусть <tex>F</tex> - первообразная <tex>f</tex> на <tex>[A,B]</tex>. Тогда по правилу дифференцирования композиции <tex>F\circ\varphi</tex> - первообразная <tex>(f\circ\varphi)\varphi'</tex> на <tex>[A,B]</tex>. Применяя к обоим интегралам [[#Формула Ньютона-Лейбница для кусочно-непрерывных функций|формулу Ньютона-Лейбница]], получаем:

<tex>\int_\alpha^\beta(f\circ\varphi)\varphi'=F\circ\varphi|_\alpha^\beta=F|_{\varphi(\alpha)}^{\varphi(\beta)}=\int_{\varphi(\alpha)}^{\varphi(\beta)}f.</tex>
}}

=== Интегральность числа пи ===

=== Формула Валлиса ===
{{Лемма
|id=l
|statement=Если <tex>m\in\mathbb{Z}_+</tex>, то

<tex>\int_0^{\pi/2}\sin^mxdx={(m-1)!!\over m!!}\cdot\begin{cases} {\pi\over2}, & \text{if }m\text{ is even,} \\ 1, & \text{if }m\text{ is odd.} \end{cases}</tex>
|proof=
Обозначим <tex>J_m=\int_0^{\pi/2}\sin^mtdt</tex>. Легко проверить, что <tex>J_0={\pi\over2},\ J_1=1</tex>. При <tex>m-1\in\mathbb{N}</tex> проинтегрируем по частям:

<tex>J_m=\int_0^{\pi/2}\sin^{m-1}xd(-\cos x)=-\sin^{m-1}x\cos x|_0^{\pi/2}+(m-1)\int_0{\pi/2}\sin^{m-2}x\cos^2xdx=(m-1)(J_{m-2}-J_m)</tex>

(в последнем равенстве мы учли, что двойная подстановка обнулилась, и применили формулу <tex>\cos^2x=1-\sin^2x</tex>). Выражая <tex>J_m</tex>, получаем реккурентное соотношение

<tex>J_m={m-1\over m}J_{m-2}.</tex>

Остается применить его несколько раз и выразить <tex>J_m</tex> через <tex>J_0</tex> или <tex>J_1</tex> в зависимости от четности <tex>m</tex>.
}}

{{Теорема
|about=Формула Валлиса
|statement=
<tex>\pi=\underset{n\to\infty}{\lim}\frac{1}{n}\left({(2n)!!\over(2n-1)!!}\right)^2.</tex>
|proof=
<tex>\forall x\in(0,\frac{\pi}{2})</tex> выполняется неравенство <tex>0<\sin x<1</tex>, поэтому <tex>\forall n\in\mathbb{N}</tex>

<tex>\sin^{2n+1}x<\sin^{2n}x<\sin^{2n-1}x,</tex>

а тогда и

<tex>J_{2n+1}<J_{2n}<J_{2n-1}.</tex>

Подставляя найденные в [[#l|лемме]] значения <tex>J_m</tex>, получаем двойное неравенство

<tex>{(2n)!!\over(2n+1)!!}<{(2n-1)!!\over(2n)!!}\cdot{\pi\over2}<{(2n-2)!!\over(2n-1)!!},</tex>

что равносильно

<tex>\left({(2n)!!\over(2n-1)!!}\right)^2{1\over2n+1}<{\pi\over2}<\left({(2n)!!\over(2n-1)!!}\right)^2{1\over2n}.</tex>

Обозначим <tex>x_n=\left({(2n)!!\over(2n-1)!!}\right)^2{1\over n}</tex>. Двойное неравенство можно преобразовать к виду

<tex>\pi<x_n<{2n+1\over2n}\pi,</tex>

откуда <tex>x_n\to\pi</tex>.
}}

=== Формула Тейлора с интегральным остатком ===
{{Теорема
|about=Формула Тейлора с остатком в интегральной форме
|statement=
Пусть <tex>n\in\mathbb{Z}_+,\ f\in C^{n+1}\langle a,b\rangle,\ x_0,x\in\langle a,b\rangle</tex>. Тогда

<tex>f(x)= \underset{k=0}{\overset{n}{\sum}} {f^{(k)}(x_0)\over k!}(x-x_0)^k+{1\over n!}\int_{x_0}^x f^{(n+1)}(t)(x-t)^n dt</tex>.
|proof=
По индукции. База индукции (случай <tex>n=0</tex>) представляет собой [[#Формула Ньютона-Лейбница для кусочно-непрерывных функций|формулу Ньютона-Лейбница]]:

<tex>f(x)=f(x_0)+\int_{x_0}^x f'(t) dt</tex>.

Пусть утверждение верно для некоторого <tex>n-1\in\mathbb{Z}_+</tex>. Докажем его для номера <tex>n</tex>. Для этого проинтегрируем его по частям в остаточном члене:

<tex>\int_{x_0}^x f^{(n)} (t) {(x-t)^{n-1}\over(n-1)!}dt = \int_{x_0}^xf^{(n)} (t) d\left(-{(x-t)^n\over n!}\right) = -\frac{1}{n!}\left[f^{(n)}(t)(x-t)^n\right]_{t=x_0}^x+\frac{1}{n!}\int_{x_0}^xf^{(n+1)}(t)(x-t)^ndt = {f^{(n)}(x_0)\over n!}(x-x_0)^n+{1\over n!}\int_{x_0}^x f^{(n+1)}(t)(x-t)^n dt</tex>.

Первое слагаемое в правой части есть слагаемое с номером <tex>n</tex> в многочлене Тейлора, а второе - новый остаточный член:

<tex>f(x)=\underset{k=0}{\overset{n-1}{\sum}}{f^{(k)}(x_0)\over k!}(x-x_0)^k+{f^{(n)}(x_0)\over n!}(x-x_0)^n+{1\over n!}\int_{x_0}^x f^{(n+1)}(t)(x-t)^ndt =\underset{k=0}{\overset{n}{\sum}} {f^{(k)}(x_0)\over k!}(x-x_0)^k+{1\over n!}\int_{x_0}^x f^{(n+1)}(t)(x-t)^ndt.</tex>
}}

=== Неравенство Чебышева для функций и конечных последовательностей ===

=== Неравенство Гельдера и Минковского ===
==== Неравенство Гельдера для интегралов ====
{{Теорема
|about=Неравенство Гёльдера для интегралов
|statement=
Пусть <tex>f,g\in C[a,b],\ p,q</tex> - сопряженные показатели. Тогда

<tex>\left\vert\int_a^b fg\right\vert\le\left(\int_a^b|f|^p\right)^{1/p}
\left(\int_a^b|g|^q\right)^{1/q}.</tex>
|proof=
Положим <tex>x_k=a+{k(b-a)\over n}\ (k\in[0:n]),\ a_k=f(x_k)(\Delta x_k)^{1/p},\ b_k=g(x_k)(\Delta x_k)^{1/q}\ (k\in[0:n-1])</tex>. Тогда <tex>a_kb_k=f(x_k)g(x_k)\Delta x_k</tex> в силу равенства <tex>{1\over p}+{1\over q}=1</tex>. Воспользуемся [[#Неравенство Гельдера|неравенством Гёльдера для сумм]]:

<tex>\left|\underset{k=0}{\overset{n-1}{\sum}}a_kb_k\right|\le \left(\underset{k=0}{\overset{n-1}{\sum}}|a_k|^p\right)^{1/p} \left(\underset{k=0}{\overset{n-1}{\sum}}|b_k|^q\right)^{1/q},</tex>

которое принимает вид

<tex>\left|\underset{k=0}{\overset{n-1}{\sum}}f(x_k)g(x_k)\Delta x_k\right|\le \left(\underset{k=0}{\overset{n-1}{\sum}}|f(x_k)|^p\Delta x_k\right)^{1/p} \left(\underset{k=0}{\overset{n-1}{\sum}}|g(x_k)|^q\Delta x_k\right)^{1/q}.</tex>

В последнем неравенстве участвуют [[#Риманова сумма|суммы Римана]] для непрерывных функций <tex>fg,\ |f|^p,\ |g|^q</tex>. При <tex>n\to\infty</tex> суммы стремятся к интегралам от этих функций. Остается сделать предельный переход в неравенстве и воспользоваться непрерывностью модуля и степенных функций.
}}
==== Неравенство Минковского для интегралов ====
{{Теорема
|about=Неравенство Минковского для интегралов
|statement=
Пусть <tex>f,g\in C[a,b],\ p\ge1</tex>. Тогда
<tex>\left(\int_a^b|f+g|^p\right)^{1/p}\le \left(\int_a^b|f|^p\right)^{1/p}+\left(\int_a^b|g|^p\right)^{1/p}.</tex>
|proof=
Для доказательства неравенства Минковского можно сделать предельный переход в [[#Неравенство Минковского|неравенстве для сумм]].
}}

=== Неравенство Йенсена для интегралов. Неравенство Коши ===
==== Неравенство Йенсена для интегралов ====
{{Теорема
|statement=Пусть <tex>f</tex> выпукла и непрерывна на <tex>\langle A,B\rangle,\ \varphi\in C([a,b]\to\langle A,B\rangle),\ \lambda\in C([a,b]\to[0,+\infty)),\ \int_a^b\lambda=1</tex>. Тогда

<tex>f\left(\int_a^b\lambda\varphi\right)\le \int _a^b\lambda \cdot (f\circ \varphi )</tex>.
|proof=
Обозначим <tex>c=\int_a^b\lambda\varphi,\ E=\{x\in[a,b]:\lambda(x)>0\},\ m=\underset{E}{\inf}\varphi,\ M=\underset{E}{\sup}\varphi</tex>

(<tex>m</tex> и <tex>M</tex> конечны по [[Участник:Katyatitkova/Матан#Теорема Вейерштрасса о непрерывном образе компакта. Следствия|теореме Вейерштрасса]]). Если <tex>m=M</tex>, то есть <tex>\varphi</tex> постоянна на <tex>E</tex>, то <tex>c=m</tex> и обе части неравенства Йенсена равны <tex>f(m)</tex>.

Пусть <tex>m<M</tex>. Тогда <tex>c\in(m,M)</tex> и, следовательно, <tex>c\in(A,B)</tex>. Функция <tex>f</tex> имеет в точке <tex>c</tex> опорную прямую; пусть она задается уравнением <tex>y=\alpha x+\beta</tex>. По [[#Опорная прямая|определению опорной прямой]] <tex>f(c)=\alpha c+\beta</tex> и <tex>f(t)\ge\alpha t+\beta\ \forall t\in\langle A,B\rangle</tex>. Поэтому

<tex>f(c)=\alpha c+\beta=\alpha\int_a^b\lambda\varphi+\beta\int_a^b\lambda=\int_a^b\lambda\cdot(\alpha\varphi+\beta)\le\int_a^b\lambda\cdot(f\circ\varphi).</tex>
}}
==== Неравенство Коши-Буняковского для интегралов ====
{{Теорема
|statement=
Пусть <tex>f,g\in C[a,b]</tex>. Тогда

<tex>\left|\int_a^bfg\right|\le\sqrt{\int_a^bf^2}\cdot\sqrt{\int_a^bg^2}.</tex>
|proof=
Для доказательства надо положить в [[#Неравенство Гельдера и Минковского|неравенстве Гёльдера]] <tex>p=q=2</tex>.
}}

=== Теорема о формуле трапеций ===

=== Формула Эйлера - Маклорена ===

=== Формула Стирлинга ===

=== Свойства несобственного интеграла: аддитивность, линейность, монотонность, интегрирование по частям ===

=== Признак сравнения сходимости несобственного интеграла ===

== Определения и факты ==

=== Список ===

* Ряды Тейлора основных элементарных функций
* Локальный экстремум
* Интеграл функции по параллелепипеду
* Почти первообразная

=== Ряды Тейлора основных элементарных функций ===

=== Локальный экстремум ===
* <math>x_0</math> называется точкой локального максимума функции <math>f,</math> если существует проколотая окрестность <math>\dot{U}(x_0)</math> такая, что
*: <math>\forall x \in \dot{U}(x_0) \quad f(x) \le f(x_0);</math>
* <math>x_0</math> называется точкой локального минимума функции <math>f,</math> если существует проколотая окрестность <math>\dot{U}(x_0)</math> такая, что
*: <math>\forall x \in \dot{U}(x_0) \quad f(x) \ge f(x_0).</math>
Если неравенства выше строгие, то <math>x_0</math> называется точкой строгого локального максимума или минимума соответственно.

=== Точка возрастания функции ===
{{Определение
|definition=Пусть <tex>f:\langle a,b\rangle\to\mathbb{R},\ x_0\in(a,b)</tex>. Если <tex>\exists \delta>0:\ \forall x\in(x_0-\delta,x_0)\ f(x)\le f(x_0)</tex> и <tex>\forall x\in(x_0,x_0+\delta)\ f(x)\ge f(x_0)</tex>, то <tex>x_0</tex> называется '''точкой возрастания''' функции <tex>f</tex>.
}}

=== Стационарная точка ===
{{Определение
|definition=Пусть <tex>f:\langle a,b\rangle\to\mathbb{R},\ x_0\in(a,b)</tex>. Если <tex>f'(x_0)=0</tex>, то <tex>x_0</tex> называется '''стационарной точкой''' функции <tex>f</tex>. Если <tex>f'(x_0)=0</tex> или <tex>f</tex> не дифференцируема в точке <tex>x_0</tex>, то <tex>x_0</tex> называется '''критической точкой''' функции <tex>f</tex>.
}}

=== Выпуклая функция ===
{{Определение
|id=определение выпуклости
|definition=Функция <tex>f: \langle a,b\rangle \to \mathbb{R}</tex> называется:

'''выпуклой вниз''' на <tex>\langle a,b\rangle</tex>, если <tex>\forall x_1,x_2\in\langle a,b\rangle, \ t\in(0,1)</tex> выполняется неравенство

<tex>f(tx_1+(1-t)x_2)\le tf(x_1)+(1-t)f(x_2)</tex>;

'''строго выпуклой вниз''' на <tex>\langle a,b\rangle</tex>, если <tex>\forall x_1,x_2\in\langle a,b\rangle \ (x_1\ne x_2), \ t\in(0,1)</tex> выполняется неравенство

<tex>f(tx_1+(1-t)x_2) < tf(x_1)+(1-t)f(x_2)</tex>.

Если выполняются противоположные неравенства, то функция <tex>f</tex> называется соответственно '''выпуклой вверх''' или '''строго выпуклой вверх''' на <tex>\langle a,b\rangle</tex>.

Часто функции, которые только что были названы выпуклыми вниз, называют просто '''выпуклыми''', а те, что были названы выпуклыми вверх, - '''вогнутыми'''.
}}
=== Выпуклое множество в R^m ===
{{Определение
|definition=Множество (на прямой, на плоскости, в трехмерном пространстве) называется '''выпуклым''', если вместе в с любыми своими двумя точками оно содержит весь отрезок, их соединяющий.
}}

=== Надграфик и подграфик ===
==== Надграфик ====
{{Определение
|definition=
Пусть <tex>f:\langle a,b\rangle\to\mathbb{R}</tex>. Множество <tex>\{(x,y)\in\mathbb{R}^2:x\in\langle a,b\rangle, y\ge f(x)\}</tex> называется '''надграфиком''' функции <tex>f</tex>.
}}
==== Подграфик ====
{{Определение
|definition=
Пусть <tex>f:[a,b]\to\mathbb{R},f\ge0</tex>. Множество

<tex>Q_f=\{(x,y)\in\mathbb{R}^2:x\in[a,b],0\le y\le f(x)\}</tex>

называется '''подграфиком''' функции <tex>f</tex>.
}}

=== Опорная прямая ===
{{Определение
|id=определение опорной прямой
|definition=Пусть <tex>f:\langle a,b\rangle\to\mathbb{R},\ x_0\in\langle a,b\rangle</tex>. Прямая, задаваемая уравнением <tex>y = \ell(x)</tex>, называется '''опорной''' для функции <tex>f</tex> в точке <tex>x_0</tex>, если

<tex>\forall x\in \langle a,b\rangle \ f(x_0)=\ell(x_0),\ f(x)\ge\ell(x)</tex>.

Если же

<tex>\forall x\in \langle a,b\rangle\backslash\{x_0\} \ f(x_0)=\ell(x_0),\ f(x)>\ell(x)</tex>,

то прямая называется '''строго опорной''' для функции <tex>f</tex> в точке <tex>x_0</tex>.
}}

=== Первообразная ===
{{Определение
|id=определение первообразной
|definition=Пусть <tex>f, F:\langle a,b\rangle\to\mathbb{R}</tex>. Функция <tex>F</tex> называется '''первообразной''' функции <tex>f</tex> на <tex>\langle a,b\rangle</tex>, если

<tex>\forall x\in\langle a,b\rangle\ F'(x)=f(x)</tex>.
}}

=== Таблица первообразных ===
1. <tex>\int0dx=C</tex>

2. <tex>\int x^\alpha dx={x^{\alpha+1}\over\alpha+1}+C,\ \alpha\ne-1</tex>

3. <tex>\int {dx\over x}=ln\vert x\vert+C</tex>

4. <tex>\int a^x dx={a^x\over \ln a}+C</tex>

5. <tex>\int \sin x dx=-\cos x+C</tex>

6. <tex>\int \cos x dx=\sin x+C</tex>

7. <tex>\int {dx\over \cos ^2 x}=\tan x+C</tex>

8. <tex>\int {dx\over \sin ^2x}=-\cot x+C</tex>

9. <tex>\int{dx\over\sqrt{1-x^2}}=\arcsin x+C=-\arccos x+C</tex>

10. <tex>\int{dx\over 1+x^2}=\arctan x+C</tex>

11. <tex>\int{dx\over\sqrt{x^2\pm1}}=\ln\vert x+\sqrt{x^2\pm1}\vert+C</tex>

12. <tex>\int{dx\over1-x^2}={1\over2}\ln\left\vert{1+x\over1-x}\right\vert+C</tex>

=== Дробление отрезка ===
{{Определение
|id=определение дробления
|definition=Пусть <tex>[a,b]</tex> - невырожденный отрезок. Набор точек

<tex>\tau = \{x_k\}^n_{k=0}:\ a=x_0<x_1<...<x_n=b</tex>

называется '''дроблением''' отрезка <tex>[a,b]</tex>. Отрезки <tex>[x_k,x_{k+1}\ (k\in[0:n-1])</tex> называют '''отрезками дробления''', через <tex>\Delta x_k</tex> обозначается длина <tex>k</tex>-го отрезка дробления. Величина

<tex>\lambda = \lambda_\tau=\underset{0\le k\le n-1}{max}\Delta x_k</tex>

называется '''рангом''' или '''мелкостью''' дробления <tex>\tau</tex>. Набор точек <tex>\xi=\{\xi_k\}^{n-1}_{k=0}</tex>, таких что <tex>\xi_k\in[x_k,x_{k+1}]\ \forall k\in[0:n-1]</tex>, называется '''оснащением''' дробления. Дробление вместе с его оснащением, то есть пара <tex>(\tau, \xi)</tex>, называется '''оснащенным дроблением'''.
}}

=== Дробление параллелепипеда ===
{{Определение
|definition=
Пусть параллелепипед задан двумя точками <tex>a,b\in\mathbb{R}^m</tex>. '''Дроблением параллелепипеда''' называется множество дроблений <tex>\lambda_1,...,\lambda_m</tex>, где <tex>\lambda_i</tex> - дробление отрезка <tex>[a_i, b_i]</tex>.
}}

=== Что значит, что одно дробление мельче другого ===
//для отрезка
{{Определение
|definition=
Дробление <tex>a</tex> мельче дробления <tex>b</tex>, если набор точек дробления <tex>a</tex> содержится в наборе этих точек для <tex>b</tex>.
}}
//для параллелепипеда
{{Определение
|definition=
Дробление мельче, если для всех дроблений из <tex>\lambda</tex> верно, что дробление из одного мельче дробления из другого.
}}
//Копипаста http://vk.com/topic-29253653_26076730?post=1937

=== Сумма Дарбу ===
{{Определение
|id=определение сумм Дарбу
|definition=Пусть <tex>f: [a,b]\to\mathbb{R},\ \tau=\{x_k\}^n_{k=0}</tex> - дробление <tex>[a,b]</tex>,

<tex>M_k=\underset{x\in[x)k,x_{k+1}]}{\sup}f(x),\ m_k=\underset{x\in[x_k,x_{k+1}]}{\inf}f(x),\ k\in[0:n-1]</tex>.

Суммы

<tex>S=S_\tau(f)=\underset{k=0}{\overset{n-1}{\sum}}M_k\Delta x_k</tex> и <tex>s=s_\tau(f)=\underset{k=0}{\overset{n-1}{\sum}}m_k\Delta x_k</tex>

называются '''верхней и нижней интегральными суммами''' или '''суммами Дарбу''' функции <tex>f</tex>, отвечающими дроблению <tex>\tau</tex>.
}}

=== Верхний интеграл Дарбу ===
{{Определение
|id=определение интеграла Дарбу
|definition=Пусть <tex>f:[a,b]\to\mathbb{R}</tex>. Величины

<tex>I^*=\underset{\tau}{\inf}S_\tau</tex>, и <tex>I_*=\underset{\tau}{\sup}s_\tau</tex>

называются '''верхним и нижним интегралами Дарбу''' функции <tex>f</tex>.
}}

=== Интегрируемая по Риману функция ===
{{Определение
|id=определение интегрируемой по Риману функции
|definition=Пусть <tex>f:[a,b]\to\mathbb{R}</tex>. Если существует предел интегральных сумм <tex>\underset{\lambda\to0}{\lim}\sigma</tex>, равный числу <tex>I</tex>, то функция <tex>f</tex> называется '''интегрируемой по Риману''' на <tex>[a,b]</tex>, а число <tex>I</tex> - '''интегралом (определенным интегралом, интегралом Римана)''' от функции <tex>f</tex> по отрезку <tex>[a,b]</tex> и обозначается <tex>\int^b_af</tex>.
}}

=== Интеграл функции по параллелепипеду ===

=== Риманова сумма ===
{{Определение
|id=определение сумм Римана
|definition=Пусть <tex>f:[a,b]\to\mathbb{R}</tex>. Суммы

<tex>\sigma=\sigma_\tau(f,\xi)=\underset{k=0}{\overset{n-1}{\sum}}f(\xi_k)\Delta x_k</tex>

называются '''интегральными суммами''' или '''суммами Римана''' функции <tex>f</tex>, отвечающими оснащенному дроблению <tex>(\tau,\xi)</tex>.
}}

=== Колебание функции на множестве ===
{{Определение
|id=определение колебания функции на множестве
|definition=Пусть <tex>f:D\subset\mathbb{R}\to\mathbb{R}</tex>. Величина

<tex>\omega(f)_D=\underset{x,y\in D}{\sup}(f(x)-f(y))</tex>

называется '''колебанием''' функции <tex>f</tex> на множестве <tex>D</tex>.
}}

=== Множество объема 0 ===
{{Определение
|definition=
Множество <tex>A\subset\mathbb{R}^n</tex> имеет объём 0, если <tex>\forall\varepsilon>0\ \exists</tex> покрытие множества <tex>A</tex> брусами <tex>B_1,...,B_k:\underset{i=1}{\overset{k}{\sum}} V(B_i)<\varepsilon</tex>.
}}

=== Множество меры 0 ===
{{Определение
|definition=
Говорят, что множество <tex>E\subset\mathbb{R}</tex> имеет '''нулевую меру''', если <tex>\forall\varepsilon>0</tex> множество <tex>E</tex> можно заключить в не более чем счетное объединение интервалов, суммарная длина которых меньше <tex>\varepsilon</tex>.
}}

=== Интеграл с переменным верхним пределом ===
{{Определение
|definition=Пусть <tex>E\subset\mathbb{R}</tex> - невырожденный промежуток <tex>f:E\to\mathbb{R},\ f</tex> интегрируема на каждом отрезке, содержащемся в <tex>E,\ a\in E</tex>. Функция

<tex>\Phi(x)=\int_a^xf,\ x\in E</tex>

называется '''интегралом с переменным верхним пределом'''.
}}

=== Кусочно-непрерывная функция ===
{{Определение
|definition=Функция <tex>f:[a,b]\to\mathbb{R}</tex> называется '''кусочно-непрерывной''' на <tex>[a,b]</tex>, если множество ее точек разрыва пусто или конечно, и все имеющиеся разрывы - первого рода.
}}

=== Почти первообразная ===

=== Несобственный интеграл ===
{{Определение
|definition=
Пусть <tex>-\infty<a<b\le+\infty,\ f\in R_{loc}[a,b)</tex>. Символ <tex>\int_a^{\to b}f</tex> называется '''несобственным интегралом'''. Интегралы <tex>\int_a^Af</tex> при <tex>A\in[a,b)</tex> называются '''частными''' или '''частичными'''. Если <tex>\exists \underset{A\to b-}{\lim}\int_a^Af</tex> в <tex>\overline{\mathbb{R}}</tex>, равный <tex>I</tex>, то символу <tex>\int_a^{\to b}f</tex> приписывают значение <tex>I</tex>. В противном случае символу <tex>\int_a^{\to b}f</tex> не приписывают никакого значения. Если <tex>\mathbb{R}</tex>, то говорят, что несобственный интеграл '''сходится'''; в противном случае говорят, что он '''расходится'''.
}}

Декартово дерево

2012-04-07T12:29:31Z

109.205.255.119:

''Эта статья про Курево''

'''Декартово дерево''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: <tex>treap (tree+heap)</tex> и дерамида (дерево+пирамида), так же существует название курево (куча + дерево).

Более строго, это структура данных, которая хранит пары <tex> (X,Y) </tex> в виде бинарного дерева таким образом, что она является бинарным деревом поиска по <tex>x</tex> и бинарной пирамидой по <tex>y</tex>. Предполагая, что все <tex>X</tex> и все <tex>Y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(X_0,Y_0)</tex>, то у всех элементов в левом поддереве <tex>X < X_0</tex>, у всех элементов в правом поддереве <tex> X > X_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> Y < Y_0</tex>.

Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.

== Операция split ==
[[file:split.png|thumb|400px|Операция split]]

Операция <tex>\mathrm{split}</tex> (''разрезать'') позволяет сделать следующее: разрезать декартово дерево <tex>T</tex> по ключу
<tex>x</tex> и получить два других декартовых дерева: <tex>T_1</tex> и <tex>T_2</tex>, причем в <tex>T_1</tex>
находятся все ключи дерева <tex>T</tex>, не большие <tex>x</tex>, а в <tex>T_2</tex> {{---}} большие <tex>x</tex>.

<tex>\mathrm{split}(T, x) \to \{T_1, T_2\}</tex>.

Эта операция устроена следующим образом.

Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня.
Посмотрим, как будут устроены результирующие деревья <tex>T_1</tex> и <tex>T_2</tex>:
* <tex>T_1</tex>: левое поддерево <tex>T_1</tex> совпадёт с левым поддеревом <tex>T</tex>. Для нахождения правого поддерева <tex>T_1</tex>, нужно разрезать правое поддерево <tex>T</tex> на <tex>T^R_1</tex> и <tex>T^R_2</tex> по ключу <tex>x</tex> и взять <tex>T^R_1</tex>.
* <tex>T_2</tex> совпадёт с <tex>T^R_2</tex>.

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

Оценим время работы операции <tex>\mathrm{split}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{split}</tex> для
дерева хотя бы на один меньшей высоты и делается ещё <tex>\mathcal{O}(1)</tex> операция. Тогда итоговая трудоёмкость этой операции
равна <tex>\mathcal{O}(h)</tex>, где <tex>h</tex> {{---}} высота дерева. Так как высота декартова дерева {{---}}
<tex>\mathcal{O}(\log n)</tex>, то и операция <tex>\mathrm{split}</tex> работает за <tex>\mathcal{O}(\log n)</tex>.

== Операция merge ==
[[file:merge.png|thumb|400px|Операция merge]]

Рассмотрим вторую операцию с декартовыми деревьями {{---}} <tex>\mathrm{merge}</tex>(''слить'').

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

<tex>\mathrm{merge}(T_1, T_2) \to T</tex>

Рассмотрим принцип работы этой операции. Пусть нужно слить деревья <tex>T_1</tex> и <tex>T_2</tex>.
Тогда, очевидно, у результирующего дерева <tex>T</tex> есть корень.
Корнем станет вершина из <tex>T_1</tex> или <tex>T_2</tex> с наибольшим ключом <tex>y</tex>. Но вершина с самым большим <tex>y</tex> из всех вершин деревьев
<tex>T_1</tex> и <tex>T_2</tex> может быть только либо корнем <tex>T_1</tex>, либо корнем <tex>T_2</tex>.
Рассмотрим случай, в котором корень <tex>T_1</tex> имеет больший <tex>y</tex>, чем корень <tex>T_2</tex>.
Случай, в котором корень <tex>T_2</tex> имеет больший <tex>y</tex>, чем корень <tex>T_1</tex>, симметричен этому.

Если <tex>y</tex> корня <tex>T_1</tex> больше <tex>y</tex> корня <tex>T_2</tex>, то он и будет являться корнем. Тогда левое поддерево
<tex>T</tex> совпадёт с левым поддеревом <tex>T_1</tex>. Справа же нужно подвесить объединение правого поддерева
<tex>T_1</tex> и дерева <tex>T_2</tex>.

Рассуждая аналогично операции <tex>\mathrm{split}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex>
равна <tex>\mathcal{O}(\log n)</tex>.

== Операция add ==
Операция <tex>\mathrm{add}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет.

===Реализация №1:===
# Разобьём наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{split}(T, k.x) \to \{T_1, T_2\}</tex>.
# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{merge}(T_1, k) \to T_1</tex>.
# Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{merge}(T_1, T_2) \to T</tex>.

=== Реализация №2: ===
Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>. Мы нашли позицию, куда будем вставлять наш элемент. Теперь вызываем <tex>\mathrm{split }(T, k.x) \to \{T_1, T_2\}</tex> от найденного элемента (от элемента вместе со всем его поддеревом), и возвращаемые ею <tex>T_1</tex> и <tex>T_2</tex> записываем в качестве левого и правого сына добавляемого элемента.

== Операция remove ==
Операция <tex>\mathrm{remove}(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.

===Реализация №1:===

# Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{split }(T, k.x) \to \{T_1, T_2\}</tex>.
# Теперь отделяем от первого дерева элемент <tex>x</tex>, опять таки разбивая по ключу <tex>x</tex>, то есть <tex>\mathrm{split }(T_1, k.x - \varepsilon) \to \{T_1, T_3\}</tex>.
# Сливаем первое дерево со втором, то есть <tex>\mathrm{merge }(T_1, T_2) \to T</tex>.

===Реализация №2:===
Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), ища удаляемый элемент. Найдя элемент, мы просто вызываем <tex>merge</tex> его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента, то есть <tex>\mathrm{merge }(T.l, T.t) \to T</tex>.