Основные характеристики дискретной случайной величины

Математическое ожидание ДСВ: $A = \sum\limits_{k} A_k * p_k$
Дисперсия D случайной величины вычисляется как математическое ожидание величины $(A-An)^2$, поэтому
$D = \sum\limits_{k}(k-An)^2p_k$
Среднеквадратическое отклонение $\delta = \sqrt{D}$. Смысл этой величины такой: случайная величина принимает значение не из промежутка $[A-r\delta,A+r\delta]$ с вероятностью не превышающей $1/r^2$. Например, событие $|A-An| > 2\delta$ происходит с вероятностью не больше $1/4$

Приближенное вычисление факториала

В 1730 году Джеймс Стирлинг в своей работе привел формулу приближенного вычисления факториала
$n! \approx \sqrt{2\pi n}*(\frac{n}{e})^n$
Она дает погрешность $\frac{1}{12n}$
Погрешность измерений $\delta x(n)$ это величина характеризующая отклонение приближенного значения от истинного. Т.е. $|I \index n - F\index n| \leq \delta x(n)$

Алгоритм Эвклида

Элегантный алгоритм Эвклида для поиска НОД (наименьшего общего делителя)

Интересное тождество

1+3+...+(2n-1) = n²
То есть, сумма первых n нечетных чисел равна квадрату n.

Последовательность Фибоначчи

Последовательность Фибоначии задается рекурсивным соотношением
Fn = Fn-1 + Fn-2
Формулу Nго члена вывел французский математик Боне.
Fn = [(1 + sqrt(5))/2]^2 + [(1 - sqrt(2))/2]^n / sqrt(5)
Выводится формула благодаря замечательной"золотой пропорции":
t = {1 - sqrt(5)) / 2
и её свойствам:
t² = t + 1
tⁿ = t^n-1 + t ^n-2
Если рассмотреть последовательность {tn}, то можно видеть что коэффициент n-ого члена при иррациональном слагаемом в числителе будет являться n-ым членом последовательности Фибоначчи! Реализация на Питоне этого алгоритма

Простой алгоритм генерации чисел Фибоначчи, реализованный на Питоне. Напомню, числа Фибоначчи, это последовательность, названная в честь математика Леонардо Пизанского, сына Боначчи, который представил её в 2002 году. Первый и второй элементы её заданы и равны 1. Остальные задаются рекурсивным соотношением:
F₁ = 1, F₂ = 1, F_k = F_k-2 + F_k-1

Задачи сортировки

Алгоритм сортировки слиянием
Реализовано на Питоне по книге Шень - программирование. Теоремы и задачи. Сложность алгоритма выражается через O-большое от некоторой функции. Например, если сложность алгоритма - O(n²), значит, что число операций в нем не больше чем C*n², где С - некоторая константа. Сложность же данного алгоритма составляет n*log(n). Для меня еще непонятно, как же выяснить сложность алгоритма. Ну, я понимаю когда сложность выражается степенью n. Сколько вложенных циклов от 1 до n, такова и степень в формуле сложности. Я вижу в формуле только один цикл по n, он как бы состоит из двух вложенных: по t+k и второй по p0, q0. Вместе они по-моему представляют из себя цикл по n. Значит, цикл верхнего уровня вносит в формулу сложности log(n).
http://pastebin.com/1mZ8vuZk
Есть еще реализация алгоритма сортировки пузырьком: http://pastebin.com/E5CvSdzz самая простая, поэтому сложность её O(n²).
Сортировка вставками, или Insert Sort
В основе лежит индекс i. В любой момент времени мы можем сказать, что массив a[1]..a[i] является упорядоченным. Но не более того.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях. Реализация использует сторожевой элемент, который ставится в начало алгоритма - чтобы исключить одно из условий проверки. Он гарантированно меньше всех элементов. Сложность алгоритма приводится в среднем и в худшем случае: O(n²)
Быстрая сортировка
Метод основан на выборе опорного элемента, который делит массив на две части. После выбора начинаем двигаться с разных концов к опорному элементу, если в левой части встречается элемент который больше опорного элемента, а правая - аналогично, меньше, то меняем их местами. Это называется разделение. Потом рекурсивно запускаем процедуру для обеих частей массива.
Каждое разделение требует n шагов, а глубина рекурсии в среднем равна log(n). Поэтому сложность алгоритма равна n*log(n). Но он неустойчив. Например, выбирая максимальный элемент из каждой части опорным элементом при процедуре разделения, получим O(n²). Но такая ситуация редкая, её вероятность 2/n. Алгоритм естественен, в случае частичной упорядоченности входного массива, показывает более хорошие результаты.