Викиконспекты ПМ-ПУ - Вклад [ru]

Евклидовы, нормированные и метрические пространства

2026-11-04T20:51:41Z

СВ: Новая страница: «{{Определение |definition= Линейное n-мерное пространство называется евклидовым векторным n-ме...»

{{Определение
|definition=
Линейное n-мерное пространство называется евклидовым векторным n-мерным пространством, если в нем задана функция, сопоставляющая двум любым элементам $a$ и $b$ этого пространства вещественное число, называемое скалярным произведением и обозначаемое $a\cdot b$, причем выполняются аксиомы:

12. $a\cdot b=b\cdot a$;

13. $\lambda (a\cdot b)=(\lambda a)\cdot b$;

14. $(a+b)\cdot c=a\cdot c+b\cdot c$;

15. $a\cdot a > 0$, если $a\ne 0$, $a\cdot a=0$, если $a=0$.
}}

Рассмотренные ранее линейные векторные пространства $V^{1}$, $V^{2}$, $V^{3}$ со скалярным произведением, определяемым по формуле <math>\vec{a}\cdot \vec{b}=|\vec{a}||\vec{b}|\cos \varphi</math>, являются евклидовыми векторными пространствами соответственно размерностей 1, 2, 3.

Векторное пространство $R^{n}$ будет евклидовым n-мерным пространством, если ввести в нем скалярное произведение для его любых двух элементов $a(\alpha_{1}, \alpha_{2}, ..., \alpha_{n} )$ и $b(\beta_{1}, \beta_{2}, ..., \beta_{n} )$ по формуле $a\cdot b=\sum_{i=1}^{n}\alpha_{i} \beta_{i} $.

Евклидово пространство еще называют конечным гильбертовым пространством.
{{Определение
|definition=
Два ненулевых элемента $a$ и $b$ евклидова пространства называются ортогональными, если равно нулю их скалярное произведение.
}}

Заметим, что для геометрических векторов $\vec{a}\cdot \vec{b}=0$ тогда и только тогда, когда $\vec{a}\bot \vec{b}$, поэтому понятие ортогональности в пространствах $V^{2} $ и $V^{3} $ эквивалентно понятию перпендикулярности.
{{Теорема
|statement=Для любых двух элементов $a$ и $b$ произвольного евклидова пространства верно неравенство <math>(a\cdot b)^{2} \le (a\cdot a)(b\cdot b), </math> называемое неравенством Коши-Буняковского.
|proof=На основании аксиомы 15 имеем неравенство $(\lambda a-b)(\lambda a-b)\ge 0$, которое можно представить в виде
<math>\lambda ^{2} (a\cdot a)-2\lambda (a\cdot b)+(b\cdot b)\ge 0</math>.

Так как $a\cdot a > 0$, то необходимым и достаточным условием неотрицательности квадратного трехчлена относительно $\lambda$ является неположительность его дискриминанта, то есть $(a\cdot b)^{2} \le (a\cdot a)(b\cdot b)$. Теорема доказана.
}}
Из неравенства Коши-Буняковского следует, что $-1\le \frac{(a\cdot b)}{\sqrt{a\cdot a} \cdot \sqrt{b\cdot b} } \le 1$. Следовательно, в любом евклидовом векторном пространстве можно определить
<math>\left|a\right|=\sqrt{a\cdot a}</math>, <math>\cos \varphi =\frac{a\cdot b}{\left|a\right|\cdot \left|b\right|}</math>, <math>\varphi =\arccos \frac{a\cdot b}{\left|a\right|\cdot \left|b\right|}</math>.

В евклидовом точечном пространстве (то есть в аффинном пространстве, в котором присоединенный линеал является евклидовым векторным пространством) можно находить расстояние между точками <math>d(A,B)=\left|\overrightarrow{AB} \right|=\sqrt{\overrightarrow{AB} \cdot \overrightarrow{AB} }</math>.
{{Определение
|definition=
Линейное n-мерное пространство $L$ называется нормированным, если имеется правило, посредством которого всякому элементу $x\in L$ ставится в соответствие вещественное число, называемое нормой указанного элемента и обозначаемое символом <math>\left\| x\right\|</math>, причем должны выполняться соотношения:

* <math>\left\| x\right\| \ge 0</math>, если $x\ne 0$, <math>\left\| x\right\| =0</math>, если $x=0$;
* <math>\left\| \lambda x\right\| =\left|\lambda \right|\cdot \left\| x\right\|</math> для любого $x\in L$ и произвольного вещественного числа $\lambda $;
* <math>\left\| x+y\right\| \le \left\| x\right\| +\left\| y\right\|</math> для любых $x,y\in L$.
}}

[[Файл:p03-17-02-triangle-inequality.svg|frame|none|800px|alt=Слева векторы x и y под углом друг к другу и их сумма: длина суммы меньше суммы длин. Справа сонаправленные векторы: длина суммы равна сумме длин.|Рис. 1. Неравенство <math>|x+y| \le |x|+|y|</math>: при несонаправленных векторах оно строгое, при сонаправленных превращается в равенство. Доказательство опирается на неравенство Коши — Буняковского: <math>x\cdot y\le|x| |y|</math>.]]

{{Теорема
|statement=Всякое евклидово пространство будет нормированным, если норму в нем определить равенством
<math>\left\| x\right\| =\sqrt{x\cdot x}</math>.
|proof=Справедливость для нормы первых двух условий вытекает из соответствующих аксиом для скалярного произведения. Опираясь на неравенство Коши-Буняковского, убедимся в справедливости последнего неравенства. Действительно, <math>\left|x\cdot y\right|\le \sqrt{x\cdot x} \cdot \sqrt{y\cdot y}</math>. Тогда
<math>\left\| x+y\right\| =\sqrt{(x+y)\cdot (x+y)} =\sqrt{(x\cdot x)+2(x\cdot y)+(y\cdot y)} \le \sqrt{(x\cdot x)+2\sqrt{x\cdot x} \sqrt{y\cdot y} +(y\cdot y)} =\sqrt{(\sqrt{x\cdot x} +\sqrt{y\cdot y} )^{2} } =\left\| x\right\| +\left\| y\right\|</math>.
}}
Сосредоточив внимание на линейных операциях в множестве, мы пришли к понятию линейного (векторного) пространства, а потом аффинного (точечного) пространства. Введя скалярное произведение в ассоциированном векторном пространстве, мы пришли к евклидову точечному пространству. Обратим теперь внимание на одно лишь свойство точечного множества {{---}} на наличие расстояния в нем. Это приводит нас к понятию метрического пространства.
{{Определение
|definition=
Множество называется метрическим пространством, если каждой паре его элементов сопоставляется по некоторому правилу неотрицательное вещественное число, называемое расстоянием, причем справедливы соотношения:

* $\rho (x,y) > 0$, если $x\ne y$; $\rho (x,y)=0$, если $x=y$;
* $\rho (x,y)=\rho (y,x)$;
* $\rho (x,y)\le \rho (x,z)+\rho (z,y)$.
}}

Отметим, что нормированное пространство можно превратить в метрическое, если положить <math>\rho (x,y)=\left\| x - y \right\|</math>.

Линейное метрическое пространство легко превратить в нормированное, если положить <math>\left\| x \right\| =\rho (x,0)</math>.

[[Файл:p03-17-01-space-hierarchy.svg|frame|none|800px|alt=Пять блоков сверху вниз: линейное, аффинное, евклидово, нормированное и метрическое пространства, с указанием того, что добавляется или остаётся на каждом уровне.|Рис. 2. Пять уровней структуры: линейное пространство, аффинное, евклидово со скалярным произведением, нормированное с нормой <math>|x|=\sqrt{x\cdot x}</math> и метрическое с расстоянием <math>\rho(x,y)=|x-y|</math>. Сверху вниз структура только теряется, поэтому обратные переходы возможны не всегда.]]

----

Конспект: [[Алгебра и геометрия]]

Файл:P03-17-01-space-hierarchy.svg

2026-11-04T20:49:09Z

СВ:

Файл:P03-17-02-triangle-inequality.svg

2026-11-04T20:48:55Z

СВ:

Скалярное произведение векторов

2026-11-04T19:02:13Z

СВ:

{{Определение
|definition=
Углом между векторами $\vec{a}$ и $\vec{b}$ называется наименьший угол между векторами $\vec{a'}$ и $\vec{b'}$, равными соответственно $\vec{a}$ и $\vec{b}$ и имеющими общее начало.
}}
Если ненулевые векторы сонаправлены, то угол между ними полагают равным $0$, если ненулевые векторы противоположно направлены, то угол между ними считают равным $\pi$.
{{Определение
|definition=
Скалярным произведением $\vec{a}\cdot \vec{b}$ двух векторов $\vec{a}$ и $\vec{b}$ называется произведение их модулей и косинуса угла между ними, то есть
<math>
\vec{a}\cdot \vec{b}= |\vec{a}|\cdot |\vec{b}|\cos \varphi .
</math>
}}

Непосредственно из определения следует, что <math>\vec{a}\cdot \vec{a}= |\vec{a}|^{2}</math>, поэтому <math>\left|\vec{a}\right|=\sqrt{\vec{a}\cdot \vec{a} }</math>, причем <math>\vec{a}\cdot \vec{a}>0</math>, если <math>\vec{a} \ne \vec{0}</math>.

Число $\vec{a}\cdot \vec{a}=\vec{a}^{2} $ называется скалярным квадратом вектора $\vec{a}$.

Пусть орт вектора $\vec{a}$ равен <math>\vec{g}=\frac{\vec{a} }{|\vec{a}|}</math>, а <math>\vec{q}=\frac{\vec{b} }{|\vec{b}|}</math> {{---}} орт вектора $\vec{b}$. Тогда в соответствии с теоремой имеем <math>Apr_{\vec{g} } \vec{b}= |\vec{b}|\cos \varphi</math>, <math>Apr_{\vec{q} } \vec{a}= |\vec{a}|\cos \varphi</math>, а в силу определения скалярного произведения получаем
<math> \vec{a}\cdot \vec{b}= |\vec{a}|Apr_{\vec{g} } \vec{b} = |\vec{b}| Apr_{\vec{q} } \vec{a} </math>.

[[Файл:p03-16-01-dot-product-sign.svg|thumb|800px|alt=Три панели с векторами a и b из общего начала: острый угол — проекция положительна, прямой — равна нулю, тупой — отрицательна.|Рис. 1. Знак <math>\vec a\cdot\vec b</math> определяется углом: при остром угле проекция <math>b</math> на <math>a</math> положительна, при прямом равна нулю, при тупом направлена против <math>a</math> и произведение отрицательно. Везде <math>\vec a\cdot\vec b=|\vec a| |\vec b|\cos\varphi</math>.]]

Понятие скалярного произведения векторов впервые появились в механике. Если вектор $\vec{a}$ изображает силу, точка приложения которой перемещается из начала в конец вектора $\vec{b}$, то работа A указанной силы определяется равенством $A= |\vec{a}|\cdot |\vec{b}|\cos \varphi$.

{{Теорема
|about=свойства скалярного произведения
|statement=Для любых трех векторов $\vec{a}, \vec{b}, \vec{c}$ и произвольного числа $\lambda$ справедливы следующие свойства:

* $\vec{a}\cdot \vec{b}=\vec{b}\cdot \vec{a}$ (коммутативность);
* $\lambda (\vec{a}\cdot \vec{b})=(\lambda \vec{a})\cdot \vec{b}$ (ассоциативность относительно числового множителя);
* $(\vec{a}+\vec{b})\cdot \vec{c}=\vec{a}\cdot \vec{c}+\vec{b}\cdot \vec{c}$ (дистрибутивность относительно суммы векторов);
* $\vec{a}\cdot \vec{a}>0$, если $\vec{a}$ {{---}} ненулевой вектор; $\vec{a}\cdot \vec{a}=0$, если $\vec{a}$ {{---}} нулевой вектор.

|proof= Первое свойство непосредственно вытекает из определения скалярного произведения. Для второго и третьего свойств имеем
<math>(\lambda \vec{a})\cdot \vec{b}= |\vec{b}|Apr_{\vec{q} } (\lambda \vec{a})=\lambda |\vec{b}|Apr_{\vec{q} } (\vec{a})=\lambda (\vec{a}\cdot \vec{b}),</math>
<math>(\vec{a}+\vec{b})\cdot \vec{c}= |\vec{c}|Apr_{\vec{e} } (\vec{a}+\vec{b})= |\vec{c}|Apr_{\vec{e} } \vec{a}+ |\vec{c}|Apr_{\vec{e} } \vec{b}=\vec{a}\cdot \vec{c}+\vec{b}\cdot \vec{c},</math>
где орт <math>\vec{e}=\frac{\vec{c} }{|\vec{c}|}</math>. Наконец, четвертое свойство вытекает непосредственно из определения.
}}
{{Теорема
|statement=Скалярное произведение двух векторов, заданных в произвольной аффинной системе координат $O\vec{e}_{1} \vec{e}_{2} \vec{e}_{3} $ своими координатами $\vec{a}(\alpha_{1}, \alpha_{2}, \alpha_{3} )$ и $\vec{b}(\beta_{1}, \beta_{2}, \beta_{3} )$, находится по формуле
<math>\vec{a}\cdot \vec{b}=\alpha_{1} \beta_{1} (\vec{e}_{1} \cdot \vec{e}_{1} )+(\alpha_{1} \beta_{2} +\alpha_{2} \beta_{1} )(\vec{e}_{1} \cdot \vec{e}_{2} )+\alpha_{2} \beta_{2} (\vec{e}_{2} \cdot \vec{e}_{2} )+(\alpha_{1} \beta_{3} +\alpha_{3} \beta_{1} )(\vec{e}_{1} \cdot \vec{e}_{3} )+(\alpha_{2} \beta_{3} +\alpha_{3} \beta_{2} )(\vec{e}_{2} \cdot \vec{e}_{3} )+\alpha_{3} \beta_{3} (\vec{e}_{3} \cdot \vec{e}_{3} ).</math>

|proof= Формула получается с помощью простых вычислений, если воспользоваться представлениями заданных векторов через базис $\vec{a}=\alpha_{1} \vec{e}_{1} +\alpha_{2} \vec{e}_{2} +\alpha_{3} \vec{e}_{3}$, $\vec{b}=\beta_{1} \vec{e}_{1} +\beta_{2} \vec{e}_{2} +\beta_{3} \vec{e}_{3} $ и свойствами скалярного произведения.
}}
Величины $g_{ij} $=$\vec{e}_{i} \cdot \vec{e}_{j} $ называются метрическими коэффициентами системы координат $O\vec{e}_{1} \vec{e}_{2} \vec{e}_{3} $. Таким образом, для вычисления скалярного произведения двух векторов в аффинной системе координат необходимо знать координаты этих векторов и метрические коэффициенты системы координат.

Модуль произвольного вектора $\vec{a}(\alpha_{1}, \alpha_{2}, \alpha_{3} )$ в произвольной аффинной системе координат $O\vec{e}_{1} \vec{e}_{2} \vec{e}_{3} $ вычисляется по формуле
<math>|\vec{a}|=\sqrt{\vec{a}\cdot \vec{a} } =\sqrt{\alpha_{1}^{2} g_{11} +\alpha_{2}^{2} g_{22} +\alpha_{3}^{2} g_{33} +2\alpha_{1} \alpha_{2} g_{12} +2\alpha_{1} \alpha_{3} g_{13} +2\alpha_{2} \alpha_{3} g_{23} }</math>.

Угол $\varphi$ между двумя векторами $\vec{a}(\alpha_{1}, \alpha_{2}, \alpha_{3} )$ и $\vec{b}(\beta_{1}, \beta_{2}, \beta_{3} )$ в аффинной системе координат $O\vec{e}_{1} \vec{e}_{2} \vec{e}_{3} $ находится по формуле
<math>\varphi = \arccos \frac{\vec{a}\cdot \vec{b} }{|\vec{a}|\cdot |\vec{b}|}</math>.

Для векторов, заданных своими координатами в ДПСК, справедливы формулы

* $n=3$: $\vec{a}=\alpha_{x} \vec{i}+\alpha_{y} \vec{j}+\alpha_{z} \vec{k}$, $\vec{b}=\beta_{x} \vec{i}+\beta_{y} \vec{j}+\beta_{z} \vec{k}$, $\vec{a}\cdot \vec{b}=\alpha_{x} \beta_{x} +\alpha_{y} \beta_{y} +\alpha_{z} \beta_{z}$, <math>|\vec{a}|$=$\sqrt{\alpha_{x}^{2} +\alpha_{y}^{2} +\alpha_{z}^{2} }</math>, <math>\varphi=\angle (\vec{a},\vec{b})=\arccos \frac{\alpha_{x} \beta_{x} +\alpha_{y} \beta_{y} +\alpha_{z} \beta_{z} }{\sqrt{\alpha_{x}^{2} +\alpha_{y}^{2} +\alpha_{z}^{2} } \cdot \sqrt{\beta_{x}^{2} +\beta_{y}^{2} +\beta_{z}^{2} } } </math>;
* $n=2$: $\vec{a}=\alpha_{x} \vec{i}+\alpha_{y} \vec{j}$, $\vec{b}=\beta_{x} \vec{i}+\beta_{y} \vec{j}$,
$\vec{a}\cdot \vec{b}=\alpha_{x} \beta_{x} +\alpha_{y} \beta_{y}, |\vec{a}|=\sqrt{\alpha_{x}^{2} +\alpha_{y}^{2} }$,
$\varphi =\angle (\vec{a},\vec{b})=\arccos \frac{\alpha_{x} \beta_{x} +\alpha_{y} \beta_{y} }{\sqrt{\alpha_{x}^{2} +\alpha_{y}^{2} } \cdot \sqrt{\beta_{x}^{2} +\beta_{y}^{2} } } $;
* $n=1$: $\vec{a}=\alpha_{x} \vec{i}, \vec{b}=\beta_{x} \vec{i},$ <math>\vec{a}\cdot \vec{b}=\alpha_{x} \beta_{x}</math>, <math>|\vec{a}| = |\alpha_{x} |, \varphi =\angle (\vec{a},\vec{b})=\arccos \frac{\alpha_{x} \beta_{x} }{|\alpha_{x} ||\beta_{x} |}</math>.

Поскольку расстояние между двумя точками $A(x_{A}, y_{A}, z_{A} )$ и $B(x_{B}, y_{B}, z_{B} )$ в трехмерном пространстве равно модулю вектора $\overrightarrow{AB} (x_{B} -x_{A}, y_{B} -y_{A}, z_{B} -z_{A} )$, то получаем следующую формулу для нахождения расстояния между названными точками в заданной ДПСК:
<math>d(A,B)=\sqrt{(x_{B} -x_{A} )^{2} +(y_{B} -y_{A} )^{2} +(z_{B} -z_{A} )^{2} }</math>.

Аналогично расстояние между двумя точками $A(x_{A}, y_{A} )$ и $B(x_{B}, y_{B})$ на плоскости находятся по формуле
<math>d(A,B)=\sqrt{(x_{B} -x_{A} )^{2} +(y_{B} -y_{A} )^{2} }</math>,
а расстояние между двумя точками $A(x_{A} )$ и $B(x_{B} )$ на прямой соответственно по формуле
<math>d(A,B)=|x_{B} -x_{A} |</math>.
{{Теорема
|statement=Необходимым и достаточным условием перпендикулярности двух ненулевых векторов в трехмерном пространстве $\vec{a}(\alpha_{x}, \alpha_{y}, \alpha_{z} )$ и $\vec{b}(\beta_{x}, \beta_{y}, \beta_{z} )$, заданных в ДПСК своими координатами, является равенство
<math>\label{GrindEQ__3_16_14_}
\alpha_{x} \beta_{x} +\alpha_{y} \beta_{y} +\alpha_{z} \beta_{z} = 0.
</math>
}}
Доказательство непосредственно следует из определения скалярного произведения.

{{Теорема
|statement=Декартовы прямоугольные координаты вектора $\vec{a}(\alpha_{x}, \alpha_{y}, \alpha_{z} )$ равны скалярным произведениям этого вектора на соответствующие базисные векторы, то есть
<math>
\alpha_{x} =\vec{a}\cdot \vec{i}, \alpha_{y} =\vec{a}\cdot \vec{j}, \alpha_{z} =\vec{a}\cdot \vec{k}.
</math>
|proof=Пусть $\vec{i}$,$\vec{j}$,$\vec{k}$ {{---}} ортонормированный базис. Тогда $\vec{a}=\alpha_{x} \vec{i}+\alpha_{y} \vec{j}+\alpha_{z} \vec{k}$, причем
<math>\vec{a}\cdot \vec{i}=\alpha_{x} \vec{i}\cdot \vec{i}+\alpha_{y} \vec{j}\cdot \vec{i}+\alpha_{z} \vec{k}\cdot \vec{i}=\alpha_{x}</math>;
<math>\vec{a}\cdot \vec{j}=\alpha_{x} \vec{i}\cdot \vec{j}+\alpha_{y} \vec{j}\cdot \vec{j}+\alpha_{z} \vec{k}\cdot \vec{j}=\alpha_{y}</math>;
<math>\vec{a}\cdot \vec{k}=\alpha_{x} \vec{i}\cdot \vec{k}+\alpha_{y} \vec{j}\cdot \vec{k}+\alpha_{z} \vec{k}\cdot \vec{k}=\alpha_{z}</math>.
}}

[[Файл:p03-16-02-dot-product-coordinates.svg|thumb|800px|alt=Вектор a в декартовой системе с координатным параллелепипедом: рёбра вдоль осей равны αx, αy, αz. Справа формулы для скалярного произведения, модуля и условия перпендикулярности.|Рис. 2. В ДПСК координаты вектора — это его проекции на орты, поэтому <math>\alpha_x=\vec a\cdot\vec i</math> и т. д. Отсюда <math>\vec a\cdot\vec b=\alpha_x\beta_x+\alpha_y\beta_y+\alpha_z\beta_z</math>, <math>|\vec a|=\sqrt{\vec a\cdot\vec a}</math>, а перпендикулярность означает <math>\vec a\cdot\vec b=0</math>.]]

Рассмотрим в ДПСК $O\vec{i} \vec{j}\vec{k}$ вектор $\overrightarrow{OM}$, приведенный в начало $O$, и его орт $\vec{e}$. Пусть $\alpha =\angle (\vec{e},\vec{i}), \beta =\angle (\vec{e},\vec{j}), \gamma =\angle (\vec{e},\vec{k})$.
{{Определение
|definition=
Косинусы $\cos \alpha$, $\cos \beta$, $\cos \gamma$ называются направляющими косинусами вектора $\overrightarrow{OM} $.
}}
{{Теорема
|statement=Направляющие косинусы вектора являются декартовыми координатами орта данного вектора.
|proof= Пусть $\vec{e}$ {{---}} орт вектора $\overrightarrow{OM}$, причем $\vec{e}=e_{x} \vec{i}+e_{y} \vec{j}+e_{z} \vec{k}$. Тогда в силу теоремы 3.16.4 и определения скалярного произведения имеем
<math> e_{x} = \vec{e}\cdot \vec{i} = |\vec{e}||\vec{i}|\cos \alpha = \cos \alpha,</math>
<math> e_{y} = \vec{e}\cdot \vec{j} = |\vec{e}||\vec{j}|\cos \beta = \cos \beta,</math>
<math> e_{z} = \vec{e}\cdot \vec{k} = |\vec{e}||\vec{k}|\cos \gamma = \cos \gamma,</math>
что и требовалось доказать.
}}
Для направляющих косинусов справедливо соотношение
<math>\cos ^{2} \alpha +\cos ^{2} \beta +\cos ^{2} \gamma =1</math>.

----

Конспект: [[Алгебра и геометрия]]

Файл:P03-16-01-dot-product-sign.svg

2026-11-04T18:52:08Z

СВ:

Файл:P03-16-02-dot-product-coordinates.svg

2026-11-04T18:51:59Z

СВ:

Геометрический смысл аффинных координат

2026-11-04T18:45:03Z

СВ: Новая страница: «Рассмотрим прямую $O\vec{e}_{1} $ и вектор $\overrightarrow{OM} =\vec{a}$, коллинеарный вектору $\vec{e}_{1} $. Тогд...»

Рассмотрим прямую $O\vec{e}_{1} $ и вектор $\overrightarrow{OM} =\vec{a}$, коллинеарный вектору $\vec{e}_{1} $. Тогда, $\vec{a}=\lambda \vec{e}_{1}$, причем $\lambda =\frac{|\vec{a}|}{|\vec{e}_{1} |}$, если $\vec{a}\uparrow \uparrow \vec{e}_{1}$, и $\lambda =-\frac{|\vec{a}|}{|\vec{e}_{1} |}$, если $\vec{a}\uparrow \downarrow \vec{e}_{1} $.

{{Определение
|definition=
Указанное число $\lambda$ называется алгебраической мерой вектора $\vec{a}$ на оси, определяемой вектором $\vec{e}_{1}$, и обозначается $\lambda =mes_{\vec{e}_{1} } \vec{a}$.
}}

[[Файл:p03-10-01-algebraic-measure.svg|thumb|800px|alt=Ось с единичным вектором e; над ней a = 2e, b = −1,5e и a + b = 0,5e, под ней шкала от −2 до 3|Рис. 1. Мера вектора на оси — коэффициент <math>\lambda</math> в равенстве <math>a = \lambda e</math>. Поэтому у <math>a = 2e</math> мера равна 2, у <math>b = -1{,}5e</math> равна −1,5, а у суммы <math>a + b = 0{,}5e</math> — 0,5: мера линейна.]]

С учетом введенного обозначения, очевидно, что $\vec{a}=\left(mes_{\vec{e}_{1} } \vec{a}\right)\vec{e}_{1} $.

{{Лемма
|statement=Для любых трех коллинеарных векторов $\vec{a}, \vec{b}, \vec{e}$ и произвольного числа $\lambda$ справедливы соотношения $mes_{\vec{e} } \left(\vec{a}+\vec{b}\right)=mes_{\vec{e} } \vec{a}+mes_{\vec{e} } \vec{b}, mes_{\vec{e} } \left(\lambda \vec{a}\right)=\lambda mes_{\vec{e} } \vec{a}$.
|proof= Пусть $\lambda \vec{a}\uparrow \uparrow \vec{e}$, тогда по определению алгебраической меры вектора
$ mes_{\vec{e} } \left(\lambda \vec{a}\right) = \frac{|\lambda \vec{a}|}{|\vec{e}|} = |\lambda |\frac{|\vec{a}|}{|\vec{e}|} =
\left[ \begin{array}{l}
{\lambda \frac{|\vec{a}|}{|\vec{e}|} =\lambda mes_{\vec{e} } \vec{a}, \lambda > 0;} \\
{-\lambda \frac{|\vec{a}|}{|\vec{e}|} =\lambda \left(-\frac{|\vec{a}|}{|\vec{e}|} \right) = \lambda mes_{\vec{e} } \vec{a}, \lambda < 0.}
\end{array} \right.
$

Если $\lambda \vec{a}\uparrow \downarrow \vec{e}$, то
$mes_{\vec{e} } \left(\lambda \vec{a}\right)=-\frac{|\lambda \vec{a}|}{|\vec{e}|} = - |\lambda |\frac{|\vec{a}|}{|\vec{e}|} =\left[\begin{array}{l} {-\lambda \frac{|\vec{a}|}{|\vec{e}|} =\lambda \left(-\frac{|\vec{a}|}{|\vec{e}|} \right)=\lambda mes_{\vec{e} } \vec{a}, \lambda > 0;} \\ {\lambda \frac{|\vec{a}|}{|\vec{e}|} =\lambda mes_{\vec{e} } \vec{a}, \lambda < 0.} \end{array}\right. $

Рассмотрим теперь алгебраическую меру суммы векторов. Так как по условию векторы $\vec{a}, \vec{b}$ являются коллинеарными, то будем считать, что $\vec{b}=\mu \vec{a}$. Тогда
$mes_{\vec{e} } \left(\vec{a}+\vec{b}\right)=mes_{\vec{e} } \left(\vec{a}+\mu \vec{a}\right)=mes_{\vec{e} } \left(1+\mu \right)\vec{a}=\left(1+\mu \right)mes_{\vec{e} } \vec{a}=mes_{\vec{e} } \vec{a}+\mu mes_{\vec{e} } \vec{a} = mes_{\vec{e} } \vec{a}+mes_{\vec{e} } \vec{b}$.
}}

Таким образом, можно утверждать, что аффинная координата произвольной точки $M$ на координатной оси равна алгебраической мере ее радиус-вектора $\overrightarrow{OM} $.

Пусть задана аффинная система координат $O\vec{e}_{1} \vec{e}_{2} $ и произвольный вектор $\vec{a}= \overrightarrow{NM} $. Спроектируем начало и конец данного вектора на координатные оси, получаем соответственно $\overrightarrow{N_{1} M_{1} } $ и $\overrightarrow{N_{2} M_{2} } $.
{{Определение
|definition=
Вектор $\overrightarrow{N_{1} M_{1} }$ ($\overrightarrow{N_{2} M_{2} }$) называется геометрической проекцией вектора $\vec{a}$ на координатную ось $O\vec{e}_{1} $ ($O\vec{e}_{2} $).
}}
Для геометрической проекции вектора на координатные оси будем использовать обозначение $\overrightarrow{N_{1} M_{1} } =\mbox{Proj}_{\vec{e}_{1} } \vec{a}$, $\overrightarrow{N_{2} M_{2} } =\mbox{Proj}_{\vec{e}_{2} } \vec{a}$.

В соответствии с правилом параллелограмма $\overrightarrow{NM} =\overrightarrow{N_{1} M_{1} } +\overrightarrow{N_{2} M_{2} }$, то есть
$\vec{a}=\mbox{Proj}_{\vec{e}_{1} } \vec{a}+\mbox{Proj}_{\vec{e}_{2} } \vec{a}$.

С другой стороны, векторы $\overrightarrow{N_{1} M_{1} } || \vec{e}_{1}$, $\overrightarrow{N_{2} M_{2} } || \vec{e}_{2}$, поэтому $\overrightarrow{N_{1} M_{1} } =\left(mes_{\vec{e}_{1} } \overrightarrow{N_{1} M_{1} } \right) \vec{e}_{1}$, $\overrightarrow{N_{2} M_{2} } =\left(mes_{\vec{e}_{2} } \overrightarrow{N_{2} M_{2} } \right) \vec{e}_{2}$, следовательно,
$\vec{a}=\left(mes_{\vec{e}_{1} } (\mbox{Proj}_{\vec{e}_{1} } \vec{a})\right) \vec{e}_{1} +\left(mes_{\vec{e}_{2} } (\mbox{Proj}_{\vec{e}_{2} } \vec{a})\right) \vec{e}_{2}$.

{{Определение
|definition=
Алгебраическая мера геометрической проекции вектора на координатную ось называется алгебраической проекцией вектора.
}}

[[Файл:p03-10-02-projections.svg|thumb|800px|alt=Вектор a = NM и его проекции N1M1 на ось Oe1 и N2M2 на ось Oe2, полученные параллельным проектированием|Рис. 2. Точки <math>N</math> и <math>M</math> спроецированы на оси: получаются <math>N_1M_1 = \operatorname{Proj}_{e_1} a</math> и <math>N_2M_2 = \operatorname{Proj}_{e_2} a</math>. Алгебраические проекции — меры этих векторов, они и служат координатами: <math>a = (\operatorname{Apr}_{e_1} a)e_1 + (\operatorname{Apr}_{e_2} a)e_2</math>.]]

Алгебраическая проекция вектора на ось $O\vec{e}_{i} $ обозначается $Apr_{\vec{e}_{i} } \vec{a}=mes_{\vec{e}_{i} } (\mbox{Proj}_{\vec{e}_{i} } \vec{a})$. Тогда с учетом введенного обозначения вектор $\vec{a}=(Apr_{\vec{e}_{i} } \vec{a})\vec{e}_{1} +(Apr_{\vec{e}_{2} } \vec{a})\vec{e}_{2}$, то есть аффинными координатами произвольного вектора являются его алгебраические проекции на координатные оси, а аффинными координатами произвольной точки {{---}} алгебраические проекции ее радиус-вектора на соответствующие координатные оси.

Допустим теперь, что в системе координат $O\vec{e}_{1} \vec{e}_{2} \vec{e}_{3} $ задан произвольный вектор $\vec{a}=$$\overrightarrow{NM} $. Спроектируем точки $N$ и $M$ на координатные оси. Тогда точки $N_1$ и $M_1$ определяют вектор $\overrightarrow{N_{1} M_{1} } =\mbox{Proj}_{\vec{e}_{1} } \vec{a}$, точки $N_2$ и $M_2$ {{---}} вектор $\overrightarrow{N_{2} M_{2} } =\mbox{Proj}_{\vec{e}_{2} } \vec{a}$, а точки $N_3$ и $M_3$ {{---}} соответственно вектор $\overrightarrow{N_{3} M_{3} } =\mbox{Proj}_{\vec{e}_{3} } \vec{a}$. В соответствии с правилом сложения векторов $\overrightarrow{NM} =\overrightarrow{N_{1} M_{1} } +\overrightarrow{N_{2} M_{2} } +\overrightarrow{N_{3} M_{3} }$, поэтому
$\vec{a}=\mbox{Proj}_{\vec{e}_{1} } \vec{a}+\mbox{Proj}_{\vec{e}_{2} } \vec{a}+\mbox{Proj}_{\vec{e}_{3} } \vec{a}=(Apr_{\vec{e}_{1} } \vec{a})\vec{e}_{1} +(Apr_{\vec{e}_{2} } \vec{a})\vec{e}_{2} +(Apr_{\vec{e}_{3} } \vec{a})\vec{e}_{3}$.

Следовательно, аффинные координаты произвольного вектора есть его алгебраические проекции на координатные оси, а аффинные координаты произвольной точки {{---}} алгебраические проекции ее радиус-вектора на соответствующие координатные оси.

----

Конспект: [[Алгебра и геометрия]]

Файл:P03-10-02-projections.svg

2026-11-04T18:44:12Z

СВ:

Файл:P03-10-01-algebraic-measure.svg

2026-11-04T18:44:01Z

СВ:

Аффинные системы координатa

2026-11-04T18:39:20Z

СВ: Новая страница: «Аффинная система координат <math>O e_{1} e_{2} ... e_{n}</math> в аффинном пространстве $A^n$ есть совокуп...»

Аффинная система координат <math>O e_{1} e_{2} ... e_{n}</math> в аффинном пространстве $A^n$ есть совокупность, состоящая из произвольной точки $O$, называемой началом координат, и базиса $e_{1}, e_{2}, ..., e_{n}$ из присоединенного линеала $L^{n}$.

[[Файл:p03-09-01-affine-frame.svg|thumb|600px|alt=Слева система O, e1, e2 и точка A(2; 1) с радиус-вектором; справа точки A(1; 2), B(2; 1) и вектор AB = (1; −1)|Рис. 1. Слева система <math>O, e_1, e_2</math>: точка <math>A</math> имеет координаты <math>(2; 1)</math>, потому что <math>OA = 2e_1 + e_2</math>. Справа <math>A(1; 2)</math>, <math>B(2; 1)</math> и вектор <math>AB = (1; -1)</math>: координаты вектора — разности координат точек.]]

Подчеркнем, что аффинная система координат задается двумя разнородными объектами {{---}} точкой $O$ из аффинного пространства и базисом $e_{1}, e_{2}, ..., e_{n} $ из присоединенного линеала.

Пусть $A$ {{---}} произвольная точка аффинного пространства $A^n$. Вместе с началом координат $O$ точка $A$ определяет элемент (радиус-вектор) $r_{A} =OA\in L^{n}$, координаты которого определяются из разложения по базису $e_{1}, e_{2}, ..., e_{n}$: $OA=x_{1} e_{1} + x_{2} e_{2} +...+ x_{n} e_{n} $.

Аффинными координатами произвольной точки $A\in A^n$ называют координаты соответствующего радиус-вектора $r_{A} =OA\in L^{n} $ и обозначают символом $A(x_{1}, x_{2}, ..., x_{n} )$.

Ясно, что координаты точки $А$ определяются однозначно в силу единственности разложения вектора по заданному базису.

Произвольный вектор $AB\in L^{n} $ можно представить как разность соответствующих радиус-векторов $AB=r_{B} -r_{A} $.

Если вектор $AB$ задан координатами своего начала $A(x_{1}, x_{2}, ..., x_{n} )$ и конца $B(y_{1}, y_{2}, ..., y_{n} )$ относительно базиса $e_{1}, e_{2}, ..., e_{n}$, то его координаты относительно того же базиса определяются из соотношения как коэффициенты разложения по указанному базису в виде
<math>AB=(y_{1} - x_{1} )e_{1} +(y_{2} - x_{2} )e_{2} +...+(y_{n} - x_{n} )e_{n}</math>
и обычно используют обозначение $AB(y_{1} -x_{1}, y_{n} -x_{2}, ..., y_{n} -x_{n} )$.

Прямой в аффинном пространстве $A^n$, проходящей через точку $C\in A^n$ в направлении ненулевого вектора $u\in L^{n}$, называется множество всех точек $P\in A^n$, для которых $CP=\lambda u$, где $\lambda \in (-\infty, +\infty )$ {{---}} вещественное число. Указанный вектор $u$ называется направляющим вектором прямой.

При рассмотрении аффинных систем координат на прямой, плоскости и трехмерном пространстве, базисные векторы соответствующих линеалов $V^{1}$, $V^{2}$, $V^{3} $ приводятся в общее начало.

Прямые в рассматриваемых пространствах, определяемые началом координат $O$ и соответствующими базисными векторами, называются осями координат ($O\vec{e}_{1}$, $O\vec{e}_{2}$, $O\vec{e}_{3}$); ($O\vec{e}_{1}$, $O\vec{e}_{2} $); $O\vec{e}_{1} $.

В трехмерном аффинном пространстве рассматривают также координатные плоскости, определяемые соответствующими парами координатных осей ($O\vec{e}_{1} \vec{e}_{2}$, $O\vec{e}_{1} \vec{e}_{3}$, $O\vec{e}_{2} \vec{e}_{3} $).

{{Определение
|definition=
Тройка базисных векторов $\vec{e}_{1}$, $\vec{e}_{2}$, $\vec{e}_{3} $ называется правой (левой), если после приведения их к общему началу по этим векторам можно направить соответственно большой, несогнутый указательный и средний пальцы правой (левой) руки.
}}

[[Файл:p03-09-02-orientation.svg|thumb|600px|alt=Слева правая пара e1, e2 с поворотом против часовой стрелки; справа правая тройка e1, e2, e3 и круговые перестановки|Рис. 2. Слева пара <math>e_1, e_2</math> правая: кратчайший поворот от первого вектора ко второму идёт против часовой стрелки. Справа правая тройка: большой, указательный и средний пальцы правой руки направлены вдоль <math>e_1, e_2, e_3</math>; круговая замена порядка ориентацию не меняет.]]

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

Очевидно, что при круговой замене ориентация тройки не изменяется, то есть если $\vec{e}_{1}$, $\vec{e}_{2}$, $\vec{e}_{3} $ правая тройка векторов, то $\vec{e}_{3}$, $\vec{e}_{1}$, $\vec{e}_{2} $ и $\vec{e}_{2}$, $\vec{e}_{3}$, $\vec{e}_{1} $ также будут правыми.

Упорядоченная пара базисных векторов $\vec{e}_{1}$, $\vec{e}_{2} $ называется правой (левой), если кратчайший поворот от $\vec{e}_{1} $ к $\vec{e}_{2} $ происходит против (по) часовой стрелки.

Аффинная система координат называется правой (левой), если ее базис правый (левый). В дальнейшем ради определенности будем рассматривать только правые системы координат.

----

Конспект: [[Алгебра и геометрия]]

Файл:P03-09-02-orientation.svg

2026-11-04T18:38:35Z

СВ:

Файл:P03-09-01-affine-frame.svg

2026-11-04T18:38:27Z

СВ:

Аффинные пространства

2026-11-04T18:35:54Z

СВ: Новая страница: «{{Определение |definition= Аффинное пространство {{---}} это множество $A$ элементов произвольной...»

{{Определение
|definition=
Аффинное пространство {{---}} это множество $A$ элементов произвольной природы, называемых точками, которому сопоставлены:

1) линеал $L$, называемый присоединенным к $A$;

2) соответствие, по которому любым двум точкам $A, B \in A$ отвечает некоторый элемент $AB \in L$ с началом в $A$ и с концом в $B$;

При этом выполняются следующие две аксиомы:

10. Для произвольной точки $A \in A$ и любого вектора ${\rm {\bf u} } \in L$ существует единственная точка $B \in A$ такая, что $AB = {\rm {\bf u} }$.

11. Для произвольных трех точек $А, В, С$ имеет место равенство $AB + BC = AC$.
}}

[[Файл:p03-08-01-affine-axioms.svg|frame|none|800px|alt=Слева по точке A и вектору u строится единственная точка B; справа для точек A, B, C выполнено AB + BC = AC|Рис. 1. Аксиома 10: по точке <math>A</math> и вектору <math>u</math> точка <math>B</math> с <math>AB = u</math> находится однозначно. Аксиома 11: для любых точек <math>A, B, C</math> выполняется <math>AB + BC = AC</math>.]]

Размерность аффинного пространства $A$ совпадает с размерностью присоединенного с $A$ линеала $L$ и обозначается символом $dim(A)$. Если $dim(A) = n$, то аффинное пространство называют $n$-мерным и используют обозначение $A^{ n}$.

Приведем примеры аффинных пространств.

Рассмотрим трехмерное линейное пространство $V^3$. Фиксируем некоторую точку $О$ и будем рассматривать всевозможные радиус-векторы с началом в точке $О$. Под точками аффинного пространства $A^{ 3}$ с присоединенным линеалом $V^3$, будем понимать концы соответствующих радиус-векторов, причем двум точкам $А$ и $В$ сопоставляется вектор $\mathop {AB}\limits^ \to = \vec{r}_B - \vec{r}_A \in V^3$. Заметим, что при такой формализации мы отождествляем точку $А$ с радиусом-вектором.

[[Файл:p03-08-02-radius-vectors.svg|frame|none|800px|alt=Точка O, радиус-векторы rA и rB и вектор AB = rB − rA|Рис. 2. С фиксированным началом <math>O</math> каждая точка получает радиус-вектор: <math>A \mapsto r_A = OA</math>, <math>B \mapsto r_B = OB</math>. Тогда <math>AB = r_B - r_A</math>: разность двух точек — вектор.]]

----

Конспект: [[Алгебра и геометрия]]

Файл:P03-08-01-affine-axioms.svg

2026-11-04T18:35:20Z

СВ:

Файл:P03-08-02-radius-vectors.svg

2026-11-04T18:35:05Z

СВ:

Изоморфизм линеалов

2026-11-04T18:33:18Z

СВ:

{{Определение
|definition=
Соответствие между элементами двух линеалов $L$ и $M$ называется взаимно однозначным, если каждому элементу из $L$ отвечает единственный элемент из $M$, причем каждый элемент из $M$ отвечает одному лишь элементу из $L$.
}}
{{Определение
|definition=
Два линеала $L$ и $M$ называются изоморфными (обозначение $L \approx M$), если между элементами этих линеалов можно установить такое взаимно однозначное соответствие
<math>\varphi :x \in L\buildrel \varphi \over \longrightarrow \varphi (x) \in M,</math>
что $\varphi (\lambda x) = \lambda \varphi (x)$, $\varphi (x + y) = \varphi (x) + \varphi (y)$, где $x,y \in L$; $\lambda $ {{---}} любое вещественное число.

Указанное отображение $\varphi :L \to M$ называют линейным изоморфизмом.
}}

[[Файл:p03-07-01-coordinate-isomorphism.svg|thumb|800px|alt=Слева вектор x = 2e1 + 3e2 в линеале L, справа точка (2; 3) в R²; между ними отображение φ|Рис. 1. Вектор <math>x = 2e_1 + 3e_2</math> линеала <math>L</math> переходит в набор своих координат <math>(2; 3) \in R^2</math>. Отображение <math>\varphi</math> сохраняет сложение и умножение на число, поэтому является изоморфизмом.]]

{{Теорема
|statement=Все линеалы одной и той же размерности изоморфны.
|proof=Пусть линеалы $L$ и $M$ являются $n$-мерными. Выберем в $L$ некоторый базис ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $, а в $M$ {{---}} базис ${\rm {\bf {e}'} }_1, {\rm {\bf {e}'} }_2, ..., {\rm {\bf {e}'} }_n .$ Сопоставим элементу $x = \sum\limits_{i = 1}^n {x_i } e_i \in L$ элемент
<math>\varphi (x) = \varphi \left( {\sum\limits_{i = 1}^n {x_i } {\rm {\bf e} }_i } \right) = \sum\limits_{i = 1}^n {x_i } {\rm {\bf {e}'} }_i \in M,</math>
т. е. вектор, имеющий те же координаты, что и вектор $x$, но относительно базиса ${\rm {\bf {e}'} }_1, {\rm {\bf {e}'} }_2, ..., {\rm {\bf {e}'} }_n .$

В силу единственности разложения элемента по базису установленное соответствие $\varphi $ является взаимно однозначным. Кроме того,
<math>
\varphi (x + y) = \varphi \left( {\sum\limits_{i = 1}^n {(x_i + y_i ){\bf e}_i } } \right) = \sum\limits_{i = 1}^n {(x_i + y_i ){\rm {\bf {e}'} }_i } = \sum\limits_{i = 1}^n {x_i {\rm {\bf {e}'} }_i } + \sum\limits_{i = 1}^n {y_i {\rm {\bf {e}'} }_i } = \varphi ({\rm {\bf x} }) + \varphi (y),
</math>

<math>
\varphi (\alpha x) = \varphi \left( {\sum\limits_{i = 1}^n {(\alpha x_i ){\bf e}_i } } \right) = \sum\limits_{i = 1}^n {(\alpha x_i ){\rm {\bf {e}'} }_i } = \alpha \sum\limits_{i = 1}^n {x_i {\rm {\bf {e}'} }_i } = \alpha \varphi (x).
</math>

Таким образом, линеалы $L$ и $M$ являются изоморфными, а построенное отображение называется координатным изоморфизмом.
}}
Заметим, что координатный изоморфизм зависит от выбора базисов в $L$ и $M$.
{{Следствие
|statement=Любое $n$-мерное линейное пространство $L$ изоморфно координатному пространству $R^n$.
}}
Отметим, что при координатном изоморфизме любому элементу $x \in L$, представимому через базис ${\bf e}_1, {\bf e}_2, ..., {\rm {\bf e} }_n $ в виде $x = \sum\limits_{i = 1}^n {x_i } {\rm {\bf e} }_i $, сопоставляется упорядоченный набор чисел $(x_1, x_2, ..., x_n ) \in R^n$, компоненты которого суть координаты элемента $x \in L$ относительно фиксированного базиса.

{{Теорема
|statement=Изоморфные линеалы имеют одну и ту же размерность.
|proof=Пусть $n$-мерный линеал $L$ изоморфен линейному пространству $M $при линейном изоморфизме $\varphi $. Убедимся, что нулевому элементу ${\rm {\bf 0} } \in L$ соответствует нулевой элемент $\varphi ({\bf 0}) \in M.$

Действительно, для любого элемента $x \in L$ имеем равенство $x + {\bf 0} = x$ и потому $\varphi ({\rm {\bf x} } + {\bf 0}) = \varphi (x)$. В силу свойств линейного изоморфизма $\varphi (x + {\bf 0}) = \varphi ({\rm {\bf x} }) + \varphi ({\bf 0})$. Сравнивая последние равенства, получаем $\varphi (x) + \varphi ({\bf 0}) = \varphi (x)$, откуда следует, что $\varphi $(\textbf{0}) есть нулевой элемент в $M$.

Пусть ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $ произвольный базис в$ L$, а $\varphi ({\bf e}_1 ), \varphi ({\rm {\bf e} }_2 ),..., \varphi ({\bf e}_n )$ {{---}} образы базисных векторов в $M$ при линейном изоморфизме $\varphi $. Составим в $M$ линейную комбинацию
<math>
\sum\limits_{i = 1}^n {\alpha _i \varphi (e_i )} = \varphi ({\bf 0}).
</math>

В силу свойств линейного изоморфизма $\varphi $ и взаимно однозначного соответствия нулевых элементов линеалов $L$ и $M $имеем соотношение $\sum\limits_{i = 1}^n {\alpha _i } e_i = {\bf 0}$. Откуда, вследствие линейной независимости элементов ${\bf e}_1, {\bf e}_2, ..., {\rm {\bf e} }_n $ получаем $\alpha _i = 0, i = \overline {1,n} $. Но тогда следует, что элементы $\varphi ({\bf e}_i )$, $i = \overline {1,n} $ из $M $линейно независимы.

Таким образом, размерность $M$ не менее $n$. Если предположить, что размерность $\dim (M) > n$, то при обратном взаимно однозначном соответствии $\varphi ^{-1}: M \to L$ окажется, что $\dim (L) > n$. Полученное противоречие показывает, что $\dim (M) = n$.
}}
[[Файл:p03-07-02-dimension-invariant.svg|frame|none|800px|alt=Четыре класса линеалов по размерности 1, 2, 3 и ∞; внутри класса V ≈ R, между классами изоморфизма нет|Рис. 2. Внутри каждого класса одинаковой размерности все линеалы изоморфны: <math>V^1 \approx R^1</math>, <math>V^2 \approx R^2</math>, <math>V^3 \approx R^3</math>. Бесконечномерные пространства образуют отдельный класс. Поэтому <math>L \approx M \iff \dim L = \dim M</math>.]]
{{Следствие
|statement=Конечномерные линеалы разных размерностей неизоморфны.
}}
{{Следствие
|statement=Бесконечномерный линеал неизоморфен никакому конечномерному линеалу.
}}
Итак, существенной характеристикой конечномерного линеала является его размерность. Линеалы, имеющие одинаковую размерность, изоморфны. Свойства линеалов, выраженные в терминах алгебраических операций сложения и умножения на вещественное число, у изоморфных линеалов одинаковые. Поэтому с алгебраической точки зрения изоморфные линеалы тождественны. На этом факте основывается, в сущности, и метод координат, на котором базируется аналитическая геометрия.

Вследствие теоремы все $n$-мерные линейные пространства изоморфны координатному линеалу $R^n$. Таким образом, в теории $n$-мерных линейных пространств, не теряя общности, можно ограничиться изучением линеала $R^n$, поскольку, очевидно, что с помощью обратного изоморфизма $\varphi ^{-1}:R^n\buildrel {\varphi ^{ - 1} } \over \longrightarrow L$ полученные в $R^n$ утверждения переносятся в исходный линеал $L$.

----

Конспект: [[Алгебра и геометрия]]

Изоморфизм линеалов

2026-11-04T18:32:47Z

СВ: Новая страница: «{{Определение |definition= Соответствие между элементами двух линеалов $L$ и $M$ называется взаи...»

{{Определение
|definition=
Соответствие между элементами двух линеалов $L$ и $M$ называется взаимно однозначным, если каждому элементу из $L$ отвечает единственный элемент из $M$, причем каждый элемент из $M$ отвечает одному лишь элементу из $L$.
}}
{{Определение
|definition=
Два линеала $L$ и $M$ называются изоморфными (обозначение $L \approx M$), если между элементами этих линеалов можно установить такое взаимно однозначное соответствие
<math>\varphi :x \in L\buildrel \varphi \over \longrightarrow \varphi (x) \in M,</math>
что $\varphi (\lambda x) = \lambda \varphi (x)$, $\varphi (x + y) = \varphi (x) + \varphi (y)$, где $x,y \in L$; $\lambda $ {{---}} любое вещественное число.

Указанное отображение $\varphi :L \to M$ называют линейным изоморфизмом.
}}

[[Файл:p03-07-01-coordinate-isomorphism.svg|thumb|800px|alt=Слева вектор x = 2e1 + 3e2 в линеале L, справа точка (2; 3) в R²; между ними отображение φ|Рис. 1. Вектор <math>x = 2e_1 + 3e_2</math> линеала <math>L</math> переходит в набор своих координат <math>(2; 3) \in R^2</math>. Отображение <math>\varphi</math> сохраняет сложение и умножение на число, поэтому является изоморфизмом.]]

{{Теорема
|statement=Все линеалы одной и той же размерности изоморфны.
|proof=Пусть линеалы $L$ и $M$ являются $n$-мерными. Выберем в $L$ некоторый базис ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $, а в $M$ {{---}} базис ${\rm {\bf {e}'} }_1, {\rm {\bf {e}'} }_2, ..., {\rm {\bf {e}'} }_n .$ Сопоставим элементу $x = \sum\limits_{i = 1}^n {x_i } e_i \in L$ элемент
<math>\varphi (x) = \varphi \left( {\sum\limits_{i = 1}^n {x_i } {\rm {\bf e} }_i } \right) = \sum\limits_{i = 1}^n {x_i } {\rm {\bf {e}'} }_i \in M,</math>
т. е. вектор, имеющий те же координаты, что и вектор $x$, но относительно базиса ${\rm {\bf {e}'} }_1, {\rm {\bf {e}'} }_2, ..., {\rm {\bf {e}'} }_n .$

В силу единственности разложения элемента по базису установленное соответствие $\varphi $ является взаимно однозначным. Кроме того,
<math>
\varphi (x + y) = \varphi \left( {\sum\limits_{i = 1}^n {(x_i + y_i ){\bf e}_i } } \right) = \sum\limits_{i = 1}^n {(x_i + y_i ){\rm {\bf {e}'} }_i } = \sum\limits_{i = 1}^n {x_i {\rm {\bf {e}'} }_i } + \sum\limits_{i = 1}^n {y_i {\rm {\bf {e}'} }_i } = \varphi ({\rm {\bf x} }) + \varphi (y),
</math>

<math>
\varphi (\alpha x) = \varphi \left( {\sum\limits_{i = 1}^n {(\alpha x_i ){\bf e}_i } } \right) = \sum\limits_{i = 1}^n {(\alpha x_i ){\rm {\bf {e}'} }_i } = \alpha \sum\limits_{i = 1}^n {x_i {\rm {\bf {e}'} }_i } = \alpha \varphi (x).
</math>

Таким образом, линеалы $L$ и $M$ являются изоморфными, а построенное отображение называется координатным изоморфизмом.
}}
Заметим, что координатный изоморфизм зависит от выбора базисов в $L$ и $M$.
{{Следствие
|statement=Любое $n$-мерное линейное пространство $L$ изоморфно координатному пространству $R^n$.
}}
Отметим, что при координатном изоморфизме любому элементу $x \in L$, представимому через базис ${\bf e}_1, {\bf e}_2, ..., {\rm {\bf e} }_n $ в виде $x = \sum\limits_{i = 1}^n {x_i } {\rm {\bf e} }_i $, сопоставляется упорядоченный набор чисел $(x_1, x_2, ..., x_n ) \in R^n$, компоненты которого суть координаты элемента $x \in L$ относительно фиксированного базиса.

{{Теорема
|statement=Изоморфные линеалы имеют одну и ту же размерность.
|proof=Пусть $n$-мерный линеал $L$ изоморфен линейному пространству $M $при линейном изоморфизме $\varphi $. Убедимся, что нулевому элементу ${\rm {\bf 0} } \in L$ соответствует нулевой элемент $\varphi ({\bf 0}) \in M.$

Действительно, для любого элемента $x \in L$ имеем равенство $x + {\bf 0} = x$ и потому $\varphi ({\rm {\bf x} } + {\bf 0}) = \varphi (x)$. В силу свойств линейного изоморфизма $\varphi (x + {\bf 0}) = \varphi ({\rm {\bf x} }) + \varphi ({\bf 0})$. Сравнивая последние равенства, получаем $\varphi (x) + \varphi ({\bf 0}) = \varphi (x)$, откуда следует, что $\varphi $(\textbf{0}) есть нулевой элемент в $M$.

Пусть ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $ произвольный базис в$ L$, а $\varphi ({\bf e}_1 ), \varphi ({\rm {\bf e} }_2 ),..., \varphi ({\bf e}_n )$ {{---}} образы базисных векторов в $M$ при линейном изоморфизме $\varphi $. Составим в $M$ линейную комбинацию
<math>
\sum\limits_{i = 1}^n {\alpha _i \varphi (e_i )} = \varphi ({\bf 0}).
</math>

В силу свойств линейного изоморфизма $\varphi $ и взаимно однозначного соответствия нулевых элементов линеалов $L$ и $M $имеем соотношение $\sum\limits_{i = 1}^n {\alpha _i } e_i = {\bf 0}$. Откуда, вследствие линейной независимости элементов ${\bf e}_1, {\bf e}_2, ..., {\rm {\bf e} }_n $ получаем $\alpha _i = 0, i = \overline {1,n} $. Но тогда следует, что элементы $\varphi ({\bf e}_i )$, $i = \overline {1,n} $ из $M $линейно независимы.

Таким образом, размерность $M$ не менее $n$. Если предположить, что размерность $\dim (M) > n$, то при обратном взаимно однозначном соответствии $\varphi ^{-1}: M \to L$ окажется, что $\dim (L) > n$. Полученное противоречие показывает, что $\dim (M) = n$.
}}
[[Файл:p03-07-02-dimension-invariant.svg|thumb|800px|alt=Четыре класса линеалов по размерности 1, 2, 3 и ∞; внутри класса V ≈ R, между классами изоморфизма нет|Рис. 2. Внутри каждого класса одинаковой размерности все линеалы изоморфны: <math>V^1 \approx R^1</math>, <math>V^2 \approx R^2</math>, <math>V^3 \approx R^3</math>. Бесконечномерные пространства образуют отдельный класс. Поэтому <math>L \approx M \iff \dim L = \dim M</math>.]]
{{Следствие
|statement=Конечномерные линеалы разных размерностей неизоморфны.
}}
{{Следствие
|statement=Бесконечномерный линеал неизоморфен никакому конечномерному линеалу.
}}
Итак, существенной характеристикой конечномерного линеала является его размерность. Линеалы, имеющие одинаковую размерность, изоморфны. Свойства линеалов, выраженные в терминах алгебраических операций сложения и умножения на вещественное число, у изоморфных линеалов одинаковые. Поэтому с алгебраической точки зрения изоморфные линеалы тождественны. На этом факте основывается, в сущности, и метод координат, на котором базируется аналитическая геометрия.

Вследствие теоремы все $n$-мерные линейные пространства изоморфны координатному линеалу $R^n$. Таким образом, в теории $n$-мерных линейных пространств, не теряя общности, можно ограничиться изучением линеала $R^n$, поскольку, очевидно, что с помощью обратного изоморфизма $\varphi ^{-1}:R^n\buildrel {\varphi ^{ - 1} } \over \longrightarrow L$ полученные в $R^n$ утверждения переносятся в исходный линеал $L$.

----

Конспект: [[Алгебра и геометрия]]

Файл:P03-07-02-dimension-invariant.svg

2026-11-04T18:32:09Z

СВ:

Файл:P03-07-01-coordinate-isomorphism.svg

2026-11-04T18:31:59Z

СВ:

Ранг матрицы

2026-11-04T18:28:31Z

СВ: Новая страница: «Пусть ${\bf a}_i \in R^n$ {{---}} произвольная $i-$я строка матрицы ${\rm {\bf S} } = [{\bf a}_1, {\bf a}_2, ..., {\bf a}_p ] = [p\...»

Пусть ${\bf a}_i \in R^n$ {{---}} произвольная $i-$я строка матрицы ${\rm {\bf S} } = [{\bf a}_1, {\bf a}_2, ..., {\bf a}_p ] = [p\times n]$. Каждая строка является элементом линеала $R^n$, поэтому если число строк в матрице $p > n$, то строки ${\bf a}_1, {\bf a}_2,..., {\bf a}_p $ линейно зависимы. С другой стороны, очевидно, что среди ${\bf a}_1, {\bf a}_2, ..., {\bf a}_p $ существует ровно $k \le n$ строк, являющихся линейно независимыми, по которым можно разложить остальные $(n - k)$ строк.

{{Определение
|definition=
Указанная совокупность $k$ строк называется '''строчечным базисом''', а число $k$ {{---}} строчечным рангом матрицы.
}}
Аналогично, если матрица ${\rm {\bf S} } = [{\bf a}^1, {\rm {\bf a} }^2, ..., {\bf a}^n]$, где ${\bf a}^j \in R^p$, то в ней существует не более $p$ линейно независимых столбцов. Среди столбцов ${\bf a}^1, {\bf a}^2, ..., {\bf a}^n$ имеется ровно $m \le p$ линейно независимых, по которым можно разложить любой из остальных $p - m$ столбцов.
{{Определение
|definition=
Указанная совокупность $m$ столбцов называется '''столбцовым базисом''', а число $m$ {{---}} '''столбцовым рангом''' матрицы $S$.
}}
[[Файл:p03-06-01-row-column-rank.svg|thumb|800px|alt=Матрица 3 × 4: третья строка равна сумме первых двух; первые два столбца образуют базис, c3 и c4 выражены через них|Рис. 1. Одна матрица <math>3 \times 4</math>: третья строка равна сумме первых двух, поэтому строчечный ранг <math>k = 2</math>. По столбцам <math>c_3 = -2c_1 + c_2</math> и <math>c_4 = -3c_1 + 2c_2</math>, поэтому и столбцовый ранг равен 2.]]

{{Теорема
|statement=Строчечный (столбцовый) ранг любой матрицы не зависит от выбора строчечного (столбцового) базиса.
|proof=Проведем доказательство для строчечного базиса. Пусть ${\bf a}_1, {\bf a}_2, ..., {\bf a}_k $ и ${\rm {\bf c} }_1, {\rm {\bf c} }_2, ..., {\rm {\bf c} }_r $ два разных строчечных базиса одной и той же матрицы. Предположим, что $r > k$. Поскольку ${\bf a}_1, {\bf a}_2, ..., {\bf a}_k $ базис, то строки ${\rm {\bf c} }_j $, $j = \overline {1,r} $ можно разложить по этому базису, т. е. ${\rm {\bf c} }_j = \sum\limits_{i = 1}^k {\alpha _{ij} } {\bf a}_i $, $j = \overline {1,r} $. Так как ${\bf a}_1, {\bf a}_2, ..., {\rm {\bf a} }_k $ линейно независимы, то в соответствии с теоремой 3.5.3 строки ${\rm {\bf c} }_1, {\rm {\bf c} }_2, ..., {\rm {\bf c} }_r $ линейно зависимы. Полученное противоречие доказывает, что $k \ge r$. Аналогично показывается, что $k $не может быть больше$ r$, поэтому $k = r$.
}}
Пусть дана прямоугольная матрица ${\bf a} = [{\bf a}_1, {\bf a}_2, ...., {\bf a}_m ] = [{\bf a}^1, {\bf a}^2,..., {\bf a}^n]$, ${\bf a}_i \in R^n, {\bf a}^j \in R^m$. Допустим, что строчечный ранг этой матрицы равен $k$. Без ограничения общности можно считать, что первые $k$ строк образуют базис, а любая другая строка матрицы ${\bf a}$ представима в виде их линейной комбинации, т. е.
<math>
{\bf a}_s = \sum\limits_{i = 1}^k {\gamma _{si} {\bf a}_i },
\quad
s = \overline {k + 1,m}.
</math>

Из первых $k$ строк матрицы ${\bf a}$ построим вспомогательную матрицу ${\rm {\bf \tilde {A} } } = [{\rm {\bf \tilde {a} } }_1, {\rm {\bf \tilde {a} } }_2, ..., {\rm {\bf \tilde {a} } }_k ]$, где ${\rm {\bf \tilde {a} } }_i = {\bf a}_i $, $i = \overline {1,k} $. Пусть ${\rm {\bf \tilde {a} } }^j$ есть $j-$й столбец матрицы ${\rm {\bf \tilde {A} } } = [{\rm {\bf \tilde {a} } }^1,{\rm {\bf \tilde {a} } }^2,..., {\rm {\bf \tilde {a} } }^n]$.

{{Лемма
|statement=Если для некоторых чисел $\beta _1, \beta _2, ..., \beta _n $ справедливо равенство $\sum\limits_{i = 1}^n {\beta _i {\rm {\bf \tilde {a} } }^i = 0}$, то $\sum\limits_{i = 1}^n {\beta _i {\bf a}^{\rm {\bf i} } = 0}$.
|proof=Если ввести обозначение
<math>{\rm {\bf b} } = \left( {{\begin{array}{c}
{\beta _1 } \\
{\beta _2 } \\
\vdots \\
{\beta _n } \\
\end{array} } } \right)</math>, то произведение ${\bf a}_j {\rm {\bf b} }$ определяет $j-$ю компоненту столбца $\sum\limits_{i = 1}^n {\beta _i {\rm {\bf a} }^i} $.
Из равенства $\sum\limits_{i = 1}^n {\beta _i {\rm {\bf \tilde {a} } }^i = 0} $ следует, что первые $k$ компонент указанного столбца $\sum\limits_{i = 1}^n {\beta _i {\bf a}^i} $ по построению матрицы
${\rm {\bf \tilde {A} } }$ равны нулю, т. е. ${\bf a}_i {\rm {\bf b} } = 0$, $i = \overline {1,k} $. Тогда для любого $s = \overline {k + 1,m} $ и имеем

<math>
{\bf a}_s {\rm {\bf b} } = \left( {\sum\limits_{i = 1}^k {\gamma _{si} {\bf a}_i } } \right){\rm {\bf b} } = \sum\limits_{i = 1}^k {\gamma _{si} ({\bf a}_i {\rm {\bf b} }) = 0} .
</math>
}}
{{Теорема
|statement=Строчечный ранг любой матрицы равен ее столбцовому рангу.
|proof=Допустим, что столбцовый базис матрицы ${\rm {\bf \tilde {A} } } = [{\rm {\bf \tilde {a} } }_1, {\rm {\bf \tilde {a} } }_2, ..., {\rm {\bf \tilde {a} } }_k ]$ состоит из $r$ первых столбцов ${\rm {\bf \tilde {a} } }^1,{\rm {\bf \tilde {a } } }^2,..., {\rm {\bf \tilde {a} } }^r$. Так как ${\rm {\bf \tilde {a} } }^i \in R^k$, то $r \le k$. Столбцы ${\rm {\bf \tilde {a} } }^1,{\rm {\bf \tilde {a} } }^2,..., {\rm {\bf \tilde {a} } }^r$ образуют базис, поэтому для любого $s = \overline {r + 1,n} $ имеем ${\rm {\bf \tilde {a} } }^s = \sum\limits_{i = 1}^r {\beta _{si} {\rm {\bf \tilde {a} } }^i} $. Следовательно, справедливо равенство $\sum\limits_{i = 1}^r {\beta _{si} {\rm {\bf \tilde {a} } }^i} - {\rm {\bf \tilde {a} } }^s = 0$. Тогда в силу леммы 3.6.1 имеем $\sum\limits_{i = 1}^r {\beta _{si} {\rm {\bf a} }^i} - {\bf a}^s = 0$, отсюда следует, что ${\bf a}^1, {\rm {\bf a} }^2, ..., {\bf a}^r$ есть столбцовый базис матрицы ${\rm {\bf A} }$. Поскольку имеем неравенство $r \le k$, то столбцовый ранг не превосходит строчечный. Аналогичные рассуждения относительно строчечного базиса приводят к выводу, что $r \ge k$. Следовательно, строчечный ранг матрицы совпадает со столбцовым рангом.
}}
{{Определение
|definition=
Общее значение столбцового и строчечного ранга называется рангом матрицы ${\bf a}$ и обозначается $rank{\rm {\bf A} }$.
}}
{{Теорема
|statement=Определитель матрицы ${\bf a} = [n\times n]$ равен нулю тогда и только тогда, когда $rank{\bf a} < n$.
|proof='''Достаточность.''' Пусть $rank{\bf a} < n$, следовательно, строки матрицы ${\bf a}$ линейно зависимы. Поэтому в соответствии с теоремой из параграфа 3 главы 3, по крайней мере, одну из них можно разложить по оставшимся строкам. Без ограничения общности будем считать, что ${\bf a}_n = \sum\limits_{i = 1}^{n - 1} {\gamma _{ni} {\bf a}_i } $. Определитель $\det {\bf a}$ не изменяется, если к любой из его строк прибавить другую строку, умноженную на заданное число. Следовательно,
<math>
\det {\bf a} = \det [{\bf a}_1, {\bf a}_2, ..., {\rm {\bf a} }_n ] = \det [{\bf a}_1, {\bf a}_2, ..., {\bf a}_n - \gamma _1 {\bf a}_1 - \cdots - \gamma _{n - 1} {\bf a}_{n - 1} ] = \det [{\bf a}_1, {\bf a}_2, ..., {\bf a}_{n - 1}, 0] = 0.
</math>

'''Необходимость.''' Доказательство проведем методом математической индукции по числу $n$. При $n = 1$ имеем $\det {\bf a} = \alpha _{11} = 0$, т. е. ${\bf a}_1 = 0$ {{---}} линейно зависимая строка. Допустим, что теорема доказана для $n = k - 1$, докажем ее для случая $n = k$.

Пусть ${\bf a} = [{\bf a}_1, {\bf a}_2, ...., {\rm {\bf a} }_k ] = \left\{ {\alpha _{ij} } \right\}_{i,j = 1}^{k,k} $. Построим вспомогательные строки, считая $\alpha _{11} \ne 0$:
<math>
{\rm {\bf b} }_2 = {\bf a}_2 - \frac{\alpha _{21} }{\alpha _{11} }{\rm {\bf a} }_1 = (0,{\alpha }'_{22}, {\alpha }'_{23}, ..., {\alpha }'_{2k} ), ..., {\rm {\bf b} }_k = {\bf a}_k - \frac{\alpha _{k1} }{\alpha _{11} }{\rm {\bf a} }_1 = (0,{\alpha }'_{k2}, {\alpha }'_{k3}, ..., {\alpha }'_{kk} ).
</math>

Тогда
<math>
\det {\bf a} = \det [{\bf a}_1, {\rm {\bf b} }_2, ..., {\rm {\bf b} }_k ] = \alpha _{11} \left| {{\begin{array}{*{20}c}
{{\alpha }'_{22} } & {{\alpha }'_{23} ...} & {{\alpha }'_{2k} } \\
\vdots & { \vdots ...} & \vdots \\
{{\alpha }'_{k2} } & {{\alpha }'_{k3} ...} & {{\alpha }'_{kk} } \\
\end{array} } } \right| = 0,
</math>
следовательно,
<math>
\det {\rm {\bf \bar {A} } } = \left| {{\begin{array}{*{20}c}
{{\alpha }'_{22} } & {{\alpha }'_{23} ...} & {{\alpha }'_{2k} } \\
\vdots & { \vdots ...} & \vdots \\
{{\alpha }'_{k2} } & {{\alpha }'_{k3} ...} & {{\alpha }'_{kk} } \\
\end{array} } } \right| = 0.
</math>

По индукционному предположению $rank{\rm {\bf \bar {A} } } < k - 1$, т. е. строки $({\alpha }'_{22}, {\alpha }'_{23}, ..., {\alpha }'_{2k} )$, ..., $({\alpha }'_{k2}, {\alpha }'_{k3}, ..., {\alpha }'_{kk} )$ линейно зависимы.
Но тогда линейно зависимыми являются ${\rm {\bf b} }_2, {\rm {\bf b} }_3, ..., {\rm {\bf b} }_k $, следовательно, существуют числа $\gamma _2, \gamma _3, ..., \gamma _k $ не равные нулю одновременно, что $\gamma _2 {\rm {\bf b} }_2 + \gamma _3 {\rm {\bf b} }_3 + ... + \gamma _k {\rm {\bf b} }_k = 0$.
Поэтому справедливо соотношение
<math>
\left( { - \gamma _2 \frac{\alpha _{21} }{\alpha _{11} } - \cdots - \gamma _k \frac{\alpha _{k1} }{\alpha _{11} } } \right){\bf a}_1 + \gamma _2 {\bf a}_2 + \gamma _3 {\bf a}_3 + ... + \gamma _k {\rm {\bf a} }_k = 0,
</math>
отсюда следует линейная зависимость ${\bf a}_1, {\bf a}_2, ..., {\bf a}_k $, т. е. $rank[{\bf a}_1, {\bf a}_2,..., {\bf a}_k ] < k$.
}}
{{Теорема
|statement=Ранг матрицы равен наибольшему порядку миноров, отличных от нуля.
|proof=Допустим, что $rank{\bf a} = k$. Тогда в матрице ${\bf a}$ существует ровно $k$ линейно независимых строк, образующих строчечный базис, и $k$ линейно независимых столбцов, составляющих столбцовый базис. Поэтому минор $k-$го порядка, построенный на указанных строках и столбцах, очевидно, не равен нулю. При этом все миноры порядка $k + 1$ и выше (если таковые имеются) будут равны нулю, как содержащие линейно зависимые строки и линейно зависимые столбцы.
}}
[[Файл:p03-06-02-rank-minor.svg|thumb|800px|alt=Матрица с выделенным минором 2 × 2, равным 1, и карточки: det A ≠ 0 при rank A = n, det A = 0 при rank A < n|Рис. 2. Минор второго порядка <math>M_2 = 1 \neq 0</math> даёт <math>\operatorname{rank} A \ge 2</math>, а все миноры третьего порядка равны нулю, так как содержат зависимые строки. Справа: для квадратной матрицы <math>\det A \neq 0 \iff \operatorname{rank} A = n</math>, а <math>\det A = 0 \iff \operatorname{rank} A < n</math>.]]

{{Лемма
|statement=Ранг произведения двух матриц не превосходит ранг каждого из сомножителей.
|proof=Пусть даны произвольные матрицы ${\bf a} = [{\bf a}_1, ..., {\bf a}_m ] = [{\bf a}^1, ..., {\rm {\bf a} }^n] = \{\alpha _{ij} \}_{i,j = 1}^{m,n} $, ${\rm {\bf B} } = [{\rm {\bf b} }_1, ..., {\rm {\bf b} }_n ] = [{\rm {\bf b} }^1,..., {\rm {\bf b} }^r] = \{\beta _{jk} \}_{j,k = 1}^{n,r} $. Тогда произведение
<math>
{\rm {\bf AB} } = [{\rm {\bf Ab} }^1,..., {\rm {\bf Ab} }^r] = \left[ {\sum\limits_{i = 1}^n {\beta _{i1} {\bf a}^i,..., } \sum\limits_{i = 1}^n {\beta _{ir} {\bf a}^i} } \right],
</math>
следовательно, каждый столбец произведения есть линейная комбинация столбцов матрицы ${\bf a}$, поэтому $rank({\rm {\bf AB} }) \le rank{\rm {\bf A} }$. Аналогично, имеем
<math>
{\rm {\bf AB} } = [{\bf a}_1 {\rm {\bf B} },..., {\bf a}_m {\rm {\bf B} }] = \left[ {\sum\limits_{j = 1}^n {\alpha _{1j} {\rm {\bf b} }_j, ..., \sum\limits_{j = 1}^n {\alpha _{mj} {\rm {\bf b} }_j } } } \right],
</math>
отсюда каждая строка произведения равна линейной комбинации строк матрицы ${\rm {\bf B} }$, т. е. $rank({\rm {\bf AB} }) \le rank{\rm {\bf B} }$.
}}
{{Лемма
|statement=Для произвольной невырожденной матрицы ${\rm {\bf B} }$ и любой матрицы ${\bf a}$ справедливо равенство $rank({\rm {\bf AB} }) = rank{\bf a}$.
|proof=Если матрица ${\rm {\bf C} } = {\rm {\bf AB} }$, то в силу леммы 3.6.2 $rank{\rm {\bf C} } \le rank{\bf a}$. Так как матрица ${\rm {\bf B} }$ по условию является невырожденной, то существует обратная матрица ${\rm {\bf B} }^{ - 1}$. Умножим матрицу ${\rm {\bf C} }$ справа на ${\rm {\bf B} }^{ - 1}$, получаем ${\rm {\bf CB} }^{ - 1} = {\rm {\bf ABB} }^{ - 1} = {\rm {\bf AE} } = {\bf a}$, следовательно, $rank{\rm {\bf C} } \ge rank{\bf a}$. Таким образом, справедливо равенство $rank{\rm {\bf C} } = rank{\bf a}$.
}}

----

Конспект: [[Алгебра и геометрия]]

Файл:P03-06-02-rank-minor.svg

2026-11-04T18:27:43Z

СВ:

Файл:P03-06-01-row-column-rank.svg

2026-11-04T18:27:36Z

СВ:

Персистентный стек

2026-11-04T18:07:13Z

СВ: /* Источники */

== TL;DR ==

'''Персистентный стек''' (persistent stack) — стек, хранящий '''все свои предыдущие версии''': каждая операция не изменяет структуру, а создаёт новую версию, оставляя старые доступными. Реализуется как '''односвязный список''': узел хранит значение и ссылку <code>prev</code> на предыдущую версию, а «текущая версия» — это просто ссылка на верхний узел. <code>push</code> создаёт один новый узел за <math>O(1)</math>, <code>pop</code> возвращает значение и ссылку на предыдущую версию — тоже <math>O(1)</math> и '''без новых ячеек'''. <math>n</math> операций <code>push</code> создают ровно <math>n</math> новых узлов, а вместе с корнем в структуре <math>n + 1</math> узел, потому что все версии '''разделяют общий хвост''' (sharing): память <math>O(n)</math>, а не <math>O(n^2)</math>. Все узлы неизменяемы, поэтому персистентный стек — это '''функциональная''' персистентность; он служит строительным блоком для персистентной очереди ([[Очередь на шести стеках]]), версионирования и неизменяемых списков.

{| class="wikitable"
|-
! Свойство !! Значение
|-
| Класс || Стек (LIFO) с полной персистентностью; функциональная структура данных
|-
| Версии || Хранятся все; доступ к версии по ссылке за <math>O(1)</math>, материализация — <math>O(k)</math>
|-
| <code>push</code> || <math>O(1)</math> времени, <math>O(1)</math> новых ячеек
|-
| <code>pop</code> || <math>O(1)</math> времени, 0 новых ячеек (список) / 1 ячейка (массив)
|-
| Память || <math>O(V)</math> под <math>V</math> узлов; <math>n</math> операций <code>push</code> → <math>n</math> новых узлов (вместе с корнем <math>n + 1</math>)
|-
| Изменяемость || нет; узлы инициализируются один раз и не меняются
|-
| Представления || односвязный список (<code>{value, prev}</code>) или массив запросов
|-
| Разделение || версии делят общие хвосты; ветвление даёт дерево версий
|-
| Персистентность || функциональная (сильнейшая форма)
|-
| Где встречается || функциональные языки (списки), персистентная очередь, undo/redo, версионирование
|}

== Определения ==

'''Персистентная структура данных''' — структура, сохраняющая доступ ко всем предшествующим версиям при выполнении операций. Различают три уровня:

* '''частичная персистентность''' (partial): можно изменять только самую новую версию, но читать — любую;
* '''полная персистентность''' (full): изменять и читать можно любую версию;
* '''функциональная персистентность''' (functional): каждая ячейка памяти инициализируется один раз и больше не изменяется, поэтому версии разделяют неизменяемые данные.

'''Версия стека''' — конкретное состояние стека (упорядоченная последовательность элементов). В персистентном стеке версия отождествляется с узлом-вершиной.

'''Узел (node)''' — запись <code>{value, prev}</code>, где <code>value</code> — значение на вершине, а <code>prev</code> — ссылка на предыдущую версию (узел ниже) или <code>null</code> для пустой версии. Узел неизменяем.

'''Текущая вершина''' (<code>top</code>) — ссылка на узел, представляющий актуальную версию. Изменение стека не переписывает узлы, а лишь заменяет <code>top</code>.

'''Разделение хвоста (sharing)''' — ситуация, когда несколько версий ссылаются на один и тот же узел (и, следовательно, на общий остаток стека). Безопасно только при неизменяемости узлов.

'''Две реализации.''' ''Списковая'': узлы связаны ссылками. ''Массивная'' (массив запросов): <code>push</code> добавляет ячейку <code>{x, i}</code>, а <code>pop</code> — копию версии <code>s[i].prev</code> (той, что лежит под вершиной); номер новой версии равен <math>n + 1</math>.

'''Обозначения.''' <math>n</math> — число элементов/операций; <math>V</math> — число версий; <code>s[i]</code> — ячейка массива запросов с номером <math>i</math>; <math>\log</math> — двоичный.

== Мотивация и интуиция ==

Обычный стек из [[Стек]] хранит '''одно''' состояние: <code>push</code> записывает элемент в ячейку, <code>pop</code> её очищает. Прошлые состояния теряются. Если нужно вернуться к предыдущему состоянию — приходится заранее копировать стек целиком, а это <math>\Theta(n)</math> времени и памяти на каждую версию и <math>\Theta(n^2)</math> суммарно. См. рис. 1.

[[Файл:pstack-01-idea.svg|thumb|700px|Рис. 1. Мутирующий стек хранит единственное состояние: <code>push(d)</code> теряет прежнюю версию; персистентный добавляет новый узел, сохраняя старые версии.]]

Списковая структура стека подсказывает решение. Стек — это цепочка «верх → … → дно». Добавление элемента можно представить не как запись в общую память, а как '''новую голову цепочки''': новый узел хранит добавленное значение и ссылку на прежнюю голову. Тогда старая цепочка никуда не девается — на неё просто никто не указывает как на текущую. Аналогично <code>pop</code> не удаляет узел, а возвращает ссылку на следующий узел цепочки. Такой стек никогда ничего не перезаписывает.

Ключевая идея в одном абзаце: '''вершина — это всего лишь указатель на узел, а узел неизменяем'''; поэтому «изменение» сводится к замене указателя, а вся история сохраняется как цепочка (точнее — дерево) узлов, делящих общие хвосты. Отсюда <math>O(1)</math> на операцию и <math>O(n)</math> суммарной памяти.

== Устройство ==

Персистентный стек состоит из узлов <code>{value, prev}</code> и ссылки <code>top</code> на текущую вершину (см. рис. 2). Пустая версия — это специальный корневой узел без значения; в массиве его роль играет sentinel <code>null</code>.

[[Файл:pstack-02-versions.svg|thumb|700px|Рис. 2. Версия = узел; <code>push</code> добавляет узел перед текущим, <code>pop</code> возвращает предыдущий узел.]]

Версии образуют связную структуру: цепочка <code>prev</code>-ссылок из любого узла ведёт вниз, к корню. Несколько версий могут указывать на один узел — это '''разделение хвостов'''. Ветвление (например, два <code>push</code> от одной и той же версии) превращает линию версий в '''дерево версий'''; именно так устроены история в редакторах и снапшоты в базах данных.

Есть два эквивалентных представления (см. рис. 3):

* '''Список.''' Узел хранит <code>value</code> и <code>prev</code>; ссылка на узел — это версия. <code>push</code> создаёт узел за <math>O(1)</math>; <code>pop</code> возвращает пару <code>(value, prev)</code> и не создаёт узлов.
* '''Массив запросов.''' Ячейка <code>s[i]</code> хранит <code>{value, prev}</code> — значение вершины версии <math>i</math> и индекс её предыдущей версии. <code>push(i, x)</code> добавляет ячейку <code>{x, i}</code> и возвращает её индекс <math>n + 1</math>; <code>pop(i)</code> возвращает значение <code>s[i].value</code> и создаёт новую версию — копию версии <code>s[i].prev</code>, лежащей под вершиной.

[[Файл:pstack-03-array.svg|thumb|700px|Рис. 3. Массив запросов: каждая ячейка = {value, prev}; операция добавляет ровно одну ячейку.]]

Массивное представление удобно, когда версии нумеруются подряд и нужен быстрый доступ по индексу; списковое — когда версии передаются как ссылки, а структура используется как неизменяемое значение (например, список в функциональном языке).

== Операции и алгоритмы ==

=== Операция: Push ===

'''Идея.''' Создать новый узел со значением <math>x</math> и ссылкой на текущую вершину; объявить его новой вершиной. Прежняя версия сохраняется без изменений.

'''Пошаговое описание (список):'''

# Создать узел <math>k</math> со значением <math>x</math> и ссылкой <code>prev ← top</code>.
# Присвоить <code>top ← k</code>.
# Вернуть новую вершину (новую версию).

'''Инвариант.''' Цепочка <code>prev</code>-ссылок из <code>top</code> перечисляет элементы стека сверху вниз; все ранее созданные узлы сохраняют свои поля.

<syntaxhighlight lang="text">
Операция Push(s, x)
Вход: персистентный стек s (ссылка top на вершину); x — элемент
Выход: новая версия стека (ссылка на новый узел)
Инвариант: элементы версии = цепочка top → prev → … → корень
Сложность: O(1) времени, O(1) новых ячеек

1 k ← новый узел
2 k.value ← x
3 k.prev ← s.top
4 s.top ← k
5 return k
</syntaxhighlight>

'''Массивная версия:'''

<syntaxhighlight lang="text">
Операция Push-Array(s, i, x)
Вход: массив s запросов; i — номер версии, от которой добавляем; x — элемент
Выход: номер новой версии
Сложность: O(1)

1 s.top ← s.top + 1
2 s[s.top].value ← x
3 s[s.top].prev ← i
4 return s.top
</syntaxhighlight>

'''Разбор.''' Стек, представленный версией 2 (<code>value = 3, prev = 1</code>), при <code>push(2, 5)</code> получает ячейку 3 (<code>value = 5, prev = 2</code>). Версия 2 не изменилась: <code>s[2]</code> по-прежнему <code>{3, 1}</code>.

'''Сложность.''' <math>O(1)</math> и на списке, и на массиве: одна запись, одна ссылка.

'''Крайние случаи.''' <code>push</code> в пустую версию даёт узел со ссылкой на корень. Если требуется добавить элемент в ''прошлую'' версию, создаётся ветвь — текущая линия не затрагивается.

См. рис. 1 и рис. 2.

=== Операция: Pop ===

'''Идея.''' Вернуть значение текущей вершины и «перейти» на предыдущую версию. В списковой реализации это просто возврат ссылки <code>prev</code>; в массивной — запись новой ячейки, повторяющей предыдущую версию (см. рис. 4).

'''Пошаговое описание (список):'''

# Если стек пуст — ошибка <code>underflow</code>.
# Запомнить значение <code>x ← top.value</code>.
# Перейти к предыдущей версии: <code>top ← top.prev</code>.
# Вернуть пару <code>(x, top)</code> — значение и новую версию.

'''Инвариант.''' Новая версия содержит все элементы исходной, кроме верхнего; исходная версия остаётся доступной по прежней ссылке.

<syntaxhighlight lang="text">
Операция Pop(s)
Вход: персистентный стек s (top ≠ корень)
Выход: пара (x, s) — верхний элемент и новая версия s
Сложность: O(1) времени, 0 новых ячеек

1 if s.top = корень
2 error "попытка pop из пустого стека"
3 x ← s.top.value
4 s.top ← s.top.prev
5 return (x, s)
</syntaxhighlight>

'''Массивная версия (копирует предыдущую ячейку):'''

<syntaxhighlight lang="text">
Операция Pop-Array(s, i)
Вход: массив s; i — номер версии (i ≠ корень)
Выход: (значение, номер новой версии)
Сложность: O(1)

1 if s[i].prev = null
2 error "pop из пустого стека"
3 x ← s[i].value
4 k ← s[s[i].prev] # узел под вершиной
5 Push-Array(s, k.prev, k.value) # новая ячейка = копия версии под i
6 return (x, s.top)
</syntaxhighlight>

Здесь <code>null</code> — sentinel пустой версии (в C++-реализации ниже он кодируется индексом 0). Поэтому <code>pop</code> от версии из одного элемента создаёт новую пустую ячейку с <code>prev = null</code> (в трассировке — ячейка 7).

'''Разбор.''' Для <code>s = [a, b, c]</code> (вершина <code>c</code>) операция <code>Pop</code> вернёт <code>c</code> и версию <code>[a, b]</code>; версия <code>[a, b, c]</code> сохраняется. В массивной версии <code>pop(3)</code> для ячейки 3 вернул <code>5</code> и завёл ячейку 4, повторяющую версию 2.

'''Сложность.''' <math>O(1)</math>; в списке ноль новых ячеек, в массиве — ровно одна.

'''Крайние случаи.''' <code>pop</code> из пустой версии — ошибка. Если <code>pop</code> применяется к «прошлой» версии, новые ячейки пишутся в конец массива, а прежние ветви остаются нетронутыми.

[[Файл:pstack-04-pop.svg|thumb|700px|Рис. 4. <code>pop</code> не удаляет данные: он лишь указывает на предыдущую версию.]]

=== Операция: Top и Empty ===

'''Идея.''' Вершина и признак пустоты — чтение за <math>O(1)</math>.

<syntaxhighlight lang="text">
Операция Top(s)
Вход: персистентный стек s
Выход: значение верхнего элемента
Инвариант: s.top — вершина текущей версии
Сложность: O(1) времени, O(1) памяти

1 if s.top = корень
2 error "вершина пустого стека не определена"
3 return s.top.value

Операция Empty(s)
Вход: персистентный стек s
Выход: true, если текущая версия пуста
Сложность: O(1) времени, O(1) памяти

1 return (s.top = корень)
</syntaxhighlight>

'''Крайние случаи.''' <code>Top</code> пустой версии — ошибка; <code>Empty</code> для корня возвращает <code>true</code>.

=== Доступ к произвольной версии ===

'''Идея.''' Версия — это ссылка (или индекс), поэтому «переход» к ней бесплатен. Материализация (выписывание всех элементов версии) стоит <math>O(k)</math> для версии из <math>k</math> элементов.

<syntaxhighlight lang="text">
Операция To-List(v) # материализация версии v
Вход: вершина v (версия стека)
Выход: список значений сверху вниз
Инвариант: v — ещё не пройденная часть версии
Сложность: O(k) времени и O(k) памяти для k элементов

1 out ← пустой список
2 while v ≠ корень
3 out.append(v.value)
4 v ← v.prev
5 return out
</syntaxhighlight>

'''Сложность.''' <math>O(k)</math> для <math>k</math> элементов; при этом версии не мешают друг другу.

== Сводная таблица сложности ==

{| class="wikitable"
|-
! Операция !! Время !! Новых ячеек !! Память
|-
| <code>Push</code> || <math>O(1)</math> || <math>O(1)</math> || +1 узел
|-
| <code>Pop</code> || <math>O(1)</math> || 0 (список) / 1 (массив) || 0 (список) / 1 ячейка (массив)
|-
| <code>Top</code> || <math>O(1)</math> || 0 || 0
|-
| <code>Empty</code> || <math>O(1)</math> || 0 || 0
|-
| Доступ к версии || <math>O(1)</math> || 0 || 0
|-
| Материализация версии из <math>k</math> элементов || <math>O(k)</math> || <math>O(k)</math> || <math>O(k)</math>
|-
| <math>n</math> операций <code>push</code> || <math>O(n)</math> суммарно || — || <math>O(n)</math> узлов
|}

Оговорка: в списковой и массивной моделях '''амортизация не нужна''' — каждая операция уже <math>O(1)</math> в худшем случае. В C++-реализации ниже используется <code>std::vector</code>: его <code>push_back</code> даёт амортизированный <math>O(1)</math>, поэтому для строгого худшего случая нужен заранее выделенный пул с резервом. Суммарная память пропорциональна '''числу созданных версий''', а не их размерам, потому что версии делят общие хвосты.

== Трассировка примера ==

Повторим последовательность из источника для массивной реализации: <code>push(1, 3)</code>, <code>push(2, 5)</code>, <code>pop(3)</code>, <code>push(3, 6)</code>, <code>push(5, 1)</code>, <code>pop(4)</code>, <code>pop(5)</code>, <code>push(7, 9)</code>.

{| class="wikitable"
|-
! index !! value !! prev !! Операция
|-
| 1 || <code>null</code> || <code>null</code> || начальная пустая версия
|-
| 2 || 3 || 1 || <code>push(1, 3)</code>
|-
| 3 || 5 || 2 || <code>push(2, 5)</code>
|-
| 4 || 3 || 1 || <code>pop(3)</code>: вернул 5, скопировал версию 2
|-
| 5 || 6 || 3 || <code>push(3, 6)</code>
|-
| 6 || 1 || 5 || <code>push(5, 1)</code>
|-
| 7 || <code>null</code> || <code>null</code> || <code>pop(4)</code>: вернул 3, скопировал версию 1 (пустую)
|-
| 8 || 5 || 2 || <code>pop(5)</code>: вернул 6, скопировал версию 3
|-
| 9 || 9 || 7 || <code>push(7, 9)</code>
|}

Разберём строку 4: <code>pop(3)</code> читает ячейку 3 (<code>value = 5, prev = 2</code>), возвращает <code>5</code>, а новой версией делает копию ячейки под ней — ячейка 4 повторяет версию 2 (<code>value = 3, prev = 1</code>). Строка 7: <code>pop(4)</code> возвращает <code>3</code>, а новой версией становится пустая (ячейка 7 повторяет корень). Все прошлые ячейки (1–6) остаются доступными: в массиве запросов ничего не перезаписывается.

== Корректность и оценка сложности ==

=== Инвариант ===

'''Инвариант.''' Для любого узла <math>v</math> цепочка <math>v, \mathrm{prev}(v), \mathrm{prev}^2(v), \dots</math> заканчивается корнем, и значения узлов вдоль цепочки образуют содержимое версии <math>v</math> сверху вниз.

'''База.''' Корень — пустая версия, цепочка длины 0.

'''Переход <code>push</code>.''' Новый узел <math>k</math> указывает на прежнюю вершину <math>v</math>, поэтому цепочка из <math>k</math> есть <math>k</math> + цепочка из <math>v</math>; значения — <math>x</math> + содержимое <math>v</math>, что и требуется. Ни один старый узел не изменён.

'''Переход <code>pop</code>.''' Новая вершина — <math>\mathrm{prev}(v)</math>; её цепочка есть содержимое версии без верхнего элемента. Исходная ссылка <math>v</math> сохраняет старый стек.

Отсюда <code>Top</code> возвращает верхний элемент, <code>Empty</code> корректно распознаёт корень, а любая версия читается за <math>O(1)</math> по ссылке (переход к прошлому состоянию — операция над указателем).

=== Оценка памяти: разделение хвостов ===

Каждый <code>push</code> создаёт '''ровно один''' новый узел; <code>pop</code> в списковой реализации не создаёт узлов вовсе. Значит, после <math>n</math> операций <code>push</code> в структуре <math>n + 1</math> узел (включая корень), то есть <math>O(n)</math> памяти — независимо от того, сколько версий сохранено и каковы их размеры (см. рис. 5). Если бы каждая версия хранилась отдельным массивом, суммарная память была бы <math>1 + 2 + \dots + n = \Theta(n^2)</math>.

[[Файл:pstack-05-sharing.svg|thumb|700px|Рис. 5. Ветви делят общий хвост: <math>n</math> операций <code>push</code> дают <math>n + 1</math> узел, а не <math>\Theta(n^2)</math> памяти.]]

=== Время ===

<code>Push</code>, <code>Pop</code>, <code>Top</code>, <code>Empty</code> выполняют постоянное число операций над указателями и записями — <math>O(1)</math> в худшем случае. Материализация версии из <math>k</math> элементов требует прохода по <math>k</math> узлам — <math>O(k)</math>; это неизбежно, поскольку выписываются <math>k</math> значений.

== Сравнение с альтернативами ==

{| class="wikitable"
|-
! Структура !! <code>push</code> !! <code>pop</code> !! Доступ к версиям !! Память под <math>n</math> версий
|-
| Обычный стек ([[Стек]]) || <math>O(1)</math> || <math>O(1)</math> || нет (одно состояние) || <math>O(n)</math>
|-
| Обычный стек + полное копирование || <math>O(1)</math> + <math>\Theta(n)</math> копия || <math>O(1)</math> || да || <math>\Theta(n^2)</math>
|-
| '''Персистентный стек (список)''' || <math>O(1)</math>, 1 узел || <math>O(1)</math>, 0 узлов || да, <math>O(1)</math> || <math>O(n)</math>
|-
| Персистентный стек (массив запросов) || <math>O(1)</math>, 1 ячейка || <math>O(1)</math>, 1 ячейка || да, <math>O(1)</math> || <math>O(n)</math>
|-
| Персистентная очередь ([[Очередь на шести стеках]]) || <math>O(1)</math> || <math>O(1)</math> || да, <math>O(1)</math> || <math>O(n)</math> суммарно (<math>O(1)</math> новых на операцию)
|}

'''Вердикт.''' Нужны прошлые состояния стека — только персистентная реализация; копирование неприемлемо из-за <math>\Theta(n^2)</math>. Между списком и массивом выбор по стилю: список удобнее для функционального кода и передачи версий как значений, массив — для нумерованных версий и индексного доступа. Персистентная очередь — следующий шаг: стек — её элементарный кирпич.

== Где применяется ==

# '''Функциональные языки и неизменяемые списки.''' Односвязный список в LISP, Haskell, OCaml, Standard ML — это персистентный стек: добавление в голову за <math>O(1)</math>, хвосты разделяются. Почему: скрытая мутация в чистом функциональном языке невозможна, а неизменяемый список её и не требует [2][3].

# '''Персистентная очередь и другие персистентные структуры.''' Делая стек персистентным, мы получаем строительный блок для очереди ([[Очередь на шести стеках]]), дека и приоритетной очереди. Почему: многие структуры сводятся к комбинации стеков/списков [1][2].

# '''Undo/redo и версионирование.''' Редакторы, СУБД с MVCC, системы контроля версий и транзакционные снапшоты хранят историю как версии структуры; откат — переход по ссылке без копирования данных [3][4].

# '''Обход и разбор с ветвлением.''' В backtracking, разборе выражений и DFS путь можно хранить как персистентный стек: каждое ветвление — новая версия, а возврат в точку выбора — переход по сохранённой ссылке. Почему: состояние стека восстанавливается за <math>O(1)</math> [2].

# '''Параллельные и распределённые вычисления.''' Неизменяемые данные естественно разделяются между потоками и репликами без блокировок: структура, разделяемая несколькими потребителями, не может быть испорчена мутацией [3][4].

Обзор основных областей — на рис. 6.

[[Файл:pstack-06-apply.svg|frame|none|700px|Рис. 6. Персистентная очередь, версионирование и undo, функциональные списки, история обхода и разбора, параллельные вычисления — пять областей, где персистентный стек служит фундаментом.]]

== Историческая справка ==

Идея функциональных списков-стеков восходит к языку '''LISP''' (Джон Маккарти, 1958–1960): операции <code>cons</code>, <code>car</code>, <code>cdr</code> строят разделяемые неизменяемые цепочки — фактически персистентный стек [2]. Термин «персистентные структуры данных» и систематическое изучение методов (путь-копирование, fat nodes, node-copying) ввели '''Дрисколл, Сарнак, Слитор и Тарьян''' в работе ''Making Data Structures Persistent'' (STOC 1986; журнальная версия — JCSS, 1989) [4]. Формальный амортизированный анализ, которым описывают стоимость операций, развил '''Роберт Тарьян''' («Amortized Computational Complexity», 1985) [5].

Учебное изложение персистентного стека (список и массив запросов) — конспект кафедры компьютерных технологий ИТМО на «Викиконспектах» [1]; оттуда же распространён разбор персистентной очереди. Понятие «функциональная персистентность» и коллекция персистентных структур систематизированы '''Крисом Окасаки''' в книге ''Purely Functional Data Structures'' (Cambridge University Press, 1998) [3].

== Типичные ошибки и подводные камни ==

* '''Путать персистентность со снапшотом-копией.''' Персистентный стек не копирует содержимое при каждой версии: узлы общие, копируется только «верх» (один узел).
* '''Мутировать узел.''' Изменение <code>value</code>/<code>prev</code> существующего узла немедленно испортит все версии, которые через него проходят. Узлы обязаны быть неизменяемыми.
* '''Освобождать память «оптимизацией».''' Удаление узлов из-под старых версий ломает персистентность; сборка мусора нужна, но только когда на узел не ссылается ни одна версия.
* '''Считать память пропорциональной числу версий, умноженному на их размер.''' Правильная оценка — <math>O(\text{число операций})</math> благодаря разделению хвостов.
* '''Ожидать <math>O(1)</math> от <code>pop</code> в массивной реализации без учёта новой ячейки.''' В массиве <code>pop</code> добавляет запись; это всё ещё <math>O(1)</math>, но память растёт на каждую модификацию.
* '''Переполнение/уход индексов в массиве запросов.''' Версии нумеруются монотонно; смешение «номера версии» и «индекса ячейки» при ветвлении приводит к ошибкам.
* '''Смешивать ''current'' и ''версию''.''' Возвращая из операции узел, а не пару «результат + новая версия», легко потерять возможность продолжать от прежней версии.
* '''Забыть про корень.''' Пустая версия должна быть корректным состоянием: без корня <code>pop</code> до конца и <code>Empty</code> работают неверно.
* '''Ожидать, что <code>To-List</code> бесплатен.''' Материализация версии — <math>O(k)</math>; путать её с <math>O(1)</math> доступом к самой версии нельзя.
* '''Полагать, что персистентность автоматически даёт быстрый произвольный <code>pop</code>.''' Для очереди на двух стеках этого мало — требуется дробление переноса (см. [[Очередь на шести стеках]]).

== Задачи для практики ==

# '''Базовые операции.''' Реализуйте персистентный стек на списке (<code>value</code>, <code>prev</code>) с <code>push</code>, <code>pop</code>, <code>top</code>, <code>empty</code>. Ограничение: узлы неизменяемы. ''Подсказка:'' <code>pop</code> возвращает пару «значение + новая версия».

# '''Ветвление.''' В списковой реализации от версии <code>[a, b, c]</code> примените <code>pop</code>, затем <code>push(d)</code>, затем ещё раз <code>pop</code>. Сколько версий существует и какие у них содержимые? ''Подсказка:'' постройте дерево версий.

# '''Память.''' Для списковой реализации докажите, что <math>n</math> операций <code>push</code> и любые <code>pop</code> порождают не более <math>n + 1</math> узлов. ''Подсказка:'' каждый <code>push</code> добавляет ровно один узел, <code>pop</code> — ноль.

# '''Массив запросов.''' Реализуйте массивную версию и воспроизведите трассировку из раздела «Трассировка примера». Сверьте значения <code>value</code> и <code>prev</code>.

# '''Материализация.''' Напишите <code>To-List(v)</code> и оцените время; добейтесь <math>O(k)</math> для версии из <math>k</math> элементов. ''Подсказка:'' идти по <code>prev</code> от вершины к корню.

# '''Общий хвост.''' Для двух версий найдите длину общего хвоста, используя только поля <code>{value, prev}</code>; добейтесь времени <math>O(\ell_1 + \ell_2)</math>, где <math>\ell_i</math> — длины версий. ''Дополнительно:'' добавьте <code>depth</code> и двоичные подъёмы (binary lifting); оцените preprocessing и время запроса LCA. ''Подсказка:'' без глубины сначала найдите глубины, затем выровняйте вершины и идите вверх вместе.

# '''Персистентная очередь.''' Используя персистентный стек, постройте персистентную очередь и оцените худшее время <code>push</code>/<code>pop</code>. ''Подсказка:'' два стека; обсудите, почему нужен <math>O(1)</math> в худшем случае.

# '''Сравнение.''' Сравните сумму памяти для <math>n</math> версий при (а) полном копировании, (б) списковой персистентности, (в) массивной. Приведите асимптотики и пример численно при <math>n = 1000</math>.

== Связанные темы ==

* [[Стек]] — базовый LIFO-стек; мутирующая реализация.
* [[Персистентная очередь]] — персистентность очереди целиком.
* [[Очередь на шести стеках]] — очередь реального времени на шести стеках.
* [[Асимптотическая сложность]] — оценки <math>O</math>, амортизация, худший случай.
* [[Персистентные структуры данных]] — общая теория: путь-копирование, fat nodes.
* [[Декартово дерево]] — персистентный treap; ещё один пример персистентности.
* [[Двоичное дерево поиска]] — персистентные структуры на деревьях.

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

# Викиконспекты ИТМО: Персистентный стек (реализации на массиве и на списке, пример). URL: https://neerc.ifmo.ru/wiki/index.php?title=Персистентный_стек.
# McCarthy J. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I // Communications of the ACM. — 1960. — Vol. 3, № 4 (основы LISP и списков).
# Okasaki C. ''Purely Functional Data Structures''. — Cambridge University Press, 1998.
# Driscoll J. R., Sarnak N., Sleator D. D., Tarjan R. E. Making Data Structures Persistent // STOC 1986; журнальная версия: Journal of Computer and System Sciences. — 1989. — Vol. 38.
# Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2.
# Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. ''Introduction to Algorithms'' (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 10 (элементарные структуры: стек, список).
# Хабрахабр. Персистентные структуры, часть 1: персистентный стек (пост 113585). URL: https://habr.com/ru/post/113585/.

[[Category:Алгоритмы и структуры данных]]

Очередь на шести стеках

2026-11-04T18:07:04Z

СВ: /* Источники */

== TL;DR ==

Обычная очередь на '''двух стеках''' работает амортизированно за <math>O(1)</math>, но отдельная операция может стоить <math>\Theta(n)</math>: когда выходной стек пуст, приходится разом перевернуть весь входной. '''Очередь на шести стеках''' (real-time queue) распределяет этот перенос на маленькие порции — не более '''3 действий за операцию''' — и тем самым даёт '''<math>O(1)</math> в худшем случае''' на каждую операцию, то есть работает в реальном времени. Стеки <math>L, L', R, R_c, R_c', S</math> и переменные <math>\mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}</math> следят за фоновым перекопированием, а копии <math>R_c, R_c'</math> обслуживают <code>pop</code>, пока выход перестраивается. Из этой конструкции одной заменой <math>(R_c, R_c') \to R'</math> получается '''персистентная очередь на пяти стеках''': каждая версия занимает <math>O(1)</math> новых ячеек, а операции остаются <math>O(1)</math> в худшем случае.

== Инфобокс ==

{| class="wikitable"
|-
! Свойство !! Значение
|-
| Класс || Очередь (FIFO) в реальном времени; на стеках
|-
| Порядок доступа || FIFO
|-
| Худший случай || <math>O(1)</math> на <code>push</code>, <code>pop</code>, <code>empty</code>
|-
| Амортизированный || <math>O(1)</math> (совпадает с худшим — амортизация не нужна)
|-
| Память || <math>O(n)</math> под элементы; <math>\le 3</math> переноса на операцию (не более 6 стеков)
|-
| Стеки || <math>L, L', R, R_c, R_c', S</math>
|-
| Переменные || <math>\mathtt{recopy}</math>, <math>\mathtt{toCopy}</math>, <math>\mathtt{copied}</math>
|-
| Режимы || обычный и перекопирования
|-
| Сравнение || 2 стека — амортизированно <math>O(1)</math>, худший <math>\Theta(n)</math>; 6 стеков — худший <math>O(1)</math>; 5 стеков — ещё и персистентность
|-
| Авторы идеи || Hood, Melville (1980); персистентный вариант — учебная традиция ИТМО, Okasaki
|-
| Где встречается || функциональные языки, персистентные структуры, системы реального времени, версионирование
|}

== Определения ==

'''Очередь''' (см. [[Очередь]] (план)) — коллекция с порядком '''FIFO''': <code>push</code> добавляет в конец, <code>pop</code> забирает из начала. Реализуется кольцевым буфером, списком или двумя стеками.

'''Реализация на двух стеках.''' Входной стек <math>L</math> принимает <code>push</code>, выходной <math>R</math> обслуживает <code>pop</code>. Когда <math>R</math> пуст, все элементы <math>L</math> переворачиваются в <math>R</math>: <math>L</math> разбирается сверху, каждый элемент кладётся в <math>R</math>. Разовый перенос стоит <math>\Theta(n)</math>, поэтому <math>O(1)</math> здесь — '''амортизированный''', а не худший.

'''Очередь в реальном времени (real-time queue).''' Очередь, у которой каждая операция выполняется за <math>O(1)</math> '''в худшем случае''', без «долгих» вызовов. Синоним: очередь с ограниченным (постоянным) временем отклика.

'''Перекопирование (recopy mode).''' Фоновый режим, в котором часть работы переноса <math>(L \to R)</math> выполняется маленькими порциями параллельно с обычными операциями. Начинается, когда <math>L.size > R.size</math>, и заканчивается, когда служебный стек <math>S</math> опустеет.

'''Шесть стеков.''' Основные: <math>L</math> — вход обычного режима, <math>R</math> — выход обычного режима. Вспомогательные: <math>L'</math> — вход во время перекопирования; <math>S</math> — буфер двойного переворота; <math>R_c</math> — копия текущего <math>R</math> (из неё идут <code>pop</code> во время перекопирования); <math>R_c'</math> — копия строящегося <math>R</math>.

'''Переменные состояния.''' <math>\mathtt{recopy}</math> — булев флаг режима; <math>\mathtt{toCopy}</math> — сколько элементов в <math>S</math> ещё «корректны» (принадлежат очереди); <math>\mathtt{copied}</math> — начат ли перенос <math>L \to R</math>.

'''Персистентная структура данных.''' Структура, к которой доступны все прошлые версии. '''Функциональная персистентность''' — сильнейшая форма: ячейка памяти инициализируется один раз и больше не меняется, поэтому версии разделяют неизменяемые данные. См. [[Персистентные структуры данных]].

'''Персистентная очередь на пяти стеках.''' Вариант, где пара <math>(R_c, R_c')</math> заменена одной неизменяемой версией <math>R'</math>, а версия очереди описывается записью <math>Q = \langle L, L', R, R', S, \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}\rangle</math>.

'''Обозначения.''' <math>n</math> — число элементов очереди; <math>|X|</math> — размер стека <math>X</math>; <math>\log</math> — двоичный. Стеки трактуются как последовательности «дно … верх».

== Мотивация и интуиция ==

Очередь на двух стеках красива, но у неё есть скрытый дефект: один <code>pop</code> на пустом <math>R</math> тянет за собой перенос всех элементов — <math>\Theta(n)</math> работы и, что важнее для персистентности, <math>\Theta(n)</math> '''новых ячеек памяти''' в одной операции. Для систем реального времени (планировщики, обработка сигналов, сетевые буферы) задержка должна быть ограничена сверху; один вызов, пропорциональный размеру структуры, недопустим. См. рис. 1.

[[Файл:q6-01-two-stacks.svg|thumb|700px|Рис. 1. Перенос <math>L \to R</math> происходит разом и даёт пик <math>\Theta(n)</math>; задача — размазать его по операциям так, чтобы каждая стоила <math>O(1)</math>.]]

Ключевая идея: '''дробить дорогую работу'''. Пока очередь обслуживает обычные <code>push</code>/<code>pop</code>, она потихоньку готовит новый выходной стек, выполняя ровно '''3 действия''' за операцию. Если начать перекопирование заранее — когда <math>|L|</math> лишь на единицу превысил <math>|R|</math>, — то на перенос останется ровно столько операций, сколько нужно, и «долгих» вызовов не будет вовсе.

Почему именно шесть стеков? Во время переноса стек <math>L</math> разбирается, поэтому новые <code>push</code> надо куда-то девать — так появляется <math>L'</math>. Пока строится новый <math>R</math>, старый выход ещё должен отвечать на <code>pop</code> — так появляется копия <math>R_c</math>. У копии тоже есть версия «на будущее» — <math>R_c'</math>. Наконец, старый <math>R</math> может не успеть опустеть (если операций <code>push</code> было много), поэтому его содержимое временно уводят в буфер <math>S</math>, чтобы через двойной переворот вернуть уже над новыми элементами <math>L</math>. Итого <math>L, L', R, R_c, R_c', S</math> — шесть стеков.

== Устройство ==

Очередь хранит шесть стеков и три переменные; вместе они реализуют FIFO с постоянным временем отклика (см. рис. 2).

[[Файл:q6-02-roles.svg|frame|none|700px|Рис. 2. <math>L</math> — вход обычного режима, <math>R</math> — выход; <math>L'</math> принимает вход во время перекопирования, <math>R_c</math> и <math>R_c'</math> — копии выхода, <math>S</math> — буфер двойного переворота.]]

Работа идёт в '''двух режимах''' (см. рис. 3):

* '''Обычный режим.''' <code>push</code> кладёт в <math>L</math>, <code>pop</code> берёт из <math>R</math> (и синхронно из <math>R_c</math>); <math>\mathtt{empty} = (R = \varnothing)</math>. После каждой операции проверка <math>\mathtt{recopy} \leftarrow (|L| > |R|)</math>.
* '''Режим перекопирования.''' <code>push</code> кладёт в <math>L'</math>, <code>pop</code> берёт из <math>R_c</math>; <math>\mathtt{empty} = \text{false}</math>; каждая операция делает не более 3 переносов. Режим длится, пока <math>S \neq \varnothing</math>.

[[Файл:q6-03-modes.svg|thumb|700px|Рис. 3. Переключение режимов: вход в перекопирование по <math>\lvert L\rvert > \lvert R\rvert</math>, выход — по пустому <math>S</math>.]]

Перекопирование не должно затянуться дольше, чем простоит старый выход, — иначе не хватит свободного стека. Гарантию дают '''инварианты''' (см. рис. 4). В обычном режиме: <math>L</math> и <math>R</math> — половины очереди, <math>|L| \le |R|</math>, <math>R = \varnothing \iff Q = \varnothing</math>, <math>R_c</math> — копия <math>R</math>, а <math>R_c'</math> и <math>S</math> подчищены так, что <math>|R_c'| \le |R| - |L|</math> и <math>|L'| = |S| = 0</math>. В режиме перекопирования: <math>|R_c| \ge \mathtt{toCopy}</math> (равенство, пока из <math>S</math> не переносили корректных элементов), и если <math>|L| = 0</math>, то либо первые <math>\mathtt{toCopy}</math> элементов <math>S</math> корректны, либо (при <math>\mathtt{toCopy} \le 0</math>) стек <math>R</math> уже содержит весь правый кусок очереди в правильном порядке.

[[Файл:q6-04-invariants.svg|thumb|700px|Рис. 4. Инвариант <math>\lvert R_c'\rvert \le \lvert R\rvert - \lvert L\rvert</math> гарантирует, что остаток <math>R_c'</math> рассосётся по элементу за операцию до следующего перекопирования.]]

== Операции и алгоритмы ==

Ниже — операции очереди. Обозначим <math>|X| = \mathtt{X.size}</math>; стек как объект со стандартными <math>\mathtt{push}, \mathtt{pop}</math>; <math>\mathtt{swap}</math> меняет местами переменные-стеки.

=== Операция: Empty ===

'''Идея.''' В обычном режиме очередь пуста тогда и только тогда, когда пуст <math>R</math>; в режиме
перекопирования очередь заведомо непуста (см. лемму о корректности <code>Empty</code> ниже).

<syntaxhighlight lang="text">
Операция Empty(Q)
Вход: очередь Q
Выход: true, если элементов нет
Инвариант: R = ∅ ⟺ Q = ∅ (в обычном режиме)
Сложность: O(1) времени, O(1) памяти

1 return (not Q.recopy) and (|R| = 0)
</syntaxhighlight>

'''Крайние случаи.''' Во время перекопирования <code>Empty</code> всегда <code>false</code>, даже если все «старые» элементы уже извлечены: за время переноса выполняется не более <math>n</math> извлечений, а в очереди было <math>2n+1</math> элементов, поэтому неперекопированный остаток лежит в <math>R_c</math> или <math>R</math>.

=== Операция: Push ===

'''Идея.''' В обычном режиме элемент идёт в <math>L</math>; попутно подчищаем <math>R_c'</math> и проверяем, не пора ли начать перекопирование. В режиме перекопирования элемент идёт в <math>L'</math> (стек <math>L</math> сейчас разбирается), и продолжаем фоновую работу.

<syntaxhighlight lang="text">
Операция Push(Q, x)
Вход: очередь Q; x — элемент
Выход: x добавлен в конец очереди
Инвариант: в обычном режиме Q = R (сверху вниз) ++ reverse(L)
Сложность: O(1) в худшем случае (не более 3 переносов)

1 if not Q.recopy
2 push(L, x)
3 if |Rc'| > 0
4 pop(Rc') # рассасываем остаток копии
5 Check-Recopy(Q)
6 else
7 push(L', x)
8 Check-Normal(Q)
</syntaxhighlight>

'''Крайние случаи.''' Если очередь была пуста, <code>push</code> запускает перекопирование (так как <math>|L| = 1 > 0 = |R|</math>), но завершает его сразу же за один вызов, попадая в обычный режим.

=== Операция: Pop ===

'''Идея.''' В обычном режиме берём верх <math>R</math> (это самый старый элемент) и синхронно чистим <math>R_c</math>. В режиме перекопирования элемент берётся из копии <math>R_c</math>; если <math>\mathtt{toCopy} > 0</math>, он «оплачен» корректным элементом из <math>S</math>, иначе берём и из перестраиваемого <math>R</math>.

<syntaxhighlight lang="text">
Операция Pop(Q)
Вход: очередь Q
Выход: самый старый элемент; error, если очередь пуста
Инвариант: возвращаемый элемент — минимальный по времени поступления
Сложность: O(1) в худшем случае (не более 3 переносов)

1 if not Q.recopy
2 x ← pop(R)
3 pop(Rc)
4 if |Rc'| > 0
5 pop(Rc')
6 Check-Recopy(Q)
7 return x
8 else
9 x ← pop(Rc)
10 if Q.toCopy > 0
11 Q.toCopy ← Q.toCopy − 1
12 else
13 pop(R)
14 pop(Rc')
15 Check-Normal(Q)
16 return x
</syntaxhighlight>

'''Крайние случаи.''' Если в режиме перекопирования <math>\mathtt{toCopy}</math> дошёл до нуля, значит, оставшиеся старые элементы уже продублированы в <math>R</math>; тогда <code>pop</code> синхронно снимает элемент из <math>R_c</math>, <math>R</math> и <math>R_c'</math>. Обращение к пустой очереди — ошибка (<code>underflow</code>), как и в любой очереди.

=== Операция: Check-Recopy ===

'''Идея.''' После операции в обычном режиме проверить, не перерос ли вход выход; если да — переключиться в режим перекопирования и сделать первый пакет переносов.

<syntaxhighlight lang="text">
Операция Check-Recopy(Q)
1 Q.recopy ← (|L| > |R|)
2 if Q.recopy
3 Q.toCopy ← |R| # столько старых элементов ещё «в деле»
4 Q.copied ← false # перенос L → R ещё не начат
5 Check-Normal(Q)
</syntaxhighlight>

=== Операция: Check-Normal ===

'''Идея.''' Доделать пакет переносов; режим перекопирования продолжается, пока непуст <math>S</math>.

<syntaxhighlight lang="text">
Операция Check-Normal(Q)
1 Additional-Operations(Q)
2 Q.recopy ← (|S| ≠ 0) # S пуст — перекопирование завершено
</syntaxhighlight>

=== Операция: Additional-Operations ===

'''Идея.''' За один вызов выполнить не более '''3''' действий над вспомогательными стеками (см. рис. 5). Четыре фазы:

# '''<math>R \to S</math>''' — пока <math>R</math> не пуст и <math>\mathtt{copied} = \text{false}</math>, перекладывать <math>R</math> в <math>S</math> (временный переворот выхода).
# '''<math>L \to R, R_c'</math>''' — как только начали, ставим <math>\mathtt{copied} \leftarrow \text{true}</math>; каждый элемент <math>L</math> идёт и в <math>R</math>, и в <math>R_c'</math>.
# '''<math>S \to R, R_c'</math>''' — первые <math>\mathtt{toCopy}</math> элементов <math>S</math> возвращаются в <math>R</math> и <math>R_c'</math> (двойной переворот восстанавливает порядок <math>R</math> и кладёт его '''над''' элементами <math>L</math>); остальные (уже логически извлечённые) отбрасываются.
# '''Смена ролей''' — если <math>S</math> пуст: <math>\mathtt{swap}(L, L')</math>, <math>\mathtt{swap}(R_c, R_c')</math>.

<syntaxhighlight lang="text">
Операция Additional-Operations(Q)
Вход: очередь Q в режиме перекопирования
Выход: сделано не более 3 переносов
Инвариант: фазы 1–4 выполняются строго по порядку
Сложность: O(1) (счётчик toDo = 3)

1 toDo ← 3
2 while (not Q.copied) and toDo > 0 and |R| > 0
3 push(S, pop(R)) # фаза 1: R → S
4 toDo ← toDo − 1
5 while toDo > 0 and |L| > 0
6 Q.copied ← true
7 x ← pop(L)
8 push(R, x) # фаза 2: L → R
9 push(Rc', x) # и L → Rc'
10 toDo ← toDo − 1
11 while toDo > 0 and |S| > 0
12 x ← pop(S) # фаза 3: S → R, Rc'
13 if Q.toCopy > 0
14 push(R, x)
15 push(Rc', x)
16 Q.toCopy ← Q.toCopy − 1
17 toDo ← toDo − 1
18 if |S| = 0
19 swap(L, L') # фаза 4: смена ролей
20 swap(Rc, Rc')
</syntaxhighlight>

'''Разбор.''' Точные состояния стеков на примере <code>push(1..7)</code> и последующих <code>pop</code> приведены в разделе «Трассировка примера». Ключевой момент фазы 3 — двойной переворот <math>R \to S \to R</math>: он возвращает относительный порядок старого выхода неизменным, но ставит его поверх элементов <math>L</math>; поскольку старые элементы и есть «перед» очереди, <code>pop</code> из нового <math>R</math> выдаёт FIFO.

'''Крайние случаи.''' Если <math>R</math> уже пуст, фаза 1 пропускается и работа сразу начинается с фазы 2. Если <math>L</math> пуст, фаза 2 пропускается. Если <math>\mathtt{toCopy} = 0</math>, элементы <math>S</math> просто извлекаются и выбрасываются — они уже были отданы через <math>R_c</math>.

[[Файл:q6-05-recopy-steps.svg|frame|none|700px|Рис. 5. За вызов <code>additionalOperations</code> — не более 3 переносов; фазы идут строго по порядку.]]

== Сводная таблица сложности ==

{| class="wikitable"
|-
! Операция !! Худший случай !! Амортизированный !! Переносов за вызов !! Память
|-
| <code>Empty</code> || <math>O(1)</math> || <math>O(1)</math> || 0 || <math>O(1)</math>
|-
| <code>Push</code> || <math>O(1)</math> || <math>O(1)</math> || <math>\le 3</math> || <math>O(1)</math>
|-
| <code>Pop</code> || <math>O(1)</math> || <math>O(1)</math> || <math>\le 3</math> || <math>O(1)</math>
|-
| <code>Check-Recopy</code> / <code>Check-Normal</code> || <math>O(1)</math> || <math>O(1)</math> || <math>\le 3</math> || <math>O(1)</math>
|-
| Вся очередь || — || — || — || <math>O(n)</math> под элементы
|}

Здесь '''худший и амортизированный случаи совпадают''': амортизация не нужна, потому что никакая операция не выполняет больше трёх переносов. Для сравнения, очередь на двух стеках имеет амортизированный <math>O(1)</math>, но худший <math>\Theta(n)</math>. В режиме перекопирования каждая «обычная» операция дополнительно тратит до 3 переносов — это уже учтено в оценке <math>O(1)</math>.

== Трассировка примера ==

Проследим <code>push(1)</code> … <code>push(7)</code>, затем семь <code>pop</code>. Стеки записаны в виде «дно … верх»; в столбце «режим»: <code>обыч.</code> — обычный, <code>перекоп.</code> — перекопирование. Значения получены прогоном реализации из раздела «Служебное».

{| class="wikitable"
|-
! Операция !! Режим !! <math>L</math> !! <math>L'</math> !! <math>R</math> !! <math>R_c</math> !! <math>R_c'</math> !! <math>S</math> !! <code>toCopy</code>
|-
| <code>push(1)</code> || обыч.→перекоп.→обыч. || — || — || 1 || 1 || — || — || 0
|-
| <code>push(2)</code> || обыч. || 2 || — || 1 || 1 || — || — || 0
|-
| <code>push(3)</code> || обыч.→перекоп. || — || — || 3,2 || 1 || 3,2 || 1 || 1
|-
| <code>push(4)</code> || перекоп.→обыч. || 4 || — || 3,2,1 || 3,2,1 || 1 || — || 0
|-
| <code>push(5)</code> || обыч. || 4,5 || — || 3,2,1 || 3,2,1 || — || — || 0
|-
| <code>push(6)</code> || обыч. || 4,5,6 || — || 3,2,1 || 3,2,1 || — || — || 0
|-
| <code>push(7)</code> || обыч.→перекоп. || 4,5,6,7 || — || — || 3,2,1 || — || 1,2,3 || 3
|-
| <code>pop()</code> → 1 || перекоп. || 4 || — || 7,6,5 || 3,2 || 7,6,5 || 1,2,3 || 2
|-
| <code>pop()</code> → 2 || перекоп. || — || — || 7,6,5,4,3 || 3 || 7,6,5,4,3 || 1 || 0
|-
| <code>pop()</code> → 3 || перекоп.→обыч. || — || — || 7,6,5,4 || 7,6,5,4 || — || — || 0
|-
| <code>pop()</code> → 4 || обыч. || — || — || 7,6,5 || 7,6,5 || — || — || 0
|-
| <code>pop()</code> → 5 || обыч. || — || — || 7,6 || 7,6 || — || — || 0
|-
| <code>pop()</code> → 6 || обыч. || — || — || 7 || 7 || — || — || 0
|-
| <code>pop()</code> → 7 || обыч. || — || — || — || — || — || — || 0
|}

Разберём два важных момента. Во-первых, <code>push(3)</code> запускает перекопирование сразу, но успевает сделать только 3 переноса (старый <math>R = \{1\}</math> уходит в <math>S</math>, два элемента <math>L</math> — в <math>R</math> и <math>R_c'</math>); завершается перенос на <code>push(4)</code>, после чего пары <math>L \leftrightarrow L'</math> и <math>R_c \leftrightarrow R_c'</math> меняются ролями. Во-вторых, при <code>push(7)</code> вход (<math>|L| = 4</math>) перерос выход (<math>|R| = 3</math>), начался новый перенос: <math>R</math> целиком ушёл в <math>S</math>, <code>toCopy = 3</code>. Следующие <code>pop</code> берут элементы из <math>R_c</math> (копия старого <math>R</math>), пока в фоне <math>L</math> переливается в новый <math>R</math>; когда <code>toCopy</code> доходит до нуля, корректная часть <math>S</math> переносится в <math>R</math>, а остальное отбрасывается, и перекопирование заканчивается. Порядок выдачи — <math>1,2,\dots,7</math> — ровно FIFO, и ни один <code>pop</code> не сделал больше трёх внутренних переносов.

== Корректность и оценка сложности ==

=== Инвариант и FIFO ===

Будем считать, что в обычном режиме элементы очереди равны <math>R</math> (сверху вниз) <math>\mathbin{+\!\!+}</math> <math>\mathrm{reverse}(L)</math>. Тогда верх <math>R</math> — самый старый элемент, и <code>Pop</code> возвращает его.

'''Лемма (сохранение порядка при перекопировании).''' После завершения перекопирования стек <math>R</math> содержит все элементы очереди в правильном порядке для извлечения.

''Доказательство.'' Пусть до перекопирования очередь равна <math>R_0 \mathbin{+\!\!+} L_0</math> (в указанном смысле). Фаза 1 переносит <math>R_0</math> в <math>S</math>, разворачивая: <math>S = \mathrm{reverse}(R_0)</math>. Фаза 2 переносит <math>L_0</math> в <math>R</math>, разворачивая: <math>R = \mathrm{reverse}(L_0)</math>. Фаза 3 переносит <math>S</math> (в порядке <math>\mathrm{reverse}(R_0)</math>) обратно в <math>R</math>, что даёт <math>R = \mathrm{reverse}(L_0) \mathbin{+\!\!+} R_0</math> в смысле стека, то есть сверху оказывается <math>R_0</math> в исходном порядке, а под ним — <math>L_0</math> в исходном порядке. Поскольку элементы <math>R_0</math> старее элементов <math>L_0</math>, это и есть FIFO-порядок. <math>\square</math>

'''Лемма (обслуживание во время перекопирования).''' Пока перекопирование не завершено, <code>Pop</code> возвращает корректный самый старый элемент, не дожидаясь конца переноса.

''Доказательство.'' В режиме перекопирования <code>Pop</code> читает <math>R_c</math> — копию старого <math>R_0</math>; в варианте на шести стеках она синхронно уменьшается вместе с <math>R</math>, а в персистентном заменена неизменяемой версией <math>R'</math>. Элементы <math>R_0</math> старее всех элементов <math>L_0 \cup L'</math>, поэтому выдача из <math>R_c</math> сохраняет FIFO. Счётчик <math>\mathtt{toCopy}</math> уменьшается и при извлечении из <math>R_c</math>, и при переносе корректного элемента из <math>S</math>; поэтому <math>|R_c| \ge \mathtt{toCopy}</math>. Пока <math>\mathtt{toCopy} > 0</math>, верх <math>R_c</math> — ещё не перенесённый корректный элемент; когда счётчик доходит до нуля, старый правый кусок уже распределён между <math>R</math> и <math>R_c</math>, и <code>Pop</code> синхронно снимает элемент из <math>R_c</math>, <math>R</math> и <math>R_c'</math>. Инвариант <math>\mathtt{toCopy}</math> не даёт прочитать «мусорные» элементы в дне <math>S</math>. <math>\square</math>

'''Лемма (корректность <code>Empty</code>).''' В обычном режиме <math>R = \varnothing \iff Q = \varnothing</math>; в режиме перекопирования очередь непуста.

''Доказательство.'' В обычном режиме инвариант <math>|L| \le |R|</math> и представление очереди как <math>R \mathbin{+\!\!+} \mathrm{reverse}(L)</math> дают эквивалентность. В режиме перекопирования в момент старта (после запускающей операции) в очереди <math>n + (n + 1) = 2n + 1</math> элементов. Перенос занимает <math>n + 1</math> операций, включая запускающую; после неё остаётся не более <math>n</math> операций, поэтому извлечь можно не более <math>n</math> элементов. Значит, хотя бы один элемент остаётся: при <math>\mathtt{toCopy} > 0</math> он лежит в <math>R_c</math>, а при <math>\mathtt{toCopy} = 0</math> весь правый кусок уже находится в <math>R</math>. Поэтому <code>Empty</code> возвращает <code>false</code> корректно. <math>\square</math>

=== Оценка <math>O(1)</math> в худшем случае ===

Все переносы выполняются только в <code>Additional-Operations</code>, где счётчик <code>toDo</code> ограничен тройкой, и в фазах 1–3 каждый шаг — один перенос (pop и один-два push). Значит, одна операция очереди делает не более 3 переносов, то есть <math>O(1)</math> в худшем случае (см. рис. 6).

Покажем, что перекопирование '''успевает''' завершиться. В момент старта <math>|R| = n</math> и <math>|L| = n + 1</math>. Требуется: <math>R \to S</math> — <math>n</math> действий; <math>L \to R, R_c'</math> — <math>n + 1</math>; <math>S \to R, R_c'</math> — <math>n</math>; две смены ролей — 2. Итого <math>3n + 3</math> действий. В распоряжении — <math>n + 1</math> операций (сама запускающая перекопирование плюс следующие за ней до завершения переноса), по 3 действия каждая, то есть ровно <math>3(n + 1) = 3n + 3</math>. Расчёт сходится: перенос гарантированно завершается.

[[Файл:q6-06-timeline.svg|thumb|700px|Рис. 6. <math>3(n+1)</math> действий на <math>n+1</math> операций — ровно 3 действия на операцию, без запаздывания.]]

'''После перекопирования.''' Пусть за <math>n</math> операций после старта произошло <math>x</math> извлечений и <math>n - x</math> добавлений. Тогда в новых стеках останется <math>n - x</math> элементов в <math>L</math> и <math>2n + 1 - x = (n - x) + (n + 1)</math> в <math>R</math>, значит, до следующего перекопирования не менее <math>n + 2</math> операций. За это время остаток <math>R_c'</math> (не более <math>n</math> элементов) успевает рассосаться: он уменьшается на 1 при каждой операции в обычном режиме. Это и есть содержание инварианта <math>|R_c'| \le |R| - |L|</math>.

=== Персистентная очередь на пяти стеках ===

Сделаем все стеки '''персистентными''' (неизменяемыми): операция возвращает новую версию, старые остаются доступны. Тогда шесть стеков превращаются в пять: пара <math>(R_c, R_c')</math> избыточна — достаточно одной версии <math>R'</math>, записанной в момент старта перекопирования; <code>pop</code> обращается к ней, и никакой синхронизации не нужно. Освобождать <math>R'</math> тоже не требуется: ячейки используются другими версиями очереди. Версия очереди — запись <math>Q = \langle L, L', R, R', S, \mathtt{recopy}, \mathtt{toCopy}, \mathtt{copied}\rangle</math>; <code>push</code> и <code>pop</code> возвращают новую версию вместе с результатом. Переносы по-прежнему ограничены тремя на операцию, поэтому каждая версия занимает <math>O(1)</math> новых ячеек и время <math>O(1)</math> в худшем случае. Псевдокод (упрощённо, по источнику):

<syntaxhighlight lang="text">
Версия Push(Q, x)
1 if not Q.recopy
2 Ln ← push(Q.L, x)
3 return Check-Recopy(⟨Ln, Q.L', Q.R, Q.R', Q.S, Q.recopy, Q.toCopy, Q.copied⟩)
4 else
5 Ln' ← push(Q.L', x)
6 return Check-Normal(⟨Q.L, Ln', Q.R, Q.R', Q.S, Q.recopy, Q.toCopy, Q.copied⟩)

Версия Pop(Q)
1 if not Q.recopy
2 ⟨Rn, x⟩ ← pop(Q.R)
3 return ⟨Check-Recopy(⟨Q.L, Q.L', Rn, Q.R', Q.S, …⟩), x⟩
4 else
5 ⟨Rn', x⟩ ← pop(Q.R')
6 if Q.toCopy > 0
7 cur ← Q.toCopy − 1
8 return ⟨Check-Normal(⟨Q.L, Q.L', Q.R, Rn', Q.S, …, cur, Q.copied⟩), x⟩
9 else
10 ⟨Rn, x⟩ ← pop(Q.R)
11 return ⟨Check-Normal(⟨Q.L, Q.L', Rn, Rn', Q.S, …, 0, Q.copied⟩), x⟩
</syntaxhighlight>

Функции <code>Check-Recopy</code>, <code>Check-Normal</code>, <code>Additional-Operations</code> повторяют версию на шести стеках, но вместо мутации создают новые версии стеков. Важное отличие: в пятистековом варианте <code>Check-Recopy</code> при входе в перекопирование фиксирует <math>R' \leftarrow R</math> — текущую версию выхода; без этого <code>pop</code> в режиме перекопирования читал бы устаревшую версию. См. рис. 7.

== Сравнение с альтернативами ==

{| class="wikitable"
|-
! Реализация !! Худший !! Амортизированный !! Память на версию !! Персистентность
|-
| Два стека || <math>\Theta(n)</math> || <math>O(1)</math> || неприменима (<math>\Theta(n)</math>) || нет
|-
| Шесть стеков (реальное время) || <math>O(1)</math> || <math>O(1)</math> || — (не персистентна) || нет
|-
| Пять стеков (персистентная) || <math>O(1)</math> || <math>O(1)</math> || <math>O(1)</math> новых ячеек || да (функциональная)
|-
| Кольцевой буфер || <math>O(1)</math> || <math>O(1)</math> || <math>\Theta(n)</math> на копию || нет
|-
| Связный список || <math>O(1)</math> || <math>O(1)</math> || <math>\Theta(1)</math>, но с риском разделения || частично (copy-on-write)
|}

[[Файл:q6-07-comparison.svg|frame|none|700px|Рис. 7. Три уровня компромисса: амортизированно <math>O(1)</math> → худший <math>O(1)</math> → худший <math>O(1)</math> с персистентностью.]]

'''Когда что выбирать.''' Нужна простая очередь общего назначения — кольцевой буфер или двусвязный список из [[Очередь]] (план). Нужна гарантия времени отклика — шесть стеков. Нужны прошлые версии (undo, функциональный язык) — персистентная очередь на пяти стеках. Если допустимы амортизированные оценки и не важна задержка, двух стеков достаточно.

== Где применяется ==

# '''Функциональные языки и библиотеки.''' В Haskell, OCaml, Standard ML очереди и деки — персистентные структуры; техника раскрытия «ленивого» переноса восходит к реальному времени и используется в <code>Data.Sequence</code>, очередях Okasaki и структурах с неизменяемыми версиями. Почему: в чисто функциональном коде структура не мутируется, а старые версии должны сохраняться [4][5].

# '''Системы реального времени.''' Планировщики, обработчики прерываний, буферы событий требуют ограниченного сверху времени отклика. Очередь с <math>O(1)</math> в худшем случае исключает редкие «долгие» вызовы, которые опасны в контурах управления и телеком-оборудовании [1][3].

# '''Персистентность и версионирование.''' Undo/redo в редакторах, транзакционные снимки, инкрементальные вычисления и системы контроля версий выигрывают от структур, где каждая версия стоит <math>O(1)</math> новых ячеек. Персистентная очередь — базовый кирпич таких систем [4].

# '''Логи событий и распределённые потоки.''' Очередь сообщений, к которой нужен доступ к прошлым состояниям (replay, аудит), строится на персистентных структурах; неизменяемость упрощает репликацию и откат [4].

# '''Обучение алгоритмам.''' Конструкция «очередь на шести стеках» — классическая задача курса дискретной математики и алгоритмов (Викиконспекты ИТМО): она тренирует инварианты, амортизационный анализ и персистентность [1][2].

# '''Олимпиадное программирование.''' Персистентная очередь и её «друзья» (персистентный стек, дек, приоритетная очередь) — инструменты задач на версии и откаты; разборы публикуются в блогах сообщества [2].

== Историческая справка ==

Операции над очередью в реальном времени первыми описали '''Роберт Худ и Роберт Мелвилл''' (R. Hood, R. Melville) в работе ''Real Time Queue Operations in Pure LISP'' (Cornell University, 1980; отчёт доступен через библиотечный депозитарий Корнеллского университета) [3]. Они показали, как реализовать очередь без долгих операций в чистом LISP, где данные неизменяемы, — именно персистентность и подталкивала к распределению переноса по операциям.

Идею подхватил '''Крис Окасаки''' (Chris Okasaki): в статье ''Simple and Efficient Purely Functional Queues and Deques'' (Journal of Functional Programming, 1995) и книге ''Purely Functional Data Structures'' (Cambridge University Press, 1998) он систематизировал персистентные очереди — «банкирскую», «физическую» и очередь реального времени [4]. Формальный '''амортизированный анализ''' (и метод потенциала) восходит к '''Роберту Тарьяну''' (R. E. Tarjan, «Amortized Computational Complexity», 1985) [5] и служит языком описания оценок в этой области.

Изложение конструкции «очередь на шести стеках» и её персистентного варианта на пяти стеках — учебная традиция кафедры компьютерных технологий ИТМО; конспект доступен на «Викиконспектах» (neerc.ifmo.ru) [1]. Популярные разборы — в блоге Codeforces [2] и на Хабрахабре [7]. Отметим, что конкретное число стеков (шесть против пяти) зависит от того, требуется ли явная копия выхода: persistence позволяет обойтись меньшим числом стеков [1].

== Типичные ошибки и подводные камни ==

* '''Путать амортизированное с худшим.''' Очередь на двух стеках — амортизированно <math>O(1)</math>, но худший случай <math>\Theta(n)</math>; только конструкция на шести стеках даёт <math>O(1)</math> в каждом вызове.
* '''Забыть подчищать <math>R_c'</math>.''' В обычном режиме остаток копии нужно уменьшать на 1 за операцию (инвариант <math>|R_c'| \le |R| - |L|</math>), иначе к следующему перекопированию не найдётся свободного стека.
* '''Неверный момент запуска.''' Перекопирование нужно начинать ровно при <math>|L| = |R| + 1</math>; позже — не хватит операций на перенос, раньше — нарушится инвариант и лишняя работа.
* '''Ошибка на единицу в <code>toCopy</code>.''' Это число ''корректных'' элементов в <math>S</math>; при <code>pop</code> во время перекопирования его нужно уменьшать, иначе можно прочитать уже извлечённый элемент.
* '''Забыть фазу 1 (<math>R \to S</math>).''' Без буфера <math>S</math> старый выход не опустеет, если операций <code>push</code> больше, чем <code>pop</code>, и не хватит стека для нового <math>R</math>; двойной переворот через <math>S</math> обязателен.
* '''Не сделать смену ролей.''' Без <math>\mathtt{swap}(L, L')</math> и <math>\mathtt{swap}(R_c, R_c')</math> новые результаты останутся в служебных стеках, а очередь будет читать старое.
* '''Попытка сделать двухстековую очередь персистентной «в лоб».''' Дорогая операция переноса порождает <math>\Theta(n)</math> новых ячеек на версию — нужна именно конструкция с дроблением.
* '''Мутируемые стеки в персистентном варианте.''' Персистентность требует неизменяемости; изменение «на месте» разрушит прошлые версии.
* '''Закольцованная рекурсия проверок.''' <code>Check-Recopy</code> вызывает <code>Check-Normal</code>, который может выставить <code>recopy</code> снова; рекурсии здесь нет — это разные шаги одной операции, но при переносе в код важно не зациклиться.
* '''Предположение, что <code>Empty</code> ложен всегда в перекопировании.''' Так и есть (в <math>R_c</math> или <math>R</math> остаются элементы), но если реализация не поддерживает инвариант <math>|L| = |R| + 1</math> в момент старта, <code>Empty</code> может соврать.

== Задачи для практики ==

# '''Два стека.''' Реализуйте очередь на двух стеках и определите худший случай. Ограничение: не более <math>O(1)</math> памяти на элемент. ''Подсказка:'' перенос происходит при опустошении выхода; худший вызов — <math>\Theta(n)</math>.

# '''Инвариант.''' Докажите, что в обычном режиме <math>R = \varnothing \iff Q = \varnothing</math>. ''Подсказка:'' используйте <math>|L| \le |R|</math> и представление <math>R \mathbin{+\!\!+} \mathrm{reverse}(L)</math>.

# '''Счёт действий.''' Покажите, что при старте перекопирования (<math>|L| = |R| + 1 = n + 1</math>) требуется ровно <math>3n + 3</math> действий и что их укладывает ровно <math>n + 1</math> операция по 3. ''Подсказка:'' сложите вклады фаз 1–4.

# '''<code>toCopy</code>.''' Объясните, почему некорректные элементы <math>S</math> скапливаются у дна, и почему условие <code>toCopy > 0</code> защищает от чтения мусора. ''Подсказка:'' элементы <math>S</math> переносятся по одному, а уменьшение <code>toCopy</code> соответствует уже отданным элементам.

# '''Трассировка.''' Вручную повторите семь <code>push</code> и семь <code>pop</code> из раздела «Трассировка примера» и сверьте состояния стеков. ''Подсказка:'' следите за флагами <code>recopy</code>, <code>copied</code>, <code>toCopy</code>.

# '''Реальное время vs персистентность.''' Объясните, почему шестистековый вариант годится для реального времени, а для персистентности достаточно пяти стеков. ''Подсказка:'' роль копии <math>R_c</math> берёт на себя версия <math>R'</math>.

# '''Пятистековая очередь.''' Реализуйте персистентную очередь на пяти неизменяемых стеках так, чтобы каждая версия занимала <math>O(1)</math> новых ячеек. ''Ограничение:'' стеки неизменяемы.

# '''Расширение до дека.''' Попробуйте добавить <code>pop_back</code>/<code>push_front</code> и обсудите, почему дек на стеках сложнее очереди. ''Подсказка:'' симметрия «лево/право» требует mirrored-структуры.

== Связанные темы ==

* [[Очередь]] (план) — базовая FIFO, кольцевой буфер, очередь на двух стеках.
* [[Стек]] (план) — строительный блок; стек как персистентная структура.
* [[Персистентный стек]] (план) — неизменяемый стек; основа персистентной очереди.
* [[Персистентная очередь]] (план) — персистентность очереди, ленивые очереди Окасаки.
* [[Асимптотическая сложность]] — амортизация, худший случай, худший и амортизированный.
* [[Персистентные структуры данных]] — неизменяемость и версии.
* [[Декартово дерево]] (план) — персистентный treap как ещё один пример персистентности.
* [[Очередь с приоритетом]] (план) — родственная структура; персистентный вариант.

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

# Викиконспекты ИТМО: Персистентная очередь (разделы «Реализация очереди на шести стеках», «Персистентная очередь на пяти стеках»). URL: https://neerc.ifmo.ru/wiki/index.php?title=Персистентная_очередь.
# Codeforces. Персистентная очередь и её друзья (блог). URL: https://codeforces.com/blog/entry/15685.
# Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980. URL: http://hdl.handle.net/1813/6273.
# Okasaki C. Simple and Efficient Purely Functional Queues and Deques // Journal of Functional Programming. — 1995. — Vol. 5, № 4; и Okasaki C. ''Purely Functional Data Structures''. — Cambridge University Press, 1998.
# Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2.
# Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. ''Introduction to Algorithms'' (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 10 (элементарные структуры: стек, очередь).
# Хабрахабр. Персистентная очередь (пост 241231). URL: https://habr.com/ru/post/241231/ ''(проверено 2026-11-03: статья о персистентной очереди, другой алгоритм — на деревьях)''.

[[Category:Алгоритмы и структуры данных]]

Персистентная очередь

2026-11-04T18:06:18Z

СВ: Новая страница: «== TL;DR == '''Персистентная очередь''' (persistent queue) — очередь, сохраняющая '''все свои версии''': к...»

== TL;DR ==

'''Персистентная очередь''' (persistent queue) — очередь, сохраняющая '''все свои версии''': каждая операция возвращает новую очередь, а прежние состояния остаются доступными. Простейший способ — копировать очередь целиком — стоит <math>\Theta(n)</math> на операцию и <math>\Theta(n^2)</math> суммарно, что неприемлемо. Очередь на двух '''неизменяемых стеках''' (<math>front</math> — голова, <math>back</math> — хвост) даёт <code>push</code> за <math>O(1)</math> и разделяет узлы версий, но <code>pop</code> при пустом <math>front</math> требует '''разворота''' <math>back</math> за <math>\Theta(n)</math>; хуже того, при '''ветвлении версий''' амортизация ломается — одну и ту же дорогую операцию можно повторить из разных версий. Поэтому персистентные очереди строят иначе: '''банкирская''' и '''физическая''' очереди (Окасаки) дают <math>O(1)</math> амортизированно с помощью '''ленивых потоков''' и кредита/потенциала, а очередь '''реального времени''' — <math>O(1)</math> '''в худшем''' случае (реализуется, например, на шести стеках; см. [[Очередь на шести стеках]]).

{| class="wikitable"
|-
! Свойство !! Значение
|-
| Класс || Очередь (FIFO) с полной персистентностью
|-
| Версии || Хранятся все; доступ к любой за <math>O(1)</math>
|-
| Цена версии || от <math>\Theta(n)</math> (копия или разворот) до <math>O(1)</math> (ленивые/реальное время)
|-
| <code>push</code> || <math>O(1)</math> (1 новый узел)
|-
| <code>pop</code> (two-stack, энергично) || <math>O(1)</math> или <math>\Theta(n)</math> при развороте
|-
| Амортизация || <math>O(1)</math> для банкирской/физической; '''не работает''' при ветвлении «в лоб»
|-
| Худший случай || <math>O(1)</math> только у очереди реального времени
|-
| Приёмы || ленивые потоки, планировщик, кредит (banker's), потенциал (physicist's)
|-
| Реализации || два стека; банкирская; физическая; реального времени (6 стеков)
|-
| Где встречается || функциональные языки, версионирование, undo, инкрементальные вычисления
|}

== Определения ==

'''Персистентная очередь''' — очередь (FIFO), операция над которой порождает '''новую версию''', не разрушая предыдущую. Подробнее об уровнях персистентности — в [[Персистентный стек]]: различают частичную (менять можно только последнюю версию), полную (любую) и функциональную (ячейки памяти неизменяемы) персистентность. Персистентная очередь обычно строится как '''функциональная''': узлы и стеки неизменяемы.

'''Версия очереди''' — конкретное состояние очереди (последовательность элементов). Операция — это функция, отображающая версию в новую версию.

'''Разделение (sharing)''' — переиспользование неизменяемых узлов несколькими версиями. Благодаря ему <math>n</math> операций <code>push</code> занимают <math>O(n)</math> памяти, а не <math>\Theta(n^2)</math>.

'''Представление на двух стеках.''' Очередь хранится парой неизменяемых стеков: <math>front</math> содержит голову очереди (верх — самый старый элемент), <math>back</math> — хвост (верх — самый новый). Логическая последовательность равна <math>front</math> (сверху вниз) <math>\mathbin{+\!\!+}</math> <math>\mathrm{reverse}(back)</math>.

'''Ленивый поток (lazy stream)''' — последовательность, хвост которой вычисляется не сразу, а по требованию. Невычисленный хвост хранится как '''thunk''' (отложенное вычисление). Форсирование thunk — вычисление отложенной части.

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

'''Банкирская очередь (banker's queue).''' Персистентная очередь с ленивым разворотом, где каждый элемент несёт '''кредит''', оплачивающий будущие шаги. Даёт <math>O(1)</math> амортизированно [3][4].

'''Физическая очередь (physicist's queue).''' Та же цель, но оплата через '''потенциал''' <math>\Phi = |back|</math> (метод потенциала Тарьяна) [3][5].

'''Очередь в реальном времени (real-time queue).''' Персистентная очередь с <math>O(1)</math> в '''худшем''' случае на операцию; планировщик форсирует постоянное число шагов за операцию [1][3].

'''Обозначения.''' <math>n</math> — число элементов/операций; <math>|X|</math> — размер структуры <math>X</math>; <math>\log</math> — двоичный.

== Мотивация и интуиция ==

Обычная очередь хранит одно состояние: <code>enqueue</code>/<code>dequeue</code> изменяют его на месте (см. [[Очередь]]). Если нужны прошлые состояния, приходится либо копировать очередь перед каждым изменением, либо вовсе отказаться от персистентности. Копирование обходится <math>\Theta(n)</math> на операцию и <math>\Theta(n^2)</math> на <math>n</math> версий — это слишком дорого. См. рис. 1.

[[Файл:pq-01-persistence.svg|thumb|700px|Рис. 1. Каждая операция создаёт новую версию; старые версии живут, и от любой можно ветвить.]]

Придумать персистентную очередь сложнее, чем персистентный стек. Стек — это одна цепочка, и <code>push</code> просто добавляет узел в начало (см. [[Персистентный стек]]). У очереди '''два конца''', и FIFO приходится восстанавливать разворотом. Первое естественное решение — два неизменяемых стека: <code>push</code> идёт в <math>back</math> (это дешёвый «стек», поэтому <math>O(1)</math>), <code>pop</code> берёт из <math>front</math>; когда <math>front</math> пуст, стек <math>back</math> разворачивается в <math>front</math>. Разворот — это <math>\Theta(|back|)</math>, и вся трудность персистентности в том, как с ним справиться.

Второе ключевое наблюдение — '''амортизация не переносится на персистентные структуры'''. В мутирующей очереди один разворот за <math>\Theta(n)</math> «оплачивается» <math>n</math> последующими дешёвыми <code>pop</code>: амортизированно <math>O(1)</math>. В персистентной структуре ту же дорогую операцию можно запустить из разных версий, и каждый раз она выполняется заново — амортизированная граница для отдельной цепочки операций не даёт гарантии. См. рис. 3. Именно поэтому для персистентных очередей указывают либо честную <math>O(1)</math> '''в худшем''' случае, либо используют '''ленивые''' вычисления, чтобы амортизация «принадлежала структуре», а не последовательности вызовов.

Ключевая идея в одном абзаце: '''разворот нужно сделать ленивым и оплачиваемым по частям'''. Если хвост очереди хранить как ленивый поток, обратный порядок получается бесплатно до момента обращения; а планировщик, форсирующий работу по одному шагу за операцию, устраняет «долгие» вызовы. Это и есть банкирская, физическая и очередь реального времени.

== Устройство ==

Персистентная очередь на двух стеках — это пара неизменяемых стеков и функция, возвращающая новую пару (см. рис. 2). Версии образуют дерево: каждое <code>push</code>/<code>pop</code> добавляет в него узел.

[[Файл:pq-02-two-stacks.svg|thumb|700px|Рис. 2. <code>push</code> идёт в <math>back</math>, <code>pop</code> берёт из <math>front</math>; при пустом <math>front</math> стек <math>back</math> разворачивается.]]

Основные компоненты и правила:

* '''<math>front</math>''' — головная часть в прямом порядке (верх — самый старый);
* '''<math>back</math>''' — хвостовая часть в обратном порядке (верх — самый новый);
* '''<code>push(x)</code>''' — новая версия с <math>back.push(x)</math>: <math>O(1)</math>, один новый узел;
* '''<code>pop()</code>''' — верх <math>front</math>; если <math>front</math> пуст, сначала <math>front \leftarrow \mathrm{reverse}(back)</math>, затем <math>back \leftarrow \varnothing</math>;
* '''<code>empty()</code>''' — <math>front</math> и <math>back</math> пусты.

Логическая инвариантность представления: очередь равна <math>front \mathbin{+\!\!+} \mathrm{reverse}(back)</math>. Пока <math>front</math> не пуст, <code>pop</code> дешёвый; дорогой шаг — исключительно разворот <math>back</math>.

'''Почему не годится «в лоб» (см. рис. 3).''' Общий для нескольких версий стек <math>back</math> нельзя развернуть один раз «для всех»: каждая версия, где <math>front</math> пуст, вынуждена строить свой разворот, то есть платить <math>\Theta(n)</math>. Значит, наивный энергичный вариант даёт худший случай <math>\Theta(n)</math> и не спасается амортизацией.

[[Файл:pq-03-amortize-breaks.svg|thumb|700px|Рис. 3. Общий <math>back</math> и две ветви: каждая ветвь платит за разворот заново, поэтому одна операция снова может стоить <math>\Theta(n)</math>.]]

'''Как исправляют.''' Два приёма (см. рис. 4):

* '''Лень (lazy).''' Хвост хранится как поток, разворот не вычисляется заранее. Обращение к нему форсирует thunk. Это превращает цену разворота в «отложенный долг», который можно оплачивать постепенно.
* '''Планировщик + кредит/потенциал.''' Банкирская очередь выдаёт каждому элементу кредит на будущие форсирования; физическая списывает работу с потенциала. Планировщик форсирует по шагу за операцию, и худшего вызова не остаётся.

[[Файл:pq-04-okasaki.svg|thumb|700px|Рис. 4. Ленивый поток хранит невычисленный хвост; планировщик форсирует постоянное число шагов, давая банкирскую, физическую и очередь реального времени.]]

== Операции и алгоритмы ==

Ниже — операции персистентной очереди на двух стеках (энергичный вариант; он корректен, но имеет худший случай <math>\Theta(n)</math>). Обозначения: <math>Q = (F, B)</math> — пара стеков; <code>push</code>/<code>pop</code> стеков возвращают новые стеки; <math>\mathrm{reverse}(S)</math> — разворот.

=== Операция: Push ===

'''Идея.''' Положить элемент в хвостовой стек <math>back</math> — это операция над стеком, то есть <math>O(1)</math> и один новый узел; головной стек не трогаем.

'''Пошаговое описание:'''

# Построить новую версию: <math>back' \leftarrow back.\mathrm{push}(x)</math>.
# Вернуть <math>(front, back')</math>.

'''Инвариант.''' Очередь версии равна <math>front \mathbin{+\!\!+} \mathrm{reverse}(back)</math>; добавление в конец не меняет голову.

<syntaxhighlight lang="text">
Операция Push(Q, x)
Вход: версия Q = (F, B); x — элемент
Выход: новая версия Q'
Инвариант: Q = F ++ reverse(B)
Сложность: O(1) времени, O(1) новых узлов

1 B' ← B.push(x)
2 return (F, B')
</syntaxhighlight>

'''Крайние случаи.''' <code>push</code> в пустую очередь даёт <math>(∅, \{x\})</math>: <code>pop</code> сразу потребует разворота.

=== Операция: Pop ===

'''Идея.''' Взять голову из <math>front</math>. Если <math>front</math> пуст, развернуть <math>back</math> в <math>front</math>; вернуть верхний элемент и новую версию с «отрезанной» головой.

'''Пошаговое описание:'''

# Если очередь пуста — ошибка <code>underflow</code>.
# Если <math>front = ∅</math>: <math>F \leftarrow \mathrm{reverse}(back)</math>, <math>B \leftarrow ∅</math>.
# <math>x \leftarrow front.\mathrm{top}()</math>.
# Вернуть <math>(x, (front.\mathrm{pop}(), back))</math>.

'''Инвариант.''' Возвращаемый <math>x</math> — самый старый элемент; новая версия содержит очередь без него.

<syntaxhighlight lang="text">
Операция Pop(Q)
Вход: версия Q = (F, B), Q ≠ (∅, ∅)
Выход: (x, Q') — головной элемент и новая версия
Инвариант: x — минимальный по времени поступления
Сложность: O(1), если F ≠ ∅; иначе Θ(|B|) — разворот

1 if F = ∅ and B = ∅
2 error "pop из пустой очереди"
3 if F = ∅
4 F ← Reverse(B) # самая дорогая операция
5 B ← ∅
6 x ← F.top()
7 return (x, (F.pop(), B))

Функция Reverse(S) # разворот стека за O(|S|)
1 R ← ∅
2 while S ≠ ∅
3 R ← R.push(S.top())
4 S ← S.pop()
5 return R
</syntaxhighlight>

'''Разбор.''' Для <math>Q = (∅, \{3,2,1\})</math> (верх <math>back</math> — 3) <code>pop</code> разворачивает <math>back</math> в <math>front = \{1,2,3\}</math>, возвращает 1 и даёт версию <math>(\{2,3\}, ∅)</math>. Следующие <code>pop</code> дешёвые, пока <math>front</math> не опустеет.

'''Сложность.''' <math>O(1)</math> при непустом <math>front</math>; <math>\Theta(|back|)</math> при развороте. Амортизированно по одной линии операций — <math>O(1)</math>, но при ветвлении это не гарантия (см. рис. 3).

'''Крайние случаи.''' <code>pop</code> пустой очереди — ошибка. Ветвление после разворота повторяет разворот в каждой ветви.

=== Техники: банкирская, физическая, реального времени ===

'''Ленивый разворот.''' Вместо немедленного <math>\mathrm{reverse}(back)</math> строят поток <code>reverse(back)</code>, хвост которого — thunk. Обращение к потоку форсирует его. Так как узлы разделяются, отложенная работа выполняется не более одного раза на версию.

'''Банкирская очередь.''' Каждому элементу при <code>push</code> выдаётся кредит; форсирование шага разворота списывает кредит. Инвариант «кредитов достаточно» гарантирует <math>O(1)</math> амортизированно, даже при передаче версий между вызовами [3][4].

'''Физическая очередь.''' Вместо явного кредита — потенциал <math>\Phi = |back|</math>; амортизированная стоимость операции <math>\hat{c} = c + \Delta\Phi</math> остаётся <math>O(1)</math> [3][5]. При <math>\Phi = |back|</math>: <code>push</code> даёт <math>\Delta\Phi = +1</math> (запас), <code>pop</code> из непустого <math>front</math> — <math>\Delta\Phi = 0</math>, разворот — <math>\Delta\Phi = -|back|</math>; поэтому амортизированная стоимость разворота равна 0 и оплачена предыдущими <code>push</code>.

'''Очередь реального времени.''' Планировщик форсирует постоянное число шагов за операцию (в шестистековой версии — до трёх переносов), поэтому отдельный вызов всегда <math>O(1)</math>. Конкретная реализация — на шести (или пяти персистентных) стеках, разобрана в [[Очередь на шести стеках]].

== Сводная таблица сложности ==

{| class="wikitable"
|-
! Операция !! Два стека (энергично) !! Ленивая (банкирская/физическая) !! Реального времени
|-
| <code>push</code> || <math>O(1)</math> || <math>O(1)</math> || <math>O(1)</math>
|-
| <code>pop</code> || <math>O(1)</math> / <math>\Theta(n)</math> разворот || <math>O(1)</math> амортизированно || <math>O(1)</math> в худшем
|-
| <code>empty</code> || <math>O(1)</math> || <math>O(1)</math> || <math>O(1)</math>
|-
| Доступ к версии || <math>O(1)</math> || <math>O(1)</math> || <math>O(1)</math>
|-
| Новых ячеек на <code>push</code> || <math>O(1)</math> || <math>O(1)</math> || <math>O(1)</math>
|-
| Новых ячеек на разворот || <math>\Theta(n)</math> || <math>\Theta(n)</math> на разворот, <math>O(1)</math> аморт. || <math>O(1)</math> на операцию
|-
| Персистентность || полная || полная || полная
|}

Оговорка: амортизированная граница <math>O(1)</math> для ленивых очередей действительна благодаря тому, что '''кредит/потенциал принадлежат структуре''', а не последовательности вызовов. Наивная энергичная очередь на двух стеках такой гарантии не даёт при ветвлении версий.

== Трассировка примера ==

Возьмём последовательность <code>push(1)</code>, <code>push(2)</code>, <code>push(3)</code>, затем два <code>pop</code>, затем ветвление от третьей версии через <code>push(9)</code>. Стеки записаны сверху вниз (верх … дно).

{| class="wikitable"
|-
! № !! Операция !! Версия <math>(F, B)</math> !! Логическая очередь !! Комментарий
|-
| v0 || старт || <math>(∅, ∅)</math> || <code>[]</code> || пусто
|-
| v1 || <code>push(1)</code> || <math>(∅, [1])</math> || <code>[1]</code> || в <math>back</math>
|-
| v2 || <code>push(2)</code> || <math>(∅, [2,1])</math> || <code>[1,2]</code> || в <math>back</math>
|-
| v3 || <code>push(3)</code> || <math>(∅, [3,2,1])</math> || <code>[1,2,3]</code> || в <math>back</math>
|-
| v4 || <code>pop()</code> → 1 || <math>([2,3], ∅)</math> || <code>[2,3]</code> || разворот <math>back</math> (Θ(n))
|-
| v5 || <code>pop()</code> → 2 || <math>([3], ∅)</math> || <code>[3]</code> || дешёвый
|-
| b || <code>v3.push(9)</code> || <math>(∅, [9,3,2,1])</math> || <code>[1,2,3,9]</code> || ветвь от v3
|-
| c || <code>v3.pop()</code> → 1 || <math>([2,3], ∅)</math> || <code>[2,3]</code> || своя версия разворота
|}

Разберём ветвление. Версия v3 не изменилась, хотя от неё построены и <math>b</math>, и <math>c</math>: узлы делятся, но разворот в <math>c</math> выполняется заново (в <math>b</math> он вообще не нужен). Это ровно тот случай, из-за которого энергичная реализация не имеет <math>O(1)</math> в худшем случае, — см. рис. 3. Трассировка сверена с реализацией из раздела «Служебное».

== Корректность и оценка сложности ==

=== Корректность FIFO ===

'''Инвариант представления.''' Логическая очередь версии <math>(F, B)</math> равна <math>F \mathbin{+\!\!+} \mathrm{reverse}(B)</math>.

'''База.''' Пустая очередь <math>(∅, ∅)</math> соответствует пустой последовательности.

'''Переход <code>push</code>.''' Новая версия <math>(F, B.\mathrm{push}(x))</math>: логически <math>F \mathbin{+\!\!+} \mathrm{reverse}(B.\mathrm{push}(x)) = F \mathbin{+\!\!+} \mathrm{reverse}(B) \mathbin{+\!\!+} [x]</math>, то есть <math>x</math> в конце. Инвариант сохранён.

'''Переход <code>pop</code>.''' Если <math>F \neq ∅</math>, верх <math>F</math> — самый старый элемент (инвариант), и новая версия <math>(F.\mathrm{pop}(), B)</math> убирает именно его. Если <math>F = ∅</math>, логическая очередь равна <math>\mathrm{reverse}(B)</math>; замена <math>F \leftarrow \mathrm{reverse}(B)</math>, <math>B \leftarrow ∅</math> сохраняет её, а верх нового <math>F</math> — самый старый элемент <math>B</math>, то есть голова очереди. Значит, <code>pop</code> возвращает корректный элемент.

'''Отсюда:''' <code>pop</code> всегда возвращает минимальный по времени поступления элемент, то есть очередь работает по FIFO, и все версии корректны.

=== Персистентность ===

'''Утверждение.''' Операции не изменяют уже существующие узлы.

''Доказательство.'' <code>push</code> создаёт новый узел со ссылкой на прежнюю вершину, <code>pop</code> возвращает существующий узел, а <math>\mathrm{reverse}</math> создаёт новые узлы, читая старые. Ни одно поле ранее созданного узла не присваивается. Значит, любая сохранённая ссылка на версию остаётся действительной — персистентность полная (можно продолжать любую версию).

=== Оценка памяти ===

<math>n</math> операций <code>push</code> создают ровно <math>n</math> узлов (по одному на <code>push</code>), которые делят версии (см. рис. 5). Развороты создают дополнительные узлы, но каждый — новый; при энергичном варианте один разворот даёт <math>\Theta(n)</math> узлов. Если требуется именно <math>O(1)</math> новых ячеек на операцию, разворот должен быть ленивым (амортизированно <math>O(1)</math>) или распределённым (худший случай <math>O(1)</math>).

[[Файл:pq-05-memory.svg|thumb|700px|Рис. 5. Версии делят общие узлы: <math>O(n)</math> против <math>\Theta(n^2)</math> при копировании.]]

=== Почему амортизация не переносится на персистентность ===

В мутирующей структуре каждая операция выполняется '''один раз''', поэтому суммарная стоимость делится на число операций. В персистентной структуре одну операцию можно выполнить '''из разных версий''' — например, первый <code>pop</code> после длинной серии <code>push</code> запускает разворот, и если от той же версии ветвятся <math>k</math> раз, разворот повторится <math>k</math> раз. Классический метод потенциала, привязанный к последовательности вызовов, теряет силу.

'''Как это лечат.''' Окасаки показал, что амортизация сохраняется, если «долг» хранится '''в самой структуре''': банкирская очередь несёт кредиты, физическая — потенциал <math>\Phi = |back|</math>. Тогда любые списания (debits) ограничены накопленным кредитом, и <math>O(1)</math> амортизированно держит даже при передаче версий [3][4]. Для <math>O(1)</math> '''в худшем''' случае применяют планировщик: одна операция — постоянное число шагов, что даёт очередь реального времени [1][3].

== Сравнение с альтернативами ==

{| class="wikitable"
|-
! Реализация !! Худший !! Амортизир. !! Новых ячеек !! Замечание
|-
| Копия всей очереди || <math>\Theta(n)</math> || <math>\Theta(n)</math> || <math>\Theta(n)</math> || просто, но <math>\Theta(n^2)</math> на историю
|-
| Два стека (энергично) || <math>\Theta(n)</math> || <math>O(1)</math> «в линии» || <math>O(1)</math> push, <math>\Theta(n)</math> разворот || амортизация не переносится
|-
| Банкирская (Okasaki) || до <math>O(n)</math> при форсировании || <math>O(1)</math> || <math>O(1)</math> аморт. || кредиты в структуре
|-
| Физическая (Okasaki) || до <math>O(n)</math> при форсировании || <math>O(1)</math> || <math>O(1)</math> аморт. || потенциал <math>\Phi</math>
|-
| Реального времени || <math>O(1)</math> || <math>O(1)</math> || <math>O(1)</math> || планировщик / 6 стеков
|}

Сводка по пяти реализациям — на рис. 6.

[[Файл:pq-06-comparison.svg|frame|none|700px|Рис. 6. От копирования (<math>\Theta(n)</math> на версию) до очереди реального времени (<math>O(1)</math>).]]

'''Вердикт.''' Нужны простые версии и допустимы амортизированные оценки — два стека или банкирская очередь. Нужна жёсткая гарантия времени отклика — очередь реального времени ([[Очередь на шести стеках]]). Копирование версий оправдано лишь на крошечных размерах.

== Где применяется ==

# '''Функциональные языки.''' В Haskell стандартные последовательности и библиотечные очереди персистентны; в OCaml и Standard ML есть как функциональные, так и мутабельные реализации. Банкирская и физическая очереди Окасаки — учебный канон и основа библиотечных реализаций. Почему: в чистом функциональном коде мутация запрещена, а старые версии нужно сохранять [3][4].

# '''Версионирование и системы контроля версий.''' История изменений — это дерево версий структуры; персистентная структура хранит её без копирования данных. Почему: ветвление версий и откаты выполняются за <math>O(1)</math> по указателям [4][6].

# '''Undo/redo и редакторы.''' Стек или очередь действий с историей строится из персистентных структур: каждое действие — новая версия, откат — переход по ссылке. Почему: <math>O(1)</math> новая память на действие и отсутствие блокировок.

# '''Инкрементальные вычисления и кэширование.''' Персистентные структуры позволяют сравнивать версии и переиспользовать общие части (например, при мемоизации путей). Почему: sharing экономит память и время [4].

# '''Параллельные вычисления.''' Неизменяемые версии безопасно разделяются потоками без синхронизации. Почему: нельзя испортить состояние, разделяемое несколькими потребителями [4].

== Историческая справка ==

Очереди в реальном времени впервые описали '''Худ и Мелвилл''' (R. Hood, R. Melville) в работе ''Real Time Queue Operations in Pure LISP'' (Cornell University, 1980), где данные неизменяемы, а перенос работы распределён по операциям [2]. Идею ленивых очередей развил '''Ф. У. Бартон''' (F. W. Burton) в статье ''An Efficient Functional Implementation of FIFO Queues'' (Information Processing Letters, 1982) [8]. Наиболее известные конструкции — '''банкирская''' и '''физическая''' очереди (с ленивыми потоками и кредитом/потенциалом) и очередь '''реального времени''' — принадлежат '''Крису Окасаки''' (статья ''Simple and Efficient Purely Functional Queues and Deques'', Journal of Functional Programming, 1995; книга ''Purely Functional Data Structures'', Cambridge University Press, 1998) [3].

Общую теорию персистентности (методы path copying, fat nodes, node copying) заложили '''Дрисколл, Сарнак, Слитор и Тарьян''' (''Making Data Structures Persistent'', STOC 1986; JCSS 1989) [6]. Формальный амортизированный анализ, включая вошедший в обиход метод потенциала, развил '''Роберт Тарьян''' («Amortized Computational Complexity», 1985) [5]. Функциональные структуры-предшественники — списки LISP (Джон Маккарти, 1960).

== Типичные ошибки и подводные камни ==

* '''Переносить амортизацию на персистентную структуру.''' Оценка <math>O(1)</math> «в линии» не означает <math>O(1)</math> при ветвлении: одну дорогую операцию можно повторить из разных версий.
* '''Считать персистентную очередь «просто очередью на двух стеках».''' Без лени/планировщика худший случай остаётся <math>\Theta(n)</math>.
* '''Форсировать весь ленивый поток в одной операции.''' Это возвращает <math>\Theta(n)</math> в отдельный вызов; нужно форсировать маленькими порциями.
* '''Забыть про инвариант кредита/потенциала.''' Без него ленивая очередь теряет амортизированную оценку (кредиты могут «закончиться»).
* '''Мутировать разделяемые узлы.''' Любая запись в общий узел испортит все версии, которые на него ссылаются.
* '''Освобождать узлы «оптимизацией».''' Узел можно удалять, только когда на него не ссылается ни одна живая версия (нужна сборка мусора).
* '''Путать дебет и кредит.''' В банкирской очереди <code>pop</code> может ничего не форсировать, но при определённых условиях обязан заплатить лишний кредит; пропуск этого нарушает инвариант.
* '''Ожидать <math>O(1)</math> от разворота eager-варианта.''' Создание <math>\Theta(n)</math> узлов на разворот — самая дорогая операция; она и есть источник проблем.
* '''Хранить версии без нужды.''' Если ветвление не требуется, персистентность — лишние накладные расходы; иногда достаточно мутирующей очереди.

== Задачи для практики ==

# '''Две версии.''' Реализуйте персистентную очередь на двух неизменяемых стеках с <code>push</code> и <code>pop</code>. Ограничение: узлы неизменяемы. ''Подсказка:'' <code>pop</code> при пустом <math>front</math> разворачивает <math>back</math>.

# '''Ветвление.''' Постройте очередь <code>[1,2,3]</code>, сделайте ветвь <code>push(4)</code> и ветвь <code>pop</code>. Сколько версий получилось и каковы их содержимые? ''Подсказка:'' обе ветви происходят от одной версии.

# '''Амортизация.''' Докажите, что в одной линии операций энергичный вариант амортизированно <math>O(1)</math>, и приведите пример ветвления, где отдельный <code>pop</code> стоит <math>\Theta(n)</math>. ''Подсказка:'' <math>n</math> дешёвых <code>pop</code> оплачивают один разворот; при ветвлении разворот повторяется.

# '''Память.''' Покажите, что <math>n</math> операций <code>push</code> без разворотов дают ровно <math>n</math> узлов. Оцените дополнительные узлы при одном развороте. ''Подсказка:'' разворот создаёт <math>\Theta(n)</math> узлов.

# '''Ленивый разворот.''' Опишите, как хранить <code>reverse(back)</code> в виде thunk и когда его форсировать. ''Подсказка:'' форсируйте по требованию головы.

# '''Кредит.''' Для банкирской очереди придумайте правило выдачи кредитов при <code>push</code> и списания при форсировании так, чтобы инвариант «кредитов хватает» сохранялся. ''Подсказка:'' один кредит на элемент оплачивает один шаг разворота.

# '''Потенциал.''' Для физической очереди вычислите <math>\Delta\Phi</math> при <code>push</code> и <code>pop</code> и покажите <math>\hat{c} = O(1)</math>. ''Подсказка:'' <math>\Phi = |back|</math>.

# '''Реальное время.''' Объясните, почему очереди с <math>O(1)</math> в худшем случае строят на нескольких стеках, а не на ленивых потоках напрямую. ''Подсказка:'' форсирование должно быть по шагу на операцию (см. [[Очередь на шести стеках]]).

== Связанные темы ==

* [[Очередь]] — обычная FIFO-очередь; кольцевой буфер.
* [[Персистентный стек]] — базовый неизменяемый стек.
* [[Очередь на шести стеках]] — очередь реального времени и персистентный вариант на пяти стеках.
* [[Асимптотическая сложность]] — амортизация, метод потенциала, худший случай.
* [[Персистентные структуры данных]] — общая теория персистентности.
* [[Декартово дерево]] — персистентный treap.

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

# Викиконспекты ИТМО: Персистентная очередь. URL: https://neerc.ifmo.ru/wiki/index.php?title=Персистентная_очередь.
# Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980. URL: http://hdl.handle.net/1813/6273.
# Okasaki C. Simple and Efficient Purely Functional Queues and Deques // Journal of Functional Programming. — 1995. — Vol. 5, № 4.
# Okasaki C. ''Purely Functional Data Structures''. — Cambridge University Press, 1998 (банкирская и физическая очереди, амортизация в функциональных структурах).
# Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2.
# Driscoll J. R., Sarnak N., Sleator D. D., Tarjan R. E. Making Data Structures Persistent // STOC 1986; JCSS. — 1989. — Vol. 38.
# Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. ''Introduction to Algorithms'' (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 10 (очередь, стек), гл. 17 (амортизированный анализ).
# Burton F. W. An Efficient Functional Implementation of FIFO Queues // Information Processing Letters. — 1982. — Vol. 14, № 5. — P. 205–206.

[[Category:Алгоритмы и структуры данных]]

Файл:Pq-06-comparison.svg

2026-11-04T18:05:25Z

СВ:

Файл:Pq-05-memory.svg

2026-11-04T18:05:18Z

СВ:

Файл:Pq-04-okasaki.svg

2026-11-04T18:05:11Z

СВ:

Файл:Pq-03-amortize-breaks.svg

2026-11-04T18:05:04Z

СВ:

Файл:Pq-02-two-stacks.svg

2026-11-04T18:04:55Z

СВ:

Файл:Pq-01-persistence.svg

2026-11-04T18:04:46Z

СВ:

Базис и размерность линеала

2026-11-04T11:35:20Z

СВ: Новая страница: «{{Определение |definition= Упорядоченная совокупность линейно независимых векторов ${\bf e}_1, {\bf...»

{{Определение
|definition=
Упорядоченная совокупность линейно независимых векторов ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n$ линеала $L$ называется '''базисом линеала''',
если для каждого вектора $x \in L$ найдутся вещественные числа $\gamma_i$, $i = \overline {1,n}$, что
<math>
x = \sum\limits_{i = 1}^n {\gamma _i {\bf e}_i}.
</math>
}}
Последнее равенство называют разложением вектора $x$ по базису ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n$.

На основании данного определения можно утверждать, что в векторном пространстве $V^1$ произвольный ненулевой вектор может быть взят в качестве базисного, в пространстве $V^2$ упорядоченная пара неколлинеарных векторов образует базис, а в $V^3$ упорядоченная тройка некомпланарных векторов образует базис.

В пространстве $R^n$ векторы ${\bf u}_1 = (1,0,..., 0)$, ${\bf u}_2 = (0,1,..., 0)$, ..., ${\bf u}_n = (0,0,..., 1)$ образуют базис, поскольку они линейно независимы и любой вектор $x = (\gamma_1, \gamma_2, ..., \gamma_n ) \in R^n$ представим в виде ${\bf x} = \gamma_1 {\bf u}_1 + \gamma_2 {\bf u}_2 + ... + \gamma_n {\bf u}_n$.

Отметим, что в определении базиса порядок элементов существенен, так как, переставляя элементы базиса, мы получаем снова базис, но уже другой.
{{Определение
|definition=
Числа $\gamma_i$, $i = \overline {1,n} $, фигурирующие в разложении элемента $x$ линеала $L$ по заданному базису ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n$ называются '''координатами''' данного вектора относительно рассматриваемого базиса.
}}
{{Теорема
|statement=Координаты всякого элемента линеала $L$ относительно заданного базиса определяются однозначно.
|proof=Допустим, что ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $ {{---}} базис линеала $L$. Пусть для некоторого вектора $x$ наряду с разложением $x = \sum\limits_{i = 1}^n {\gamma _i {\bf e}_i}$ существует еще и другое разложение $x = \sum\limits_{i = 1}^n {\mu _i {\bf e}_i}$. Но тогда справедливо равенство ${\bf 0} = \sum\limits_{i = 1}^n {(\gamma _i - \mu _i ) {\bf e}_i}$. Базисные элементы ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n$ линейно независимы, поэтому для всех $i = \overline {1,n} $ имеем $\gamma_i = \mu_i$.
}}

[[Файл:p03-05-01-basis-coordinates.svg|thumb|800px|alt=Слева разложение x = 2e1 + e2 по базису e1, e2; справа другой базис f1, f2 и координаты (1; 1)|Рис. 1. Слева <math>x = 2e_1 + e_2</math>, координаты <math>(2; 1)</math>. Справа тот же приём с другим базисом <math>f_1 = e_1</math>, <math>f_2 = e_1 + e_2</math>: разложение <math>x = f_1 + f_2</math> даёт другие координаты <math>(1; 1)</math>.]]

{{Теорема
|statement=При сложении элементов линеала $L$ их координаты складываются, а при умножении вектора на вещественное число все его координаты умножаются на данное число.
|proof=Пусть элементы ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $ образуют базис в $L$, $x$ и ${\bf y}$ {{---}} произвольные элементы из $L$, $\lambda $ {{---}} произвольное вещественное число, ${\bf s} = x + y$, ${\bf p} = \lambda x$.
Ясно, что $x = \sum\limits_{i = 1}^n {\gamma _i {\bf e}_i}$, $y = \sum\limits_{i = 1}^n {\mu _i e_i}$, ${\bf s} = \sum\limits_{i = 1}^n {\sigma _i e_i}$, ${\bf p} = \sum\limits_{i = 1}^n {\delta _i e_i}$. Используя аксиомы 1-8 линеала $L$, получаем
<math>
{\rm {\bf s} } = x + y = \sum\limits_{i = 1}^n {\gamma _i } e_i + \sum\limits_{i = 1}^n {\mu _i } e_i = \sum\limits_{i = 1}^n {(\gamma _i + \mu _i )} e_i,
</math>

<math>
{\rm {\bf p} } = \lambda x = \lambda \left( {\sum\limits_{i = 1}^n {\gamma _i } e_i } \right) = \sum\limits_{i = 1}^n {\lambda \gamma _i } e_i .
</math>

В силу единственности разложения по базису имеем $\sigma _i = \gamma _i + \mu _i $, $\delta _i = \lambda \gamma _i $, $i = \overline {1,n} $.
}}

{{Теорема
|statement=Если каждый из $(n + 1)$ элементов $y_0, y_1,..., y_n$ линеала $L$ представим в виде линейной комбинации n линейно независимых элементов $x_1, x_2, ..., x_n$ того же линеала, т. е.
$y_i = \sum\limits_{i = 1}^n {\lambda _{ij} x_i }$, $j = \overline {0,n}$, то элементы $y_0, y_1, ..., y_n $ линейно зависимы.
}}
{{Следствие
|statement=Любые $(n + 1)$ векторов линейного пространства $R^n$ являются линейно зависимыми.
|proof=Возьмем произвольно векторы $y_k = (\alpha _{k1}, \alpha _{k2}, ..., \alpha _{kn} )$, $k = \overline {0,n} $.
Поскольку ${\rm {\bf u} }_1 = (1,0,..., 0)$, ${\rm {\bf u} }_2 = (0,1,..., 0)$, ..., ${\rm {\bf u} }_n = (0,0,..., 1)$ образуют базис в пространстве $R^n$, то для любого $k = \overline {0,n} $ имеем $y_k = \alpha _{k1} {\rm {\bf u} }_1 + \alpha _{k2} {\rm {\bf u} }_2 + \cdots + \alpha _{kn} {\rm {\bf u} }_n $. Следовательно, в силу теоремы 3.5.3 произвольные $(n + 1)$ векторов из линеала $R^n$ линейно зависимы.
}}
{{Следствие
|statement=Любые два базиса линеала $L$ содержат одно и то же число векторов.
|proof=Пусть ${\bf e}_1, {\bf e}_2 ,..., {\bf e}_n $ базис линеала $L$, а <math>{\rm {\bf {e}'} }_1, {\rm {\bf {e}'} }_2, ..., {\rm {\bf {e}'} }_{n + 1}</math> другой базис этого же линеала. Так как <math>{\rm {\bf {e}'} }_i = \sum\limits_{j = 1}^n {\alpha _j {\bf e}_j }, i = \overline {1,n + 1} </math>, причем ${\bf e}_1, {\bf e}_2,..., {\bf e}_n $ линейно независимы. В силу теоремы <math>{\rm {\bf {e}'} }_1, {\rm {\bf {e}'} }_2, ..., {\rm {\bf {e}'} }_{n + 1}</math> {{---}} линейно зависимы. Полученное противоречие и доказывает следствие.'''
}}
{{Определение
|definition=
Линеал $L$ называют $n$-мерным, если в нем существует базис, состоящий из $n$ векторов.
}}
Число $n$ называют '''размерностью''' линеала $L$ и обозначают символом $\dim (L) = n$.
Таким образом, размерность пространства {{---}} это наибольшее число его линейно независимых элементов.
Если линеал $L$ является $n-$мерным и необходимо подчеркнуть его размерность, то обычно используют обозначение $L^n$. Ясно, что $\dim (V^1) = 1$, $\dim (V^2) = 2$, $\dim (V^3) = 3.$
Линеал $\Theta $, содержащий единственный нулевой элемент, является нуль-мерным.
{{Определение
|definition=
Линеал $L$ называется бесконечномерным, если для любого натурального числа $N$ в нем найдется линейно независимая система, состоящая из $N$ элементов.
}}
Примером бесконечномерного линеала является линейное пространство непрерывных на заданном отрезке функций.
{{Теорема
|statement=Для того чтобы линеал $L был n$-мерным, необходимо и достаточно, чтобы в нем существовала линейно независимая система, состоящая из $n$ элементов, а всякая система, содержащая более $n$ векторов, была бы линейно зависимой.
|proof='''Необходимость.''' Если линеал является $n$-мерным, то в нем существует базис ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $, состоящий из $n$ элементов. Произвольный вектор $x_j \in L$, $j = \overline {0,n} $ представим в виде линейной комбинации векторов ${\rm {\bf e} }_1, {\bf e}_2, ..., {\bf e}_n $, поэтому любая совокупность более чем $n$ элементов является линейно зависимой.

'''Достаточность.''' Пусть ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $ линейно независимые элементы. Возьмем произвольный вектор $x \in L$. По условию векторы ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $,$x$ линейно зависимы, т. е. существует нетривиальная линейная комбинация $\alpha _1 {\bf e}_1 + \alpha _2 {\bf e}_2 + ... + \alpha _n {\bf e}_n + \alpha x = {\bf 0}$, причем $\alpha \ne 0$. Но тогда x может быть разложен по ${\bf e}_1, {\bf e}_2, ..., {\bf e}_n $, т. е. эти элементы {{---}} базис линеала $L$.
В $n$-мерном линеале $L$ всякий базис состоит из n упорядоченных линейно независимых элементов, при этом любой вектор линеала $L^n$ единственным образом представим в виде линейной комбинации базисных элементов.
}}
Это утверждение не вытекает из аксиом 1 {{---}} 8 линейного пространства. Поэтому следует сформулировать новую аксиому.

'''9. (аксиома размерности).''' Линейное пространство $L$ конечномерно и его размерность равна $n$.
При выполнении этой аксиомы из аксиом 1-8 очевидно вытекает сформулированное утверждение.

[[Файл:p03-05-02-dimension-ladder.svg|frame|none|800px|alt=Шесть линеалов с размерностями 0, 1, 2, 3, n и ∞ и пиктограммами числа независимых направлений|Рис. 2. Размерность — наибольшее число независимых направлений: <math>\dim \Theta = 0</math>, <math>\dim V^1 = 1</math>, <math>\dim V^2 = 2</math>, <math>\dim V^3 = 3</math>, <math>\dim R^n = n</math>; пространство непрерывных функций бесконечномерно.]]

----

Конспект: [[Алгебра и геометрия]]

Файл:P03-05-02-dimension-ladder.svg

2026-11-04T11:34:54Z

СВ:

Файл:P03-05-01-basis-coordinates.svg

2026-11-04T11:33:30Z

СВ:

Персистентный стек

2026-11-04T11:22:04Z

СВ: Новая страница: «== TL;DR == '''Персистентный стек''' (persistent stack) — стек, хранящий '''все свои предыдущие версии''':...»

Файл:Pstack-06-apply.svg

2026-11-04T11:21:36Z

СВ:

Файл:Pstack-05-sharing.svg

2026-11-04T11:21:29Z

СВ:

Файл:Pstack-04-pop.svg

2026-11-04T11:21:21Z

СВ:

Файл:Pstack-03-array.svg

2026-11-04T11:21:13Z

СВ:

Файл:Pstack-02-versions.svg

2026-11-04T11:21:06Z

СВ:

Файл:Pstack-01-idea.svg

2026-11-04T11:20:57Z

СВ:

Очередь на шести стеках

2026-11-04T10:14:09Z

СВ: Новая страница: «== TL;DR == Обычная очередь на '''двух стеках''' работает амортизированно за <math>O(1)</math>, но отде...»

Файл:Q6-07-comparison.svg

2026-11-04T10:12:35Z

СВ:

Файл:Q6-06-timeline.svg

2026-11-04T10:12:25Z

СВ:

Файл:Q6-05-recopy-steps.svg

2026-11-04T10:12:15Z

СВ:

Файл:Q6-04-invariants.svg

2026-11-04T10:12:07Z

СВ:

Файл:Q6-03-modes.svg

2026-11-04T10:11:58Z

СВ:

Файл:Q6-02-roles.svg

2026-11-04T10:11:48Z

СВ:

Файл:Q6-01-two-stacks.svg

2026-11-04T10:11:28Z

СВ:

Персистентные структуры данных

2026-11-04T10:09:59Z

СВ: /* TL;DR */

== TL;DR ==

'''Персистентная структура данных''' (persistent data structure) сохраняет доступ ко '''всем своим предыдущим версиям''': каждая операция создаёт новую версию, не разрушая старые. Наивный способ — копировать структуру целиком — стоит <math>\Theta(n)</math> на операцию и <math>\Theta(n^2)</math> на историю. Поэтому применяют '''разделение данных (sharing)''': три классических метода — '''path copying''' (копируем только путь до изменённого места, остальные поддеревья общие), '''fat nodes''' (каждое поле хранит историю значений по версиям) и '''node copying''' (узел копируется при заполнении, с ограничением входящей степени). Различают уровни персистентности: '''частичная''', '''полная''', '''функциональная''' и '''слитная''' (confluent, с объединением версий). Персистентность — основа функциональных языков, систем контроля версий, многоверсионных СУБД (MVCC), undo/redo и безопасного разделения данных между потоками. Конкретные реализации разобраны в [[Персистентный стек|персистентный стек]], [[Персистентная очередь|персистентная очередь]] и [[Очередь на шести стеках|очередь на шести стеках]].

{| class="wikitable"
|-
! Свойство
! Значение
|-
| Класс
| Приём/семья структур, сохраняющих версии
|-
| Что общего
| операция не разрушает прошлые состояния; новая версия = ссылка
|-
| Уровни
| частичная, полная, функциональная, слитная
|-
| Методы
| path copying, fat nodes, node copying, функциональная пересборка
|-
| Цена обновления
| от <math>\Theta(n)</math> (копия) до <math>O(\log n)</math> (path copying); fat nodes — <math>O(1)</math> на обновление; node copying — <math>O(1)</math> аморт. при ограниченной входящей степени
|-
| Цена доступа к версии
| <math>O(1)</math> по ссылке; материализация — <math>O(k)</math>
|-
| Память
| <math>O(n)</math>–<math>O(n\log n)</math> при разделении против <math>\Theta(n^2)</math> при копировании
|-
| Ключевое требование
| неизменяемость (или учёт версий) разделяемых узлов
|-
| Родственные
| ретроактивные и кинетические структуры, MVCC
|-
| Где встречается
| функциональные языки, Git, СУБД, геометрия, undo, параллельность
|}

== Определения ==

'''Персистентная структура данных''' — структура, поддерживающая доступ ко всем версиям, порождённым последовательностью операций. Противоположность — '''эфемерная''' (ephemeral) структура, хранящая лишь текущее состояние.

'''Версия (version)''' — состояние структуры после некоторого набора операций. Доступ к версии обычно осуществляется по ссылке на её «корень» (или по индексу) за <math>O(1)</math>.

'''Уровни персистентности''' (см. рис. 1):

* '''частичная (partial)''' — изменять можно только самую новую версию, читать — любую;
* '''полная (full)''' — изменять и читать можно любую версию (версии образуют дерево);
* '''функциональная (functional)''' — каждая ячейка инициализируется один раз и не меняется; новая версия строится только из старых;
* '''слитная (confluent)''' — любую версию можно изменять и, кроме того, '''объединять''' две версии (merge); версии образуют ациклический граф (DAG).

[[Файл:psd-01-levels.svg|thumb|700px|Рис. 1. Уровни персистентности различаются тем, что разрешено менять и читать; функциональный — сильнейший по неизменяемости, слитный — по операциям.]]

'''Path copying (копирование пути).''' Обновление копирует только узлы вдоль пути от корня до изменяемого места; поддеревья, не лежащие на пути, '''разделяются''' между версиями. Применяется к деревьям.

'''Fat node (толстый узел).''' Каждое поле узла хранит не одно значение, а '''список пар (версия, значение)''', накапливаемый по мере изменения. Чтение поля на версии <math>v</math> — поиск последнего присваивания с номером <math>\le v</math>.

'''Node copying (копирование узла).''' Узел копируется, когда его «слоты» для новых указателей заняты; копия и оригинал хранят списки версий указателей. Требует '''ограниченной входящей степени''' (bounded in-degree): у каждого узла не более <math>O(1)</math> входящих ссылок.

'''Функциональная пересборка.''' Новая версия строится целиком из старых данных (например, <math>b</math>-дерево пересобирается снизу вверх); проста, но стоит <math>O(n)</math>.

'''Обозначения.''' <math>n</math> — размер структуры; <math>m</math> — число модификаций поля; <math>V</math> — число версий; <math>\log</math> — двоичный. «Ссылка на версию» — указатель на корень (или индекс).

== Мотивация и интуиция ==

Обычные структуры '''эфемерны''': массив, список или дерево хранят одно состояние, а операции его перезаписывают. Если нужна история, приходится либо заранее копировать структуру, либо реконструировать прошлое по журналу. Копирование даёт <math>\Theta(n)</math> на операцию и, при <math>n</math> версиях, <math>\Theta(n^2)</math> суммарной памяти (см. рис. 2). Для больших структур это неприемлемо.

[[Файл:psd-02-naive.svg|thumb|700px|Рис. 2. Полная копия на каждое изменение: <math>1+2+\dots+n = \Theta(n^2)</math>; разделение данных снижает память до <math>O(n\log n)</math> для сбалансированного BST (для списка/стека — до <math>O(n)</math>).]]

Ключевая идея — '''не копировать то, что не изменилось'''. Меняя одно поле, мы затрагиваем лишь небольшую часть структуры; всё остальное можно '''переиспользовать''' — на неизменяемые части могут ссылаться и старая, и новая версии. Отсюда два больших подхода:

* '''Функциональный''' (immutable): узлы не меняются вовсе; изменение = создание новых узлов со ссылками на старые части. Пример — path copying.
* '''In-place''': структура дополняется информацией о версиях, но сами «старые» данные остаются на месте. Примеры — fat nodes и node copying.

Зачем это нужно: функциональные языки (нет мутации), версионирование и undo, многоверсионные СУБД (читатель видит снапшот, писатель ему не мешает), вычислительная геометрия (история изменений), безопасное разделение данных между потоками. Подробности по конкретным структурам — в [[Персистентный стек|персистентный стек]], [[Персистентная очередь|персистентная очередь]], [[Декартово дерево|декартово-дерево]].

== Устройство ==

Персистентная структура — это набор '''неизменяемых узлов''' (или узлов с версионной историей), связанных ссылками, и '''набор версий''', каждая из которых задаётся ссылкой на свой корень. Обычно версия включает номер (или время), монотонно возрастающий.

=== Path copying ===

При обновлении (например, <code>insert</code> в дерево поиска) копируются узлы '''вдоль пути''' корень → лист, а не соседние поддеревья. Новая версия получает новый корень; старая продолжает ссылаться на нетронутые поддеревья. См. рис. 3: при вставке 55 копируются только узлы 50 и 70, а поддерево 30 остаётся общим.

[[Файл:psd-03-pathcopying.svg|thumb|700px|Рис. 3. Копируется только путь вставки; поддеревья вне пути разделяются между версиями.]]

Цена: для сбалансированного дерева путь имеет длину <math>O(\log n)</math>, значит, <code>insert</code> создаёт <math>O(\log n)</math> новых узлов и столько же времени. Память на одну операцию — <math>O(\log n)</math>; суммарно за <math>n</math> вставок — <math>O(n\log n)</math>. Доступ к любой версии — <math>O(1)</math> по её корню. Требование: узлы '''неизменяемы''' (иначе испортится старая версия).

=== Fat nodes и node copying ===

Если структура не дерево (или хочется экономить на копировании пути), применяют in-place методы (см. рис. 4). В '''fat node''' каждое поле хранит список значений по версиям; изменение — это добавление пары в конец списка. В '''node copying''' узел имеет фиксированное число слотов; когда они заполнены, создаётся копия, а список версий указывает, какая копия «актуальна» для версии.

[[Файл:psd-04-fatnodes.svg|thumb|700px|Рис. 4. Fat nodes хранят историю в полях; node copying копирует узел при заполнении слотов (нужна ограниченная входящая степень).]]

=== Версии как дерево или граф ===

Для полной и слитной персистентности версии удобно представлять '''деревом''' (или DAG), где ребро — операция над версией (см. рис. 5). Это делает явной структуру истории и объясняет, почему амортизированные оценки «не переносятся»: одну и ту же дорогую операцию можно выполнить из разных версий.

[[Файл:psd-05-versiontree.svg|thumb|700px|Рис. 5. Частичная персистентность — линия, полная — дерево, слитная — DAG с операциями merge.]]

== Операции и алгоритмы ==

Общих «операций» у класса нет — они определяются конкретной структурой. Но есть универсальные процедуры: обновление через path copying, чтение/запись fat-поля, доступ к версии. Все примеры ниже даны для '''персистентного бинарного дерева поиска (BST)''' как канонической структуры.

=== Операция: Insert через path copying ===

'''Идея.''' Спускаясь к месту вставки, каждый узел пути заменяем его копией с обновлённой ссылкой на изменённого ребёнка; у листа создаём новый узел. Поддеревья вне пути переиспользуются.

'''Пошаговое описание:'''

# Если дерево пусто — вернуть версию из одного нового узла.
# Спуститься по ключу: влево при <math>k < \text{key}</math>, вправо при <math>k > \text{key}</math>.
# На обратном пути создать копию каждого узла пути, подставив обновлённого ребёнка.
# Если ключ уже есть — вернуть узел без копирования (структура не меняется).

'''Инвариант.''' Каждый узел любой версии неизменяем; версия определяется ссылкой на корень; все поддеревья, не лежащие на пути, общие с предыдущей версией.

<syntaxhighlight lang="text">Операция Insert(v, k)
Вход: версия v (корень дерева); k — ключ
Выход: новая версия v' (корень), содержащая k
Инвариант: v и v' — корректные BST; изменены только узлы пути
Сложность: O(h) времени и новых узлов (h — высота; O(log n) для сбалансированного)

1 if v = NIL
2 return новый узел ⟨k, NIL, NIL⟩
3 if k = v.key
4 return v # без изменений
5 if k < v.key
6 l' ← Insert(v.left, k)
7 if l' = v.left
8 return v # изменений не было
9 return новый узел ⟨v.key, l', v.right⟩
10 else
11 r' ← Insert(v.right, k)
12 if r' = v.right
13 return v
14 return новый узел ⟨v.key, v.left, r'⟩</syntaxhighlight>
'''Разбор.''' Дерево <code>{50, 30, 70}</code>; <code>Insert(55)</code> копирует 50 и 70, создаёт узел 55; поддерево 30 остаётся общим (рис. 3). Другая ветвь от той же версии (<code>Insert(25)</code>) не конфликтует: версии независимы.

'''Сложность.''' <math>O(h)</math>; для сбалансированного дерева <math>O(\log n)</math>.

'''Крайние случаи.''' Совпадающий ключ не создаёт копий; пустое дерево — один новый узел.

=== Операция: Fat-Node Set и Get ===

'''Идея.''' Поле хранит список <code>(версия, значение)</code>; <code>Set</code> добавляет пару, <code>Get</code> ищет последнее присваивание с номером <math>\le</math> запрошенного.

<syntaxhighlight lang="text">Операция Fat-Set(node, field, version, value)
Вход: узел; поле; номер версии; значение
Сложность: O(1)

1 list[node][field].append((version, value))

Операция Fat-Get(node, field, version)
Вход: узел; поле; номер версии
Выход: значение поля в этой версии
Сложность: O(log m) — двоичный поиск по истории длины m

1 h ← list[node][field]
2 return Value-At(h, version) # последняя пара с version' ≤ version</syntaxhighlight>
'''Разбор.''' Поле <code>key</code> менялось в версиях 1 и 4: <code>[(1,5), (4,8)]</code>. <code>Fat-Get(·, 3)</code> вернёт 5, <code>Fat-Get(·, 4)</code> и позже — 8.

'''Крайние случаи.''' Запрос версии раньше первого присваивания — ошибка (значения ещё не было).

=== Замечание: доступ к версии ===

'''Идея.''' Версия — это ссылка на корень; доступ <math>O(1)</math>. Материализация (выписывание всех элементов) — <math>O(k)</math> для версии из <math>k</math> элементов. Обновление любой версии даёт новую ветвь.

== Сводная таблица сложности ==

{| class="wikitable"
|-
! Метод
! Обновление
! Доступ к корню
! Доступ к значению
! Память на операцию
! Условия
|-
| Полная копия
| <math>\Theta(n)</math>
| <math>O(1)</math>
| <math>O(1)</math> по индексу
| <math>\Theta(n)</math>
| —
|-
| Path copying
| <math>O(\log n)</math>
| <math>O(1)</math>
| <math>O(\log n)</math>
| <math>O(\log n)</math>
| сбалансированное дерево, узлы неизменяемы
|-
| Fat nodes
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(\log m)</math>
| <math>O(1)</math>
| история в полях
|-
| Node copying
| <math>O(1)</math> аморт.
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(1)</math> аморт.
| ограниченная входящая степень
|-
| Функциональная пересборка
| <math>O(n)</math>
| <math>O(1)</math>
| <math>O(1)</math> по индексу
| <math>O(n)</math>
| полная перестройка
|}

Оговорки: доступ к корню версии — <math>O(1)</math> для всех методов; <math>O(\log m)</math> у fat nodes — это чтение поля, а не доступ к версии. Память указана на операцию; суммарно за <math>V</math> версий полная копия даёт <math>\Theta(Vn)</math>, path copying — <math>O(V\log n)</math> для сбалансированного дерева. Точные классы зависят от модели (pointer machine) и структуры; <math>O(\log n)</math> в path copying достигается за счёт балансировки. См. рис. 6.

== Трассировка примера ==

Проследим серию вставок в персистентное BST и число '''новых''' узлов на каждую операцию (прогон реализации из раздела «Служебное»).

{| class="wikitable"
|-
! Операция
! Версия
! Новых узлов
! Общие поддеревья
|-
| старт
| v0
| 0
| —
|-
| <code>insert(50)</code>
| v1
| 1
| —
|-
| <code>insert(30)</code>
| v2
| 2
| —
|-
| <code>insert(70)</code>
| v3
| 2
| 30
|-
| <code>insert(20)</code>
| v4
| 3
| 70
|-
| <code>insert(40)</code>
| v5
| 3
| 70, 20
|-
| <code>insert(60)</code>
| v6
| 3
| 30, 20, 40
|-
| <code>insert(80)</code>
| v7
| 3
| 30, 60
|-
| <code>insert(55)</code>
| v8
| 4
| 30, 20, 40, 80
|}

Вставка <code>55</code> в дерево из семи узлов создаёт '''четыре''' новых узла: путь <code>50 → 70 → 60 → 55</code> (копируются 50, 70, 60 и создаётся лист 55), тогда как полная копия дала бы семь. Все поддеревья вне пути (в частности, содержащие 20, 30, 40 и 80) разделяются между v7 и v8: это и есть sharing.

Проверка fat-узла: поле менялось в версиях 1, 4 и 7. Тогда <code>Fat-Get(·, v)</code> возвращает значение версии 1 при <math>v \in [1,3]</math>, версии 4 при <math>v \in [4,6]</math> и версии 7 при <math>v \ge 7</math> — поиск по истории даёт корректный «срез по времени».

== Корректность и оценка сложности ==

=== Инвариант персистентности ===

'''Инвариант.''' Любая версия <math>v</math> остаётся корректной навсегда: её узлы и все достижимые из них узлы не изменяются после создания.

'''Для функциональных структур (path copying).''' Операция создаёт только новые узлы; поля старых узлов не присваиваются. Значит, множество узлов, достижимых из <math>v</math>, и их поля постоянны — инвариант выполняется по определению.

'''Для fat nodes.''' Узлы «на месте» меняются, но каждое изменение фиксируется с номером версии; чтение на версии <math>v</math> выбирает последнее присваивание с номером <math>\le v</math>. Если все запросы версии <math>v</math> используют один и тот же номер <math>v</math>, старое «содержимое» восстанавливается однозначно — инвариант сохраняется на уровне запроса.

=== Корректность path copying ===

'''Утверждение.''' <code>Insert(v, k)</code> возвращает корректное BST, содержащее тот же набор ключей, что и <math>v</math>, плюс <math>k</math> (если его не было).

''Доказательство (по индукции по высоте).'' База: пустое дерево → узел-лист с ключом <math>k</math>, корректно. Шаг: при <math>k < v.\text{key}</math> рекурсивно вставляем в левое поддерево; по индукции получаем корректное BST <math>l'</math> с прежними ключами плюс <math>k</math>. Новый узел <math>\langle v.\text{key}, l', v.\text{right}
\rangle</math> сохраняет порядок (все ключи <math>l'</math> меньше <math>v.\text{key}</math>, все ключи <math>v.\text{right}</math> больше). Аналогично для правого поддерева. Ключ <math>k</math> не создаёт копий, если уже есть. <math>\square</math>

=== Оценка сложности и памяти ===

* '''Path copying.''' Время и число новых узлов — длина пути <math>O(h)</math>. Для сбалансированного дерева <math>h = O(\log n)</math>; для вырожденного — <math>O(n)</math>. Суммарно за <math>n</math> вставок — <math>O(n\log n)</math> узлов.
* '''Fat nodes.''' Обновление <math>O(1)</math> (добавление в список), доступ <math>O(\log m)</math> (двоичный поиск по истории длины <math>m</math>), память <math>O(1)</math> на изменение.
* '''Node copying.''' При ограниченной входящей степени — <math>O(1)</math> амортизированно на обновление и <math>O(1)</math> доступ; без ограничения метод теряет оценку.

=== Почему нельзя слепо копировать амортизацию ===

Оценки вида «амортизированно <math>O(1)</math>» опираются на '''последовательность операций'''. В персистентной структуре одну и ту же операцию можно выполнить из '''разных версий''', поэтому делить работу на «число операций» нельзя: дорогой шаг «переигрывается» через ветвление. Именно поэтому, например, энергичная очередь на двух стеках ([[Персистентная очередь|персистентная очередь]]) не даёт худшего <math>O(1)</math> без дополнительных приёмов (ленивые потоки и кредит/потенциал). Более того, для функциональных структур с ленью амортизацию удаётся сохранить, только если «долг» хранится '''внутри структуры''' (кредит у банкирской очереди, потенциал у физической) [3][4].

== Сравнение с альтернативами ==

{| class="wikitable"
|-
! Метод
! Обновление
! Доступ к значению
! Память на операцию
! Когда выбирать
|-
| Полная копия
| <math>\Theta(n)</math>
| <math>O(1)</math>
| <math>\Theta(n)</math>
| крошечные структуры, простота
|-
| Path copying
| <math>O(\log n)</math>
| <math>O(\log n)</math>
| <math>O(\log n)</math>
| сбалансированные деревья; функциональный стиль
|-
| Fat nodes
| <math>O(1)</math>
| <math>O(\log m)</math>
| <math>O(1)</math>
| важна память, дорогой доступ приемлем
|-
| Node copying
| <math>O(1)</math> аморт.
| <math>O(1)</math>
| <math>O(1)</math> аморт.
| ограниченная входящая степень
|-
| Функциональная пересборка
| <math>O(n)</math>
| <math>O(1)</math>
| <math>O(n)</math>
| пакетные обновления, простота кода
|}

[[Файл:psd-06-comparison.svg|thumb|700px|Рис. 6. Ориентировочные оценки методов; точные классы зависят от модели и структуры.]]

'''Вердикт.''' Для деревьев почти всегда берут path copying: он прост и даёт <math>O(\log n)</math>. Когда память критична и структура произвольная, смотрят на fat nodes/node copying (с оговоркой про входящую степень). Если обновления пакетные — допустима пересборка. Для гарантии <math>O(1)</math> в худшем случае нужны специальные конструкции ([[Очередь на шести стеках|очередь на шести стеках]] ).

== Где применяется ==

# '''Функциональные языки.''' В Haskell, OCaml, Standard ML списки, деревья и очереди неизменяемы; любая операция возвращает новое значение, а старые продолжают существовать. Почему: язык не допускает мутации, и персистентность — не надстройка, а базовый способ работы [3].
# '''Системы контроля версий.''' Git хранит коммиты как '''DAG''' неизменяемых объектов (blob, tree, commit): новая версия ссылается на старые. Ветвление и слияние коммитов — операции над DAG, но это не confluent merge структур. Почему: неизменяемость даёт целостность и дешёвое ветвление [6].
# '''СУБД и многоверсионность (MVCC).''' Читателю выдаётся '''снапшот''', соответствующий версии данных на момент старта транзакции, а писатель не блокирует его. Индексы могут использовать versioned pages или copy-on-write; конкретный механизм зависит от СУБД. Почему: согласованное чтение без блокировок [4][7].
# '''Вычислительная геометрия.''' Для точек, отрезков и планарных подразбиений методы персистентности позволяют отвечать на запросы «на момент времени <math>t</math>»; классическая работа Дрисколла и др. посвящена именно таким применениям [1].
# '''Undo/redo и редакторы.''' История действий — дерево версий документа; откат — переход по ссылке, а не восстановление из журнала. Почему: <math>O(1)</math> для списка/стека и <math>O(\log n)</math> для дерева на шаг истории.
# '''Параллельные вычисления.''' Неизменяемые данные безопасно разделяются между потоками без блокировок: гонки и порча общего состояния невозможны. Почему: нет записи в общие узлы.

См. рис. 7: общий мотив применений.

[[Файл:psd-07-apply.svg|thumb|700px|Рис. 7. Общий мотив: заменить мутацию созданием версии.]]

== Историческая справка ==

Методы персистентности систематически изложили '''Джеймс Дрисколл, Нил Сарнак, Дэниел Слитор и Роберт Тарьян''' в работе ''Making Data Structures Persistent'' (STOC 1986; журнальная версия — Journal of Computer and System Sciences, 1989). Они ввели fat nodes и node copying и показали, что структуры с ограниченной входящей степенью можно сделать полностью персистентными за <math>O(1)</math> амортизированного времени и памяти на операцию [1]. Метод '''path copying''' для функциональных («аппликативных») структур описал '''Юджин Майерс''' (E. W. Myers) в работе ''Efficient Applicative Data Types'' (POPL 1984) ⚠️ требует проверки точных выходных данных [2].

Понятие '''функциональной персистентности''' и обширную коллекцию персистентных структур систематизировал '''Крис Окасаки''' в книге ''Purely Functional Data Structures'' (Cambridge University Press, 1998); он же показал, как сохранять амортизированные оценки в ленивых структурах (кредит/потенциал) [3]. Формальный амортизированный анализ, включая метод потенциала, развил '''Роберт Тарьян''' («Amortized Computational Complexity», 1985) [5]. Предшественником функциональных структур считаются списки LISP (Джон Маккарти, 1960).

Термин «персистентная структура данных» закрепился после работы [1]; обзоры и уточнения (ретроактивность, кинетические структуры) даны, например, в ''Handbook of Data Structures and Applications'' (глава H. Kaplan о персистентности) ⚠️ требует проверки деталей [8].

== Типичные ошибки и подводные камни ==

* '''Копировать всё «на всякий случай».''' Новички копируют структуру целиком, получая <math>\Theta(n)</math> на операцию; выигрыш персистентности — именно в разделении.
* '''Мутировать разделяемые узлы.''' Любая запись в общий узел портит все версии, которые на него ссылаются; функциональный подход требует неизменяемости.
* '''Забыть про ограничение входящей степени.''' Node copying корректен и быстр только при <math>O(1)</math> входящих ссылок на узел; иначе число копий растёт.
* '''Ожидать <math>O(1)</math> доступа от fat nodes.''' Доступ — поиск по истории, обычно <math>O(\log m)</math>; путать дешёвое обновление с дешёвым чтением нельзя.
* '''Переносить амортизацию на персистентность без оговорок.''' Дорогая операция «переигрывается» через ветвление; нужен кредит/потенциал внутри структуры.
* '''Не освобождать недостижимые версии.''' Память растёт неограниченно; для удаления нужна сборка мусора (или явное «забывание» старых версий).
* '''Путать персистентность с транзакциями.''' Персистентность — про версии, а не про атомарность и изоляцию; это разные уровни абстракции.
* '''Сливать версии без правил (confluent).''' Merge должен быть определён и согласован с операциями структуры; коммутативность не обязательна — конкатенация списков не коммутативна.
* '''Считать path copying бесплатным для любой структуры.''' Он опирается на дерево и короткий путь; для графа с большим числом обратных ссылок он деградирует.
* '''Забывать про вырождение.''' В несбалансированном дереве path copying стоит <math>O(n)</math>; балансировка критична для оценки <math>O(\log n)</math>.

== Задачи для практики ==

# '''Path copying.''' Реализуйте персистентное BST с <code>insert</code> через копирование пути. Ограничение: старые версии неизменяемы. ''Подсказка:'' возвращайте новый корень; не меняйте поля старых узлов.
# '''Счёт узлов.''' Для вставки в сбалансированное дерево докажите, что создаётся <math>O(\log n)</math> узлов. ''Подсказка:'' копируется ровно путь.
# '''Fat nodes.''' Реализуйте поле с историей <code>(version, value)</code> и чтение на версии <math>v</math> двоичным поиском. Оцените время <code>Set</code>/<code>Get</code>. ''Подсказка:'' <code>upper_bound</code> по номеру версии.
# '''Ветвление.''' От версии <math>v</math> примените две разные вставки и покажите, что обе новые версии корректны и не влияют друг на друга. ''Подсказка:'' подумайте про дерево версий.
# '''Память.''' Сравните суммарную память <math>n</math> обновлений при (а) полной копии и (б) path copying. Приведите асимптотики и численный пример при <math>n = 10^4</math>. ''Подсказка:'' <math>\Theta(n^2)</math> против <math>O(n\log n)</math>.
# '''Node copying.''' Объясните, почему ограничение входящей степени необходимо, и приведите структуру, где оно нарушается. ''Подсказка:'' узел с <math>n</math> входящими ссылками.
# '''Амортизация.''' Приведите пример, где амортизированная граница ломается при ветвлении, и объясните, как кредит/потенциал это исправляет. ''Подсказка:'' см. [[Персистентная очередь]].
# '''Confluent.''' Предложите правило merge для персистентного множества ключей (объединение без дубликатов) и оцените время. ''Подсказка:'' слияние двух деревьев поиска.

== Связанные темы ==

* [[Персистентный стек]] — простейшая персистентная структура (список и массив запросов).
* [[Персистентная очередь]] — персистентность очереди, ленивые очереди Окасаки.
* [[Очередь на шести стеках]] — <math>O(1)</math> в худшем случае; персистентная очередь на пяти стеках.
* [[Декартово дерево]] — персистентный treap (split/merge, path copying).
* [[Двоичное дерево поиска]] — база для path copying.
* [[B+-дерево]] — индекс СУБД; обновление копированием пути.
* [[Асимптотическая сложность]] — амортизация, метод потенциала, худший случай.

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

# Driscoll J. R., Sarnak N., Sleator D. D., Tarjan R. E. Making Data Structures Persistent // STOC 1986; Journal of Computer and System Sciences. — 1989. — Vol. 38 (fat nodes, node copying, ограниченная входящая степень).
# Myers E. W. Efficient Applicative Data Types // POPL. — 1984 (path copying для аппликативных структур) ⚠️ требует проверки точных выходных данных.
# Okasaki C. ''Purely Functional Data Structures''. — Cambridge University Press, 1998.
# Silberschatz A., Korth H. F., Sudarshan S. ''Database System Concepts''. — McGraw-Hill, 7th ed., 2019 (многоверсионность, индексы).
# Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2.
# Chacon S., Straub B. ''Pro Git''. — Apress, 2nd ed., 2014 (объекты и DAG версий).
# Wikipedia: Persistent data structure. URL: <nowiki>https://en.wikipedia.org/wiki/Persistent_data_structure</nowiki>.
# Kaplan H. Persistent Data Structures // ''Handbook of Data Structures and Applications''. — Chapman & Hall/CRC, 2004.