π - отношение длины окружности к её диаметру. 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.
нелинейный
НЕЛИНЕ́ЙНЫЙ -ая, -ое. Матем. Отклоняющийся от прямо пропорциональной зависимости. Н-ая акустика (раздел акустики, изучающий свойства звуковых волн большой амплитуды). Н-ая оптика (раздел оптики, изучающий совокупность явлений, наблюдающихся при взаимодействии интенсивных световых полей с веществом). Н-ая среда (среда, свойства которой зависят от интенсивности взаимодействующих с ней физических полей).
Подписаться на:
Сообщения (Atom)