Архив рубрики «Математика»

Задача минимизации методами наискорейшего спуска и поразрядного приближения

1. Техническое задание
1. Разработать программу для решения задачи оптимизации для функции:

f(x1,x2)= 100 (x2 — x12)2 + (1 — x1)2 + (√[x12+x22 — 1)2 + 100 (ϕ(x1, x2)) 2, где
ϕ(x1, x2) = 0.5*π arctg(x2/x1), x1 > 0
ϕ(x1, x2) = 0.25, x1 = 0
ϕ(x1, x2) = 0.5*π (π + arctg(x2/x1)), x1 > 0

Прочитать остальную часть записи »

Вероятность (что это такое)

Обсудим физические предпосылки определения вероятности. Известен один опытный факт, объясняющий введение понятия вероятности.

Предположим, имеется некоторый эксперимент, где Ω — множество его возможных исходов; А — некоторое случайное событие, например бросание игральной кости; А — {появление четного числа}.
Прочитать остальную часть записи »

Введение в теорию вероятностей

Изучаемая теорией схема
Предполагается, что проводится некоторый эксперимент, результат ω (исход эксперимента) заранее неизвестен, непредсказуем, изменяется при повторении эксперимента при неизменных условиях. Известно множество всех возможных исходов эксперимента; это множество обозначим
Прочитать остальную часть записи »

Комбинация метода случайного поиска (спуска) и метода Фибонначи

1. Задание
Разработать программу, реализующую систему поиска экстремума функции

f(x1, x2 = 1/x1 + x13 — 7x12 + x1x2 — x22 + 9x1 + 3x2 + 12

Прочитать остальную часть записи »

Математические основы анализа и синтеза дискретных систем

Написать программу, производящую оптимизацию (поиск минимуму) двух заданных целевых функций (см. ниже) с использованием совмещения метода Кифера-Вольфовица и метода последовательных приближений. Программа должна уметь построить линии уровня (10 – 15 линий) которые должны заполнять все поле экрана. Также программа должна отображать траекторию движения точки поиска. Найти значения и точки всех минимумов.
Прочитать остальную часть записи »

Кольца и поля, примеры колец и полей

Определение: Кольцо (R,{+,•}) есть множество с двумя определенными на нем операциями (функциями)):
1) Сумма x+y: RxR → R
2) Произведение x*y: RxR → R

Удовлетворяющие следующим аксиомам:
1) (x+y) + z = x + (y+z)
2) x+y = y+x
3) ∃0∈R_x + 0 = x
4) ∀x∈R_∃(-x)∈R: x + (-x) = 0
R- Есть абелева группа по сложению.
5) (x*y)*z = x*(y*z)
6) (x+y)*z = x*z + y*z; x*(y+z) = x*y + x*z
Кольцо коммутативно, если умножение коммутативно.
7) x*y = y*z
Прочитать остальную часть записи »

Нормальные подгруппы, фактор группы, теорема групповом гомоморфизме

Определение: Гомоморфизм группы G в группу H есть отображение φ: G→H, для которого φ(g1*g2) = φ(g1)*φ(g2), ∀g1, g2∈G. Изоморфизм есть взаимно однозначный гомоморфизм. Афтоморфизм есть изоморфизм группы в себя.
Прочитать остальную часть записи »

Группы, свойства групп, циклическая группа и ее генератор

Определение: Группа G есть универсальная алгебра (G,{*, ¬,e}) с бинарной операцией умножения, унарной операцией x-1: S → S, и выделенном элементом единицей e, удовлетворяющей следующим аксиомам:

1) ∀x, y, z ∈ G, x*(y*z) = (x*y)*z, .
2) x*x-1 = x-1*x = e.
3) x*e = e*x = x.
Прочитать остальную часть записи »

Полугруппы (примеры полугрупп), подполугруппы, циклические полугруппы

Определение: Полугруппа S есть универсальная алгебра (S, {*}) с первой бинарной операцией x*y: SxS → S (умножение), удовлетворяющей аксиоме ассоциативности: ∀x, y, z ∈ S.
1) x*(y*z) = (x*y)*z.
Полугруппа коммутативна, если
2) x*y = y*x.
Прочитать остальную часть записи »

Индексы (логарифмы)

Пусть (a, m) = 1. По теореме Эйлера существует такое целое положительное γ, например φ(m), что aγ ≡ 1 (mod p).

Определение: Наименьшее положительное δ, для которого aδ ≡ 1 (mod p) называющийся экспонентой, которой a ∈ по mod m. Обозначение a ∈ exp δ (mod m).
Прочитать остальную часть записи »

Модульная арифметика

an (mod m) = a*a* …* a (mod m)

Теорема (Эйлера): Если m>1 и (a,m)=1, то aφ(m) ≡ 1 (mod m).

Следствие (теорема Ферма): Если простое p не делит a, то ap-1 ≡ 1 (mod p).
Определение: a-1 обратно к a по mod m, если a*a-1 ≡ 1 (mod m).
Прочитать остальную часть записи »

Целые числа, сравнения — дискретная математика

Z = {…, -3, -2, -1, 0, 1, 2, 3, …}, N={0,1,2,3,…}, N+ = {1,2,3,…}
Теорема (деления целых чисел): Пусть b∈N+. Пусть всякое a∈Z единственным образом представимо в виде a=b*q+r, 0≤0Прочитать остальную часть записи »

Конгруенции и фактор-алгебры, теоремы о гомоморфизме

Пусть φ: A→B есть функция и φ(A)=B. Отображение φ: A→B порождает разбиение множества А на классы, ядерная эквивалентность, для которого σφ обладает тем свойствам, что a1σφa2↔φ(a1)=φ(a2) ∀a1, a2∈A. Пусть A/σ = {Ab; b∈B} есть множество классов эквивалентности (фактор- множество по эквивалентности σ), тогда отображение h: A/σ → B взаимнооднозначно, тогда отображение p:A → A/σ с p(a) = Aφ(a) есть каноническое отображение. Тогда φ = h*p есть каноническое представление функции φ. Пусть [a]σ есть класс эквивалентности, содержащий элемент a из A, тогда p(a)=[a]σ=Aφ(a), h([a]σ) = φ(a). Пусть записи (a,a’)∈σ, aσa’, a~a'(σ), a~a’ означают, что элементы a и a’ эквивалентны.


Прочитать остальную часть записи »

Примеры универсальных алгебр, подалгебры, гомоморфизм и изоморфизм алгебр

Пусть А есть произвольное множество. n- местная операция над А есть функция (отображение) f: An → A, An = A⋅…⋅A . Ноль — арная операция на А есть элемент из А. Пусть n(f) есть местность (арность) операции на f. Универсальная алгебра есть система U = (A, Ω), где А есть некоторое множество, Ω={fini(x1,…,xn): i=1,2,…}. Тип универсальной алгебры U есть последовательность (n1, n2, ..) арностей функций fi. Сигнатура есть множество Ω символов операций из Ω.
Прочитать остальную часть записи »

Комбинаторно-логический аппарат, формула включений и исключений

Пусть имеем N объектов, которые могут обладать или не обладать n свойствами 1,2,..,n

Примем следующие обозначения:
N(0) [или N(⎤1,⎤2,..,⎤n)]-число объектов, не обладающих ни одним из свойств 1,2,..,n.
N(i1,i2,..,ir)-число объектов, обладающих свойствами i1,i2,..,ir (возможно и другими свойствами)
N=K — число объектов, обладающих в точности К свойствами.
N>=K — число объектов, обладающих не менее, чем К свойствами.
Прочитать остальную часть записи »

Производящие функции для размещений с повторениями с ограничениями и без ограничений на число повторов

Теорема: Пусть множество М={х1,…,хn}.
Функции f (t, х1,…,хm)= ∏(1+xkt/1! + [xkt]2/2! + … + (xkt)Ck/Ck!) и
g (t)= f (t, 1,…1)= ∏(1+t/1! + t2/2! + … + tCk/Ck!)
являются производящими функциями для размещений и для числа размещений из n элементов, причём в каждом размещении элемент ХК встречается ≤ СК раз к= 1,2,..,n .
Прочитать остальную часть записи »

Сочетания с повторениями без ограничения на число повторений

Теорема: пусть множество М={х1,…,хn}

Функции f (t, х1,…,хn)= ∏ (1+xkt + [xkt]2 + …) и g (t)= f (t, 1,…1) = ∏ (1+t+t2 + …)
являются порождающими функциями для сочетаний и для числа сочетаний из n элементов с повторами без ограничений на число повторов.
Прочитать остальную часть записи »

Производящая функция для сочетаний без повторений и с повторениями с ограничением на число повторений

Теорема: Пусть М={x1,x2,…,xn}. Функции f(t,x1, 2, …, n) = ∏(1+xkt) и g(t) = f(t, 1, 1, …, 1) = (1 + t)n есть порождающие функции для сочетаний и для числа сочетаний из n элементов.
Прочитать остальную часть записи »

Производящие функции для комбинаторных конфигураций и их числа

Аппарат формальных степенных рядов есть достаточно универсальный метод порождения и пересчета комбинаторных конфигураций.

Определение: Порождающая функция для множества (для числа) всех комбинаторных конфигураций данного типа, построенных на основе множества М={x1,x2,…,xn} есть функция f(t,x1,…,xn) (функция g(t)), в формальном разложении которой в ряд по степеням t коэффициент при tr есть все комбинаторные конфигурации (число всех комбинаторных конфигураций) из n элементов по r каждой конфигурации.
Прочитать остальную часть записи »

Подсчет числа размещений, перестановок, сочетаний без повторов и с повторами

Число размещений без повторений
Теорема: Число размещений без повторений из n элементов по r Anr = n(n-1)(n-2)…(n-r+1) = n!/(n-r)!.

Доказательство: В r-размещении (а1,a2,…,ar) n-элементного множества M элемент а1 можно выбрать n способами. После этого элемент a2 можно выбрать n-1 способами (из оставшихся n-1 элементов множества M). После этого элемент a3 можно выбрать n-2 способами. И так далее. Наконец, элемент аr можно выбрать n-г+1 способами. По правилу произведения = n (n-1) (n-2)… (n-r+1);
умножив и разделив правую часть равенства на (n-r)(n-r-1)…3*2*1. Получим Anr = n!/(n-r)!.
Прочитать остальную часть записи »

Правило суммы и правило произведения

Правило суммы: Пусть конечное множество M разбито на два непересекающихся подмножества M1 и M2 (в объединении дающих все множество М). Тогда мощность |M| = |M1| + |M2|.

Правило произведения: Пусть в некотором множестве объект а может быть выбран n способами, и после этого (то есть после выбора объекта а) объект b может быть выбран m способами. Тогда объект ab может быть выбран n*m способами.
Прочитать остальную часть записи »

Элементы комбинаторики — размещения, перестановки, сочетания с повторами и без повторов

Определение: Перестановка n-элементного множества М есть упорядоченный набор длины n, составленный из попарно различных элементов множества М. Обозначим через множество всех перестановок из n элементов и через Рn число всех перестановок из n элементов. Например, если M = {а,b,с}, то РM = {(а,b,с), (а,с,b), (b,а,с). (b,с.а), (с,а,b), (с,b,а)}; Рn =3!= 6.
Прочитать остальную часть записи »

Алгебра логики : правила построения и преобразования логических выражений

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

Обозначения
Я буду придерживаться обозначений, ясных большинству людей и привычных для программистов.
• «Истина» — true
• «Ложь» — false
• Логическое «и» — and
• Логическое «или» — or
• Логическое отрицание — not
Прочитать остальную часть записи »

Линейные рекуррентные уравнения однородные и неоднородные с постоянными коэффициентами

Определение: Уравнение L(x(k)) = x(k+n) + a1(k)x(k+n+1) + … + an(k)x(k) = {0, F(k)}, причём
0 – (R0) однородное уравнение.
F(k) – R1 неоднородное уравнение.
где ai(k) – функция в N→R, i = 1…n и F(k)≠0 (тривиально) – неизвестная функция, x(k) – неизвестная функция называются линейными рекуррентными уравнениями (ЛРУ) однородными и неоднородными соответственно с постоянными коэффициентами.
Прочитать остальную часть записи »

Фундаментальная система решений, общее решение однородного и неоднородного ЛРУ с помощью ФСР

Определение: Нетривиальная система функций f1(k)…fn(k) линейно зависима ⇔ ∃ числа с1…сn≠0 одновременно, для которых c1f1(k) + … + cnfn(k) = 0 ∀k∈N
Прочитать остальную часть записи »

Линейные рекуррентные уравнения(ЛРУ) однородные и неоднородные с переменными коэффициентами

Определение: Уравнение L(x(k)) = x(k+n) + a1(k)x(k+n-1) + … + an(k)x(k) = {0, F(k)}, причём: 0 – (R0) однородное уравнение, F(k) – R1 неоднородное уравнение.

где ai(k) – функция в N→R, i = 1…n и F(k)≠0 (тривиально) – неизвестная функция, x(k) – неизвестная функция, называются линейными рекуррентными уравнениями (ЛРУ) однородными и неоднородными соответственно с переменными коэффициентами.
Прочитать остальную часть записи »

Рекуррентные уравнения, порядок уравнения, частное и общее решение

Пусть F(t1, t2,…, tn+1):Rn+1→R – есть некоторая (n+1) – местная функция.

Определение: Соотношение (уравнение) R x(k+1) = F(k,x(k),x(k+1),..,x(k+n-1)) с неизвестной функцией натурального аргумента x(k): N→R, k∈N = {0,1,2,…} называется рекуррентным (рекурсивным). Число n – порядок уравнения (R).
Прочитать остальную часть записи »

Многочлен циклов (цикловой индекс), теорема Пойа

Пусть G есть группа подстановок множества Х={1,2,…n} и пусть конечное множество Y={1,2,…,m} имеет не менее двух элементов. Пусть есть множество всех функций из Х в У. (Х→У).


Прочитать остальную часть записи »

Нормальное распределение (закон Гаусса) – теория вероятностей

Закон Гаусса является одним из наиболее распространенных в теории надежности. Нормальное распределение оказывается справедливым для очень многих явлений в силу действия центральной предельной теоремы, сформулированной Ляпуновым: если случайная величина Х представляет собой сумму очень большого числа взаимно независимых случайных величин, влияние каждой из которых на всю сумму ничтожно мало, то величина Х имеет распределение, близкое к нормальному.
Прочитать остальную часть записи »

Распределение Вейбулла – теория вероятностей

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




Статистика