Обобщенное склеивание троичных векторов (3 видео)

Быстрое внутреннее произведение троичных векторов

Рассмотрим два вектора, а также В, размера N, 7 uint32_t с использованием следующей кодировки:

знак 0, значение 0 → 0
знак 0, значение 1 → 1
знак 1, значение 1 → -1.

Реализация C ++, о которой я думал, выглядит следующим образом:

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

Содержание

Решение
Другие решения
Редактировать:
Основные понятия теории графов G = (V, E),
Операции над n-мерными векторами: сложение, умножение, свойства
Сложение n-векторов
Умножение n-вектора на число
Операции над 2-мерными и 3-мерными векторами
Свойства операций над n-мерными векторами
🎦 Видео

Видео:10 класс, 43 урок, Компланарные векторыСкачать

Решение

Мне нравится иметь 2 uint32_t , но я думаю, что ваш фактический расчет немного расточительный

Всего несколько незначительных моментов:

Я не уверен насчет ссылки (получение a а также b от const & ) — это добавляет уровень косвенности по сравнению с помещением их в стек. Когда код такой маленький (может быть, пара часов), это важно. Попробуйте пройти по значению и посмотрите, что вы получите

__builtin_popcount может быть, к сожалению, очень неэффективным. Я использовал его сам, но обнаружил, что даже очень простая реализация, которую я написал, была намного быстрее, чем эта. Однако — это зависит от платформы.

По сути, если у платформы есть аппаратная реализация попкорна, __builtin_popcount использует это. Если нет — он использует очень неэффективную замену.

Видео:Преобразование логических выражений / Упрощение выражений (практика) [Алгебра логики] #6Скачать

Другие решения

Одна серьезная проблема здесь — это повторное использование psign а также pvalue переменные для положительного и отрицательного векторов. Вы не делаете ни своему компилятору, ни себе никакой пользы, запутывая свой код таким образом.

Было бы возможно для вас, чтобы закодировать свое троичное состояние в std::bitset и определить продукт с точки зрения and ? Например, если ваши троичные типы:

Я считаю, что вы могли бы определить их продукт как:

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

Редактировать:

Мое глупое предложение не считало, что (-1)(-1) = 1 , который не может быть обработан предложенным мною представлением. Спасибо @ user92382 за то, что подняли это.

В зависимости от вашей архитектуры вы можете оптимизировать временные битовые векторы — например, если ваш код будет скомпилирован в FPGA или размещен в ASIC, то последовательность логических операций будет лучше с точки зрения скорости / энергии / площади, чем сохранение и чтение / запись в два больших буфера.

Видео:Разложение вектора по базису. 9 класс.Скачать

Основные понятия теории графов G = (V, E),

Основные понятия теории графов G = (V, E), V – непустое множество вершин, Е» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_0.jpg» alt=»>Основные понятия теории графов G = (V, E), V – непустое множество вершин, Е» /> Основные понятия теории графов G = (V, E), V – непустое множество вершин, Е – произвольное множество ребер – пар (vi, vj) элементов из V, т. е. vi  V, vj  V, Е  V 2. Неориентированный Ориентированный (орграф)

Основные понятия теории графов Ребро е2  v1v3 имеет» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_1.jpg» alt=»>Основные понятия теории графов Ребро е2  v1v3 имеет» /> Основные понятия теории графов Ребро е2  v1v3 имеет концы v1 и v3. Ориентированное ребро (дуга) a4 = (v3, v2) имеет начало v3 и конец v2 (дуга a4 исходит из v3 и заходит в v2). В неориентированном графе v и ребро е инцидентны, если v – один из концов ребра е. В орграфе v и дуга а инцидентны, если v – либо начало, либо конец дуги а.

Основные понятия теории графов В неориентированном графе две вершины» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_2.jpg» alt=»>Основные понятия теории графов В неориентированном графе две вершины» /> Основные понятия теории графов В неориентированном графе две вершины смежны, если они инцидентны одному и тому же ребру. Окрестность N(v) вершины v – множество всех вершин, смежных v. |N(v)| = d(v) – степень вершины v. В орграфе: полуокрестность исхода N +(v): полуокрестность захода N ‑(v). Полустепени d+(v), d‑(v).

Основные понятия теории графов Графы конечные, графы бесконечные. Граф G = (V, E)» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_3.jpg» alt=»>Основные понятия теории графов Графы конечные, графы бесконечные. Граф G = (V, E)» /> Основные понятия теории графов Графы конечные, графы бесконечные. Граф G = (V, E) пустой, если Е  . Неориентированный граф полный, если любые две его вершины смежны. Kn – полный п-вершинный граф. G = (V,E) – дополнение графа G = (V, E), E = U E, где U – множество ребер полного графа с множеством вершин V. Двудольный граф G = (V, V, E) – для любого е = ху  Е: х  V, у  V. Дерево – связный граф без циклов.

Матричные представления графа Матрица смежности» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_4.jpg» alt=»>Матричные представления графа Матрица смежности» /> Матричные представления графа Матрица смежности

Матричные представления графа Матрица инцидентности» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_5.jpg» alt=»>Матричные представления графа Матрица инцидентности» /> Матричные представления графа Матрица инцидентности

Части графа Н = (W, F) – подграф графа G = (V, E),» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_6.jpg» alt=»>Части графа Н = (W, F) – подграф графа G = (V, E),» /> Части графа Н = (W, F) – подграф графа G = (V, E), если W  V, F  E. Н = (W, F) – остовный подграф, если W = V. Н = (W, F) – подграф, порожденный множеством W, если F содержит все ребра, оба конца которых принадлежат W. v1, e1, v2, e2, …, ek, vk + 1 – маршрут, ei = vivi + 1, i = 1, 2, …, k. Длина маршрута – количество ребер. Цепь – маршрут, все ребра которого различны. Простая цепь – цепь, все вершины которой различны. Расстояние между вершинами – длина кратчайшей цепи.

Части графа Маршрут v1, e1, v2, e2, … , ek, v1 – циклический.» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_7.jpg» alt=»>Части графа Маршрут v1, e1, v2, e2, … , ek, v1 – циклический.» /> Части графа Маршрут v1, e1, v2, e2, … , ek, v1 – циклический. Цикл – циклическая цепь. Простой цикл. Граф связный, если любые две его вершины связаны цепью. Компонента связности графа – связный подграф, не содержащийся ни в каком другом его связном подграфе. В орграфе: v1, а1, v2, а2, … , аk, vk + 1 – маршрут, если аi = (vi, vi + 1). Путь – маршрут, где все вершины различны. v1, а1, v2, а2, … , аk, v1 – контур. Вершина vj достижима из vi, если имеется путь из vi в vj. Орграф сильно связный, если любая вершина достижима из любой вершины.

Обобщения графов Мультиграф – граф, в котором любые две вершины могут быть» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_8.jpg» alt=»>Обобщения графов Мультиграф – граф, в котором любые две вершины могут быть» /> Обобщения графов Мультиграф – граф, в котором любые две вершины могут быть связаны любым количеством ребер (допускает кратные ребра). Взвешенный граф – вершины и/или ребра снабжаются весами в виде действительных чисел. Смешанный граф – наряду с элементами ориентированного графа (дугами) имеются элементы неориентированного графа (ребра). Гиперграф. Если ребром графа является пара вершин, то ребром гиперграфа может быть любое непустое подмножество множества вершин. От гиперграфа можно перейти к двудольному графу, долями которого являются множество вершин и множество ребер гиперграфа, а ребра показывают принадлежность вершин гиперграфа его ребрам.

Изоморфизм графов Два графа G = (V, Е) и H = (W,» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_9.jpg» alt=»>Изоморфизм графов Два графа G = (V, Е) и H = (W,» /> Изоморфизм графов Два графа G = (V, Е) и H = (W, F) изоморфны, если между их множествами вершин имеется взаимно однозначное соответствие, сохраняющее отношение смежности.  : V  W,  : E  F, и если (vi)  wk и (vj)  wl, то (vivj)  wkwl. v1 v2 v3 w1 w2 w3 w4 v4 v5 v6 w5 w6 (v1)  w1, (v2)  w3, (v3)  w6, (v4)  w4, (v5)  w5, (v6)  w2. (v1v4)  w1w4, (v1v5)  w1w5, (v1v6)  w1w2, (v2v4)  w3w4, (v2v5)  w3w5, (v2v6)  w2w3, (v3v4)  w4w6, (v3v5)  w5w6, (v3v6)  w2w6.

Изоморфизм графов Канонизация графа Величина а инвариантна относительно преобразования Т, если она» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_10.jpg» alt=»>Изоморфизм графов Канонизация графа Величина а инвариантна относительно преобразования Т, если она» /> Изоморфизм графов Канонизация графа Величина а инвариантна относительно преобразования Т, если она не меняет свое значение при преобразовании Т. а называется инвариантой относительно Т. В нашем случае Т – перенумерация вершин. Инварианты графа: число вершин, число ребер, число компонент связности… Инварианты вершины: степень, полустепени, число вершин, отстоящих от данной вершины на определенном расстоянии… Канонизация графа заключается в упорядочении его вершин по значениям инвариант. Пусть для вершин графа имеется система инвариант 1, 2, … , р. Считаем, что задано отношение частичного порядка на множестве вершин графа V = , такое, что vi vj, если k(vi)  k(vj) для некоторого k  <1, 2, … , р) и l(vi) = l(vj) для всех l  k.

Изоморфизм графов Канонизация графа Полная канонизация графа достигается, когда порядок оказывается» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_11.jpg» alt=»>Изоморфизм графов Канонизация графа Полная канонизация графа достигается, когда порядок оказывается» /> Изоморфизм графов Канонизация графа Полная канонизация графа достигается, когда порядок оказывается полным и строгим. Разобьем множество V вершин графа G на подмножества S1, S2, … , Sm, число т которых равно числу различных степеней вершин и в каждом из которых присутствуют вершины с одинаковой степенью. Инварианта вершины vi  V – вектор размерности т, компоненты которого соответствуют множествам S1, S2, … , Sm и значением j-й компоненты является число вершин из множества Sj, смежных с vi. Если в одном и том же Sk (k = 1, 2, … , m) оказались вершины с различными векторами, то разобьем это Sk так, чтобы в каждом из получившихся множеств оставались вершины с одинаковыми векторами, соответственно увеличив размерность векторов и придав их компонентам новые значения.

Изоморфизм графов Канонизация графа » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_12.jpg» alt=»>Изоморфизм графов Канонизация графа » /> Изоморфизм графов Канонизация графа v1 v2 v4 v3 v5 v6

Изоморфизм графов Пример однородных неизоморфных графов» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_13.jpg» alt=»>Изоморфизм графов Пример однородных неизоморфных графов» /> Изоморфизм графов Пример однородных неизоморфных графов

Циклы и разрезы Цикломатическое число графа Дерево – это связный граф,» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_14.jpg» alt=»>Циклы и разрезы Цикломатическое число графа Дерево – это связный граф,» /> Циклы и разрезы Цикломатическое число графа Дерево – это связный граф, число ребер которого на единицу меньше числа вершин. Дерево – это связный граф, не имеющий циклов. Дерево – это граф, в котором каждая пара вершин связана одной и только одной цепью. Лес – граф, каждая компонента связности которого является деревом. Пусть G – неориентированный граф с п вершинами, т ребрами и р компонентами связности. Остовное дерево – остовный подграф в виде дерева связного графа (р = 1). Число ребер в остовном дереве п – 1. Число ребер в остовном лесе п – р. (G)  m – n  p – цикломатическое число (G)  n – p – коцикломатическое число.

Циклы и разрезы Базис циклов Т – остовное дерево связного» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_15.jpg» alt=»>Циклы и разрезы Базис циклов Т – остовное дерево связного» /> Циклы и разрезы Базис циклов Т – остовное дерево связного графа G = (V, E). Добавление одного ребра из Е к Т приводит к появлению точно одного простого цикла. m – n  1 – число таких циклов в графе G. Оно совпадает с (G). Эти циклы независимы (каждый из них имеет ребро, не принадлежащее никакому другому). Фундаментальные циклы. Они составляют базис циклов графа G. Любой цикл, не принадлежащий базису, может быть выражен в виде линейной комбинации фундаментальных циклов. Всякий цикл графа G представим т-мерным булевым вектором, в котором i-я компонента имеет значение 1 или 0 в зависимости от того, принадлежит или нет i-е ребро данному циклу. Любой цикл можно выразить как покомпонентную сумму по модулю 2 векторов, представляющих фундаментальные циклы. Сумма по модулю 2: 0  0  0, 0  1  1, 1  0  1, 1  1  0.

Циклы и разрезы Базис циклов » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_16.jpg» alt=»>Циклы и разрезы Базис циклов » /> Циклы и разрезы Базис циклов v2 v3 е3 е5 е1 е4 е6 v4 е7 v1 е2 v5 Фундаментальные циклы: v1, е1, v2, е3, v3, е6, v5, е2, v1; v2, v3, v5; v3, v4, v5. е1е2е3е4е5е6е7 е1е2е3е4е5е6е7 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1

Циклы и разрезы Базис разрезов » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_17.jpg» alt=»>Циклы и разрезы Базис разрезов » /> Циклы и разрезы Базис разрезов v2 v3 е3 е5 е1 е4 е6 v4 е7 v1 е2 v5 Разрез графа – множество ребер, удаление которых увеличивает число компонент связности. Под разрезом будем понимать минимальный разрез, т.е. такой, что при удалении из него любого ребра он перестает быть разрезом. Фундаментальный разрез содержит одно и только одно ребро е, принадлежащее остовному дереву Т. Кроме е, он содержит все ребра, не принадлежащие Т, но входящие в фундаментальные циклы, содержащие е.

Циклы и разрезы Базис разрезов » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_18.jpg» alt=»>Циклы и разрезы Базис разрезов » /> Циклы и разрезы Базис разрезов v2 v3 е3 е5 е1 е4 е6 v4 е7 v1 е2 v5 Базис разрезов – множество фундаментальных разрезов. е1е2е3е4е5е6е7 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1

Циклы и разрезы Матрицы циклов и разрезов » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_19.jpg» alt=»>Циклы и разрезы Матрицы циклов и разрезов » /> Циклы и разрезы Матрицы циклов и разрезов v2 v3 е3 е5 е1 е4 е6 v4 е7 v1 е2 v5 Матрица фундаментальных циклов Матрица фундаментальных разрезов

Циклы и разрезы Матрицы циклов и разрезов Матрица фундаментальных» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_20.jpg» alt=»>Циклы и разрезы Матрицы циклов и разрезов Матрица фундаментальных» /> Циклы и разрезы Матрицы циклов и разрезов Матрица фундаментальных циклов Матрица фундаментальных разрезов

Доминирующие множества графа S – доминирующее множество (S  V), если S » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_21.jpg» alt=»>Доминирующие множества графа S – доминирующее множество (S  V), если S » /> Доминирующие множества графа S – доминирующее множество (S  V), если S  N(S)  V, где N(S)  . Если S – доминирующее множество некоторого графа G, то всякое S  S также является доминирующим. Минимальное доминирующее множество – ни одно его собственное подмножество не является доминирующим. Наименьшее доминирующее множество – имеет наименьшую мощность (G). (G) – число доминирования графа G. Задача о ферзях.

Доминирующие множества графа v2 » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_22.jpg» alt=»>Доминирующие множества графа v2 » /> Доминирующие множества графа v2 v3 v1 v4 v7 v6 v5 Строка vi матрицы представляет множество  N(vi). Минимальные доминирующие множества: , , , , , , , , , и .

Независимые множества графа S – независимое множество (S  V), если S » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_23.jpg» alt=»>Независимые множества графа S – независимое множество (S  V), если S » /> Независимые множества графа S – независимое множество (S  V), если S  N(S)  . Если S – независимое множество некоторого графа G, то всякое S  S также является независимым. Максимальное независимое множество – не является собственным подмножеством ни одного независимого множества. Наибольшее независимое множество – имеет наибольшую мощность (G). (G) – число независимости графа G. Задача о ферзях.

Независимые множества графа v2 » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_24.jpg» alt=»>Независимые множества графа v2 » /> Независимые множества графа v2 v3 v1 v4 v7 v6 v5 Максимальные независимые множества: , , , , ,

Независимые множества графа Нахождение всех максимальных независимых множеств V  Независимые множества графа Нахождение всех максимальных независимых множеств V  Независимые множества графа Нахождение всех максимальных независимых множеств V  – множество вершин графа G = (V, Е). G1, G2, … , Gn – последовательность порожденных подграфов: Gi = (Vi, Еi), где Vi = (i = 1, 2, … , n). S i = – совокупность всех максимальных независимых множеств графа Gi. К каждому Sji (j = 1, 2, … , ki) применяется формула S  (Sji N(vi  1))  .

Независимые множества графа Сколько всего может быть максимальных независимых множеств в графе с» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_26.jpg» alt=»>Независимые множества графа Сколько всего может быть максимальных независимых множеств в графе с» /> Независимые множества графа Сколько всего может быть максимальных независимых множеств в графе с п вершинами? 2 · 3k – 1, если п = 3k – 1; 3 · 3k – 1, если п = 3k; 4 · 3k – 1, если п = 3k + 1. …

Независимые множества графа Нахождение наибольшего независимого множества. Вершинное покрытие графа G = (V,» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_27.jpg» alt=»>Независимые множества графа Нахождение наибольшего независимого множества. Вершинное покрытие графа G = (V,» /> Независимые множества графа Нахождение наибольшего независимого множества. Вершинное покрытие графа G = (V, E) – множество В  V такое, что каждое ребро из Е инцидентно хотя бы одной вершине из В. Если В – наименьшее вершинное покрытие, то V B – наибольшее независимое множество. v2 е3 v3 е1 е4 е7 е5 v1 е2 е8 v4 е10 v7 е6 v6 е9 v5 В = , V B = .

Независимые множества графа Нахождение наибольшего независимого множества. «Жадный» алгоритм. » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_28.jpg» alt=»>Независимые множества графа Нахождение наибольшего независимого множества. «Жадный» алгоритм. » /> Независимые множества графа Нахождение наибольшего независимого множества. «Жадный» алгоритм. v3 v3 v2 v1 v4 v4 v5 v5 v6 v7 v7 v7 v8 v8 v8 v9 v9 v9

Независимые множества графа Нахождение наибольшего независимого множества. «Жадный» алгоритм. » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_29.jpg» alt=»>Независимые множества графа Нахождение наибольшего независимого множества. «Жадный» алгоритм. » /> Независимые множества графа Нахождение наибольшего независимого множества. «Жадный» алгоритм. v3 v2 v1 v4 v1 v2 v5 v6 v7 v6 v7 v6 v7 v8 v8 v8 v8 v9 v9 v9 v9

Раскраска графа Раскраска графа G = (V, Е) – такое разбиение множества» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_30.jpg» alt=»>Раскраска графа Раскраска графа G = (V, Е) – такое разбиение множества» /> Раскраска графа Раскраска графа G = (V, Е) – такое разбиение множества V на непересекающиеся подмножества V1, V2, … , Vk, что никакие две вершины из любого Vi (i = 1, 2, …, k) не смежны. Задача: раскрасить вершины графа G в минимальное число цветов. (G) – хроматическое число графа G (минимум k). Любое Vi (i = 1, 2, …, k) – независимое множество. Раскраска V1, V2, … , Vk – совокупность независимых множеств.

Раскраска графа Неточность «жадного» алгоритма видна на последовательности: » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_34.jpg» alt=»>Раскраска графа Неточность «жадного» алгоритма видна на последовательности: » /> Раскраска графа Неточность «жадного» алгоритма видна на последовательности: , , , … Граф G является k-хроматическим, если (G) = k. Т е о р е м а К ё н и г а. Непустой граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.

Раскраска графа Метод раскраски графа k – число задействованных цветов; А –» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_35.jpg» alt=»>Раскраска графа Метод раскраски графа k – число задействованных цветов; А –» /> Раскраска графа Метод раскраски графа k – число задействованных цветов; А – множество еще не раскрашенных вершин; В1, В2, … , Вk – совокупность подмножеств множества вершин V, такая, что Bi (i = 1, 2, … , k) содержит те и только те вершины из множества А, которые нельзя раскрасить в i-й цвет. 1. Имеется вершина v  A, такая, что v  Bi для всех i = 1, 2, … , k. v красится в (k + 1)-й цвет, удаляется из множества А и из всех Bi. Формируется Вk + 1 и k := k + 1. Если таких вершин несколько, из них выбирается та, для которой Вk + 1 имеет максимальную мощность. 2. Имеется вершина v  A и цвет i, такие, что v  Bi и N(v)  A  Bi. v красится в i-й цвет, удаляется из А и из всех Bj. В остальных случаях выбираются цвет i и вершина v из А такие, что v  Bi и приращение Bi минимально среди всех пар v, Bi (v  A, i = 1, 2, … , k). Вершина v красится в i-й цвет и удаляется из А из всех Bj.

Раскраска графа Метод раскраски графа » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_36.jpg» alt=»>Раскраска графа Метод раскраски графа » /> Раскраска графа Метод раскраски графа Цвет Вершины Bi 1 1 1 1 2 2 1 1 2 2,8 1 1,7 2 2,8 1 1,7 2 2,6,8 1 1,7 2 2,3,6,8 1 1,7 , 1. Имеется вершина v  A, такая, 2 2,3,6,8 что v  Bi для всех i = 1, 2, … , k. 1 1,7  2. Имеется вершина v  A и цвет i 2 2,3,6,8,10 такие, что v  Bi и N(v)  A  Bi 1 1,4,7 2 2,3,6,8,10 Результат: , , , . Точный алгоритм дает , , .

Обходы графа Эйлеровы цепи и циклы Задача о кёнигсбергских мостах (1736″ src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_37.jpg» alt=»>Обходы графа Эйлеровы цепи и циклы Задача о кёнигсбергских мостах (1736″ /> Обходы графа Эйлеровы цепи и циклы Задача о кёнигсбергских мостах (1736 г.) Эйлеров цикл содержит все ребра графа. Эйлерова цепь. Т е о р е м а Э й л е р а. Связный неориентированный граф имеет эйлеров цикл тогда и только тогда, когда степени всех его вершин четны. В связном неориентированном графе существует эйлерова цепь тогда и только тогда, когда он имеет не более двух вершин с нечетной степенью.

Обходы графа Эйлеровы цепи и циклы Эйлеров граф – граф, имеющий» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_38.jpg» alt=»>Обходы графа Эйлеровы цепи и циклы Эйлеров граф – граф, имеющий» /> Обходы графа Эйлеровы цепи и циклы Эйлеров граф – граф, имеющий эйлеров цикл. Алгоритм Флёри: 1. Идем из некоторой вершины по ребру и удаляем каждое пройденное ребро, помещая его в получаемую последовательность. Начальная вершина выбирается произвольно. 2. Отправляясь из очередной вершины, никогда не идем по ребру, удаление которого делает граф несвязным. Задача китайского почтальона: Каждому ребру ei графа G приписывается положительный вес с(ei) (расстояние). Требуется найти маршрут, проходящий через каждое ребро графа G по крайней мере один раз и такой, что сумма величин nic(ei) минимальна, где ni – число прохождений ребра еi.

Обходы графа Гамильтоновы цепи и циклы Цикл называется гамильтоновым, если» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_39.jpg» alt=»>Обходы графа Гамильтоновы цепи и циклы Цикл называется гамильтоновым, если» /> Обходы графа Гамильтоновы цепи и циклы Цикл называется гамильтоновым, если он проходит каждую вершину графа ровно один раз. Гамильтонова цепь – цепь, проходящая каждую вершину графа ровно один раз. Граф, содержащий гамильтонов цикл, называется гамильтоновым графом. v3 v1: v2, v4, v5, v6; (v1, v2, v3, v4, v6) v2: v1, v3, v4, v5; (v1, v2, v3, v4) v5 v4 v3: v2, v4, v5; (v1, v2, v3) v2 v4: v1, v2, v3, v6; (v1, v2, v3, v5) v5: v1, v2, v3; (v1, v2, v4) v6: v1, v4. (v1, v2, v4, v3, v5) v1 v6 (v1, v2, v4, v6) (v1, v2, v5, v3, v4, v6, v1)

Обходы графа Кратчайшие пути в графе Ребра графа G» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_40.jpg» alt=»>Обходы графа Кратчайшие пути в графе Ребра графа G» /> Обходы графа Кратчайшие пути в графе Ребра графа G = (V, E) взвешены действительными положительными числами. Вес ребра e = vivj будем считать его длиной l(e) = l(vivj). Найти цепь С минимальной длины, соединяющую вершины v1 и vn в графе G, т. е. такую цепь, для которой величина минимальна. Алгоритм Форда Каждой вершине vi  V припишем индекс (vi). При этом положим (v1)  0 и (vi)  +  для i  1. На каждом шаге находим такое ребро vivj, что (vi) – (vj)  l(vivj), и индекс (vi) заменяем на (vi) = (vj) + l(vivj). Шаги повторяются, пока находятся ребра, для которых выполняется неравенство (vi) – (vj)  l(vivj). Путь строим, начиная с vп и двигаясь обратно к v1. После вершины vi выбираем вершину vj чтобы выполнялось (vi) – (vj) = l(vivj).

Обходы графа Кратчайшие пути в графе » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_41.jpg» alt=»>Обходы графа Кратчайшие пути в графе » /> Обходы графа Кратчайшие пути в графе v2 10 v5 1 10 1 2 5 v3 v6 v1 10 4 2 v8 6 4 1 5 8 v4 3 v7 v1 v2 v3 v4 v5 v6 v7 v8 ______________________________ 0        1 10 6 11 14 9 16 13 15

Планарные графы Граф укладывается на некоторой поверхности, если его можно» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_42.jpg» alt=»>Планарные графы Граф укладывается на некоторой поверхности, если его можно» /> Планарные графы Граф укладывается на некоторой поверхности, если его можно так нарисовать на этой поверхности, что никакие два ребра не будут иметь общей точки, кроме, возможно, общей вершины. Граф планарный, если его можно уложить на плоскости. Плоский граф – граф, уложенный на плоскости. Грань плоского графа – область плоскости, ограниченная ребрами, любые две точки которой могут быть соединены линией, не пересекающей ребра графа. Грани внешняя и внутренние. Т е о р е м а Э й л е р а. Для всякого связного плоского графа, имеющего f1 f2 f3 п вершин, т ребер и f граней, имеет место соотношение п – т  f  2. (Формула Эйлера)

Планарные графы Максимальный планарный граф и простейшие непланарные графы » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_43.jpg» alt=»>Планарные графы Максимальный планарный граф и простейшие непланарные графы » /> Планарные графы Максимальный планарный граф и простейшие непланарные графы Т е о р е м а П о н т р я г и н а – К у р а т о в с к о г о. Необходимым и достаточным условием непланарности графа является любое из следующих условий: 1) в графе можно выделить пять вершин, каждая из которых связана цепью с любой другой из них, причем все эти цепи не пересекаются по ребрам; 2) в графе можно выделить два множества, состоящие из трех вершин каждое, так, что каждая вершина одного множества связана цепью со всеми вершинами другого множества, причем все эти цепи не пересекаются по ребрам.

Планарные графы Раскраска планарных графов (раскраска карт) Плоский граф» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_44.jpg» alt=»>Планарные графы Раскраска планарных графов (раскраска карт) Плоский граф» /> Планарные графы Раскраска планарных графов (раскраска карт) Плоский граф и его двойственный граф Раскраска граней плоского графа, при которой соседние грани раскрашиваются в различные цвета, эквивалентна раскраске вершин его двойственного графа. Гипотеза четырех красок доказана с помощью ЭВМ в 1976 г. 1 482 конфигурации. 2 000 ч машинного времени.

Комбинаторные задачи и методы комбинаторного поиска Три типа комбинаторных задач: Задачи подсчета» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_45.jpg» alt=»>Комбинаторные задачи и методы комбинаторного поиска Три типа комбинаторных задач: Задачи подсчета» /> Комбинаторные задачи и методы комбинаторного поиска Три типа комбинаторных задач: Задачи подсчета – сколько конфигураций определенного вида? Перечислительные задачи – получение всех конструкций определенного вида. Оптимизационные комбинаторные задачи – получение конструкции, обладающей оптимальным значением некоторого параметра среди всех конструкций данного вида.

Комбинаторные задачи и методы комбинаторного поиска Задачи подсчета: Число размещений (разместить п» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_46.jpg» alt=»>Комбинаторные задачи и методы комбинаторного поиска Задачи подсчета: Число размещений (разместить п» /> Комбинаторные задачи и методы комбинаторного поиска Задачи подсчета: Число размещений (разместить п предметов по т ящикам) U(m, n) = тп. Число перестановок Р(n) = п · (п – 1) · … · 2 · 1 = п!. Число размещений без повторений А(m, n) = т · (т – 1) · … · (т – п + 1) = Число сочетаний

Комбинаторные задачи и методы комбинаторного поиска Особенности оптимизационных комбинаторных задач Решение» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_47.jpg» alt=»>Комбинаторные задачи и методы комбинаторного поиска Особенности оптимизационных комбинаторных задач Решение» /> Комбинаторные задачи и методы комбинаторного поиска Особенности оптимизационных комбинаторных задач Решение комбинаторной задачи сводится зачастую к полному перебору различных вариантов. Велика зависимость трудоемкости задачи от размера области возможных решений. Множество, среди элементов которого отыскивается решение, всегда конечно. Реализовав полный перебор, либо найдем решение, либо убедимся в том, что решения нет.

Комбинаторные задачи и методы комбинаторного поиска Вычислительная сложность оптимизационных задач Трудоемкость» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_48.jpg» alt=»>Комбинаторные задачи и методы комбинаторного поиска Вычислительная сложность оптимизационных задач Трудоемкость» /> Комбинаторные задачи и методы комбинаторного поиска Вычислительная сложность оптимизационных задач Трудоемкость алгоритма оценивается функцией f(n), где п – натуральное число, выражающее объем исходных данных. f(n) = O(g(n)), если найдется такая константа с, что f(n)  сg(n) для любого n  0, где g(n)  некоторая конкретная функция от n. О(1)  трудоемкость не зависит от объема исходных данных. О(п)  алгоритм линейный. О(пb)  алгоритм полиномиальный. g(n) = 2п  алгоритм обладает неполиномиальной, или экспоненциальной, сложностью.

Комбинаторные задачи и методы комбинаторного поиска Связь трудоемкости алгоритма с максимальным размером задачи,» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_52.jpg» alt=»>Комбинаторные задачи и методы комбинаторного поиска Связь трудоемкости алгоритма с максимальным размером задачи,» /> Комбинаторные задачи и методы комбинаторного поиска Связь трудоемкости алгоритма с максимальным размером задачи, решаемой за единицу времени

Комбинаторные задачи и методы комбинаторного поиска Связь размера задачи, решаемой за заданное время,» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_54.jpg» alt=»>Комбинаторные задачи и методы комбинаторного поиска Связь размера задачи, решаемой за заданное время,» /> Комбинаторные задачи и методы комбинаторного поиска Связь размера задачи, решаемой за заданное время, с быстродействием вычислительной машины

Комбинаторные задачи и методы комбинаторного поиска Комбинаторный поиск представляется как обход дерева поиска.» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_56.jpg» alt=»>Комбинаторные задачи и методы комбинаторного поиска Комбинаторный поиск представляется как обход дерева поиска.» /> Комбинаторные задачи и методы комбинаторного поиска Комбинаторный поиск представляется как обход дерева поиска. Вершины соответствуют ситуациям, возникающим в процессе поиска, ребра – отдельным шагам процесса. Корень дерева – вершина, соответствующая начальной ситуации. Выделение корня придает дереву ориентацию, при которой все пути ведут из корня в остальные вершины. Некоторые ситуации соответствуют решениям.

Задача о кратчайшем покрытии Дано: А = ; В1, В2,» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_57.jpg» alt=»>Задача о кратчайшем покрытии Дано: А = ; В1, В2,» /> Задача о кратчайшем покрытии Дано: А = ; В1, В2, …, Вт; Bi  A, i = 1, 2, …, m, причем В1  В2  …  Вт = А. Требуется выделить так, чтобы выполнялось при минимальном k. Матричная формулировка: требуется найти наименьшее множество строк заданной булевой матрицы, чтобы каждый ее столбец имел единицу хотя бы в одной строке из этого множества.

Задача о кратчайшем покрытии Для матрицы » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_58.jpg» alt=»>Задача о кратчайшем покрытии Для матрицы » /> Задача о кратчайшем покрытии Для матрицы – кратчайшее покрытие.

Задача о кратчайшем покрытии Алгоритмы решения «Жадный» алгоритм повторяет операцию: выбор строки с» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_59.jpg» alt=»>Задача о кратчайшем покрытии Алгоритмы решения «Жадный» алгоритм повторяет операцию: выбор строки с» /> Задача о кратчайшем покрытии Алгоритмы решения «Жадный» алгоритм повторяет операцию: выбор строки с максимальным числом единиц, включение ее в решение и удаление ее и покрываемых ею столбцов из матрицы. Для матрицы находит покрытие , хотя кратчайшее – . Минимаксный алгоритм повторяет операцию: выбор столбца с минимальным числом единиц, выбор покрывающей его строки с максимальным числом единиц, включение ее в решение и удаление ее и покрываемых ею столбцов из матрицы. Точный алгоритм совершает обход дерева поиска.

Задача о кратчайшем покрытии Обход дерева поиска » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_60.jpg» alt=»>Задача о кратчайшем покрытии Обход дерева поиска » /> Задача о кратчайшем покрытии Обход дерева поиска a1 B2 B5 a3 B1 B3 B5 a4 a4 [1] B4 B4 Одно из покрытий (не обязательно кратчайшее) – B1, B2, B4.

Задача о кратчайшем покрытии Обход дерева поиска. Правила редукции 1. Если столбец k» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_61.jpg» alt=»>Задача о кратчайшем покрытии Обход дерева поиска. Правила редукции 1. Если столбец k» /> Задача о кратчайшем покрытии Обход дерева поиска. Правила редукции 1. Если столбец k имеет единицы везде, где имеет единицы столбец l, то столбец k можно удалить.  2. Если строка i имеет единицы везде, где имеет единицы строка j, то строку j можно удалить. 

Булевы функции х1, х2, . , хn – булевы переменные, принимают значения» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_62.jpg» alt=»>Булевы функции х1, х2, . , хn – булевы переменные, принимают значения» /> Булевы функции х1, х2, . , хn – булевы переменные, принимают значения из . х = (х1, х2, . , хn) – n‑компонентный булев вектор. п – длина вектора, или размерность. 2п – число всех различных векторов, состоящих из констант 0 и 1 и образующих булево пространство . f : n  – булева функция. М = n – область определения, – область значений. Mf1 – область, где функция f принимает значение 1. Mf0 – область, где функция f принимает значение 0. Mf1 – характеристическое множество функции f.

Булевы функции Способы задания Таблица истинности:» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_63.jpg» alt=»>Булевы функции Способы задания Таблица истинности:» /> Булевы функции Способы задания Таблица истинности:

Булевы функции Способы задания Матричный способ – перечисление элементов Mf1: » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_64.jpg» alt=»>Булевы функции Способы задания Матричный способ – перечисление элементов Mf1: » /> Булевы функции Способы задания Матричный способ – перечисление элементов Mf1: Более компактное задание:

Булевы функции Способы задания Матричный способ (интервальный) – троичная матрица: » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_65.jpg» alt=»>Булевы функции Способы задания Матричный способ (интервальный) – троичная матрица: » /> Булевы функции Способы задания Матричный способ (интервальный) – троичная матрица: Булевы векторы а = (а1, а2, … , ап) и b = (b1, b2, … , bп) находятся в отношении  (а  b, а меньше b), если аi  bi для любого i = 1, 2, … , п, в противном случае они несравнимы. При этом считается, что 0  1. Интервал булева пространства – множество векторов, среди которых есть минимальный и максимальный векторы, а также все векторы, меньшие максимального и большие минимального. Интервал представляется троичным вектором.

Булевы функции Способы задания Векторное задание – булев вектор,» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_67.jpg» alt=»>Булевы функции Способы задания Векторное задание – булев вектор,» /> Булевы функции Способы задания Векторное задание – булев вектор, компоненты которого соответствуют наборам значений аргументов. Функция задается вектором (0 1 1 1 0 1 0 1).

Булевы функции Алгебраический способ задания булевых функций. Карты Карно. » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_68.jpg» alt=»>Булевы функции Алгебраический способ задания булевых функций. Карты Карно. » /> Булевы функции Алгебраический способ задания булевых функций. Карты Карно. Функции полностью определенные. Функции не полностью определенные, или частичные. Частичная булева функция делит булево пространство на три части: Mf1, Mf0 и Mf –. Обычно задаются Mf1 и Mf0.

Булевы функции Векторная форма задания булевой функции позволяет легко определить число» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_69.jpg» alt=»>Булевы функции Векторная форма задания булевой функции позволяет легко определить число» /> Булевы функции Векторная форма задания булевой функции позволяет легко определить число булевых функций от п переменных – это число всех 2n-компонентных булевых векторов. – число булевых функций от п переменных. Функция f(х1, х2, . , хn) существенно зависит от аргумента хi, если f(х1, х2, . , хi – 1, 0, хi + 1, … , хn)  f(х1, х2, . , хi – 1, 1, хi + 1, … , хn). хi – существенный аргумент. В противном случае хi – несущественный, или фиктивный аргумент.

Булевы функции Элементарные булевы функции и алгебраические формы Элементарные булевы функции» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_70.jpg» alt=»>Булевы функции Элементарные булевы функции и алгебраические формы Элементарные булевы функции» /> Булевы функции Элементарные булевы функции и алгебраические формы Элементарные булевы функции – функции от одной и двух переменных. Булевы функции от одной переменной Из таблицы видно, что 0 = 1 и1 = 0.

Булевы функции Булевы функции от двух переменных» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_72.jpg» alt=»>Булевы функции Булевы функции от двух переменных» /> Булевы функции Булевы функции от двух переменных

Булевы функции Булевы функции от двух переменных » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_74.jpg» alt=»>Булевы функции Булевы функции от двух переменных » /> Булевы функции Булевы функции от двух переменных Все представленные операции составляют алгебру логики.

Булевы функции Алгебраическое задание Любая булева функция от любого числа аргументов» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_75.jpg» alt=»>Булевы функции Алгебраическое задание Любая булева функция от любого числа аргументов» /> Булевы функции Алгебраическое задание Любая булева функция от любого числа аргументов может быть представлена формулой алгебры логики. Формулу, содержащую более чем одну операцию, можно рассматривать как суперпозицию элементарных функций, т.е. использование одних функций в качестве аргументов других функций. Определение формулы: 1) каждый символ переменной есть формула; 2) если А и В – формулы, то формулами являются А и (А  В), где  – любая операция алгебры логики; 3) других формул нет. Приоритеты: 1)  ; 2) ; 3)  и ; 4)

Булевы функции Вычисление по формуле » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_76.jpg» alt=»>Булевы функции Вычисление по формуле » /> Булевы функции Вычисление по формуле f(x1, x2, x3) = А = В – равносильность формул А и В.

Булева алгебра Булева алгебра содержит только три операции: ,  и .» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_79.jpg» alt=»>Булева алгебра Булева алгебра содержит только три операции: ,  и .» /> Булева алгебра Булева алгебра содержит только три операции: ,  и . Основные законы булевой алгебры: Коммутативность: х  у  у  х; х у  у х. Ассоциативность: х  (у  z)  (x  y)  z; x (y z)  (x y) z. Дистрибутивность: x (y  z)  x y  x z; x  y z  (x  y) (x  z). Идемпотентность: x  x  x; x x  x.

Булева алгебра Основные законы булевой алгебры: Законы де Моргана: » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_84.jpg» alt=»>Булева алгебра Основные законы булевой алгебры: Законы де Моргана: » /> Булева алгебра Основные законы булевой алгебры: Законы де Моргана: ; =x y. Законы операций с константами: x  0  x; x 1  x; x 0  0; x  1  1; х х  1; хх  0. Закон двойного отрицания: . Принцип двойственности.

Булева алгебра Вывод формул х  х у  х и » src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_85.jpg» alt=»>Булева алгебра Вывод формул х  х у  х и » /> Булева алгебра Вывод формул х  х у  х и х (х  у)  х: х  х у  х 1  х у  х (1  у)  х1 = х; х (х  у)  х х  х у  х  х у  х. Все операции алгебры логики можно выразить через булевы операции: х  у = xy x y; х

у =xy  x y; х  у =x  y. Преобразование формулы алгебры логики в булеву формулу: ((х  у)  (х  z))y = = (x  y  xz x z)y = (x  y z)y =xy yz.

Интерпретации алгебры логики Булева алгебра множеств: Константам 1 и 0 соответствуют множества U и» src=»https://present5.com/presentacii/20170504/59-dm.ppt_images/59-dm.ppt_86.jpg» alt=»>Интерпретации алгебры логики Булева алгебра множеств: Константам 1 и 0 соответствуют множества U и» /> Интерпретации алгебры логики Булева алгебра множеств: Константам 1 и 0 соответствуют множества U и . Операциям  ,  и  соответствуют  ,  и  Алгебра событий, используемая в теории вероятностей: Операции отрицания (), объединения () и пересечения (). А  В или АВ – произведение независимых событий, А  В – сумма несовместимых событий. Исчисление высказываний: a – «не а». a  b – «a либо b». a  b – «a и b». a

b – «a равносильно b». a  b – «a или b». a  b – «если a, то b».

Видео:89. Разложение вектора по двум неколлинеарным векторамСкачать

Операции над n-мерными векторами: сложение, умножение, свойства

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

n -вектор – упорядоченный набор n действительных чисел.

Записывается в виде строки a = ( a 1 , a 2 , . . . , a n ) или столбца a = a 1 a 2 ⋮ a n , где

a i – координаты n-вектора, обозначаемые латинскими буквами и записываемые в скобках.

Размерность n -вектора – это количество его координат. Например, задан n -мерный вектор b → с координатами (2, -5, 3, 9). Заданный вектор является четырёхмерным.

Равные n -векторы – n -векторы, имеющие одну и ту же размерность, а также равенство одноименных координат.

Нулевой вектор – вектор, у которого все координаты равны нулю: 0 = ( 0 , 0 , . . , 0 )

Противоположные векторы – векторы с координатами, равными по модулю, но противоположными по знаку. Например,

a = ( a 1 , a 2 , . . . , a n )

— a = ( — a 1 , — a 2 , . . . , — a n )

Над n -мерными векторами возможно проведение операций сложения и умножения на число.

Видео:Компланарны ли векторы: a=(2;5;8), b=(1;-3;-7) и c=(0;5;10)?Скачать

Сложение n-векторов

Результатом сложения двух n -мерных векторов будет вектор, координаты которого являются суммой соответствующих координат заданных векторов.

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

Исходные данные: a = ( a 1 , a 2 , . . . , a n ) и a = ( b 1 , b 2 , . . . , b n ) .

Результатом будет вектор a + b = ( a 1 + b 1 , a 2 + b 2 , . . . , a n + b n ) .

Операция вычитания отдельно не рассматривается, поскольку по сути разностью векторов a и b является сумма векторов а и – b .

Видео:#вектор Разложение вектора по ортам. Направляющие косинусыСкачать

Умножение n-вектора на число

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

Исходные данные: a = ( a 1 , a 2 , . . . , a n ) и число λ .

Результатом произведения будет:

λ · a = ( λ · a 1 , λ · a 2 , . . . , λ · a n )

Множество всех n -векторов с производимыми действиями умножения на число и сложения составляют линейное пространство.

Видео:§20 Нахождение объёма параллелипипедаСкачать

Операции над 2-мерными и 3-мерными векторами

Операции над 2-мерными и 3-мерными векторами полностью сопоставимы с аналогичными операциями над векторами-геометрическими объектами. По сути координаты двухмерных и трехмерных векторов являются координатами вектора на плоскости или в пространстве в прямоугольной системе координат.

Видео:Три способа упрощения логической функцииСкачать

Свойства операций над n-мерными векторами

Исходные данные: векторы a = ( a 1 , a 2 , . . . , a n ) , b = ( b 1 , b 2 , . . . , b n ) , c = ( c 1 , c 2 , . . . , c n ) и действительные или комплексные числа λ , μ .

Свойство коммутативности: a + b = b + a .
Свойство ассоциативности: ( a + b ) + c = a + ( b + c ) .
Свойство использования нейтрального элемента по сложению (нулевой вектор): a + 0 = a .
Свойство использования нейтрального элемента по умножению (число, равное 1): 1 · а = а

Любой ненулевой вектор а имеет противоположный вектор — а и верным является равенство:

Сочетательное свойство умножения: ( λ · μ ) · a = λ · ( μ · a ) .

Первое распределительное свойство: ( λ + μ ) · a = λ · a + μ · a .

Второе распределительное свойство: λ · ( a + b ) = λ · a + λ · b .

Рассмотри некоторые примеры по теме.

Исходные данные: векторы a = ( 1 , 2 , 7 , 0 ) , b = ( 1 2 , — 1 , ln 5 , 2 . 3 )

Необходимо найти сумму и разность векторов.

Решение

Заданные вектора имеют одинаковую размерность, следовательно, операция сложения выполнима. Для этого найдем сумму координат векторов:

a + b = ( 1 , 2 , 7 , 0 ) + ( 1 2 , — 1 , ln 5 , 2 . 3 ) = = ( 1 + 1 2 , 2 + ( — 1 ) , 7 + ln 5 , 0 + 2 . 3 ) = = ( 3 2 , 2 — 1 , 7 + ln 5 , 2 . 3 )

Разницей исходных векторов будет являться сумма векторов a и b · ( — 1 ) :

a — b = a + ( — 1 ) · b = ( 1 , 2 , 7 , 0 ) + ( — 1 ) · ( 1 2 , — 1 , ln 5 , 2 . 3 )

Выполним умножение вектора на число:

a — b = ( 1 , 2 , 7 , 0 ) + ( — 1 ) · ( 1 2 , — 1 , ln 5 , 2 . 3 ) = = ( 1 , 2 , 7 , 0 ) + ( ( — 1 ) · 1 2 , ( — 1 ) · ( — 1 ) , ( — 1 ) · ln 5 , ( — 1 ) · 2 . 3 ) = = ( 1 , 2 , 7 , 0 ) + ( — 1 2 , 1 , ln 1 5 , — 2 . 3 )

И совершим действие сложения:

a — b = ( 1 , 2 , 7 , 0 ) + ( — 1 2 , 1 , ln 1 5 , — 2 . 3 ) = = ( 1 + ( — 1 2 ) , 2 + 1 , 7 + ln 1 5 , 0 + ( — 2 . 3 ) ) = = ( 1 2 , 2 + 1 , 7 + ln 1 5 , — 2 . 3 )

Ответ:

a + b = ( 3 2 , 2 — 1 , 7 + ln 1 5 , 2 . 3 ) a — b = ( 1 2 , 2 + 1 , 7 + ln 1 5 , — 2 . 3 )

Исходные данные: векторы a = ( 1 , 2 , 7 , 0 ) , b = ( 1 2 , — 1 , ln 5 , 2 . 3 )

Необходимо найти вектор: a — 2 · ( b + 3 · a )

Решение

Упростим выражение, опираясь на свойства операций над векторами:

a — 2 · ( b + 3 · a ) = a — 2 · b — 6 · a = — 5 · a + ( — 2 ) · b

Определим координаты полученного вектора:

— 5 · a + ( — 2 ) · b = = — 5 · ( 1 , 2 , 7 , 0 ) + ( — 2 ) ( 1 2 , — 1 , ln 5 , 2 . 3 ) = = ( ( — 5 ) · 1 , ( — 5 ) · 2 , ( — 5 ) · 7 , ( — 5 ) · 0 ) + + ( ( — 2 ) · 1 2 , ( — 2 ) · ( — 1 ) , ( — 2 ) · ln 5 , ( — 2 ) · 2 . 3 ) = = ( — 5 , — 5 2 , — 35 , 0 ) + ( — 1 , 2 , ln 1 25 , — 4 . 6 ) = = ( — 5 + ( — 1 ) , — 5 2 + 2 , — 35 + ln 1 25 , 0 + ( — 4 . 6 ) ) = = ( — 6 , — 5 2 + 2 , — 35 + ln 1 25 , — 4 . 6 )

Ответ:

a — 2 · ( b + 3 · a ) = ( — 6 , — 5 2 + 2 , — 35 + ln 1 25 , — 4 . 6 )

Исходные данные: векторы с = 1 2 — 3 , d = 0 0 3 , e = — 1 — 1 1

Необходимо определить координаты вектора: c + d + 2 e

Решение

Выполним операцию умножения вектора е на число 2, а затем найдем сумму:

c + d + 2 · e = 1 2 — 3 + 0 0 3 + 2 · — 1 — 1 1 = = 1 2 — 3 + 0 0 3 + 2 · ( — 1 ) 2 · ( — 1 ) 2 · 1 = = 1 2 — 3 + 0 0 3 + — 2 — 2 2 = = 1 + 0 + ( — 2 ) 2 + 0 + ( — 2 ) — 3 + 3 + 2 = — 1 0 2

Ответ: c + d + 2 · e = — 1 0 2

Исходные данные: векторы a = ( 1 , 2 , 7 , 0 ) , b = ( 1 2 , — 1 , ln 5 , 2 . 3 ) , f = ( 4 , 11 , 21 )

Необходимо найти вектор: 3 · a + 2 · b — 7 · ( a + f )

Решение

Исходные векторы имеют разную размерность ( а и f ), поэтому выполнить необходимые операции не представляется возможным.

Ответ: невозможно выполнить указанные действия с заданными векторами.