Все вероятности в мире находятся в одном простом круге
π - отношение длины окружности к её диаметру. 3.1415926535... это только начало. Оно продолжается бесконечно, без единого повтора. А значит внутри этой бесконечной цепи чисел содержатся все остальные числа - дата вашего рождения, код вашего сейфа и номер страховки - все они там где-то, и если преобразовать эти цифры в буквы, то вы получите все существующие слова во всех возможных комбинациях - первое слово, которое вы сказали в детстве, имена ваших возлюбленных, вся история вашей жизни, всё что мы говорим или делаем.
"Будучи математиком, ты тратишь всю свою жизнь на то, чтобы доказать какую-то теорему"
Во время обучения в школе, я про это дело немного забыл, так как начал серьезно увлекаться математикой. Понимаете, нужно было выбирать между математикой и программированием, и я выбрал первое. На то была вполне резонная причина: мой папа – математик, кандидат физико-математических наук. Он окончил МГУ им. Ломоносова, и мне казалось, что у него я смогу многому научиться. Я был участником республиканских олимпиад – мне нравилось решать сложные задачи. Но в какой-то момент я задумался: будучи математиком, ты тратишь всю свою жизнь на то, чтобы доказать какую-то теорему. Но попытки бывают тщетны. И ты по новой включаешься в процесс, а для этого нужна истинная страсть к предмету.
Данияр Турмухамбетов
Тета большое
Через Θ(f) (читается тета большое) мы обозначаем класс функций, растущих с той же скоростью, что и f. С формальной точки зрения этот класс представляет собой пересечение двух предыдущих классов, Θ(f) = Ω(f) ⋂ Ο(f).
O большое
На другом конце спектра находится класс O(f) (читается о большое). Этот класс состоит из функций, растущих не быстрее f. Функция f представляет собой верхнюю границу класса O(f). С формальной точки зрения g принадлежит классу O(f), если g(n) ⩽ cf(n) для всех n, начиная с некоторого порога n0, и для некоторой положительной константы c.
Проверить, принадлежит ли данная функция классу O(f), можно двумя способами: либо с помощью данного выше определения, либо воспользовавшись следующим описанием: g ∈ O(f), если \lim_{n\to\infty}\frac{g(n)}{f(n)}=c для некоторой константы c. Это означает, что если предел отношения g(n)/f(n) существует и он меньше бесконечности, то g ∈ O(f). Для некоторых функций это не так-то просто проверить. По правилу Лопиталя, в таком случае можно заменить предел отношения самих функций пределом отношения их производных.
Проверить, принадлежит ли данная функция классу O(f), можно двумя способами: либо с помощью данного выше определения, либо воспользовавшись следующим описанием: g ∈ O(f), если \lim_{n\to\infty}\frac{g(n)}{f(n)}=c для некоторой константы c. Это означает, что если предел отношения g(n)/f(n) существует и он меньше бесконечности, то g ∈ O(f). Для некоторых функций это не так-то просто проверить. По правилу Лопиталя, в таком случае можно заменить предел отношения самих функций пределом отношения их производных.
Омега большое
Класс функций, растущих по крайней мере так же быстро, как f, мы обозначаем через Ω(f) (читается омега большое). Функция g принадлежит этому классу, если при всех значениях аргумента n, больших некоторого порога n0, значение g(n) > cf(n) для некоторого положительного числа c. Можно считать, что класс Ω(f) задаётся указанием своей нижней границы: все функции из него растут по крайней мере так же быстро, как f.
Обозначения из работ Дейкстры
В логических выражениях литера & обозначает конъюнкцию и читается как "и". Литера ~ обозначает отрицание и читается как "не". Комбинация литер or обозначает дизъюнкцию и читается как "или". Литеры A и E, набранные жирным шрифтом, обозначают кванторы общности и существования.
Нижеследующие формулы определяют смысл нотации в левой части через выражение в правой. Интерпретация символа "…" оставлена интуиции.
Ai: m ≤ i < n : Pi Pm & Pm+1 & … & Pn-1
Здесь Pi - некоторые предикаты, а формула утверждает, что выполняются все Pi для значений индекса i из диапазона от m до n, но не включая само n.
Ei: m ≤ i < n : Pi Pm or Pm+1 or … or Pn-1
Здесь Pi - некоторые предикаты, а формула утверждает, что выполняются некоторые из Pi для каких-то значений индекса i из диапазона от m до n, но не включая само n.
Ei: m ≤ i < n : Pi Pm or Pm+1 or … or Pn-1
Здесь Pi - некоторые предикаты, а формула утверждает, что выполняются некоторые из Pi для каких-то значений индекса i из диапазона от m до n, но не включая само n.
Si: m ≤ i < n : xi = xm + xm+1 + … + xn-1
MIN i: m ≤ i < n : xi = минимальное среди значений (xm, … , xn-1)
MAX i: m ≤ i < n : xi = максимальное среди значений (xm, … , xn-1)
Скорости роста функций
Графики четырех функций:
 |
| https://ggbm.at/GWhpSG98 |
Функция содержащая x2, сначала растёт медленно, однако чем больше x, тем выше скорость роста функции. Скорость роста функций, содержащих x, постоянна всем интервале значений переменной. Функция 2logx вообще кажется постоянной, но это обман зрения. На самом деле она растёт, только очень медленно. Относительная высота значений функций также зависит от того, большие или маленькие значения переменной мы рассматриваем. Сравним значения функций при x = 2. Функцией с наименьшим значением в этой точке является x2/8, а с наибольшим - функция x+10. Однако с возрастанием x функция x2/8 становится и остаётся впоследствии наибольшей.
Формулы суммирования
Пусть, скажем, у нас есть алгоритм с циклом. Если переменная цикла принимает значение 5, то цикл выполняется 5 раз, а если значение равно 20, то двадцать. Вообще, если значение переменной цикла равно M, то цикл выполняется M раз. В целом если переменная цикла пробегает все значения от 1 до N, то суммарное число выполнений цикла равно сумме всех натуральных чисел от 1 до N. Мы записываем эту сумму в виде
N конечное значение переменной суммирования ∑i i=1 начальное значение переменной суммирования
Если какое-нибудь значение записано в виде подобной суммы, то его зачастую стоит упростить, чтобы результат можно было сравнивать с другими подобными выражениями. Не так уж просто сообразить, какое из двух чисел
и
больше. Поэтому для упрощения суммы можно пользоваться следующими формулами, в которых C - не зависящая от i постоянная:
При упрощении сумм можно сначала разбить их на более простые суммы с помощью вышеприведённых равенств, а затем заменять суммы с помощью остальных тождеств.
N ∑(i2-i) i=11
и
N ∑(i2-20i) i=0
больше. Поэтому для упрощения суммы можно пользоваться следующими формулами, в которых C - не зависящая от i постоянная:
N N ∑Ci = C∑i; i=1 i=1 N N-L ∑i = ∑(i+L); i=L i=0 N N L-1 ∑i = ∑i - ∑i; i=L i=0 i=0 N N N ∑(A+B) = ∑A + ∑B; i=1 i=1 i=1 N N ∑(N-i) = ∑i; i=0 i=0Это равенство означает, что сумма чисел от 0 до N равна сумме чисел от N до 0.
При упрощении сумм можно сначала разбить их на более простые суммы с помощью вышеприведённых равенств, а затем заменять суммы с помощью остальных тождеств.
N ∑1 = N; i=1 N ∑C = CN; i=1 N ∑i = ( N(N+1) ) / 2; i=1Это равенство легко запомнить, если разбить числа от 1 до N на пары. Складывая 1 с N, 2 с N-1 и т.д., мы получим набор сумм, каждая из которых равна N+1. Сколько всего будет таких сумм? Разумеется их число равно половине числа разбиваемых на пары элементов, т.е. N/2. Поэтому сумма всех N чисел равна (N/2)*(N+1) = ( N(N+1) ) / 2.
N N(N+1)(2N+1) 2N3+3N2+N ∑i2 = -------------- = -------------; i=1 6 6 N ∑2i = 2N+1 - 1; i=0Это равенство легко запомнить через двоичные числа. Сумма степеней двойки от нулевой до десятой равна двоичному числу 11111111111. Прибавив к этому числу 1, мы получим 100000000000, т.е. 211. Но этот результат на 1 больше суммы степеней двойки от нулевой до десятой, поэтому сама сумма равна 211 - 1. Если теперь вместо 10 подставить N, то мы придём к этому неравенству.
N AN+1 - 1 ∑Ai = ---------- для любого числа A; i=1 A - 1 N ∑i2i = (N - 1)2N+1 + 2; i=1 N ∑(1/i) ≈ ln(N); i=1 N ∑log2(i) ≈ Nlog2(N) - 1,5. i=1
Логарифмы
logbx = a тогда и только тогда, когда ba = x.
Логарифмом числа x по основанию b называется такой показатель степени a, в которую нужно возвести b, чтобы получить x. Основанием логарифма может служить любое положительно число, отличное от 1.
log1045 ≈ 1,653 поскольку 101,653 ≈ 45.
Если основание логарифма больше 1, то он является строго возрастающей функцией. Это означает, что если x > y, то logbx > logby для любого основания b. Логарифм - взаимно однозначная функция, т.е. если logbx = logby, то x = y.
Свойства логарифма, справедливые при положительных значениях входящих в них переменных:
- logb1 = 0;
- logbb = 1;
- logb(xy) = logbx + logby;
- logbxy = ylogbx;
- logax = (logbx) / (logba).
log4275 = (loge75) / (loge42) ≈ 1,155.
Большинство калькуляторов позволяют вычислять логарифмы по основанию 10 и натуральные логарифмы (по основанию e).
Округление влево и вправо
Округление влево (или целая часть) числа x
⌊x⌋ - наибольшее целое число, не превосходящее x.
⌊2,5⌋ = 2
⌊-7,3⌋ = -8
Округление вправо числа x
⌈x⌉ - наименьшее целое число, которое не меньше, чем x.
⌈2,5⌉ = 3
⌈-7,3⌉ = -7
Округление влево и вправо применяется, когда нужно подсчитать, сколько раз было выполнено то или иное действие, причем результат будет представлять собой частное некоторых величин. Например, при попарном сравнении N элементов, когда первый элемент сравнивается со вторым, третий с четвертым и т.д., число сравнений будет равно ⌊N/2⌋. Если N = 10, то попарных сравнений будет 5, и ⌊10/2⌋ = ⌊5⌋ = 5. А если N = 11, то число сравнений не изменится и останется равным пяти, и ⌊11/2⌋ = ⌊5,5⌋ = 5.
нелинейный
НЕЛИНЕ́ЙНЫЙ -ая, -ое. Матем. Отклоняющийся от прямо пропорциональной зависимости. Н-ая акустика (раздел акустики, изучающий свойства звуковых волн большой амплитуды). Н-ая оптика (раздел оптики, изучающий совокупность явлений, наблюдающихся при взаимодействии интенсивных световых полей с веществом). Н-ая среда (среда, свойства которой зависят от интенсивности взаимодействующих с ней физических полей).
Разница между делением с остатком и сравнением по модулю
mod в математике
Запись a ≡ b (mod m) означает, что a - b кратно m.Кратно - означает что a - b делится на m нацело, например 12 кратно 3.
Пример 1
Если число n делится на m, то оно сравнимо с нулем по модулю m:
n ≡ 0 (mod m).
Пример 2
Решить x ≡ 0 (mod 3) значит найти все такие х, которые сравнимы с нулем по mod 3.
Пример 3
Числа
3, 10, 17, 24, 31, …, (7k + 3)
сравнимы между собой по mod 7. Таким образом, все такие числа являются решениями уравнения x ≡ 3 (mod 7).
Пример 4 (асимметричное шифрование)
За основу алгоритма Хеллман предложил функцию Yx (mod P). Обратное преобразование для такой функции очень сложно, и можно сказать что, по сути, заключается в полном переборе исходных значений.
К примеру вам сказали, что 5x (mod 7) = 2, попробуйте найдите x, а?
Нашли? А теперь представьте что за Y и P взяты числа порядка 10300.
Кстати сказать, для повышения стойкости, число P должно являться простым числом, а Y — являться первообразным корнем по модулю P.
Bootstrapping в математике
Мне кажется есть какая-то связь между этим:
Некоторая сложность в написании учебного пособия по программированию для начинающих состоит в том, что рассматриваемая область знания содержит новые понятия, ни на чём привычном не основанные.
Вообще говоря, подобная проблема возникает и в любой другой области знаний. Например, известно, что точка в математике определяется как бесконечно малая окружность, в то время как сама окружность - это совокупность расположенных определённым образом точек. Легко заметить, что эти термины определены через самих себя. Вместе с тем, эта нечаянность не стала в математике камнем преткновения. И окружности, и точки, и линии, а вместе с ними другие термины, принятые в математике, благополучно сосуществуют. Более того, каждому человеку интуитивно понятно, что такое точка, а что - окружность.
и раскруткой. Понятие линии раскручивается из понятия точки.
Системы счисления для "чайников"
Давайте попробуем самостоятельно изобрести числа.
Во первых мы живем в мире объектов. Главным критерием объекта является его некая обособленность. Если что-то может быть изолировано или оторвано от его среды, то мы можем назвать это объектом. Рассмотрим такой объект нашего мира как лошадь. При наблюдении нескольких объектов возникает понятие множества.
 |
| Множество лошадей |
Описательная статистика
Описательная статистика, цели
Любой статистический анализ начинается с описательной статистики. Цель описательной статистики - обработать и систематизировать эмпирические данные, представить их в наглядном виде (графическом или табличном), рассчитать основные статистические показатели наблюдаемых данных.
Описательная нужна для того чтобы:
- Выявить ошибки в данных. Во время сбора наблюдений могут произойти сбои и часть данных может записаться некорректно.
- Увидеть структуру данных и выяснить однородны ли ваши данные.
- Найти нарушения в статистических предположениях. Вы могли предполагать, что изучаемая величина имеет нормальный закон распределения, однако посмотрев на данные, вы возможно поменяете ваше мнение и будете использовать другие статистические методы.
- Сгенерировать гипотезы и выдвинуть предположения, которые вы будете в дальнейшем проверять.
Выборка. Выборочное пространство
Основные задачи математической статистики. Примеры задач
Математическая статистика - это наука разрабатывающая методы регистрации, описания, и анализа данных наблюдений и экспериментов, с целью построения вероятностных моделей массовых случайных явлений.
Примеры задач при решении которых применяется математическая статистика.
Относительной частотой события A называют отношение числа испытаний m, в которых данное событие появилось, к общему числу n фактически проведённых испытаний: W(A)=\frac{m}{n}, или короче: \omega=\frac{m}{n}. Дальше »
Переменная величина называется случайной, если в результате опыта она может принимать действительные значения с определёнными вероятностями. Наиболее полной, исчерпывающей характеристикой случайной величины является закон распределения. Закон распределения – функция (таблица, график, формула), позволяющая определять вероятность того, что случайная величина Х принимает определенное значение хi или попадает в некоторый интервал. Если случайная величина имеет данный закон распределения, то говорят, что она распределена по этому закону или подчиняется этому закону распределения. Дальше »
Любое статистическое исследование включает в себя сбор данных, представление данных в наглядной форме и анализ данных.Относительной частотой события A называют отношение числа испытаний m, в которых данное событие появилось, к общему числу n фактически проведённых испытаний: W(A)=\frac{m}{n}, или короче: \omega=\frac{m}{n}. Дальше »
Переменная величина называется случайной, если в результате опыта она может принимать действительные значения с определёнными вероятностями. Наиболее полной, исчерпывающей характеристикой случайной величины является закон распределения. Закон распределения – функция (таблица, график, формула), позволяющая определять вероятность того, что случайная величина Х принимает определенное значение хi или попадает в некоторый интервал. Если случайная величина имеет данный закон распределения, то говорят, что она распределена по этому закону или подчиняется этому закону распределения. Дальше »
Основные понятия и теоремы "Теории вероятностей"
- Что такое случайное событие?
- Что такое вероятностное пространство?
- Что такое случайная величина?
- Закон распределения случайной величины:
- Что такое распределение вероятностей?
- Что такое функция распределения?
- Что такое плотность распределения?
- Что такое математическое ожидание?
- Что такое дисперсия?
- Что такое начальные и центральные моменты?
- Что такое функции от случайных величин?
- зависимые и независимые события и случайные величины
- случайные вектора, из распределения и характеристики
- последовательности случайных величин
- предельные теоремы
- теоремы Муавра-Лапласа
- закон больших чисел
- центральная предельная теорема
- основные законы распределений
- норамльный
- равномерный на [a,b]
- экспоненциальный
- логистический
- Пуассона
- геометрический
- биномиальный
Подписаться на:
Сообщения (Atom)