Векторы.
Проекция вектора

РефератПомощь в написанииУзнать стоимостьмоей работы

Широко известные формулы сокращённого умножения квадрата суммы и разности, куба суммы и разности, являются частными случаями бинома Ньютона. Если степень n бинома Ньютона невысока, коэффициенты многочлена могут быть найдены не расчётом по формуле количества сочетаний, а с помощью так называемого треугольника Паскаля. Формула включений-исключений (или принцип включений-исключений) — комбинаторная… Читать ещё >

Векторы. Проекция вектора (реферат, курсовая, диплом, контрольная)

Вектор-упорядоченный набор элементов. Элементы вектора называются координатами или компонентами. Число координат — длина вектора.

Два вектора равны, если они имеют одинаковую длину и равны соответствующие координаты: и.

Проекцией вектора на ось () называется его i-я компонента.

Проекцией вектора на оси с номерами называется вектор длины .

Прямое произведение

Прямым (декартовым) произведением множеств и () называется множество всех векторов, таких, что :

Множество X² называют декартовым квадратом множества X, множество X³ называют — декартовым кубом множества X.

Декартово произведение двух множеств обладает следующими свойствами:

1. AЧB? BЧA-некоммутативность
2. AЧ (BЧС) = (AЧB) ЧC= AЧBЧC — ассоциативность

3. AЧ (BC) = (AЧB) (AЧC) — дистрибутивность по объединению.

4. AЧ (BC) = (AЧ B) (AЧ C) — дистрибутивность по пересечению.

5. AЧ (BC) = (AЧB)(BЧC)— дистрибутивность по разности
6. (A Ч B)(C Ч D)=(AC)Ч (BD)

Доказать теоретико-множественные тождества Доказать следующие тождества:

1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7. ;
8. ;
9. ;
10. ;
11. ;
12. ;
13. ;
14. ;
15. ;
16. ;
17. ;
18. ;
19. ;
20. ;

Доказать, что:

1. и ;
2. и ;
3. ;
4. ;
5. ;
6. ;
7. ;
8. ;
9. .

Множества конечные и бесконечные Множество называется конечным, если оно состоит из конечного числа элементов, и бесконечным — в противоположном случае.

Мощность конечного множества, А — это число его элементов.

Мощность множества обозначают |A|.

Взаимно-однознаное соответствие множеств, А и В — это такое соответствие, когда каждому элементу множества, А ставится в соответствие единственный элемент множества В, и каждому элементу множества В ставится в соответствие единственный элемент множества А.

Два множества называются эквивалентными, если между их элементами можно установить взаимно-однозначное соответствие. Такие множества ещё называют равномощными.

Множество, А является счётным, если между, А и множеством натуральных чисел можно установить взаимо-однозначное соответствие.

Пример.

Множества целых и рациональных чисел являются счётными.

Множество называется не более чем счётным, если оно конечно или счётно.

Множество называется несчётным, если оно бесконечно и не является счётным.

Множество [0, 1] и любое эквивалентное ему множество называются континуальными.

Континуальное множество — множество, равномощное множеству действительных чисел.

Нахождение мощности объединения множеств.

Мощность объединения двух множеств:

Мощность объединения трех множеств:

Сформулировать и доказать теорему о мощности прямого произведения Пусть — конечные множества. Соответственно мощности этих множеств равны:

Тогда мощность прямого произведения множеств равна произведению мощностей соответствующих множеств, т. е.

Доказательство методом математической индукции.

Для теорема тривиально верна. Предположим, что она верна и для и докажем ее справедливость для .

По предположению.

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

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

Следствие:

Неравенство мощностей Операции над мощностями Свойства сложения и умножения (коммутативность, ассоциативность и дистрибутивность):

Свойства, включающие возведение в степень:

Операции над соответствиями Так как соответствия можно считать множествами, то все операции над множествами (пересечение, объединение, разность, дополнение и т. д.) можно применить и к соответствиям.

Свойства бинарных отношений.

1. Рефлексивность Отношение R на множестве X называется рефлексивным, если для любого xX имеет место xRx, то есть, каждый элемент xX находится в отношении R к самому себе.

Все диагональные элементы матрицы равны 1; при задании отношения графом каждый элемент имеет петлю — дугу (x, x).

2. Антирефлексивность Отношение R на множестве X называется антирефлексивным, если из x₁Rx₂ следует, что x₁x₂ .(ни один элемент xX не находится в отношении R с самим собой).

Все диагональные элементы являются нулевыми; при задании отношения графом ни один элемент не имеет петли — нет дуг вида (x, x).

3. Симметричность Отношение R на множестве X называется симметричным, если для каждой пары (x_{1, x_{2)X² из x_{1Rx_{2 следует x_{2Rx_{1 (иначе говоря, для любой пары R выполняется либо в обе стороны, либо не выполняется вообще).}}}}}}

Матрица симметричного отношения является симметричной относительно главной диагонали, а в задающем графе для каждой дуги из x_{i в x_{k существует противоположно направленная дуга из x_{k в x_i.}}}

4. Асимметричность Отношение R называется асимметричным, если для каждой пары (x₁, x₂) X² из x₁Rx₂ следует, что не выполняется x₂Rx₁ (иначе говоря, для любой пары R выполняется либо в одну сторону, либо не выполняется вообще).

5. Антисимметричность Отношение R называется антисимметричным, если из x₁Rx₂ и x₂Rx₁ следует, что x₁=x₂.

6. Транзитивность Отношение R называется транзитивным, если для любых x₁, x₂, x₃ из x₁Rx₂ из x₂Rx₃ следует x₁Rx₃.

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

7. Антитранзитивность Отношение R называется антитранзитивным, если для любых x1, x2,x3 из x1Rx2 и x2Rx3 следует, что x1Rx3 не выполняется.

8. Связность Отношение R называется связным, если любой пары x1x2 R выполняется хотя бы в одну сторону (из x1Rx2 или x2Rx1).

Типы отношений Отношение эквивалентности.

Бинарное отношение называется отношением эквивалентности (обозначается), если оно.

1) рефлексивно;
2) симметрично;
3) транзитивно.

Отношение порядка Бинарное отношение называется отношением частичного порядка (обозначается), если оно.

1) рефлексивно;
2) антисимметрично;
3) транзитивно.

Отношение строгого порядка Бинарное отношение называется отношением строгого порядка (обозначается <), если оно.

1) антирефлексивно (если a, то ab)
2) асимметрично (если aто не верно b)
3) транзитивно (если a и b, то a).

Отношение толерантности

Отношение называется отношением толерантности, если оно:

1) рефлексивно;
2) симметрично;

Отношение доминирования

Отношение называется отношением доминирования, если оно:

1) антирефлексивно;
2) асимметрично.
5. Правило суммы

Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m+n) способами.

При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта, А не совпадал с каким-либо способом выбора объекта В. множество проекция вектор матрица Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n — k) способов выбора, где k—число совпадений.

Правило произведения Если объект, А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А, В) в указанном порядке можно осуществить mn способами.

При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.

Основные комбинаторные конфигурации Набор элементов xi1,…, xik из множества X={x1, …, xn} называется выборкой объема k из n элементов или, иначе, (n, k)-выборкой.

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

Перестановкой без повторений из n элементов называется всякий упорядоченный набор из этих элементов.

Размещением без повторений из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества (упорядоченная (n, k)-выборка без возвращений называется). Перестановка также является размещением из n элементов по n.

Число различных размещений (без повторений) из n элементов по k обозначается и вычисляется по формуле

Сочетанием без повторений из n по k называется неупорядоченный набор k элементов, выбранных из данных n элементов (неупорядоченная (n, k)-выборка без возвращения). Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Количество всех различных сочетаний (без повторений) из n элементов по k обозначают или :

Свойства сочетаний

Размещением с повторениями из n элементов по k называется упорядоченный набор из k элементов некоторого n-элементного множества, среди которых могут быть одинаковые элементы (упорядоченная (n, k)-выборка с возвращением). Число элементов каждого вида неограниченно. Число различных размещений с повторениями из n элементов по k обозначается и вычисляется по формуле Перестановки с повторениями Перестановками с повторениями из n элементов по k называется упорядоченное подмножество из k элементов n-элементного множества, в которой каждый элемент множества встречается ki раз (причем, k1+k2+…+kn=k). Число перестановок с повторениями обозначается Сочетаниями с повторениями из n элементов по k называются неупорядоченные подмножества k элементов, выбранных из данных n элементов, среди которых могут быть одинаковые элементы, и которые отличаются они хотя бы одним элементом (неупорядоченная (n, k)-выборка с возвращением). Число элементов каждого вида неограниченно.

Число различных сочетаний с повторениями из n элементов по k обозначается и вычисляется по формуле Размещением с повторениями из n элементов по k называется упорядоченный набор из k элементов некоторого n-элементного множества, среди которых могут быть одинаковые элементы (упорядоченная (n, k)-выборка с возвращением). Число элементов каждого вида неограниченно. Число различных размещений с повторениями из n элементов по k обозначается и вычисляется по формуле Перестановки с повторениями Перестановками с повторениями из n элементов по k называется упорядоченное подмножество из k элементов n-элементного множества, в которой каждый элемент множества встречается ki раз (причем, k1+k2+…+kn=k). Число перестановок с повторениями обозначается Сочетаниями с повторениями из n элементов по k называются неупорядоченные подмножества k элементов, выбранных из данных n элементов, среди которых могут быть одинаковые элементы, и которые отличаются они хотя бы одним элементом (неупорядоченная (n, k)-выборка с возвращением). Число элементов каждого вида неограниченно.

Число различных сочетаний с повторениями из n элементов по k обозначается и вычисляется по формуле

Бином Ньютона Бином Ньютона — это формула, выражающая выражение в виде многочлена. Эта формула имеет вид:

где число сочетаний из n элементов по k.

Треугольник Паскаля имеет вид:

1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

Формула бинома Ньютона может быть обобщена для произвольного числа слагаемых:

, где

Формула включений и исключений

Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре^[1].

Например, в случае двух множеств формула включений-исключений имеет вид:

В сумме элементы пересечения учтены дважды, и чтобы компенсировать это мы вычитаем из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.

Таким же образом и в случае множеств процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении Метод рекуррентных отношений Основная идея метода заключается в том, что некоторые определители можно свести к вычислению определителей, имеющих аналогичный вид, но меньший порядок. Если удается установить вид этой зависимости в виде явной формулы, то эта формула — последовательным ее применением — позволит нам «спуститься» к определителям малых порядков.

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

a0,a1,a2,… (1.1)

называют формальный степенной ряд вида

(1.2).

Часто бывает удобно рассматривать ряд вида

, (1.3).

который называется экспоненциальной производящей функцией последовательности a0, a1,a2,…

Числа an и называются коэффициентами ряда (1.2) и ряда (1.3) соответственно.

Линейные операции наиболее часто встречающиеся операции над числовыми последовательностями.

Если

то Сдвиг начала

Вправо Если

то.

влево Если то.

Изменение масштаба Если то.

Подобие Если то Свёртка Если.

то Метод ветвей и границ В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия «разделяй и властвуй»). На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда — наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы.

Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т. д.

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

Запишем исходную задачу в терминах целочисленного линейного программирования.

Введем следующие переменные:

С использованием введенных обозначений простейшая задача размещения записывается следующим образом

y_i іx_ij, i ОI, j ОJ,

x_ij, y_i, y_i О {0, 1}, iОI, jОJ.

Двойственная задача линейного программирования имеет вид:

v_j Ј g_ij + w_ij, iОI, jОJ,

w_ij і 0, iОI, jОJ.

Приближенное решение двойственной задачи используется в качестве нижней оценки.

Для сокращения размерности задачи применяется так называемый блок предварительной отбраковки. Он основан на применении условий дополняющей нежесткости для задач линейного программирования

Если для оптимального решения двойственной задачи выражение в скобках положительно для некоторого iОI, то «скорее всего» в исходной целочисленной задаче y_i = 0, и размерность можно уменьшить. Понятно, что данный эвристический прием не всегда приводит к правильному решению. Поэтому в качестве порога лучше брать не 0, а некоторую величину d і0, выбор которой зависит от исходных данных. Эту величину называют порогом отбраковки. Очевидно, что при d і max c_i, размерность задачи не сокращается.

Другой способ уменьшения трудоемкости алгоритма состоит в искусственном завышении нижней оценки. Предположим, что нас интересует не только оптимальное решение, но и приближенные решения с относительной погрешностью не более e. Тогда завышение нижней оценки в (1 + e) раз приводит к желаемому результату.

Показать весь текст

Заполнить форму текущей работой