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

Целочисленный двоичный поиск

2013-10-06T20:54:50Z

79.175.1.33: /* Принцип работы */

{{Определение
|definition=
'''Целочисленный двоичный поиск (бин. поиск)''' - алгоритм поиска объекта по заданному признаку во множестве объектов, упорядоченных по тому же самому признаку.
}}

== Формулировка задачи ==
Пусть нам дан упорядоченный массив, состоящий только из целочисленых элементов. Нам надо найти в нем индекс, по которому находится искомый элемент, или же мы можем находить интервалы вхождения искомого элемента. Для этой задачи мы и можем использовать двоичный поиск.

==Принцип работы==
Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остается та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие - это левосторонний/правосторонний двоичный поиск.

== Правосторонний/левосторонний целочисленный двоичный поиск ==
Когда мы ищем правосторонним бин. поиском, то он возвращает индекс самого правого вхождения заданного значения х. 
Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения х. 
Это разделение помогает находить количество подряд идущих равных значений. 
Например: 
Задан отсортированный массив [1, 2, 2, 2, 2, 3, 5, 8, 9, 11] 
Правосторонний поиск двойки выдаст в результате 5, в то время как левосторонний выдаст 2. 
От сюда следует, что количество подряд идущих двоек равно длине отрезка [2;5] = 4. 
Если искомого элемента нету, то правосторонний поиск выдаст минимальный элемент, больший искомого, а левосторонний наоборот, максимальный элемент, меньший искомого.

== Алгоритм двоичного поиска ==
[[Файл:shcemebinsearch.png|350px|thumb|right|Схема бин. поиска]]
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
В случае равенства возвращать его, а если искомое больше(в случае правостороннего - не меньше), чем элемент сравнения,
то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на 1, или же пока мы не найдём искомый индекс.

== Код ==
<pre>binSearch(l, r) // l, r - левая и правая границы
while l < r - 1 // запускаем цикл
m = (l + r) / 2; // m - середина области поиска
if a[m] < k
l = m;
else
r = m; // сужение границ
</pre>
В случае правостороннего поиска изменится знак сравнения при сужении границ на (<tex>a[m] <= k</tex>).

Инвариант цикла: пусть левый индекс меньше или равен искомого элемента, а правый — строго больше, тогда если <tex>l = r - 1</tex>, то понятно, что <tex>l</tex> — самое правое вхождение (так как следующее уже больше).

== Источники ==

*Д. Кнут - Искусство программирования (Том 3, 2-е издание)

==Ссылки==
[http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Википедия - двоичный поиск]

Целочисленный двоичный поиск

2013-10-06T20:54:13Z

79.175.1.33: /* Формулировка задачи */

{{Определение
|definition=
'''Целочисленный двоичный поиск (бин. поиск)''' - алгоритм поиска объекта по заданному признаку во множестве объектов, упорядоченных по тому же самому признаку.
}}

== Формулировка задачи ==
Пусть нам дан упорядоченный массив, состоящий только из целочисленых элементов. Нам надо найти в нем индекс, по которому находится искомый элемент, или же мы можем находить интервалы вхождения искомого элемента. Для этой задачи мы и можем использовать двоичный поиск.

==Принцип работы==
Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остается та часть множества, где находится искомый объект. Или же, в зависимости от постоновки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие - это левосторонний/правосторонний двоичный поиск.

== Правосторонний/левосторонний целочисленный двоичный поиск ==
Когда мы ищем правосторонним бин. поиском, то он возвращает индекс самого правого вхождения заданного значения х. 
Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения х. 
Это разделение помогает находить количество подряд идущих равных значений. 
Например: 
Задан отсортированный массив [1, 2, 2, 2, 2, 3, 5, 8, 9, 11] 
Правосторонний поиск двойки выдаст в результате 5, в то время как левосторонний выдаст 2. 
От сюда следует, что количество подряд идущих двоек равно длине отрезка [2;5] = 4. 
Если искомого элемента нету, то правосторонний поиск выдаст минимальный элемент, больший искомого, а левосторонний наоборот, максимальный элемент, меньший искомого.

== Алгоритм двоичного поиска ==
[[Файл:shcemebinsearch.png|350px|thumb|right|Схема бин. поиска]]
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
В случае равенства возвращать его, а если искомое больше(в случае правостороннего - не меньше), чем элемент сравнения,
то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на 1, или же пока мы не найдём искомый индекс.

== Код ==
<pre>binSearch(l, r) // l, r - левая и правая границы
while l < r - 1 // запускаем цикл
m = (l + r) / 2; // m - середина области поиска
if a[m] < k
l = m;
else
r = m; // сужение границ
</pre>
В случае правостороннего поиска изменится знак сравнения при сужении границ на (<tex>a[m] <= k</tex>).

Инвариант цикла: пусть левый индекс меньше или равен искомого элемента, а правый — строго больше, тогда если <tex>l = r - 1</tex>, то понятно, что <tex>l</tex> — самое правое вхождение (так как следующее уже больше).

== Источники ==

*Д. Кнут - Искусство программирования (Том 3, 2-е издание)

==Ссылки==
[http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Википедия - двоичный поиск]

Теоретический минимум по функциональному анализу за 6 семестр

2013-06-12T08:36:49Z

79.175.1.33: /* 20 Спектральный радиус ограниченного самосопряженного оператора и его норма */

== 1 <tex> A^* </tex> и его ограниченность ==
Пусть оператор <tex> A </tex> действует из <tex> E </tex> в <tex> F </tex>, и функционал <tex> \varphi </tex> принадлежит <tex> F^* </tex>.

Рассмотрим <tex> f(x) = \varphi (Ax), | f(x) | \le \| \varphi \| \| A \| \| x \| </tex>.

Получили новый функционал <tex> f </tex>, принадлежащий <tex> E^* </tex>. <tex> \varphi \mapsto \varphi A </tex>.

<tex> \varphi A = A^* (\varphi), A^* : F^* \to E^* </tex>. <tex> A^* </tex> {{---}} '''сопряженный оператор''' к <tex> A </tex>.

{{Теорема
|statement=
Если <tex> A </tex> {{---}} линейный ограниченный оператор, то <tex> \| A^* \| = \| A \| </tex>.
}}

== 2 Ортогональные дополнения <tex> E </tex> и <tex> E^* </tex> ==
{{Определение
|definition=
Пусть <tex> E </tex> {{---}} НП, <tex> S \subset E^* </tex>.

<tex> S^{\bot} = \{ x \in E \mid \forall f \in S: f(x) = 0 \} </tex> {{---}} '''ортогональное дополнение''' <tex> S </tex>.

Аналогично, если <tex> T \subset E </tex>, то <tex> T^{\bot} = \{ f \in E^* \mid \forall x \in T: f(x) = 0 \} </tex>.
}}

{{Утверждение
|statement= <tex> \{ 0 \} = (E^*)^{\bot}, \{ \mathbf{0} \} = E^{\bot} </tex>.
}}

== 3 Ортогональное дополнение R(A) ==
{{Теорема
|statement= <tex> A \in \mathcal{L}(E,F) \implies \operatorname{Cl} R(A) = (\operatorname{Ker} A^*)^\perp </tex>.
}}

== 4 Ортогональное дополнение <tex> R(A^*) </tex> ==
{{Теорема
|statement= <tex> A \in \mathcal{L}(E,F),~R(A) = \operatorname{Cl} R(A) \implies R(A^*) = (\operatorname{Ker}A )^\perp </tex>.
}}

== 5 Арифметика компактных операторов ==
{{Определение
|definition=
Множество называется '''относительно компактным (предкомпактным)''', если его замыкание компактно
}}
{{Определение
|definition=
Линейный ограниченный оператор <tex> A : X \to Y </tex> называется '''компактным''', если <tex> A </tex> переводит любое ограниченное подмножество <tex> X </tex> в относительно компактное множество из <tex> Y </tex>.
}}
{{Утверждение
|statement =
<tex> A \in \mathcal{L} (X,Y), ~ B \in \mathcal{L} (Y,Z) </tex>, <tex> C = B \cdot A </tex> (произведение, суперпозиция). Тогда:

# Если <tex> B </tex> — ограниченный, <tex> A </tex> — компактный, то <tex> C </tex> — компактный.
# Если <tex> B </tex> — компактный, <tex> A </tex> — ограниченный, то <tex> C </tex> — компактный.
}}

== 6 О компактности <tex> A^* </tex>, сепарабельность <tex> R(A) </tex> ==

{{Утверждение
|statement =
Пусть <tex> A </tex> — компактный, тогда <tex> R(A) </tex> — сепарабельно (то есть, в <tex> R(A) </tex> существует счетное всюду плотное подмножество).
}}

{{Утверждение
|statement =
<tex>A</tex> - компактен <tex>\Rightarrow</tex> <tex>A^*</tex> - компактен
}}

== 7 Базис Шаудера, лемма о координатном пространстве ==
{{Определение
|definition=
Базисом Шаудера в банаховом пространстве <tex>X</tex> называется множество его элементов <tex>e_1, e_2 \dots e_n \dots</tex> такое, что у любого <tex>x</tex> в <tex>X</tex> существует единственное разложение <tex>x = \sum\limits_{i = 1}^{\infty} \alpha_i e_i</tex>.
}}

Определим <tex>F = \{(\alpha_1 \dots \alpha_n\dots) \mid \exists x \in X: \sum\limits_{n=1}^\infty \alpha_n e_n \to x \}</tex> — это линейное пространство.

Так как ряд сходится, <tex>F</tex> можно превратить в НП, определив норму как <tex>\| \alpha \| = \sup\limits_n \left\| \sum\limits_{i=1}^n \alpha_i e_i\right\|</tex>.

{{Утверждение
|statement=
Пространство <tex> F </tex> относительно этой нормы — банахово.
}}

== 8 Почти конечномерность компактного оператора ==
{{Теорема
|about=
почти конечномерность компактного оператора
|statement=
Если <tex>X</tex> — банахово пространство с базисом Шаудера, <tex>A:X \to X</tex> — компактный, то для всех <tex>\varepsilon > 0</tex> существует разложение оператора <tex>A</tex> в сумму двух компактных операторов: <tex>A = A_1 + A_2</tex> такое, что:

# <tex>\operatorname{dim}(R(A_1)) < +\infty</tex>
# <tex>\|A_2\| < \varepsilon</tex>
}}

== 9 Размерность Ker(I-A) компактного A ==
{{Утверждение
|statement=
<tex>A</tex> {{---}} компактный оператор. Тогда <tex>\dim\operatorname{Ker}(I-A) < + \infty</tex>
}}

== 10 Замкнутость R(I-A) компактного A ==
{{Теорема
|statement=
Пусть <tex>T = I - A</tex>, <tex>A</tex> компактен, тогда <tex> R(T) </tex> замкнуто.
}}

== 11 Лемма о Ker(I-A)^n компактного A ==
{{Утверждение
|statement=
Пусть <tex> M_n = \operatorname{Ker} ((I - A)^n), n \in \mathbb N</tex>, <tex> A </tex> — компактный оператор.
Тогда <tex> \exists n_0: M_{n_0} = M_{n_0 + 1} </tex>.
}}

== 12 Условие справедливости равенства R(I-A)=E ==
{{Утверждение
|statement=
Пусть <tex> A </tex> — компактный оператор на банаховом <tex> X </tex>, <tex> T = I - A </tex>.
Тогда <tex> R(T) = X \Leftrightarrow \operatorname{Ker} T = \{0\} </tex>.
}}

== 13 Альтернатива Фредгольма-Шаудера ==
{{Теорема
|about=
альтернатива Фредгольма-Шаудера
|statement=
Пусть <tex>A:X \to X</tex> — компактный оператор и <tex>T = A - \lambda I</tex>. Тогда возможно только две ситуации:
# <tex>\operatorname{Ker} T = \{0\}</tex>, тогда <tex> y = Tx</tex> разрешимо для любого <tex>y</tex>
# <tex>\operatorname{Ker} T \ne \{0\}</tex>, тогда <tex> y = Tx</tex> разрешимо только для тех <tex>y</tex>, которые принадлежат <tex>(\operatorname{Ker} T^*)^\perp</tex>
}}

== 14 Спектр компактного оператора ==
Рассмотрим <tex>A - \lambda I</tex>.

# <tex>\operatorname{Ker} (A - \lambda I) \ne \{0\}</tex>, тогда оператор необратим, и <tex>\lambda</tex> — собственное число, то есть <tex>\lambda \in \sigma(A)</tex>.
# <tex>\operatorname{Ker} (A - \lambda I) = \{0\}</tex>, тогда по альтернативе, оператор непрерывно обратим, то есть <tex>\lambda \in \rho(A)</tex>.

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

{{Теорема
|statement=
Спектр компактного оператора не более чем счётен и его предельной точкой может быть только 0.
}}

== 15 Определение самосопряженного оператора, неравенство для (a+ib)(I-A) ==
{{Определение
|definition=Оператор <tex>\mathcal{A}</tex> называется ''самосопряжённым'' (<tex>\mathcal{A} = \mathcal{A}^*</tex>), если <tex>\forall x, y : \langle \mathcal{A}x, y \rangle = \langle x, \mathcal{A}y \rangle</tex>
}}
<tex>\lambda \in \mathbb{C}</tex>, <tex>\lambda \mathcal{I} - \mathcal{A} = (\mu\mathcal{I} - \mathcal{A}) + i\nu\mathcal{I}</tex>

<tex>\|(\lambda\mathcal{I}-\mathcal{A})x\| \ge |\nu|\cdot\|x\|</tex>

== 16 Вещественность спектра ограниченного самосопряженного оператора ==
{{Утверждение
|statement=Собственные числа самосопряжённого оператора вещественны
}}

== 17 Критерий включения в резольвентное множество ограниченного самосопряженного оператора ==
{{Теорема
|statement=Пусть <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор. Тогда
<tex>\lambda \in \rho(\mathcal{A}) \iff \exists m > 0 : \forall x \in \mathcal{H} : \|(\lambda\mathcal{I}-\mathcal{A})x\| \ge m\|x\|</tex>
}}

== 18 Критерий включения в спектр ограниченного самосопряженного оператора ==
{{Теорема
|statement=Пусть <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор. Тогда
<tex>\lambda \in \sigma(\mathcal{A}) \iff \exists x_n : \|x_n\| = 1 : \|(\lambda\mathcal{I}-\mathcal{A})x_n\| \to 0 </tex>
}}

== 19 Локализация спектра с.с. оператора посредством чисел m- и m+ ==
{{Определение
|definition=<tex>m_- = \inf\limits_{\|x\| = 1} \langle \mathcal{A}x, x\rangle, m_+ = \sup\limits_{\|x\| = 1} \langle \mathcal{A}x, x \rangle</tex>
}}
{{Теорема
|statement=1. <tex>\sigma(\mathcal{A}) \subset [m_-; m_+]</tex>

2. <tex>m_+, m_- \in \sigma(\mathcal{A})</tex>
}}

== 20 Спектральный радиус ограниченного самосопряженного оператора и его норма ==
{{Утверждение
|statement=Если <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор, то <tex>r_\sigma(\mathcal{A}) = \|\mathcal{A}\|</tex>
}}

== 21 Теорема Гильберта-Шмидта ==
{{Теорема
|author=Гильберт, Шмидт
|statement=Если <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор в гильбертовом пространстве <tex>\mathcal{H}</tex>, а <tex>M_{\lambda_i}</tex>{{---}} его (оператора) собственные подпространства, то <tex>\mathcal{H} = M_{\lambda_1} \oplus M_{\lambda_2} \oplus \cdots \oplus M_{\lambda_n} \oplus \cdots </tex>
}}

== 22 Разложение резольвенты компактного самосопряженного оператора. ==
<tex>R_\lambda(y) = \sum\limits_{n=1}^\infty \frac{\langle y, \varphi_n\rangle}{\lambda-\lambda_n}\varphi_n</tex>

== 23 Локальная сходимость метода простой итерации ==
{{Теорема
|about=Локальная теорема о простой итерации
|statement=
Пусть известно, что существует <tex> \overline{x}: \mathcal{T}(\overline{x}) = \overline{x} </tex> и <tex> \| \mathcal{T}(\overline{x})' \| \le q < 1 </tex>.

Тогда существует такой шар <tex> V_{\delta} (\overline x) </tex>, что если <tex> x_0 \in V_{\delta} (\overline x) </tex>, то:
* Метод простых итераций корректно определен: <tex> \mathcal{T}x_n \in V_{\delta} (\overline x), n \ge 0</tex>.
* <tex> x_n \to \overline x </tex>
}}

== 24 Локальная сходимость метода Ньютона для операторных уравнений ==
<tex> \mathcal{F}(x) = x - \Gamma(x) \mathcal{T} (x)</tex>
{{Утверждение
|statement=<tex> \mathcal{F}'(\overline x) = 0 </tex>
}}

== 25 Проекторы Шаудера ==
<tex> \forall \varepsilon > 0 \exists y_1 \in M, \hdots, y_p \in M </tex> {{---}} конечная <tex> \varepsilon </tex>-сеть.

Построим следующую функцию: <tex> \forall j = 1, \hdots, p, \forall y \in M: </tex>

<tex> \mu_j(y) = \begin{cases}
0 & \mbox{if } \| y - y_j \| \ge \varepsilon \\
\varepsilon - \| y - y_j \| & \mbox{if } \| y - y_j \| < \varepsilon \end{cases}
</tex>

<tex> S(y) = \sum\limits_{j=1}^p \mu_j(y) </tex>
{{Определение
|definition=

<tex dpi = 140> P_\varepsilon (y) = \sum\limits_{j=1}^p \frac {\mu_j(y)} {S(y)} y_j </tex> {{---}} ''проектор Шаудера''.

}}

== 26 Теорема Шаудера о неподвижной точке ==
{{Теорема
|author=Шаудер
|about=о неподвижной точке
|statement=
Пусть <tex> M </tex> {{---}} ограниченное замкнутое выпуклое подмножество B-пространства <tex> X </tex> и <tex> \mathcal{T} </tex> вполне непрерывно отображает <tex> M </tex> в себя.

Тогда <tex> \exists x^* \in M : x^* = Tx^* </tex>.
}}

[[Категория: Функциональный анализ 3 курс]]

Теоретический минимум по функциональному анализу за 6 семестр

2013-06-12T05:29:47Z

79.175.1.33: /* 2 Ортогональные дополнения E и E^* */

== 1 <tex> A^* </tex> и его ограниченность ==
Пусть оператор <tex> A </tex> действует из <tex> E </tex> в <tex> F </tex>, и функционал <tex> \varphi </tex> принадлежит <tex> F^* </tex>.

Рассмотрим <tex> f(x) = \varphi (Ax), | f(x) | \le \| \varphi \| \| A \| \| x \| </tex>.

Получили новый функционал <tex> f </tex>, принадлежащий <tex> E^* </tex>. <tex> \varphi \mapsto \varphi A </tex>.

<tex> \varphi A = A^* (\varphi), A^* : F^* \to E^* </tex>. <tex> A^* </tex> {{---}} '''сопряженный оператор''' к <tex> A </tex>.

{{Теорема
|statement=
Если <tex> A </tex> {{---}} линейный ограниченный оператор, то <tex> \| A^* \| = \| A \| </tex>.
}}

== 2 Ортогональные дополнения <tex> E </tex> и <tex> E^* </tex> ==
{{Определение
|definition=
Пусть <tex> E </tex> {{---}} НП, <tex> S \subset E^* </tex>.

<tex> S^{\bot} = \{ x \in E \mid \forall f \in S: f(x) = 0 \} </tex> {{---}} '''ортогональное дополнение''' <tex> S </tex>.

Аналогично, если <tex> T \subset E </tex>, то <tex> T^{\bot} = \{ f \in E^* \mid \forall x \in T: f(x) = 0 \} </tex>.
}}

{{Утверждение
|statement= <tex> \{ 0 \} = (E^*)^{\bot}, \{ \mathbf{0} \} = E^{\bot} </tex>.
}}

== 3 Ортогональное дополнение R(A) ==
{{Теорема
|statement= <tex> A \in \mathcal{L}(E,F) \implies \operatorname{Cl} R(A) = (\operatorname{Ker} A^*)^\perp </tex>.
}}

== 4 Ортогональное дополнение <tex> R(A^*) </tex> ==
{{Теорема
|statement= <tex> A \in \mathcal{L}(E,F),~R(A) = \operatorname{Cl} R(A) \implies R(A^*) = (\operatorname{Ker}A )^\perp </tex>.
}}

== 5 Арифметика компактных операторов ==
{{Определение
|definition=
Множество называется '''относительно компактным (предкомпактным)''', если его замыкание компактно
}}
{{Определение
|definition=
Линейный ограниченный оператор <tex> A : X \to Y </tex> называется '''компактным''', если <tex> A </tex> переводит любое ограниченное подмножество <tex> X </tex> в относительно компактное множество из <tex> Y </tex>.
}}
{{Утверждение
|statement =
<tex> A \in \mathcal{L} (X,Y), ~ B \in \mathcal{L} (Y,Z) </tex>, <tex> C = B \cdot A </tex> (произведение, суперпозиция). Тогда:

# Если <tex> B </tex> — ограниченный, <tex> A </tex> — компактный, то <tex> C </tex> — компактный.
# Если <tex> B </tex> — компактный, <tex> A </tex> — ограниченный, то <tex> C </tex> — компактный.
}}

== 6 О компактности <tex> A^* </tex>, сепарабельность <tex> R(A) </tex> ==

{{Утверждение
|statement =
Пусть <tex> A </tex> — компактный, тогда <tex> R(A) </tex> — сепарабельно (то есть, в <tex> R(A) </tex> существует счетное всюду плотное подмножество).
}}

{{Утверждение
|statement =
<tex>A</tex> - компактен <tex>\Rightarrow</tex> <tex>A^*</tex> - компактен
}}

== 7 Базис Шаудера, лемма о координатном пространстве ==
{{Определение
|definition=
Базисом Шаудера в банаховом пространстве <tex>X</tex> называется множество его элементов <tex>e_1, e_2 \dots e_n \dots</tex> такое, что у любого <tex>x</tex> в <tex>X</tex> существует единственное разложение <tex>x = \sum\limits_{n = 1}^{\infty} \alpha_i e_i</tex>.
}}

Определим <tex>F = \{(\alpha_1 \dots \alpha_n\dots) \mid \exists x \in X: \sum\limits_{n=1}^\infty \alpha_n e_n \to x \}</tex> — это линейное пространство.

Так как ряд сходится, <tex>F</tex> можно превратить в НП, определив норму как <tex>\| \alpha \| = \sup\limits_n \left\| \sum\limits_{i=1}^n \alpha_i e_i\right\|</tex>.

{{Утверждение
|statement=
Пространство <tex> F </tex> относительно этой нормы — банахово.
}}

== 8 Почти конечномерность компактного оператора ==
{{Теорема
|about=
почти конечномерность компактного оператора
|statement=
Если <tex>X</tex> — банахово пространство с базисом Шаудера, <tex>A:X \to X</tex> — компактный, то для всех <tex>\varepsilon > 0</tex> существует разложение оператора <tex>A</tex> в сумму двух компактных операторов: <tex>A = A_1 + A_2</tex> такое, что:

# <tex>\operatorname{dim}(R(A_1)) < +\infty</tex>
# <tex>\|A_2\| < \varepsilon</tex>
}}

== 9 Размерность Ker(I-A) компактного A ==
{{Утверждение
|statement=
<tex>A</tex> {{---}} компактный оператор. Тогда <tex>\dim\operatorname{Ker}(I-A) < + \infty</tex>
}}

== 10 Замкнутость R(I-A) компактного A ==
{{Теорема
|statement=
Пусть <tex>T = I - A</tex>, <tex>A</tex> компактен, тогда <tex> R(T) </tex> замкнуто.
}}

== 11 Лемма о Ker(I-A)^n компактного A ==
{{Утверждение
|statement=
Пусть <tex> M_n = \operatorname{Ker} ((I - A)^n), n \in \mathbb N</tex>, <tex> A </tex> — компактный оператор.
Тогда <tex> \exists n_0: M_{n_0} = M_{n_0 + 1} </tex>.
}}

== 12 Условие справедливости равенства R(I-A)=E ==
{{Утверждение
|statement=
Пусть <tex> A </tex> — компактный оператор на банаховом <tex> X </tex>, <tex> T = I - A </tex>.
Тогда <tex> R(T) = X \Leftrightarrow \operatorname{Ker} T = \{0\} </tex>.
}}

== 13 Альтернатива Фредгольма-Шаудера ==
{{Теорема
|about=
альтернатива Фредгольма-Шаудера
|statement=
Пусть <tex>A:X \to X</tex> — компактный оператор и <tex>T = A - \lambda I</tex>. Тогда возможно только две ситуации:
# <tex>\operatorname{Ker} T = \{0\}</tex>, тогда <tex> y = Tx</tex> разрешимо для любого <tex>y</tex>
# <tex>\operatorname{Ker} T \ne \{0\}</tex>, тогда <tex> y = Tx</tex> разрешимо только для тех <tex>y</tex>, которые принадлежат <tex>(\operatorname{Ker} T^*)^\perp</tex>
}}

== 14 Спектр компактного оператора ==
Рассмотрим <tex>A - \lambda I</tex>.

# <tex>\operatorname{Ker} (A - \lambda I) \ne \{0\}</tex>, тогда оператор необратим, и <tex>\lambda</tex> — собственное число, то есть <tex>\lambda \in \sigma(A)</tex>.
# <tex>\operatorname{Ker} (A - \lambda I) = \{0\}</tex>, тогда по альтернативе, оператор непрерывно обратим, то есть <tex>\lambda \in \rho(A)</tex>.

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

{{Теорема
|statement=
Спектр компактного оператора не более чем счётен и его предельной точкой может быть только 0.
}}

== 15 Определение самосопряженного оператора, неравенство для (a+ib)(I-A) ==
{{Определение
|definition=Оператор <tex>\mathcal{A}</tex> называется ''самосопряжённым'' (<tex>\mathcal{A} = \mathcal{A}^*</tex>), если <tex>\forall x, y : \langle \mathcal{A}x, y \rangle = \langle x, \mathcal{A}y \rangle</tex>
}}
<tex>\lambda \in \mathbb{C}</tex>, <tex>\lambda \mathcal{I} - \mathcal{A} = (\mu\mathcal{I} - \mathcal{A}) + i\nu\mathcal{I}</tex>

<tex>\|(\lambda\mathcal{I}-\mathcal{A})x\| \ge |\nu|\cdot\|x\|</tex>

== 16 Вещественность спектра ограниченного самосопряженного оператора ==
{{Утверждение
|statement=Собственные числа самосопряжённого оператора вещественны
}}

== 17 Критерий включения в резольвентное множество ограниченного самосопряженного оператора ==
{{Теорема
|statement=Пусть <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор. Тогда
<tex>\lambda \in \rho(\mathcal{A}) \iff \exists m > 0 : \forall x \in \mathcal{H} : \|(\lambda\mathcal{I}-\mathcal{A})x\| \ge m\|x\|</tex>
}}

== 18 Критерий включения в спектр ограниченного самосопряженного оператора ==
{{Теорема
|statement=Пусть <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор. Тогда
<tex>\lambda \in \sigma(\mathcal{A}) \iff \exists x_n : \|x_n\| = 1 : \|(\lambda\mathcal{I}-\mathcal{A})x_n\| \to 0 </tex>
}}

== 19 Локализация спектра с.с. оператора посредством чисел m- и m+ ==
{{Определение
|definition=<tex>m_- = \inf\limits_{\|x\| = 1} \langle \mathcal{A}x, x\rangle, m_+ = \sup\limits_{\|x\| = 1} \langle \mathcal{A}x, x \rangle</tex>
}}
{{Теорема
|statement=1. <tex>\sigma(\mathcal{A}) \subset [m_-; m_+]</tex>

2. <tex>m_+, m_- \in \sigma(\mathcal{A})</tex>
}}

== 20 Спектральный радиус ограниченного самосопряженного оператора и его норма ==
{{Утверждение
|statement=Если <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор, то <tex>r_\rho(\mathcal{A}) = \|\mathcal{A}\|</tex>
}}

== 21 Теорема Гильберта-Шмидта ==
{{Теорема
|author=Гильберт, Шмидт
|statement=Если <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор в гильбертовом пространстве <tex>\mathcal{H}</tex>, а <tex>M_{\lambda_i}</tex>{{---}} его (оператора) собственные подпространства, то <tex>\mathcal{H} = M_{\lambda_1} \oplus M_{\lambda_2} \oplus \cdots \oplus M_{\lambda_n} \oplus \cdots </tex>
}}

== 22 Разложение резольвенты компактного самосопряженного оператора. ==
<tex>R_\lambda(y) = \sum\limits_{n=1}^\infty \frac{\langle y, \varphi_n\rangle}{\lambda-\lambda_n}\varphi_n</tex>

== 23 Локальная сходимость метода простой итерации ==
{{Теорема
|about=Локальная теорема о простой итерации
|statement=
Пусть известно, что существует <tex> \overline{x}: \mathcal{T}(\overline{x}) = \overline{x} </tex> и <tex> \| \mathcal{T}(\overline{x})' \| \le q < 1 </tex>.

Тогда существует такой шар <tex> V_{\delta} (\overline x) </tex>, что если <tex> x_0 \in V_{\delta} (\overline x) </tex>, то:
* Метод простых итераций корректно определен: <tex> \mathcal{T}x_n \in V_{\delta} (\overline x), n \ge 0</tex>.
* <tex> x_n \to \overline x </tex>
}}

== 24 Локальная сходимость метода Ньютона для операторных уравнений ==
<tex> \mathcal{F}(x) = x - \Gamma(x) \mathcal{T} (x)</tex>
{{Утверждение
|statement=<tex> \mathcal{F}'(\overline x) = 0 </tex>
}}

== 25 Проекторы Шаудера ==
<tex> \forall \varepsilon > 0 \exists y_1 \in M, \hdots, y_p \in M </tex> {{---}} конечная <tex> \varepsilon </tex>-сеть.

Построим следующую функцию: <tex> \forall j = 1, \hdots, p, \forall y \in M: </tex>

<tex> \mu_j(y) = \begin{cases}
0 & \mbox{if } \| y - y_j \| \ge \varepsilon \\
\varepsilon - \| y - y_j \| & \mbox{if } \| y - y_j \| < \varepsilon \end{cases}
</tex>

<tex> S(y) = \sum\limits_{j=1}^p \mu_j(y) </tex>
{{Определение
|definition=

<tex dpi = 140> P_\varepsilon (y) = \sum\limits_{j=1}^p \frac {\mu_j(y)} {S(y)} y_j </tex> {{---}} ''проектор Шаудера''.

}}

== 26 Теорема Шаудера о неподвижной точке ==
{{Теорема
|author=Шаудер
|about=о неподвижной точке
|statement=
Пусть <tex> M </tex> {{---}} ограниченное замкнутое выпуклое подмножество B-пространства <tex> X </tex> и <tex> \mathcal{T} </tex> вполне непрерывно отображает <tex> M </tex> в себя.

Тогда <tex> \exists x^* \in M : x^* = Tx^* </tex>.
}}

[[Категория: Функциональный анализ 3 курс]]

Теоретический минимум по функциональному анализу за 6 семестр

2013-06-11T14:26:32Z

79.175.1.33: /* 23 Локальная сходимость метода простой итерации */

== 1 A^* и его ограниченность ==
Пусть оператор <tex> A </tex> действует из <tex> E </tex> в <tex> F </tex>, и функционал <tex> \varphi </tex> принадлежит <tex> F^* </tex>.

Рассмотрим <tex> f(x) = \varphi (Ax), | f(x) | \le \| \varphi \| \| A \| \| x \| </tex>.

Получили новый функционал <tex> f </tex>, принадлежащий <tex> E^* </tex>. <tex> \varphi \mapsto \varphi A </tex>.

<tex> \varphi A = A^* (\varphi), A^* : F^* \to E^* </tex>. <tex> A^* </tex> {{---}} '''сопряженный оператор''' к <tex> A </tex>.

{{Теорема
|statement=
Если <tex> A </tex> {{---}} линейный ограниченный оператор, то <tex> \| A^* \| = \| A \| </tex>.
}}

== 2 Ортогональные дополнения E и E^* ==
{{Определение
|definition=
Пусть <tex> E </tex> {{---}} НП, <tex> S \subset E^* </tex>.

<tex> S^{\bot} = \{ x \in E \mid \forall f \in S: f(x) = 0 \} </tex> {{---}} '''ортогональное дополнение''' <tex> S </tex>.

Аналогично, если <tex> T \subset E </tex>, то <tex> T^{\bot} = \{ f \in E^* \mid \forall x \in T: f(x) = 0 \} </tex>.
}}

== 3 Ортогональное дополнение R(A) ==
{{Теорема
|statement= <tex> A \in \mathcal{L}(E,F) \implies \operatorname{Cl} R(A) = (\operatorname{Ker} A^*)^\perp </tex>.
}}

== 4 Ортогональное дополнение R(A^*) ==
{{Теорема
|statement= <tex> A \in \mathcal{L}(E,F),~R(A) = \operatorname{Cl} R(A) \implies R(A^*) = (\operatorname{Ker}A )^\perp </tex>.
}}

== 5 Арифметика компактных операторов ==
{{Определение
|definition=
Множество называется '''относительно компактным (предкомпактным)''', если его замыкание компактно
}}
{{Определение
|definition=
Линейный ограниченный оператор <tex> A : X \to Y </tex> называется '''компактным''', если <tex> A </tex> переводит любое ограниченное подмножество <tex> X </tex> в относительно компактное множество из <tex> Y </tex>.
}}
{{Утверждение
|statement =
<tex> A \in \mathcal{L} (X,Y), ~ B \in \mathcal{L} (Y,Z) </tex>, <tex> C = B \cdot A </tex> (произведение, суперпозиция). Тогда:

# Если <tex> B </tex> — ограниченный, <tex> A </tex> — компактный, то <tex> C </tex> — компактный.
# Если <tex> B </tex> — компактный, <tex> A </tex> — ограниченный, то <tex> C </tex> — компактный.
}}

== 6 О компактности A^*, сепарабельность R(A) ==

{{Утверждение
|statement =
Пусть <tex> A </tex> — компактный, тогда <tex> R(A) </tex> — сепарабельно (то есть, в <tex> R(A) </tex> существует счетное всюду плотное подмножество).
}}

{{Утверждение
|statement =
<tex>A</tex> - компактен <tex>\Leftrightarrow</tex> <tex>A^*</tex> - компактен
}}

== 7 Базис Шаудера, лемма о координатном пространстве ==
{{Определение
|definition=
Базисом Шаудера в банаховом пространстве <tex>X</tex> называется множество его элементов <tex>e_1, e_2 \dots e_n \dots</tex> такое, что у любого <tex>x</tex> в <tex>X</tex> существует единственное разложение <tex>x = \sum\limits_{n = 1}^{\infty} \alpha_i e_i</tex>.
}}

Определим <tex>F = \{(\alpha_1 \dots \alpha_n\dots) \mid \exists x \in X: \sum\limits_{n=1}^\infty \alpha_n e_n \to x \}</tex> — это линейное пространство.

Так как ряд сходится, <tex>F</tex> можно превратить в НП, определив норму как <tex>\| \alpha \| = \sup\limits_n \left\| \sum\limits_{i=1}^n \alpha_i e_i\right\|</tex>.

{{Утверждение
|statement=
Пространство <tex> F </tex> относительно этой нормы — банахово.
}}

== 8 Почти конечномерность компактного оператора ==
{{Теорема
|about=
почти конечномерность компактного оператора
|statement=
Если <tex>X</tex> — банахово пространство с базисом Шаудера, <tex>A:X \to X</tex> — компактный, то для всех <tex>\varepsilon > 0</tex> существует разложение оператора <tex>A</tex> в сумму двух компактных операторов: <tex>A = A_1 + A_2</tex> такое, что:

# <tex>\operatorname{dim}(R(A_1)) < +\infty</tex>
# <tex>\|A_2\| < \varepsilon</tex>
}}

== 9 Размерность Ker(I-A) компактного A ==
{{Утверждение
|statement=
<tex>A</tex> {{---}} компактный оператор. Тогда <tex>\dim\operatorname{Ker}(I-A) < + \infty</tex>
}}

== 10 Замкнутость R(I-A) компактного A ==
{{Теорема
|statement=
Пусть <tex>T = I - A</tex>, <tex>A</tex> компактен, тогда <tex> R(T) </tex> замкнуто.
}}

== 11 Лемма о Ker(I-A)^n компактного A ==
{{Утверждение
|statement=
Пусть <tex> M_n = \operatorname{Ker} ((I - A)^n), n \in \mathbb N</tex>, <tex> A </tex> — компактный оператор.
Тогда <tex> \exists n_0: M_{n_0} = M_{n_0 + 1} </tex>.
}}

== 12 Условие справедливости равенства R(I-A)=E ==
{{Утверждение
|statement=
Пусть <tex> A </tex> — компактный оператор на банаховом <tex> X </tex>, <tex> T = I - A </tex>.
Тогда <tex> R(T) = X \Leftrightarrow \operatorname{Ker} T = \{0\} </tex>.
}}

== 13 Альтернатива Фредгольма-Шаудера ==
{{Теорема
|about=
альтернатива Фредгольма-Шаудера
|statement=
Пусть <tex>A:X \to X</tex> — компактный оператор и <tex>T = A - \lambda I</tex>. Тогда возможно только две ситуации:
# <tex>\operatorname{Ker} T = \{0\}</tex>, тогда <tex> y = Tx</tex> разрешимо для любого <tex>y</tex>
# <tex>\operatorname{Ker} T \ne \{0\}</tex>, тогда <tex> y = Tx</tex> разрешимо только для тех <tex>y</tex>, которые принадлежат <tex>(\operatorname{Ker} T^*)^\perp</tex>
}}

== 14 Спектр компактного оператора ==
Рассмотрим <tex>A - \lambda I</tex>.

# <tex>\operatorname{Ker} (A - \lambda I) \ne \{0\}</tex>, тогда оператор необратим, и <tex>\lambda</tex> — собственное число, то есть <tex>\lambda \in \sigma(A)</tex>.
# <tex>\operatorname{Ker} (A - \lambda I) = \{0\}</tex>, тогда по альтернативе, оператор непрерывно обратим, то есть <tex>\lambda \in \rho(A)</tex>.

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

{{Теорема
|statement=
Спектр компактного оператора не более чем счётен и его предельной точкой может быть только 0.
}}

== 15 Определение самосопряженного оператора, неравенство для (a+ib)(I-A) ==
{{Определение
|definition=Оператор <tex>\mathcal{A}</tex> называется ''самосопряжённым'' (<tex>\mathcal{A} = \mathcal{A}^*</tex>), если <tex>\forall x, y : \langle \mathcal{A}x, y \rangle = \langle x, \mathcal{A}y \rangle</tex>
}}
<tex>\lambda \in \mathbb{C}</tex>, <tex>\lambda \mathcal{I} - \mathcal{A} = (\mu\mathcal{I} - \mathcal{A}) + i\nu\mathcal{I}</tex>

<tex>\|(\lambda\mathcal{I}-\mathcal{A})x\| \ge |\nu|\cdot\|x\|</tex>

== 16 Вещественность спектра ограниченного самосопряженного оператора ==
{{Утверждение
|statement=Собственные числа самосопряжённого оператора вещественны
}}

== 17 Критерий включения в резольвентное множество ограниченного самосопряженного оператора ==
{{Теорема
|statement=Пусть <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор. Тогда
<tex>\lambda \in \rho(\mathcal{A}) \iff \exists m > 0 : \forall x \in \mathcal{H} : \|(\lambda\mathcal{I}-\mathcal{A})x\| \ge m\|x\|</tex>
}}

== 18 Критерий включения в спектр ограниченного самосопряженного оператора ==
{{Теорема
|statement=Пусть <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор. Тогда
<tex>\lambda \in \sigma(\mathcal{A}) \iff \exists x_n : \|x_n\| = 1 : \|(\lambda\mathcal{I}-\mathcal{A})x_n\| \to 0 </tex>
}}

== 19 Локализация спектра с.с. оператора посредством чисел m- и m+ ==
{{Определение
|definition=<tex>m_- = \inf\limits_{\|x\| = 1} \langle \mathcal{A}x, x\rangle</tex>

<tex>m_+ = \sup\limits_{\|x\| = 1} \langle \mathcal{A}x, x \rangle</tex>
}}
{{Теорема
|statement=1. <tex>\sigma(\mathcal{A}) \subset [m_-; m_+]</tex>

2. <tex>m_+, m_- \in \sigma(\mathcal{A})</tex>
}}

== 20 Спектральный радиус ограниченного самосопряженного оператора и его норма ==
{{Утверждение
|statement=Если <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор, то <tex>r_\rho(\mathcal{A}) = \|\mathcal{A}\|</tex>
}}

== 21 Теорема Гильберта-Шмидта ==
{{Теорема
|author=Гильберт, Шмидт
|statement=Если <tex>\mathcal{A}</tex>{{---}} самосопряжённый оператор в гильбертовом пространстве <tex>\mathcal{H}</tex>, а <tex>M_{\lambda_i}</tex>{{---}} его (оператора) собственные подпространства, то <tex>\mathcal{H} = M_{\lambda_1} \oplus M_{\lambda_2} \oplus \cdots \oplus M_{\lambda_n} \oplus \cdots </tex>
}}

== 22 Разложение резольвенты компактного самосопряженного оператора. ==
<tex>R_\lambda(y) = \sum\limits_{n=1}^\infty \frac{\langle y, \varphi_n\rangle}{\lambda-\lambda_n}\varphi_n</tex>

== 23 Локальная сходимость метода простой итерации ==
{{Теорема
|about=Локальная теорема о простой итерации
|statement=
Пусть известно, что существует <tex> \overline{x}: \mathcal{T}(\overline{x}) = \overline{x} </tex> и <tex> \| \mathcal{T}(\overline{x})' \| \le q < 1 </tex>.

Тогда существует такой шар <tex> V_{\delta} (\overline x) </tex>, что если <tex> x_0 \in V_{\delta} (\overline x) </tex>, то:
* Метод простых итераций корректно определен: <tex> \mathcal{T}x_n \in V_{\delta} (\overline x), n \ge 0</tex>.
* <tex> x_n \to \overline x </tex>
}}

== 24 Локальная сходимость метода Ньютона для операторных уравнений ==
<tex> \mathcal{F}(x) = x - \Gamma(x) \mathcal{T} (x)</tex>
{{Утверждение
|statement=<tex> \mathcal{F}'(\overline x) = 0 </tex>
}}

== 25 Проекторы Шаудера ==
<tex> \forall \varepsilon > 0 \exists y_1 \in M, \hdots, y_p \in M </tex> {{---}} конечная <tex> \varepsilon </tex>-сеть.

Построим следующую функцию: <tex> \forall j = 1, \hdots, p, \forall y \in M: </tex>

<tex> \mu_j(y) = \begin{cases}
0 & \mbox{if } \| y - y_j \| \ge \varepsilon \\
\varepsilon - \| y - y_j \| & \mbox{if } \| y - y_j \| < \varepsilon \end{cases}
</tex>

<tex> S(y) = \sum\limits_{j=1}^p \mu_j(y) </tex>
{{Определение
|definition=

<tex dpi = 140> P_\varepsilon (y) = \sum\limits_{j=1}^p \frac {\mu_j(y)} {S(y)} y_j </tex> {{---}} ''проектор Шаудера''.

}}

== 26 Теорема Шаудера о неподвижной точке ==
{{Теорема
|author=Шаудер
|about=о неподвижной точке
|statement=
Пусть <tex> M </tex> {{---}} ограниченное замкнутое выпуклое подмножество B-пространства <tex> X </tex> и <tex> \mathcal{T} </tex> вполне непрерывно отображает <tex> M </tex> в себя.

Тогда <tex> \exists x^* \in M : x^* = Tx^* </tex>.
}}

[[Категория: Функциональный анализ 3 курс]]

Замкнутость КС-языков относительно различных операций

2013-01-21T18:01:14Z

79.175.1.33: /* Прямой и обратный гомоморфизм */

В отличие от [[Замкнутость регулярных языков относительно различных операций|регулярных языков]], [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-языки]] не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.

Здесь и далее считаем, что <tex> L_1 </tex> и <tex> L_2 </tex> -- КС языки.

== Операции с КС-языками ==

=== Объединение ===

{{ Утверждение
|statement= <tex> L_1 \cup L_2 </tex> также является КС-языком.
|proof=

Построим КС-грамматику для языка <tex> L_1 \cup L_2 </tex>. Для этого рассмотрим соответствующие КС-грамматики для языков <tex> L_1 </tex> и <tex> L_2 </tex>. Пусть стартовые символы в них имеют имена <tex> S </tex> и <tex> T </tex> соответственно. Тогда стартовый символ для <tex> L_1 \cup L_2 </tex> обозначим за <tex> S' </tex> и добавим правило <tex> S' \to S\,|\,T </tex>.

Покажем, что <tex> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </tex>. В левую сторону: поскольку <tex> S \Rightarrow^{*} w </tex> и есть правило <tex> S' \to S </tex>, то, по определению <tex> \Rightarrow^{*} </tex> получаем, что <tex> S' \Rightarrow^{*} w </tex>. Аналогично и для <tex> T </tex>.

В обратную сторону, пусть <tex> S' \Rightarrow^{*} w </tex>. Поскольку <tex> S' \to S\,|\,T </tex> -- единственные правила, в которых нетерминал <tex> S' </tex> присутствует в правой части, а значит, либо <tex> S' \Rightarrow S \Rightarrow^{*} w </tex>, либо <tex> S' \Rightarrow T \Rightarrow^{*} w </tex>, что и требовалось доказать.

}}

=== Конкатенация ===

{{ Утверждение
|statement= <tex> L_1 \cdot L_2 </tex> -- КС-язык.
|proof=КС-грамматика для <tex> L_1 \cdot L_2 </tex> выглядит следующим образом: <tex> S' \to S T </tex>, и <tex> S </tex> -- стартовый символ.
Доказательство аналогично случаю с объединением.
}}

=== Замыкание Клини ===

{{ Утверждение
|statement= <tex> L^{*} = \bigcup\limits_{i = 0}^{\infty} L^i </tex> -- КС-язык.
|proof=Если <tex> S </tex> -- стартовый символ КС-грамматики для языка <tex> L </tex>, то добавим в КС-грамматику для языка <tex> L^{*} </tex> новый стартовый символ <tex> S' </tex> и правила <tex> S' \to S S' \, | \, \varepsilon </tex>.
}}

=== Прямой и обратный гомоморфизм ===

В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ <tex> x \in \Sigma </tex> заменяется на <tex> h(x) </tex>. Для обратного гомоморфизма можно построить [[Автоматы с магазинной памятью|МП-автомат]] для <tex> h^{-1}(L) </tex> на основе МП-автомата для языка <tex> L </tex> (назовем его <tex> M </tex>). Считаем, что <tex> M </tex> допускает слова [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|по пустому стеку]]. Новый автомат будет действовать следующим образом:

# Если входное слово закончилось, допускаем либо не допускаем его по пустому стеку.
# Иначе считываем символ <tex> x </tex>.
# Сохраняем <tex> h(x) </tex> в буффере.
# Запускаем <tex> M </tex> на слове, находящемся в буфере.
# После того, как <tex> M </tex> обработал весь буфер, переходим к пункту 2.

Пусть в автомате <tex> M </tex> было <tex> n </tex> состояний. Для того, чтобы научиться сохранять слова в буфере, создадим <tex> |\Sigma|^{k+1} n </tex> дополнительных состояний в новом автомате, где <tex> k = \max\limits_{c \in \Sigma} | h(c) | </tex>. Это позволит в состоянии кодировать слово, которое находится сейчас в буфере. Переходы в этих состояниях совершаются на основе того, что стоит на первом месте в буфере, состояния автомата и вершины стека. На ленту переходы в этих состояниях не смотрят. Из состояния, в котором буфер пуст, добавим <tex> \varepsilon </tex>-переход в начальное состояние. Необходима картинка.

=== Разворот ===

Для того, чтобы построить КС-грамматику для языка <tex> L^{R} = \{ w^{R} \mid w \in L \} </tex>, необходимо развернуть все правые части правил грамматики для <tex> L </tex>.

=== Дополнение, пересечение и разность ===

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

{{ Утверждение
|statement= <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако <tex> \overline{L} </tex> -- КС-язык.
|proof=

То, что <tex> L </tex> -- не КС язык, доказывается с помощью леммы о разрастании. Для <tex> \overline{L} </tex> можно составить [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]].
}}

{{ Утверждение
|statement= Если <tex> L_1 = a^i b^i c^j , L_2 = a^i b^j c^j </tex>, то <tex> L_1 \cap L_2 </tex> не является КС-языком.
|proof=
<tex> L_1 = \{ a^i b^i \} \cdot \{ c^j \}, L_2 = \{ a^i \} \cdot \{ b^j c^j \} </tex>. По замкнутости КС-языков относительно конкатенации получаем, что <tex> L_1 </tex> и <tex> L_2 </tex> являются КС-языками.

Но <tex> L_1 \cap L_2 = \{ a^i b^i c^i \mid i \in \mathbb{N} \} </tex>, что по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]] для КС-языков не является КС-языком.
}}

Для разности достаточно заметить, что <tex> \overline{L} = \Sigma^{*} \setminus L </tex>, поэтому разность КС-языков также необязательно является КС-языком.

Более того, задачи определения того, является ли дополнение КС-языка КС-языком и проверки непустоты пересечения КС-языков являются алгоритмически [[Разрешимые (рекурсивные) языки|неразрешимыми]].

=== Примеры других операций ===

{{ Определение
|definition=
<tex> Half(L) = \{ w \mid ww \in L \} </tex>
}}

Операция <tex> Half </tex> также не сохраняет КС-язык таковым. Рассмотрим язык <tex> L = \{ a^n b a^n b a^m b a^l b a^k b a^k b \} </tex>. <tex> L </tex> -- КС-язык. Посмотрим, что есть <tex> Half(L) </tex>. Пусть <tex> \alpha = a^n b a^n b a^m b a^l b a^k b a^k b = ww </tex>. Отсюда следует, что:
* <tex> n = l </tex>
* <tex> n = k </tex>
* <tex> m = k </tex>

А значит, <tex> n = l = k = m </tex>, и <tex> Half(L) = \{ a^n b a^n b a^n b \} </tex>, и по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]] КС-языком не является.

== Операции над КС-языком и регулярным языком ==

=== Пересечение ===

Тем не менее, хоть пересечение двух КС-языков не обязательно является КС-языком, но пересечение КС-языка и регулярного языка -- всегда КС-язык. Для доказательства этого построим МП-автомат для пересечения регулярного языка и КС-языка.

Пусть регулярный язык задан своим [[Детерминированные конечные автоматы|ДКА]], а КС-язык -- своим МП-автоматом c допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для двух ДКА.

Более формально, пусть <tex> R </tex> -- регулярный язык, заданный своим ДКА <tex> \langle \Sigma, Q_1, s_1, T_1, \delta_1 \rangle </tex>, и <tex> L </tex> -- КС-язык, заданный своим МП-автоматом: <tex> \langle \Sigma, \Gamma, Q_2, s_2, T_2, z_0, \delta_2 \rangle </tex>. Тогда прямым произведением назовем следующий автомат:

* <tex> Q = \{ \langle q_1, q_2 \rangle \mid q_1 \in Q_1, q_2 \in Q_2 \} </tex>. Иначе говоря, состояние в новом автомате -- пара из состояния первого автомата и состояния второго автомата.
* <tex> s = \langle s_1, s_2 \rangle </tex>
* Стековый алфавит <tex> \Gamma </tex> остается неизменным.
* <tex> T = \{ \langle t_1, t_2 \rangle \mid t_1 \in T_1, t_2 \in T_2 \} </tex>. Допускающие состояния нового автомата -- пары состояний, где оба состояния были допускающими в своем автомате.
* <tex> \delta ( \langle q_1, q_2 \rangle, c, d) = \langle \delta_1 (q_1, c), \delta_2 (q_2, c, d) \rangle </tex>. При этом на стек кладется то, что положил бы изначальный МП-автомат при совершении перехода из состояния <tex> q_2 </tex>,
видя на ленте символ <tex> c </tex> и символ <tex> d </tex> на вершине стека.

Этот автомат использует в качестве состояний пары из двух состояний каждого автомата, а за операции со стеком отвечает только МП-автомат. Слово допускается этим автоматом <tex> \iff </tex> слово допускается и ДКА и МП-автоматом, то есть язык данного автомата совпадает с <tex> R \cap L </tex>.

=== Разность ===

Разность КС-языка и регулярного языка выражается следующим образом: <tex> L \setminus R = L \cap \overline{R} </tex>, а, поскольку регулярные языки замкнуты относительно дополнения, то разность можно выразить через пересечение.

Алгоритм построения Эйлерова цикла

2012-03-08T21:26:58Z

79.175.1.33: /* Доказательство */

== Описание алгоритма ==
Алгоритм находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном]], так и в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]]. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить алгоритм из вершины с нечетной степенью. 
Алгоритм напоминает поиск в глубину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины <tex>v</tex> строим путь, добавляя на каждом шаге не пройденное еще ребро. Вершины пути накапливаются в стеке <tex>S</tex>. Когда наступает момент, что для текущей вершины <tex>w</tex> все инцидентные ей ребра уже пройдены, записываем вершины из <tex>S</tex> в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Тогда продолжаем путь вперед по не посещенным ребрам.

== Псевдокод ==

findPath(v):
S.clear()
S.add(v)
while not stack.isEmpty():
w := S.top()
if E contains(w, u):
S.add(u)
remove(w, u)
else:
S.pop()
print w


== Доказательство ==
Пусть <tex>P</tex> {{---}} напечатанный путь. Заметим, что первой в <tex>S</tex> помещается вершина <tex>v</tex>, и она будет последней перемещена из <tex>S</tex> в <tex>P</tex>. Следовательно, она будет последней вершиной в <tex>P</tex>. Далее, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены, активной будет стартовая вершина <tex>v</tex> (Так как степени всех вершин четны). Значит, эта вершина будет первой перемещена из <tex>S</tex> в <tex>P</tex>. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в <tex>P</tex>, находится вершина <tex>v</tex>. Иначе говоря, если эта последовательность представляет маршрут, то этот маршрут замкнут. 
Покажем, что <tex>P</tex> это маршрут содержащий все ребра. 
Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым. 
Будем говорить, что ребро <tex>(w,u)</tex> представлено в <tex>S</tex> или <tex>P</tex>, если в какой-то момент работы алгоритма вершины <tex>w</tex> и <tex>u</tex> находятся рядом. Каждое ребро графа представлено в <tex>S</tex>. Допустим в какой-то момент из <tex>S</tex> в <tex>P</tex> перемещена вершина <tex>w</tex>, а следующей в <tex>S</tex> лежит <tex>u</tex>. Возможны 2 варианта:
#На следующем шаге <tex>u</tex> перемещена в <tex>S</tex>. Тогда <tex>(w,u)</tex> представлено в <tex>P</tex>.
#Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине <tex>u</tex>. Ввиду четности степеней эта последовательность может закончиться только в вершине <tex>u</tex>, а значит она следующей попадет в <tex>P</tex> и <tex>(w,u)</tex> будет представлено в <tex>P</tex>.

Отсюда понятно, что последовательность вершин в <tex>P</tex> является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз. 

<tex> \Box </tex>

== Рекурсивная реализация ==

findPath(v):
for (v, u) from E
remove(v, u)
findPath(u)
print v


== Время работы ==
Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.

== См. также ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]

Алгоритм построения Эйлерова цикла

2012-02-24T08:53:03Z

79.175.1.33: /* Доказательство */

== Описание алгоритма ==
Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью.

== Псевдокод ==

findPath(v):
S.clear()
S.add(v)
while not stack.isEmpty():
w := S.top()
if E contains (w, u):
S.add(u)
remove(w, u)
else:
S.pop()
print w


== Доказательство ==
Пусть <tex>P</tex> - напечатанный путь. Заметим, что первой в <tex>S</tex> помещается вершина <tex>v</tex>, и она будет последней перемещена из <tex>S</tex> в <tex>P</tex>. Следовательно, она будет последней вершиной в <tex>P</tex>. Далее, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены, активной будет стартовая вершина <tex>v</tex> (Так как степени всех вершин четны). Значит, эта вершина будет первой перемещена из <tex>S</tex> в <tex>P</tex>. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в <tex>P</tex>, находится вершина <tex>v</tex>. Иначе говоря, если эта последовательность представляет маршрут, то этот маршрут замкнут. 
Покажем, что <tex>P</tex> это маршрут содержащий все ребра. 
Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым. 
Будем говорить, что ребро <tex>(w,u)</tex> представлено в <tex>S</tex> или <tex>P</tex>, если в какой-то момент работы алгоритма вершины <tex>w</tex> и <tex>u</tex> находятся рядом. Каждое ребро графа представлено в <tex>S</tex>. Допустим в какой-то момент из <tex>S</tex> в <tex>P</tex> перемещена вершина <tex>w</tex>, а следующей в <tex>S</tex> лежит <tex>u</tex>. Возможны 2 варианта:
#На следующем шаге <tex>u</tex> перемещена в <tex>S</tex>. Тогда <tex>(w,u)</tex> представлено в <tex>P</tex>.
#Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине <tex>u</tex>. Ввиду четности степеней эта последовательность может закончиться только в вершине <tex>u</tex>, а значит она следующей попадет в <tex>P</tex> и <tex>(w,u)</tex> будет представлено в <tex>P</tex>.

Отсюда понятно, что последовательность вершин в <tex>P</tex> является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз. 

<tex> \Box </tex>

== Рекурсивная реализация ==

findPath(v):
for (v, u) from E
remove (v, u)
findPath(u)
print v


== Время работы ==
Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.

== См. также ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]

Алгоритм построения Эйлерова цикла

2012-02-24T08:45:49Z

79.175.1.33: /* Доказательство */

== Описание алгоритма ==
Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью.

== Псевдокод ==

findPath(v):
S.clear()
S.add(v)
while not stack.isEmpty():
w := S.top()
if E contains (w, u):
S.add(u)
remove(w, u)
else:
S.pop()
print w


== Доказательство ==
Пусть <tex>P</tex> - напечатанный путь. Заметим, что первой в <tex>S</tex> помещается вершина <tex>v</tex>, и она будет последней перемещена из <tex>S</tex> в <tex>P</tex>. Следовательно, она будет последней вершиной в <tex>P</tex>. Далее, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены, активной будет стартовая вершина <tex>v</tex>(Так как степени всех вершин четны). Значит, эта вершина будет первой перемещена из <tex>S</tex> в <tex>P</tex>. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в <tex>P</tex>, находится вершина <tex>v</tex>. Иначе говоря, если эта последовательность представляет маршрут, то этот маршрут замкнут. 
Покажем, что <tex>P</tex> это маршрут содержащий все ребра. 
Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым. 
Будем говорить, что ребро <tex>(w,u)</tex> представлено в <tex>S</tex> или <tex>P</tex>, если в какой-то момент работы алгоритма вершины <tex>w</tex> и <tex>u</tex> находятся рядом. Каждое ребро графа представлено в <tex>S</tex>. Допустим в какой-то момент из <tex>S</tex> в <tex>P</tex> перемещена вершина <tex>w</tex>, а следующей в <tex>S</tex> лежит <tex>u</tex>. Возможны 2 варианта:
#На следующем шаге <tex>u</tex> перемещена в <tex>S</tex>. Тогда <tex>(w,u)</tex> представлено в <tex>P</tex>.
#Сначала будет пройдена некоторая последовательность ребер, начинающаяся в вершине <tex>u</tex>. Ввиду четности степеней эта последовательность может закончиться только в вершине <tex>u</tex>, а значит она следующей попадет в <tex>P</tex> и <tex>(w,u)</tex> будет представлено в <tex>P</tex>.

Отсюда понятно, что последовательность вершин в <tex>P</tex> является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз. 

<tex> \Box </tex>

== Рекурсивная реализация ==

findPath(v):
for (v, u) from E
remove (v, u)
findPath(u)
print v


== Время работы ==
Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.

== См. также ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]

Алгоритм построения Эйлерова цикла

2012-02-23T22:17:30Z

79.175.1.33: /* Доказательство */

== Описание алгоритма ==
Приведенный ниже псевдокод алгоритма находит [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров цикл]] как в [[Ориентированный граф|ориентированном графе]], так и в неориентированном графе. Перед запуском алгоритма необходимо [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|проверить граф на эйлеровость]]. Чтобы построить [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров путь]], нужно запустить функцию из вершины с нечетной степенью.

== Псевдокод ==

findPath(v):
S.clear()
S.add(v)
while not stack.isEmpty():
w := S.top()
if E contains (w, u):
S.add(u)
remove(w, u)
else:
S.pop()
print w


== Доказательство ==
Пусть <tex>P</tex> - напечатанный путь. Заметим, что первой в <tex>S</tex> помещается вершина <tex>v</tex>, и она будет последней перемещена из <tex>S</tex> в <tex>P</tex>. Следовательно, она будет последней вершиной в <tex>P</tex>. Далее, как было отмечено выше, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены, активной будет стартовая вершина <tex>v</tex>. Значит, эта вершина будет первой перемещена из <tex>S</tex> в <tex>P</tex>. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в <tex>P</tex>, находится вершина <tex>v</tex>. Иначе говоря, если эта последовательность представляет маршрут, то этот маршрут замкнут. 
Покажем, что маршрут замкнут. 
Отметим, что в конечном итоге каждое ребро будет пройдено. Действительно, допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из <tex>S</tex>, и <tex>S</tex> не мог стать пустым.
<tex> \Box </tex>

== Рекурсивная реализация ==

findPath(v):
for (v, u) from E
remove (v, u)
findPath(u)
print v


== Время работы ==
Если реализовать удаление ребер за <tex>O(1)</tex>, то алгоритм будет работать за <tex>O(E)</tex>.

== См. также ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [http://e-maxx.ru/algo/euler_path Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]

Алгоритм построения Эйлерова цикла

2012-02-23T14:49:56Z

79.175.1.33: /* Псевдокод */