Математика

Метрические характеристики графов. Деревья. Планарность графов

Метрические характеристики графа
В этом параграфе G - связный граф.
1. Пусть и и v - две несовпадающие вершины графа G. Длина кратчайшего (u,v) - маршрута называется расстоянием между вершинами и и v и обозначается через d(u,v). Положим также d(u,u) = 0.
Теорема 1. Расстояние d(u, v) удовлетворяет аксиомам метрики:
а) d(u,v) ≥ 0;

Определение графа. Виды графов. Подграфы. Операции над графами

Изоморфизм. Помеченные и непомеченные графы. Матрицы, ассоциативные с помеченными графами.
Определение графа

Множество с операциями. Алгебраические структуры. Полугруппа. Моноид. Группа

Определение и примеры.
10. Группа подстановок.
Определение 2.1. Бинарной операцией на множестве X называется правило, по кото¬рому любым двум элементам x, y из множества X ставится в соответствие некоторый, однозначно определенный, элемент из X, обозначаемый х * у.

Кольца. Поля. Определение и примеры Кольцо Zm и кольцо Zp

Определение 2.13. Алгебраическая система (К, +, ∙) с двумя бинарными операциями, сложением и умножением, называется кольцом, если:
1) (К, +) - абелева группа;
2) {К,∙) - полугруппа;
3) операция умножения дистрибутивна относительно операции сложения, то есть:
а ∙ (b + с) = а ∙ b + а ∙ с, (b + с) ∙ а = b ∙ а + с ∙ а, Vа, b,с К.

Множество инъективных отображений Множество биективных отображений

Определение 1.27. Пусть X и Y непустые множества. Отображение f : X → Y назы¬вается иньективным, если из условия х1 ≠ х2 (х1, х2 - любые элементы множества X) следует, что f{x1) ≠ f(x2).
Множество всех инъективных отображений обозначим InYX

Число сочетаний из n элементов по m элементам

Число различных m-элементных подмножеств множества, состоящего из п элементов, называют числом сочетаний длины т из п элементов и обозначают . Итак, = n!/(m!(n-m)!) - число различных m-элементных подмножеств множества, состоящего из п эле¬ментов.
Следствие. Пусть |Х| = п. Тогда число всех различных подмножеств множества X равно

Множество YX, и количество элементов |YX| в этом множестве

Определение 1.25. Пусть X и Y - непустые множества. Множество всех отображений из X в Y назовем множество степень и обозначим YX, то есть YX = {f | f : X → Y} .
Теорема 1.26. Пусть X uY - конечные непустые множества. Тогда |YX| = |Y||X|.

Декартово произведение множеств. Количество элементов в декартовом произведении конечных множеств

Определение 1.22. Декартовым произведением двух множеств X uY называется мно¬жество пар (х,у) таких, что х X, у Y. Обозначим это множество X × Y.
Итак X × Y = {(х,у) | х X, у Y} . Равенство элементов в множестве X × Y понимается следующим образом: (x1, y1) = (x2, y2) тогда и только тогда, когда x1 = х2 и у1 = у2. Очевидно, что X × Y ≠ Y × X, если X ≠ У.

Конечные множества. Правила суммы для конечных множеств

Комбинаторика - это раздел математики, посвященный способам подсчета числа элемен¬тов в конечном множестве. В этом параграфе все множества предполагаются конечными, то есть в них конечное число элементов. Будем обозначать |Х| число элементов множества X.
В качестве аксиом в комбинаторике принимаются следующие:

Отображения множеств. Типы отображений. Композиция. Обратимость отображений

Определение 1.9. Пусть X и Y - множества. Отображением f из множества X в множество Y мы будем называть правило, по которому каждому элементу х множе¬ства X ставится в соответствие вполне определенный (единственный) элемент y = f(x) множества Y. Обозначать данное отображение будем f: X → Y.

Метод перебора

Ме́тод перебо́ра (метод равномерного поиска) — простейший из методов поиска значений действительно-значных функций по какому-либо из критериев сравнения (на максимум, на минимум, на определённую константу). Применительно к экстремальным задачам является примером прямого метода условной одномерной пассивной оптимизации.

Метод множителей Лагранжа

Описание метода
Составим функцию Лагранжа в виде линейной комбинации функции f и функций φi, взятыми с коэффициентами, называемыми множителями Лагранжа — λi,

где
Составим систему из n + m уравнений, приравняв к нулю частные производные функции Лагранжа L(x,λ) по xj и λi.

Метод Давидона-Флетчера-Пауэлла

Метод Давидона-Флетчера-Пауэлла (ДФП) основан на использовании соотношений (3.23) и (3.24).

Из уравнения

f(x0+h)-f(x0) =

=h^T*С f(x0)+1/2* h^TG(x0)* h+...

следует, что при выполнении условий непрерывности любую функцию можно аппроксимировать в окрестности точки x0 функцией

j(x)=f(x)+(x-x0)T* С f(x0)+* (x-x0)T*G(x0)* (x-x0), (3.23)

Метод наискорейшего спуска

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

МЕТОД проекции ГРАДИЕНТА Розена

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

Метод золотого сечения

Метод золотого сечения применяется для поиска минимума функции одного переменного на отрезке. Метод использует следующее свойство непрерывных функций: если точки g и h (g < h) расположены на (a, b) и f(g) ≤ f(h), то на отрезке [a, h] есть хотя бы один минимум функции. Аналогично, если f(g) ≥ f(h), то на отрезке [g, b] есть хотя бы один минимум.

Powered by Drupal - Design by artinet