Линейный оператор

2013-06-11T17:48:55Z

89.163.5.56: /* Линейный оператор проектирования */

{{Определение
|definition=Пусть <tex>X</tex> и <tex>Y</tex> - линейные пространства над полем <tex>F</tex>. Отображение <tex>A:X \rightarrow Y</tex> называется линейным оператором, если <tex>\forall x_1,x_2 \in X</tex>, <tex>\forall \lambda \in F</tex>:
* <tex>A(x_1+x_2)=A(x_1)+A(x_2)</tex>
* <tex>A(\lambda \cdot x_1) = \lambda \cdot A(x_1)</tex>
}}

NB: Гомоморфизм
{{Определение
|definition=Линейный оператор <tex>A:X \rightarrow X</tex> называется автоморфизмом.
}}
NB: <tex>A(x) = Ax</tex>
{{Определение
|definition=<tex>A,B:X \rightarrow Y</tex>, <tex>A=B</tex>, если <tex>\forall x \in X:Ax = Bx</tex>
}}
{{Определение
|definition=<tex>O</tex> называется нулевым оператором, если <tex>\forall x \in X:Ox=Oy</tex>
}}
== Примеры ==
=== Тождественный оператор ===
<tex>I:X \rightarrow X</tex> по формуле <tex>Ix=x</tex>
=== Линейный оператор проектирования ===
<tex>X=L1 + L2</tex>

<tex>P_{L_1}^{||L_2}:X \rightarrow L_1</tex>

<tex>P_{L_2}^{||L1}:X \rightarrow L_2</tex>

NB: <tex>P_{L_{1,2}}^{||L_{2,1}}:X \rightarrow X</tex> (<tex>L_1</tex> и <tex>L_2</tex> - п.п. <tex>X</tex>)

=== Оператор дифференцирования ===
Пусть <tex>X=P_n; D:P_n \rightarrow P_{n-1}</tex>
по формуле <tex>(Dp)(t)={dp(t) \over dt} = p^{'}(t)</tex>
=== Интегральный оператор ===
Пусть <tex>X=C(a,b)</tex>
<tex>K(s,t)</tex>
<tex>s \in (a,b)</tex>
<tex>t \in (a,b)</tex>

<tex>(Bf)(s) = integral_a^b K(s,t) \cdot f(t) \ cdot dt</tex>

<tex>B:C(a,b) \rightarrow C(a,b)</tex>

== Матрица линейного оператора ==
Пусть <tex>A:X->Y</tex>

Пусть п.п. <tex>X \leftarrow \{e_k\}_{k=1}^n, dim X=n</tex>

Пусть п.п. <tex>Y \leftarrow \{h_i\}_{i=1}^m, dim Y = m</tex>

<tex>m != n</tex>

<tex>Ae_k=\displaystyle \sum_{i=1}^m \alpha_k^i \cdot h_i = A=||\alpha_k^i||(k=1,...,n)</tex>

<tex>
A=
\begin{pmatrix}
\alpha_1^1 & \cdots & \alpha_n^1 \\
\alpha_1^2 & \cdots & \alpha_n^2 \\
\cdots & \cdots & \cdots \\
\alpha_1^m & \cdots & \alpha_n^m \\
\end{pmatrix}
</tex>

== Примеры ==
=== Нулевой оператор ===
<tex>
O_{[m \ times n]}=
\begin{pmatrix}
0 & \cdots & 0 \\
\cdots & \cdots & \cdots \\
0 & \cdots & 0 \\
\end{pmatrix}
</tex>
=== Оператор дифференцирования ===
<tex>D:P_n \rightarrow P_{n-1}</tex>

<tex>\{1,t,t^2,...,t^n\}</tex>

<tex>
D=
\begin{pmatrix}
0 & 1 & 0 & 0 & \cdots & 0 \\
0 & 0 & 2 & 0 & \cdots & 0 \\
0 & 0 & 0 & 3 &\cdots & 0 \\
\cdots & \cdots & \cdots & \cdots &\cdots & \cdots \\
0 & 0 & 0 & 0 &\cdots & n \\
0 & 0 & 0 & 0 & \cdots & 0 \\
\end{pmatrix}
</tex>

Декартово дерево

2012-04-11T11:06:44Z

89.163.5.56: /* Реализация №1: */

''Эта статья про Курево''

'''Декартово дерево''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: <tex>treap (tree+heap)</tex> и дерамида (дерево+пирамида), так же существует название курево (куча + дерево).

Более строго, это структура данных, которая хранит пары <tex> (X,Y) </tex> в виде бинарного дерева таким образом, что она является бинарным деревом поиска по <tex>x</tex> и бинарной пирамидой по <tex>y</tex>. Предполагая, что все <tex>X</tex> и все <tex>Y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(X_0,Y_0)</tex>, то у всех элементов в левом поддереве <tex>X < X_0</tex>, у всех элементов в правом поддереве <tex> X > X_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> Y < Y_0</tex>.

Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.

== Операция split ==
[[file:split.png|thumb|400px|Операция split]]

Операция <tex>\mathrm{split}</tex> (''разрезать'') позволяет сделать следующее: разрезать декартово дерево <tex>T</tex> по ключу
<tex>x</tex> и получить два других декартовых дерева: <tex>T_1</tex> и <tex>T_2</tex>, причем в <tex>T_1</tex>
находятся все ключи дерева <tex>T</tex>, не большие <tex>x</tex>, а в <tex>T_2</tex> {{---}} большие <tex>x</tex>.

<tex>\mathrm{split}(T, x) \to \{T_1, T_2\}</tex>.

Эта операция устроена следующим образом.

Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня.
Посмотрим, как будут устроены результирующие деревья <tex>T_1</tex> и <tex>T_2</tex>:
* <tex>T_1</tex>: левое поддерево <tex>T_1</tex> совпадёт с левым поддеревом <tex>T</tex>. Для нахождения правого поддерева <tex>T_1</tex>, нужно разрезать правое поддерево <tex>T</tex> на <tex>T^R_1</tex> и <tex>T^R_2</tex> по ключу <tex>x</tex> и взять <tex>T^R_1</tex>.
* <tex>T_2</tex> совпадёт с <tex>T^R_2</tex>.

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

Оценим время работы операции <tex>\mathrm{split}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{split}</tex> для
дерева хотя бы на один меньшей высоты и делается ещё <tex>\mathcal{O}(1)</tex> операция. Тогда итоговая трудоёмкость этой операции
равна <tex>\mathcal{O}(h)</tex>, где <tex>h</tex> {{---}} высота дерева. Так как высота декартова дерева {{---}}
<tex>\mathcal{O}(\log n)</tex>, то и операция <tex>\mathrm{split}</tex> работает за <tex>\mathcal{O}(\log n)</tex>.

== Операция merge ==
[[file:merge.png|thumb|400px|Операция merge]]

Рассмотрим вторую операцию с декартовыми деревьями {{---}} <tex>\mathrm{merge}</tex>(''слить'').

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

<tex>\mathrm{merge}(T_1, T_2) \to T</tex>

Рассмотрим принцип работы этой операции. Пусть нужно слить деревья <tex>T_1</tex> и <tex>T_2</tex>.
Тогда, очевидно, у результирующего дерева <tex>T</tex> есть корень.
Корнем станет вершина из <tex>T_1</tex> или <tex>T_2</tex> с наибольшим ключом <tex>y</tex>. Но вершина с самым большим <tex>y</tex> из всех вершин деревьев
<tex>T_1</tex> и <tex>T_2</tex> может быть только либо корнем <tex>T_1</tex>, либо корнем <tex>T_2</tex>.
Рассмотрим случай, в котором корень <tex>T_1</tex> имеет больший <tex>y</tex>, чем корень <tex>T_2</tex>.
Случай, в котором корень <tex>T_2</tex> имеет больший <tex>y</tex>, чем корень <tex>T_1</tex>, симметричен этому.

Если <tex>y</tex> корня <tex>T_1</tex> больше <tex>y</tex> корня <tex>T_2</tex>, то он и будет являться корнем. Тогда левое поддерево
<tex>T</tex> совпадёт с левым поддеревом <tex>T_1</tex>. Справа же нужно подвесить объединение правого поддерева
<tex>T_1</tex> и дерева <tex>T_2</tex>.

Рассуждая аналогично операции <tex>\mathrm{split}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex>
равна <tex>\mathcal{O}(\log n)</tex>.

== Операция add ==
Операция <tex>\mathrm{add}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет.

===Реализация №1:===
# Разобьём наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{split}(T, k.x) \to \{T_1, T_2\}</tex>.
# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{merge}(T_1, k) \to T_1</tex>.
# Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{merge}(T_1, T_2) \to T</tex>.

=== Реализация №2: ===
Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>. Мы нашли позицию, куда будем вставлять наш элемент. Теперь вызываем <tex>\mathrm{split }(T, k.x) \to \{T_1, T_2\}</tex> от найденного элемента (от элемента вместе со всем его поддеревом), и возвращаемые ею <tex>T_1</tex> и <tex>T_2</tex> записываем в качестве левого и правого сына добавляемого элемента.

== Операция remove ==
Операция <tex>\mathrm{remove}(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.

===Реализация №1:===

# Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{split }(T, k.x) \to \{T_1, T_2\}</tex>.
# Теперь отделяем от первого дерева элемент <tex>x</tex>, опять таки разбивая по ключу <tex>x</tex>, то есть <tex>\mathrm{split }(T_1, k.x - \varepsilon) \to \{T_1, T_3\}</tex>.
# Сливаем первое дерево со вторым, то есть <tex>\mathrm{merge }(T_1, T_2) \to T</tex>.

===Реализация №2:===
Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), ища удаляемый элемент. Найдя элемент, мы просто вызываем <tex>merge</tex> его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента, то есть <tex>\mathrm{merge }(T.l, T.t) \to T</tex>.

== Литература ==
Todo

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

Викиконспекты - Вклад участника [ru]

Линейный оператор

Декартово дерево