| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Сравнение чисто жадного и ортогонального жадного алгоритмов К. С. Вишневецкийab a Московский государственный университет им. М. В. Ломоносова b Московский центр фундаментальной и прикладной математики
Англоязычная версия:
Mathematical Notes, 2024, Volume 115, Issue 1, Pages DOI: https://doi.org/10.1134/S0001434624010048 
Реферативные базы данных:
  1. ВведениеПусть $H$ – действительное гильбертово пространство со скалярным произведением $\langle \cdot, \cdot \rangle$ и нормой $\|\cdot\|$, $D$ – словарь, т.е. подмножество единичной сферы $S(H)$, линейные комбинации элементов которого плотны в $H$ [1; гл. 2, § 1]. Также нам понадобится дополнительное условие на словарь:
$$
\begin{equation}
\forall\, x \in H \quad \exists\, g(x) \in D\colon \sup_{p \in D} |\langle x, p \rangle|= |\langle x, g(x) \rangle|.
\end{equation}
\tag{1}
$$
Для всякого вектора $x \in H$ определена последовательность наименьших $m$-членных уклонений относительно словаря $D$ [1; гл. 1, § 1]:
$$
\begin{equation*}
\sigma_m(x, D)=\sigma_m(x):=\inf \biggl\{\biggl\|x-\sum_{j=1}^m \lambda_j h_j\biggr\|\colon h_j \in D, \lambda_j \in \mathbb{R}\biggr\}.
\end{equation*}
\notag
$$
Если словарь $D$ удовлетворяет условию (1), то корректно определены жадные алгоритмы относительно словаря $D$ [1; гл. 2, § 1], выдающие по каждому элементу $x \in H$ последовательности жадных остатков. Чисто жадный алгоритм:
$$
\begin{equation*}
x_0:=x, \qquad x_{n+1}:=x_n-\langle x_n, g(x_n) \rangle g(x_n)=x_n-P_{\operatorname{span}\{g(x_n)\}}(x_n), \quad n=0, 1, 2, \dots,
\end{equation*}
\notag
$$
где $P_L(x)$ – ортогональная проекция вектора $x$ на подпространство $L \subset H$. Ортогональный жадный алгоритм:
$$
\begin{equation*}
x_0^{\mathrm o}:=x, \qquad x_{n+1}^{\mathrm o}:=x-P_{\operatorname{span}\{g(x_0^{\mathrm o}), g(x_1^{\mathrm o}), \dots, g(x_n^{\mathrm o})\}}(x), \quad n=0, 1, 2, \dots\,.
\end{equation*}
\notag
$$
Жадный алгоритм со свободной релаксацией:
$$
\begin{equation*}
x_0^r:=x, \qquad x_{n+1}^r:=x-P_{\operatorname{span}\{x_0^r-x_n^r, g(x_n^r)\}}(x), \quad n=0, 1, 2, \dots\,.
\end{equation*}
\notag
$$
Словарь $D$ можно считать симметричным: при замене $D$ на $D \cup (-D)$ так определенные жадные алгоритмы не изменятся. Известно, что все эти алгоритмы сходятся, т.е. $x_n \to 0$, $x_n^{\mathrm o} \to 0$ и $x_n^r \to 0$ при $n \to \infty$ [1; гл. 2, § 2], [2; теорема 3.1]. Отметим, что указанные алгоритмы могут реализовываться по-разному, в силу неоднозначности выбора элементов $g(x_n)$, $g(x_n^{\mathrm o})$ и $g(x_n^r)$. В дальнейшем под последовательностью $x_n$, $x_n^{\mathrm o}$ или $x_n^r$ подразумевается произвольная реализация соответствующего алгоритма. Будем говорить, что два жадных алгоритма работают одинаково до $n$-го шага, если для любого начального вектора $x$ из равенств $g(x_k^1)=g(x_k^2)$ при $0 \leqslant k \leqslant n- 1$ следуют равенства $x_k^1=x_k^2$ при $1 \leqslant k \leqslant n$. Будем говорить, что два жадных алгоритма работают одинаково, если для любого натурального $n$ они работают одинаково до $n$-го шага. Все три указанных выше жадных алгоритма работают одинаково до 1-го шага, более того, на первом шаге они дают наилучшее 1-членное приближение, т.е. для любого $x \in H$ справедливы равенства При $n \geqslant 2$ нормы $n$-х остатков во всех указанных алгоритмах уже вообще говоря больше или равны $\sigma_n(x)$. Также из определения ортогонального жадного алгоритма и жадного алгоритма со свободной релаксацией видно, что они работают одинаково до 2-го шага. Данная работа является продолжением работы автора [3], в которой описывались словари $D$ с условием $\|x_n\|=\sigma_n(x)$ при всех $x \in H$ и натуральных $n$, где $x_n$ – произвольная последовательность чисто жадных остатков вектора $x$ относительно словаря $D$. Цель настоящей работы – найти условия на словарь $D$, необходимые или достаточные для одинаковой работы чисто жадного и ортогонального жадного алгоритмов. Более того, показывается, что при выполнении найденных достаточных условий все три жадных алгоритма работают одинаково и реализуют наилучшие $m$-членные приближения, т.е. справедливы равенства $\|x_n\|=\|x_n^{\mathrm o}\|= \|x_n^r\|=\sigma_n(x)$ при всех $x \in H$ и натуральных $n$. Хорошо известно, что эти равенства выполнены в случае, когда $D$ состоит из элементов произвольного ортонормированного базиса в $H$. 2. Двумерный случайВ случае двумерного евклидова пространства $H=\mathbb{R}^2$ нетрудно полностью описать словари с указанным свойством. Пусть $a, b \in S(\mathbb{R}^2)$ и $a \neq -b$. Обозначим через $\widehat{(a,b)}$ меньшую открытую дугу окружности $S(\mathbb{R}^2)$ с концами в точках $a$ и $b$. Для вектора $a \in \mathbb{R}^2$ обозначим за $R(a)$ вектор, ортогональный $a$ и определенный с точностью до знака. Предложение 1. Пусть $D \subset S(\mathbb{R}^2)$ – замкнутое симметричное множество, содержащее не менее 4 точек, $S(\mathbb{R}^2) \setminus D=\bigcup_{k=1}^N \widehat{(a_k,b_k)}$, где $N \leqslant \infty$. Тогда следующие условия эквивалентны: Доказательство. Так как пространство двумерное, для всех $x \in \mathbb{R}^2$ справедливы равенства
Импликация 1) $\Rightarrow$ 2) очевидна. 2) $\Leftrightarrow$ 3), так как ортогональный жадный алгоритм и жадный алгоритм со свободной релаксацией работают одинаково до 2-го шага. 2) $\Rightarrow$ 4). Возьмем произвольное $k$ и элемент $x_0=2a_k/3+b_k/3$. Элемент $g(x_0)=a_k$ выбирается однозначно, и $x_1=x_1^{\mathrm o}=x_0-\langle x_0, a_k \rangle a_k$. Так как $x_2^{\mathrm o}=0$, то $x_2=0$, следовательно, Поскольку $\langle x_1, a_k \rangle=0$, имеем $R(a_k)=\pm x_1/ \|x_1\| \in D$ в силу симметричности словаря. Для $b_k$ рассуждения аналогичны.4) $\Rightarrow$ 1). Если $x_0 / \|x_0\| \in D$, то а значит, $\|x_n\|=\|x_n^{\mathrm o}\|=\|x_n^r\|=\sigma_n(x)=0$ для всякого $n \geqslant 1$.Пусть $x_0 / \|x_0\| \notin D$, т.е. $x_0 / \|x_0\| \in \widehat{(a_k,b_k)}$ для некоторого $k$. Без ограничения общности можно считать, что $g(x_0)=a_k$ и $x_1=x_0-\langle x_0, a_k \rangle$. Все три жадных алгоритма работают одинаково до 1-го шага, и выполнено равенство (2). Поскольку $\langle x_1, a_k \rangle=0$, то $x_1 / \|x_1\|=\pm R(a_k) \in D$. Тогда
$$
\begin{equation*}
\|x_2\|=\|x_2^{\mathrm o}\|= \|x_2^r\|=\sigma_2(x)=0,
\end{equation*}
\notag
$$
а значит, $\|x_n\|=\|x_n^{\mathrm o}\|=\|x_n^r\|=\sigma_n(x)=0$ для всякого $n \geqslant 2$.
Предложение 1 доказано. 3. Необходимое условие для дискретных словарейВ случае $\operatorname{dim}H \geqslant 3$ задача полного описания словарей, для которых чистый жадный и ортогональный жадный алгоритмы работают одинаково, представляется довольно трудной. Ниже в следствии 1 мы получим такое описание для дискретных словарей. Параметром когерентности [1; гл. 2, § 6] словаря $D$ называется величина
$$
\begin{equation*}
M(D):=\sup\bigl\{|\langle g, h \rangle|\colon g \neq \pm h,\, g, h \in D\bigr\}.
\end{equation*}
\notag
$$
Теорема 1. Пусть $D \subset S(H)$ – симметричный словарь, удовлетворяющий условию (1), $M(D) < 1$ и $\operatorname{dim}H \geqslant 3$. Если чисто жадный и ортогональный жадный алгоритмы работают одинаково до 2-го шага, то пространство $H$ представляется в виде $H=\bigoplus^{\perp}_{\alpha \in A}H_{\alpha}$ такой прямой суммы попарно ортогональных подпространств ($A$ – некоторое подмножество индексов), что $D \subset \bigcup_{\alpha \in A} H_{\alpha}$, $\operatorname{dim}H_{\alpha} \in \{1, 2\}$ и для всех $\alpha$ выполнено условие Замечание 1. В силу одинаковой работы ортогонального жадного алгоритма и жадного алгоритма со свободной релаксацией до 2-го шага, в условии теоремы ортогональный жадный алгоритм можно заменить на жадный алгоритм со свободной релаксацией. Лемма 1. Пусть выполнены условия теоремы 1. Тогда для любого начального вектора $x_0 \in H$ при любом выборе $g(x_0)$ и $g(x_1)$ справедливо равенство Доказательство. Пусть выполнены равенства $g(x_0)=g(x_0^{\mathrm o})$ и $g(x_1)=g(x_1^{\mathrm o})$. Так как чисто жадный и ортогональный жадный алгоритмы работают одинаково до 2-го шага, то $x_2=x_2^{\mathrm o}$. Тогда
$$
\begin{equation*}
\begin{aligned} \, & - \langle x_1, g(x_1) \rangle \langle g(x_1), g(x_0) \rangle=\langle x_1, g(x_0) \rangle- \langle x_1, g(x_1) \rangle \langle g(x_1), g(x_0) \rangle \\ &\qquad =\bigl\langle x_1-\langle x_1, g(x_1) \rangle g(x_1), g(x_0) \bigr\rangle=\langle x_2, g(x_0) \rangle=\langle x_2^{\mathrm o}, g(x_0) \rangle=0. \end{aligned}
\end{equation*}
\notag
$$
Следовательно, $\langle g(x_0), g(x_1) \rangle=0$, так как $\langle x_1, g(x_1) \rangle \neq 0$.
Лемма доказана. Лемма 2. Пусть выполнены условия теоремы 1. Тогда для любого элемента $d \in D$, начального вектора $x_0 \in H$ с условием $\langle x_0 , d \rangle=0$ равенство $\langle g(x_0), d \rangle=0$ выполнено при любом выборе $g(x_0)$. Доказательство. Рассмотрим начальный вектор $y=d+\varepsilon x_0$, где $\varepsilon > 0$ таково, что $g(y)=d$. Такое $\varepsilon$ существует в силу условия $M(D) < 1$. Тогда $y_1=\varepsilon x_0$ и в качестве $g(y_1)$ можно взять $g(x_0)$. Применяя лемму 1 к начальному вектору $y$, получаем $\langle g(x_0), d \rangle=0$.
Лемма доказана. На множестве $H \setminus \{0\}$ введем отношение эквивалентности: $d \sim h$, если $\operatorname{span}\{d\}=\operatorname{span}\{h\}$. Множество всех классов эквивалентности обозначим $P(H)$, класс эквивалентности элемента $d$ обозначим $[d]$, также будем отождествлять $[d]$ и $\operatorname{span}\{d\}$. Для произвольного подмножества $K \subset H \setminus \{0\}$ положим $[K]:=\{[d]\colon d \in K\}$. Лемма 3. Пусть выполнены условия теоремы 1. Тогда для любых различных $[d], [h] \in [D]$ элементы $[d_1], [h_1]$, определенные условиями принадлежат $[D]$. В дальнейшем будем использовать обозначения Доказательство. Возьмем начальный вектор $x$ с условием $\langle x, d \rangle\,{=}\,\langle x, h \rangle\,{=}\,0$. Обозначим $e_1=g(x)$ (любой из элементов удовлетворяющих этому условию); тогда по лемме 2 имеем $\langle e_1, d \rangle=\langle e_1, h \rangle=0$.
В общем случае, пусть есть система $\{d, h, e_{\alpha}\colon \alpha \in A\} \subset D$ такая, что все элементы системы попарно ортогональны, кроме пары элементов $d$ и $h$. Если данная система не является базисом в $H$, то найдется вектор $y$, ортогональный всем элементам данной системы, тогда по лемме 2 данную систему можно расширить, добавив к ней элемент $g(y)$. В итоге получим базис $\{d, h, e_{\alpha}\colon \alpha \in A\} \subset D$, в котором все элементы попарно ортогональны, кроме пары элементов $d$ и $h$. Теперь применим лемму 2 к начальному вектору $d_1$ и элементам $\{d, e_{\alpha}\colon \alpha \in A\} \subset D$, получим что $d_1$ и $g(d_1)$ ортогональны всем элементам $\{d, e_{\alpha}\colon \alpha \in A\} \subset D$; следовательно, $[d_1]=[g(d_1)] \in [D]$. Аналогично с вектором $h_1$. Лемма доказана. Лемма 4. Пусть $X_3 \subset H$ – трехмерное подпространство, $D \subset S(H)$ – словарь, замкнутый относительно операции $\Delta$, и $\operatorname{span}\{D_3\}=X_3$, где $D_3=D \cap X_3$. Тогда найдется такой класс $[d] \in [D_3]$, что $\langle d, h \rangle=0$ для всех $[h] \in [D_3]$, $[h] \neq [d]$. Лемма 4 идентична лемме 2 из [3] (последняя сформулирована в [3] несколько иначе, но фактически в ней рассматриваются словари, замкнутые относительно операции $\Delta$). Доказательство теоремы 1. Возьмем произвольный элемент $[g_1] \in [D]$.
Если для всех $[h] \in [D]$ и $[h] \neq [g_1]$ верно $\langle g_1, h \rangle=0$, то положим $H_{[g_1]}:=\operatorname{span}\{g_1\}$. Если найдется такой $[g_2] \neq [g_1]$, что $[g_2] \in [D]$ и $\langle g_1, g_2 \rangle \neq 0$, то положим $H_{[g_1]}:=\operatorname{span}\{g_1, g_2\}$. Для всех $[h] \in [D] \setminus [(H_{[g_1]})]$ верно $\langle g_1, h \rangle=\langle g_2, h \rangle=0$ по лемме 4, примененной к $X_3=\operatorname{span}\{g_1,g_2,h\}$. Заметим, что следовательно,
$$
\begin{equation*}
H=\overline{\operatorname{span}\{H_{[h]}\colon [h] \in [D]\}}
\end{equation*}
\notag
$$
в силу полноты словаря. Также для любых $[h_1], [h_2] \in [D]$ либо $H_{[h_1]}=H_{[h_2]}$, либо $H_{[h_1]} \cap H_{[h_2]}=\{0\}$ и $H_{[h_1]} \perp H_{[h_2]}$. Таким образом, где суммирование ведется только по тем $[h] \in [D]$, у которых $H_{[h]}$ различны.
Условие
$$
\begin{equation*}
H_{\alpha} \cap D= \begin{cases} \{\pm e_{\alpha}\}, & \operatorname{dim}H_{\alpha}=1, \\ \displaystyle \bigcup_{k=1}^{N(\alpha)} \{ \pm e_{\alpha}^{k}, \pm f_{\alpha}^k\}, & \operatorname{dim}H_{\alpha}=2, \text{ где } e_{\alpha}^k \perp f_{\alpha}^k, \end{cases}
\end{equation*}
\notag
$$
выполнено в силу леммы 3 и симметричности словаря $D$.
Теорема 1 доказана. 4. Достаточное условиеТеорема 2. Пусть $D \subset S(H)$ – симметричный словарь. Пусть пространство $H$ представляется в виде $H=\bigoplus^{\perp}_{\alpha \in A}H_{\alpha}$ такой прямой суммы попарно ортогональных подпространств ($A$ – некоторое подмножество индексов), что $D \subset \bigcup_{\alpha \in A} H_{\alpha}$, $\operatorname{dim}H_{\alpha} \in \{1, 2\}$ и для всех $\alpha$ выполнено условие: Здесь $D_{\alpha}$ – словарь в плоскости $H_{\alpha}$ такой, что $S(H_{\alpha}) \setminus D_{\alpha}=\bigcup_{k=1}^{N_{\alpha}} \widehat{(a_k^{\alpha},b_k^{\alpha})}$, где $N_{\alpha} \leqslant \infty$, и удовлетворяющий условию $R_{\alpha}(a_k^{\alpha}), R_{\alpha}(b_k^{\alpha}) \in D_{\alpha}$, где $R_{\alpha}(a)$ – вектор, лежащий в плоскости $H_{\alpha}$ и ортогональный $a$ (определенный с точностью до знака). Тогда чисто жадный алгоритм, ортогональный жадный алгоритм и жадный алгоритм со свободной релаксацией работают одинаково и реализуют наилучшие $m$-членные приближения, т.е. $\|x_n\|=\|x_n^{\mathrm o}\|=\|x_n^r\|=\sigma_n(x)$ при всех натуральных $n$. Доказательство. По произвольному элементу $x \in H$ построим ортонормированную систему. Пусть $\alpha \in A$ и $P_{\alpha}(x)$ – ортогональная проекция вектора $x$ на подпространство $H_{\alpha}$. Рассмотрим только те $\alpha \in A$, для которых $P_{\alpha}(x) \neq 0$.
В случае $\operatorname{dim}H_{\alpha}=1$ положим $\lambda_{\alpha}=|\langle x, h_{\alpha} \rangle|$, $e_{\alpha}=\operatorname{sgn}\langle x, h_{\alpha} \rangle h_{\alpha}$. В случае $\operatorname{dim}H_{\alpha}=2$ положим $\lambda_{\alpha}'=\max_{g \in D_{\alpha}}\langle x, g \rangle=\langle x, e_{\alpha}'\rangle$, где $e_{\alpha}' \in D_{\alpha}$ (выбираем любой вектор, реализующий указанный максимум). Если $P_{\alpha}(x)/ \|P_{\alpha}(x)\| \neq e_{\alpha}'$, то полагаем $e_{\alpha}''=\pm R(e_{\alpha}')$, где знак плюс или минус выбирается так, чтобы $\lambda_{\alpha}''=\langle x, e_{\alpha}''\rangle \geqslant 0$. Имеем $e_{\alpha}'' \in D$ так как $R_{\alpha}(a_k^{\alpha}), R_{\alpha}(b_k^{\alpha}) \in D_{\alpha}$ при всех $k$. Таким образом, $\{e_{\alpha}, e_{\alpha}', e_{\alpha}''\}$ – не более чем счетная ортонормированная система, $\{\lambda_{\alpha}, \lambda_{\alpha}', \lambda_{\alpha}''\}$ – соответствующие неотрицательные коэффициенты Фурье элемента $x$. Упорядочим элементы системы по невозрастанию соответствующих коэффициентов Фурье (такое упорядочивание не единственное), получим разложение $x=\sum_{k=0}^{\infty}\lambda_k e_k$. По построению ортонормированной системы имеем
$$
\begin{equation*}
x_n=\sum_{k=n}^{\infty}\lambda_k e_k, \qquad \|x_n\|^2=\sum_{k=n}^{\infty}\lambda_k^2
\end{equation*}
\notag
$$
для последовательности чисто жадных остатков в случае, когда чисто жадный алгоритм на каждом шаге выбирает $e_n$ в качестве $g(x_n)$. При этом при любой другой работе чисто жадного алгоритма нормы $\|x_n\|$ будут такими же, а в качестве $g(x_n)$ выбираются векторы этой же системы в другом порядке.
Теперь покажем, что справедливо равенство для всех натуральных $m$. Действительно, пусть $y=\sum_{k=1}^{m}\mu_k h_k$ – $m$-членная комбинация элементов словаря $D$. Не ограничивая общности, пусть $h_1 \neq e_k$ при всех $k$ и $h_1 \in H_{\alpha}$.Если $P_{\alpha}(x)=0$, то заменим в $m$-членной комбинации все $\mu_k h_k \in H_{\alpha}$ на нулевые элементы. Если $P_{\alpha}(x)/\|P_{\alpha}(x)\| \in H_{\alpha} \cap D$, то заменим в $m$-членной комбинации $\mu_1 h_1$ на $P_{\alpha}(x)$, а все остальные $\mu_k h_k \in H_{\alpha}, k \neq 1$, на нулевые элементы. В случае $P_{\alpha}(x)/\|P_{\alpha}(x)\| \notin H_{\alpha} \cap D$ рассмотрим два варианта. Если $h_k \notin H_{\alpha}$ при $2 \leqslant k \leqslant m$, то заменим в $m$-членной комбинации $\mu_1 h_1$ на $\langle x, e_{\alpha}' \rangle e_{\alpha}'$. В противном случае, не ограничивая общности можно считать, что $h_2 \in H_{\alpha}$. Тогда заменим в $m$-членной комбинации $\mu_1 h_1$ и $\mu_2 h_2$ на $\langle x, e_{\alpha}' \rangle e_{\alpha}'$ и $\langle x, e_{\alpha}'' \rangle e_{\alpha}''$, а все остальные $\mu_k h_k \in H_{\alpha}$, $k > 2$, на нулевые элементы. При таких заменах норма $\|x-y\|$ не увеличится. Таким образом, доказано неравенство $\sigma_m(x,D) \geqslant \sigma_m(x,\{e_k\})$. Обратное неравенство следует из включения $\{e_k\} \subset D$. Осталось вспомнить хорошо известное равенство [1; гл. 1, § 1]
$$
\begin{equation*}
\sigma_n(x, \{e_k\})^2=\|x_n\|^2=\sum_{k=n}^{\infty}\lambda_k^2.
\end{equation*}
\notag
$$
В итоге показано, что $\|x_n\|=\sigma_n(x)$ для любого $n$ и любой реализации чисто жадного алгоритма, и $\{g(x_n)\}_0^{\infty}$ – ортонормированная система. Осталось показать, что чисто жадный алгоритм, ортогональный жадный алгоритм и жадный алгоритм со свободной релаксацией работают одинаково. Докажем это по индукции. Пусть для всех $k \leqslant n$ выполнены равенства
$$
\begin{equation*}
x_k=x_k^{\mathrm o}=x_k^r, \qquad g(x_k)=g(x_k^{\mathrm o})=g(x_k^r).
\end{equation*}
\notag
$$
Так как системы $\{g(x_k)\}_0^{n}$, $\{g(x_k^{\mathrm o})\}_0^{n}$, $\{g(x_k^r)\}_0^{n}$ совпадают, а $\{g(x_k)\}_0^{n}$ – ортонормирована, имеем
$$
\begin{equation*}
\begin{aligned} \, x_{n+1} &=x_n-P_{\operatorname{span}\{g(x_n)\}}(x_n), \\ x_{n+1}^{\mathrm o} &=x-P_{\operatorname{span}\{g(x_0^{\mathrm o}), g(x_1^{\mathrm o}), \dots, g(x_n^{\mathrm o})\}}(x) \\ &=x-P_{\operatorname{span}\{g(x_0^{\mathrm o}), g(x_1^{\mathrm o}), \dots, g(x_{n-1}^{\mathrm o})\}}(x)-P_{\operatorname{span}\{g(x_n)\}}(x_n) \\ &=x_n^{\mathrm o}-P_{\operatorname{span}\{g(x_n)\}}(x_n)=x_{n+1}, \\ x_{n+1}^r &=x-P_{\operatorname{span}\{x_0^r-x_n^r, g(x_n^r)\}}(x)=x-P_{\operatorname{span}\{x_0^r-x_n^r\}}(x)- P_{\operatorname{span}\{g(x_n)\}}(x) \\ &=x_n^r-P_{\operatorname{span}\{g(x_n)\}}(x_n)=x_{n+1}. \end{aligned}
\end{equation*}
\notag
$$
Таким образом $x_{n+1}=x_{n+1}^{\mathrm o}=x_{n+1}^r$, что и требовалось.
Теорема доказана. Следствие 1. Пусть $D \subset S(H)$ – симметричный словарь, удовлетворяющий условию (1), и $M(D) < 1$. Следующие условия эквивалентны: Автор благодарен П. А. Бородину за постановку задачи и помощь в работе над статьей. 
Цитирование в формате AMSBIB
\RBibitem{Vis24} |
|
||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|