Автоматы, рассматриваемые как преобразователи информации, используются в системах передачи сообщений и выполняют различные функции, в том числе кодирования этих сообщений. В последней ситуации принятое получателем закодированное сообщение должно быть однозначно декодировано. В этой главе рассматриваются автоматы, удовлетворяющие этому требованию.
Основополагающие работы в области исследования автоматов, являющихся моделями таких устройств, принадлежат Д. Хаффмену [76] и С. Ивену [74]. В этих работах введены и изучены два класса автоматов, названных соответственно
В этой лекции предложены обобщения БПИ- и БПИК-автоматов в двух направлениях. Одно из них связано с отказом от предположения об их инициальности, а второе - с исследованием такого рода автоматов со структурированными входными и выходными алфавитами. В последней ситуации восстановление неизвестных входных последовательностей осуществляется не в полном объеме, а на заданном подмножестве компонент структурированного входного символа.
В этом разделе в качестве математической модели ДУ используется слабоинициальный
Пусть $$\bar p=\bar {x_1} \dots \bar {x_k}$$ - последовательность входных символов (входное слово) автомата $$A$$. Число $$d(\bar p)=k$$ назовем длиной слова $$\bar p$$.
Пусть $$\bar x=(x_1, \dots, x_n) \in X, I \le i_1 \le i_2 \le \dots \le i_{\nu}$$, - натуральные числа, $$1 \le i_j \le n$$, тогда проекцией $$\bar x$$ по каналам с номерами $$i_1, i_2, \dots, i_{\nu}$$ назовем вектор $$(x_{i_1}, \dots, x_{i_{\nu}})$$ и будем обозначать ее $$pr_{i_1, \dots, i_{\nu}} \bar x$$, а проекцией слова $$\ bar p= \bar {x_1} \dots \bar {x_k}$$ по тем же каналам назовем упорядоченную последовательность $$(pr_{i_1, \dots, i_{\nu}} \bar {x_1}, \dots, pr_{i_1, \dots, i_{\nu}} \bar {x_k})$$ и будем обозначать ее $$pr_{i_1, \dots, i_{\nu}} \bar p$$.
Рассмотрим следующую задачу. На автомат $$A$$, находящийся в одном из состояний множества $$S_0$$, но неизвестно, в каком именно, подается неизвестное входное слово $$\bar p$$, и наблюдается реакция автомата на это слово по выходным каналам с номерами $$j_1 < j_2< \dots < j_{\mu}$$, где $$1 \le j_i \le m$$. Требуется построить эксперимент, проводимый с автоматом $$A$$ после приложения слова $$\bar p$$, позволяющий распознать проекцию этого слова по каналам с номерами $$i_1, i_2, \dots, i_{\nu}$$, где $$i_1 < i_2 < \dots < i_{\nu}$$.
Автоматы, для которых сформулированная задача может быть решена независимо от входного слова $$\bar p$$ и действительного начального состояния из множества $$S_0$$, назовем обобщенными автоматами без потери информации (ОБПИ-автоматами).
Далее, не теряя общности, положим, что $$i_1=1, i_2=2, \dots, i_{\nu}=\nu$$ и соответственно $$j_1=1, j_2=2, \dots, j_{\mu}=\mu$$, т. е. реакция автомата $$A$$ на слово $$\bar p$$ наблюдается по первым $$\mu$$ выходным каналам, а в каждом символе $$\bar {x_i} (i=\overline {1,k})$$ слова $$\bar p$$ восстановлению подлежат сигналы, поступающие на автомат по первым $$\nu$$ входным каналам.
Из формулировки задачи следует, что ОБПИ-автоматы должны обладать следующим свойством:
$$\forall_{s,t \in S_0} \forall_{\bar p, \bar q \in X*} pr_{1, \dots, \mu} \lambda (s, \bar p)=pr_{1, \dots, \mu} \lambda (t, \bar p) \to pr_{1, \dots, \nu} \bar p=pr_{1, \dots, \nu} \bar q$$Отметим, что определенные нами ОБПИ-автоматы в качестве частного случая включают в себя ранее известные БПИ-автоматы, введенные Д. Хаффменом [76], и автоматы существенно без потери информации (СБПИ-автоматы) [9] [43], введенные автором предлагаемой монографии. БПИ-автоматы получаются при $$|S_0|=1, \nu =n, \mu = m$$, а СБПИ-автоматы получаются при $$S_0=S, \nu = n, \mu = m$$.
Определение 3.1. Пару состояний $$s$$ и $$t$$ автомата $$A$$ назовем
Заметим, что если $$s=t$$, то приведенное определение совпадает с определением из [76], и в этом случае $$s$$ называется СПИ-состоянием.
Теорема 3.1. Для того чтобы автомат $$A$$ был ОБПИ-автоматом, необходимо и достаточно, чтобы он не имел СПИ-состояний.
Доказательство. Необходимость условий теоремы очевидна, покажем их достаточность.
Пусть условия теоремы выполняются. Предположим, что на вход автомата $$A$$ было подано неизвестное слово $$\bar {\nu}$$, а на первых $$\mu$$ выходных каналах наблюдалось слово $$\bar w$$. По таблице переходов-выходов автомата $$A$$ определим пары "состояние - входное слово" $$(s_{i_1}; \bar {\nu_1}), \dots, (s_{i_r}; \bar {\nu_r})$$, такие, что $$s_{i_j} \in S_0$$ и $$pr_{1, \dots, \mu} \lambda (s_{i_j}, \nu_j)=\bar w$$, где $$j=1, \dots, r$$. Понятно, что среди слов $$\bar {\nu_1}, \dots, \bar {\nu_r}$$ находится и искомое слово.
Пусть $$\delta (s_{i_j}, \bar {\nu_j})=s_{i_j}*; j=1, \dots, r$$. Покажем, что между парами $$(s_{i_j}, \bar {\nu})$$ и состояниями $$s_{i_j}*$$ существует взаимно однозначное соответствие. Последнее означает, что такое соответствие существует и между $$pr_{1, \dots, \nu} \bar {\nu_j}$$ и состояниями $$s_{i_j}*, j=1, \dots, r$$.
Если все состояния $$s_{i_1}*, \dots, s_{i_r}*$$ попарно различны, справедливость сформулированного утверждения очевидна. Предположим, что среди состояний $$s_{i_1}*, \dots, s_{i_r}*$$ имеется по крайней мере два совпадающих. Без ограничения общности можно считать, что $$s_{i_1}*=s_{i_2}*$$. Из последнего равенства следует, что $$\delta (s_{i_1}, \bar {nu_1})= \delta (s_{i_2}, \bar {\nu_2})$$. По построению пары $$(s_{i_1}, \bar {\nu_1})$$ и $$(s_{i_2}, \bar {\nu_2})$$ различны, что возможно только в следующих трех случаях:
В первом случае состояние $$S_{i_1}$$ является по определению СПИ-состоянием, что противоречит нашему предположению. Во втором случае пара состояний $$S_{i_1}$$ и $$s_{i_2}$$ является по определению
Продолжим доказательство теоремы. Предположим, что среди состояний $$s_{i_1}*, \dots, s_{i_r}*$$ все попарно различные состояния образуют множество $$\hat S=\{\hat {s_{k_1}}, \dots, \hat {s_{k_f}}\}$$, где $$f \le r$$. Рассматривая $$\hat S$$ в качестве множества допустимых начальных состояний автомата $$A$$, построим для него установочную последовательность $$L$$. Обозначим через $$s$$ состояние, в которое перейдет автомат $$A$$ после подачи слова $$L$$, а выходную последовательность, которую он выдает при этом, обозначим через $$M$$. Если пара $$(L,M)$$ порождается только из одного состояния множества $$\hat S$$ (этот факт легко установить по таблице переходов-выходов автомата $$A$$ ), тогда, очевидно, существует взаимно однозначное соответствие между заключительным состоянием $$s$$ и состоянием $$\hat {s_{k_i}}$$, между $$\hat {s_{k_i}}$$ и $$s_{i_j}*$$ и, наконец, между $$s_{i_j}*$$ и $$pr_{1, \dots, \nu}, \bar {\nu_j}$$. В силу сказанного, знание заключительного состояния $$s$$ позволяет однозначно восстановить проекцию неизвестного входного слова, поданного на автомат $$A$$, по каналам с номерами $$1, \dots, \nu$$.
Если пара $$(L,M)$$ порождается из двух различных состояний множества $$\hat S$$, например $$\hat {s_{k_1}}$$ и $$\hat {s_{k_2}}$$, то им взаимно однозначно соответствуют состояния $$s_{i_a}*$$ и $$s_{i_b}*$$, последним - состояния $$s_{i_a}$$ и $$s_{i_b}$$ из множества $$S_0$$, а состояниям $$S_{i_a}$$ и $$S_{i_b}$$, в свою очередь, взаимно однозначно соответствуют входные слова $$\bar {\nu_a}$$ и $$\bar {\nu_b}$$. В силу выполненных выше построений имеем следующие равенства:
$$\delta (s_{i_a}, \bar {\nu_a}L)= \delta (s_{i_b}, \bar {\nu_b}L), pr_{1, \dots, \mu} \lambda (s_{i_a}, \bar {\nu_a}L)=pr_{1, \dots, \mu} \lambda (s_{i_b}, \bar {\nu_b}L)=\bar w pr_{1, \dots, \mu} M$$Если входные слова $$\bar {\nu_a}$$ и $$\bar {\nu_b}$$ таковы, что $$pr_{1, \dots, \mu} \bar {\nu_a}=pr_{1, \dots, \mu} \bar {\nu_b}$$, то искомая проекция восстанавливается однозначно. Если же выписанные только что проекции различны, то это означает, что пара состояний $$s_{i_a}$$ и $$s_{i_b}$$ является
Заметим, что аналогичные рассуждения справедливы и для случая, когда пара $$(L,M)$$ порождается более чем из двух состояний.
Теорема доказана.
Доказательство теоремы фактически содержит алгоритм распознавания проекции неизвестного входного слова по заданному множеству каналов, который сформулируем в явном виде.
Из множества пар $$(s_{i_1}; \bar {\nu_1}), \dots, (s_{i_r}; \bar {\nu_r})$$ выделяем все те его элементы, для которых $$\delta (s_{i_j}, \bar {\nu_j})=s_{k_f}*, f=1, \dots, b$$. Если этот элемент один, то проекция второго члена выделенной пары по каналам $$1, \dots, \nu$$ и есть искомое входное слово. Если число таких элементов больше двух, то у них упомянутые проекции вторых членов пар совпадают и являются искомым входным словом.
Рассмотрим пример. Пусть ОБПИ-автомат задан графом на рис.3.1. Условимся, что для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу, т. е. $$\nu =\mu =1$$. Пусть $$S_0=\{1,2\}$$, на автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдалась реакция 0,1,1. Строим последовательность пар "состояние - входное слово", упомянутую в пункте 1 алгоритма: (1;10,00,10), (1;10,00,11), (1;10,00,00), (1;10,00,11), (1;10,01,10), (1;10,01,11), (1;10,01,00), (1;10,01,10), (1;11,00,10), (1;11,00,11), (1;11,00,00), (1;11,00,10), (1;11,01,10), (1;11,01,11), (1;11,01,00), (1;11,01,10), (2;10,10,10), (2;10,10,11), (2;10,11,10), (2;10,11,11), (2;11,10,10), (2;11,10,11), (2;11,11,10), (2;11,11,11).
(рис 3.1) Нетрудно убедиться, что упомянутое в пункте 2 алгоритма множество есть $$\hat S =\{1,2,3\}$$. Установочной последовательностью для рассматриваемого автомата с множеством допустимых начальных состояний $$\hat S$$ является, например, слово длиной два $$L=01,01$$. Пользуясь таблицей 3.1, по действительной реакции автомата на слово $$L$$ находим состояния $$\hat {s_{k_i}}$$, упомянутые в пункте 3 алгоритма.
| Состояние автомата | ВХОДНАЯ ПОСЛЕДОВАТЕЛЬ-НОСТЬ | Реакция автомата | Заключительное состояние |
|---|---|---|---|
| 1 | 01,01 | 00,00 | 1 |
| 2 | 01,01 | 10,10 | 1 |
| 3 | 01,01 | 10,00 | 1 |
Если $$\hat {s_{k_i}}=1$$, то ему соответствуют пары (1;10,00,00), (1;10,00,01), (1;10,01,00), (1;10,01,01), …, (1;11,01,00) и проекцией по 1-му входному каналу неизвестного входного слова является 1,0,0. При $$\hat {s_{k_i}}=2$$ искомая проекция есть 1,0,1 и, например, при $$\hat {s_{k_i}}=3$$ проекция равна 1,1,1.
Хотя теорема 3.1 позволила обосновать метод восстановления искомой проекции неизвестного входного слова, однако ответить с ее помощью на вопрос, является ли конкретный автомат ОБПИ-автоматом, сложно из-за отсутствия эффективного способа проверки условий теоремы. Ввиду этого ниже сформулируем еще одно необходимое и достаточное условие принадлежности автомата классу ОБПИ, но в других по сравнению с теоремой 3.1 терминах, допускающее простую проверку.
С этой целью по аналогии с [74] введем понятие
Аналогичное определение сформулируем и для случая, когда выходной символ $$\bar y$$ наблюдается не по всем, а только по $$\mu$$ выделенным каналам с номерами $$j_1 < j_2 < \dots j_m$$: дуга $$s_i \to s_j$$ имеет пометку $$pr_{j_1, j_2, \dots, j_{\mu}} \bar y$$, если
$$\exists {x \in X} \delta (s_i, \bar x)=s_j pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_j, \bar x)=pr_{j_1, j_2, \dots, j_{\mu}} \bar y$$Понятно, что две вершины графа могут связываться несколькими дугами с разными пометками.
Пусть $$\Gamma \{S_0\}$$ - множество всех состояний автомата $$A$$, достижимых из множества допустимых начальных состояний $$S_0$$ путями любой длины.
По графу автомата $$A$$ построим другой ориентированный конечный граф $$G(A)$$ следующим образом.
В графе $$G(A)$$ две вершины могут быть связаны несколькими дугами с разными пометками.
Пусть неизвестное входное слово необходимо восстановить по каналам с номерами $$i_1, \dots, i_{\nu}$$, где $$i_1<i_2<\dots < i_{\nu}$$.
Дугу $$\{s_k, s_l\} \to \{s_i, s_j\}$$ с пометкой $$pr_{j_1, j_2, \dots, j_mu}}$$ назовем выделенной, если
$$\exists_{x_1, x_2 \in X} \delta (s_k, \bar {x_1})= s_i \delta (s_l, \bar {x_2})=s_j pr_{j_1, \dots, j_{\mu}} \lambda (s_k, \bar {x_1})=pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_l, \bar {x_2})=pr_{j_1, j_2, \dots, j_{\mu}} \bat y \to pr_{i_1, \dots, i_{\nu}} \bar {x_1} \ne pr_{i_1, \dots, i_{\nu}} \bar {x_2}$$Из графа $$G(A)$$ удалим все вершины вида $$\{s,s\}$$ вместе с инцидентными им дугами, если последние, в свою очередь, инцидентны только вершинам такого же вида, а также изолированные вершины. Полученный в результате такого удаления ориентированный конечный граф назовем
Теорема 3.2. Автомат $$T(A)$$ является ОБПИ-автоматом тогда и только тогда, когда все пути в проверочном графе $$T(A)$$, ведущие в вершины вида $$\{s,s\}$$, не содержат выделенных дуг.
Необходимость. Пусть $$A$$ есть ОБПИ-автомат, но в $$T(A)$$ существует путь с выделенной дугой $$\{s_k, s_l\} \to \{s_i, s_j\}$$, ведущий в вершину вида $$\{s,s\}$$. Предположим, что $$\bar p$$ и $$\bar q$$ - два таких входных слова, что $$\delta (s_k, \bar p)=\delta (s_l, \bar q)=s$$, и они соответствуют пути по графу в $$T(A)$$, начинающемуся с упомянутой выделенной дуги. Последнее означает, что
$$\exists_{s_k, s_l \in T|{S_0\}} \exists_{\bar p, \bar q \in X*} pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_k, \bar p)=pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_l, \bar q) \to pr_{i_1, \dots, i_{\nu}} \bar p \ne pr_{i_1, \dots, i_{\nu}} \bar q$$Из сравнения этого высказывания с (3.1) вытекает, что $$A$$ не может быть ОБПИ-автоматом, а это противоречит исходной посылке.
Достаточность. Докажем ее методом от противного. Пусть $$A$$ не является ОБПИ-автоматом. Покажем тогда, что в графе $$T(A)$$ существует путь, ведущий в вершину вида $$\{s,s\}$$, содержащий выделенную дугу. Поскольку $$A$$ не есть ОБПИ-автомат, то
$$\exists {s_k, s_l \in S_0} \exists {p, q \in X*} \delta (s_k, \bar p) = \delta (s_l. \bar q)=s pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_k, \bar p)=pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_l, \bar q) \to pr_{i_1, \dots, i_{\nu}} \bar p \ne pr-\_{i_1}, \dots, i_{\nu}} \bar q$$Пусть $$\bar {x_p}$$ и $$\bar {x_q}$$ - первые слева символы в словах $$\bar p$$ и $$\bar q$$, проекции которых по каналам $$i_1, \dots, i_{\nu}$$ различны. Пусть при подаче этих символов автомат $$A$$ осуществляет переходы из состояний $$s_1, s_2$$ в состояния $$\hat {s_1}, \hat {s_2}$$ соответственно. Отсюда следует, что в графе $$T(A)$$ существует выделенная дуга, соединяющая вершины $$\{s_1, s_2\}$$ и $$\{\hat {s_1}, \hat {s_2}\}$$. Это означает существование в графе $$T(A)$$ пути из $$\{s_1, s_2\}$$ в $$\{s,s\}$$, первая дуга которого выделенная. Этим завершается доказательство достаточности условий теоремы.
В качестве примера на рис.3.2 изображен проверочный граф для автомата, представленного на рис.3.1, в предположении, что $$\nu = \mu =1$$. На рисунке двойные стрелки соответствуют выделенным дугам, над каждой дугой стоит соответствующая ей пометка. В этом проверочном графе все возможные пути, заканчивающиеся в вершинах вида $$\{s,s\}$$, могут начинаться только в вершинах $$\{1,1\}$$ либо $$\{3/3\}$$, при этом конечной вершиной в любом из этих путей является вершина $$\{1,1\}$$. Из рис.3.2 видно, что ни один из этих путей не содержит выделенных дуг, следовательно, рассматриваемый автомат относится к классу ОБПИ-автоматов.
(рис 3.2) Если задан автомат $$A$$ с $$n$$ входными и $$m$$ выходными каналами, то возникает вопрос: для каких подмножеств входных и выходных каналов он является ОБПИ-автоматом? Очевидно, что $$A$$ может не быть БПИ-автоматом в классическом смысле, но в то же время быть ОБПИ-автоматом, если восстановление входных сигналов производится по некоторому подмножеству входных каналов.
При отыскании всех возможных подмножеств входных и выходных каналов, для которых заданный автомат $$A$$ является ОБПИ-автоматом, в первую очередь представляет интерес случай, когда подмножество входных каналов - максимальное, а подмножество выходных каналов - минимальное по мощности. Далее такой автомат будем называть оптимальным. Это соответствует ситуации, когда при минимальных затратах, определяемых объемом наблюдаемой информации на выходах, удается однозначно восстановить максимальный объем информации, поступившей на вход автомата.
Опишем способ, позволяющий получить ответ на сформулированный выше вопрос. Условимся далее через $$A_M^R$$ обозначать автомат, у которого выходные символы наблюдаются по каналам с номерами из множества $$M$$, а восстановление сигналов ведется по каналам с номерами из множества $$R$$.
По графу автомата $$A$$ построим его проверочный граф $$T(A)$$ при $$\nu = n$$ и $$\mu =m$$, т. е. предполагая, что реакция $$A$$ наблюдается по всем его выходным каналам, а восстановление неизвестного входного слова также ведется по всем каналам. Используя $$T(A)$$, найдем в нем все пути, ведущие в вершины вида $$\{s,s\}$$, и образуем на этой основе множество $$\Gamma=\{\gamma_1, \gamma_2, \dots, \gamma_t\}$$ всех входящих в эти пути выделенных дуг. Если $$\Gamma = \varnothing$$, то по теореме 3.2 автомат $$A$$ есть ОБПИ-автомат, и при $$\mu = m$$ он будет, очевидно, таковым для любого $$\nu$$, где $$1 \le \nu \le n$$. Если $$\Gamma \ne \varnothing$$, то для каждого $$i=\overline {1,t}$$ построим множество $$R_i*$$ целых чисел, представляющих собой номера входных каналов, на которых на дуге $$\gamma_i$$ происходит потеря информации. Последнее означает, что если реакция автомата $$A$$ соответствует отметке дуги $$\gamma_i$$, то в каналах с номерами из множества $$R_t*$$ сигналы могут иметь значения как 0, так и 1. Используя множество $$R*=R_1Y \dots YR_t*$$, построим $$R=\{1, \dots, n\}\r*$$. Из способа построения следует, что, во-первых, $$R$$ содержит все те номера входных каналов, по каждому из которых и по их совокупности рассматриваемый автомат $$A$$ является ОБПИ-автоматом, и, во-вторых, $$R$$ - максимальный по мощности, сохраняющий свойство ОБПИ.
Далее через $$T_Q^R(A)$$ обозначим проверочный граф автомата $$A$$, предполагая, что наблюдение реакций ведется по каналам с номерами из множества $$Q$$, а восстановление неизвестного входного слова - по каналам с номерами из множества $$R$$.
Пусть $$M=\{1, \dots, m\}$$. Для каждого $$j, 1 \le j \le m$$, построим проверочный граф $$T_{M\\{j\}}^R(A)$$. Нетрудно сообразить, что дуги графа $$T_M^R(A)$$ одновременно являются и дугами графа $$T_{M\\{j\}}^R(A)$$, но в последнем, кроме того, могут появиться и новые. Если последний упомянутый граф удовлетворяет условиям теоремы 3.2, то, очевидно, $$j$$ -й выходной канал избыточен в том смысле, что отказ от наблюдения реакции по нему не повлияет на возможности восстановления неизвестного входного слова по каналам из множества $$R$$. Пусть $$M*=\{j_1, j_2, \dots, j_s\}$$ - множество номеров всех избыточных выходных каналов автомата $$A$$. Если $$M*= \varnothing$$, то построенный на 1-м этапе автомат $$A_M^R$$ - искомый. При $$M*\ne \varnothing$$ рассмотрим все возможные сочетания пар каналов из множества $$M*$$, число которых равно $$C_{|M|}^2$$. Для каждой из упомянутых пар каналов $$J+\{j_k, j_l\}$$ построим проверочный граф $$T_{M\J}^R(A)$$ и проверим для него выполнение условий теоремы 3.2. Если ни один из таких графов не удовлетворяет условиям этой теоремы, то автоматы $$A_{M\\{J_i\}}^R, i=\overline {1,s}$$, - искомые оптимальные автоматы. В противном случае формируем все возможные сочетания $$J$$ троек номеров из множества $$M*$$ и ищем среди проверочных графов $$T_{M\J}^R(A)$$ такие, которые удовлетворяют условиям теоремы 3.2. Указанный процесс продолжается до того момента, когда на очередном этапе все графы вида $$T_{M\J}^R(A)$$, где $$1 \le |J| \le s$$, не удовлетворяют условиям теоремы 3.2. Тогда автоматы $$A_{M\J}^R$$, построенные на предыдущем этапе и являющиеся ОБПИ-автоматами, - искомые оптимальные.
Отметим, что для поиска всех оптимальных ОБПИ-автоматов в худшем случае может потребоваться построение $$\sum_{i=1}^{s} C_s^i$$ различных проверочных графов, где $$s$$ - число избыточных выходных каналов автомата $$A$$.
Автоматы, рассматриваемые как преобразователи информации, используются в системах передачи сообщений и выполняют различные функции, в том числе кодирования этих сообщений. В последней ситуации принятое получателем закодированное сообщение должно быть однозначно декодировано. В этой главе рассматриваются автоматы, удовлетворяющие этому требованию.
Основополагающие работы в области исследования автоматов, являющихся моделями таких устройств, принадлежат Д. Хаффмену [76] и С. Ивену [74]. В этих работах введены и изучены два класса автоматов, названных соответственно
В этой лекции предложены обобщения БПИ- и БПИК-автоматов в двух направлениях. Одно из них связано с отказом от предположения об их инициальности, а второе - с исследованием такого рода автоматов со структурированными входными и выходными алфавитами. В последней ситуации восстановление неизвестных входных последовательностей осуществляется не в полном объеме, а на заданном подмножестве компонент структурированного входного символа.
В этом разделе в качестве математической модели ДУ используется слабоинициальный
Пусть $$\bar p=\bar {x_1} \dots \bar {x_k}$$ - последовательность входных символов (входное слово) автомата $$A$$. Число $$d(\bar p)=k$$ назовем длиной слова $$\bar p$$.
Пусть $$\bar x=(x_1, \dots, x_n) \in X, I \le i_1 \le i_2 \le \dots \le i_{\nu}$$, - натуральные числа, $$1 \le i_j \le n$$, тогда проекцией $$\bar x$$ по каналам с номерами $$i_1, i_2, \dots, i_{\nu}$$ назовем вектор $$(x_{i_1}, \dots, x_{i_{\nu}})$$ и будем обозначать ее $$pr_{i_1, \dots, i_{\nu}} \bar x$$, а проекцией слова $$\ bar p= \bar {x_1} \dots \bar {x_k}$$ по тем же каналам назовем упорядоченную последовательность $$(pr_{i_1, \dots, i_{\nu}} \bar {x_1}, \dots, pr_{i_1, \dots, i_{\nu}} \bar {x_k})$$ и будем обозначать ее $$pr_{i_1, \dots, i_{\nu}} \bar p$$.
Рассмотрим следующую задачу. На автомат $$A$$, находящийся в одном из состояний множества $$S_0$$, но неизвестно, в каком именно, подается неизвестное входное слово $$\bar p$$, и наблюдается реакция автомата на это слово по выходным каналам с номерами $$j_1 < j_2< \dots < j_{\mu}$$, где $$1 \le j_i \le m$$. Требуется построить эксперимент, проводимый с автоматом $$A$$ после приложения слова $$\bar p$$, позволяющий распознать проекцию этого слова по каналам с номерами $$i_1, i_2, \dots, i_{\nu}$$, где $$i_1 < i_2 < \dots < i_{\nu}$$.
Автоматы, для которых сформулированная задача может быть решена независимо от входного слова $$\bar p$$ и действительного начального состояния из множества $$S_0$$, назовем обобщенными автоматами без потери информации (ОБПИ-автоматами).
Далее, не теряя общности, положим, что $$i_1=1, i_2=2, \dots, i_{\nu}=\nu$$ и соответственно $$j_1=1, j_2=2, \dots, j_{\mu}=\mu$$, т. е. реакция автомата $$A$$ на слово $$\bar p$$ наблюдается по первым $$\mu$$ выходным каналам, а в каждом символе $$\bar {x_i} (i=\overline {1,k})$$ слова $$\bar p$$ восстановлению подлежат сигналы, поступающие на автомат по первым $$\nu$$ входным каналам.
Из формулировки задачи следует, что ОБПИ-автоматы должны обладать следующим свойством:
$$\forall_{s,t \in S_0} \forall_{\bar p, \bar q \in X*} pr_{1, \dots, \mu} \lambda (s, \bar p)=pr_{1, \dots, \mu} \lambda (t, \bar p) \to pr_{1, \dots, \nu} \bar p=pr_{1, \dots, \nu} \bar q$$Отметим, что определенные нами ОБПИ-автоматы в качестве частного случая включают в себя ранее известные БПИ-автоматы, введенные Д. Хаффменом [76], и автоматы существенно без потери информации (СБПИ-автоматы) [9] [43], введенные автором предлагаемой монографии. БПИ-автоматы получаются при $$|S_0|=1, \nu =n, \mu = m$$, а СБПИ-автоматы получаются при $$S_0=S, \nu = n, \mu = m$$.
Определение 3.1. Пару состояний $$s$$ и $$t$$ автомата $$A$$ назовем
Заметим, что если $$s=t$$, то приведенное определение совпадает с определением из [76], и в этом случае $$s$$ называется СПИ-состоянием.
Теорема 3.1. Для того чтобы автомат $$A$$ был ОБПИ-автоматом, необходимо и достаточно, чтобы он не имел СПИ-состояний.
Доказательство. Необходимость условий теоремы очевидна, покажем их достаточность.
Пусть условия теоремы выполняются. Предположим, что на вход автомата $$A$$ было подано неизвестное слово $$\bar {\nu}$$, а на первых $$\mu$$ выходных каналах наблюдалось слово $$\bar w$$. По таблице переходов-выходов автомата $$A$$ определим пары "состояние - входное слово" $$(s_{i_1}; \bar {\nu_1}), \dots, (s_{i_r}; \bar {\nu_r})$$, такие, что $$s_{i_j} \in S_0$$ и $$pr_{1, \dots, \mu} \lambda (s_{i_j}, \nu_j)=\bar w$$, где $$j=1, \dots, r$$. Понятно, что среди слов $$\bar {\nu_1}, \dots, \bar {\nu_r}$$ находится и искомое слово.
Пусть $$\delta (s_{i_j}, \bar {\nu_j})=s_{i_j}*; j=1, \dots, r$$. Покажем, что между парами $$(s_{i_j}, \bar {\nu})$$ и состояниями $$s_{i_j}*$$ существует взаимно однозначное соответствие. Последнее означает, что такое соответствие существует и между $$pr_{1, \dots, \nu} \bar {\nu_j}$$ и состояниями $$s_{i_j}*, j=1, \dots, r$$.
Если все состояния $$s_{i_1}*, \dots, s_{i_r}*$$ попарно различны, справедливость сформулированного утверждения очевидна. Предположим, что среди состояний $$s_{i_1}*, \dots, s_{i_r}*$$ имеется по крайней мере два совпадающих. Без ограничения общности можно считать, что $$s_{i_1}*=s_{i_2}*$$. Из последнего равенства следует, что $$\delta (s_{i_1}, \bar {nu_1})= \delta (s_{i_2}, \bar {\nu_2})$$. По построению пары $$(s_{i_1}, \bar {\nu_1})$$ и $$(s_{i_2}, \bar {\nu_2})$$ различны, что возможно только в следующих трех случаях:
В первом случае состояние $$S_{i_1}$$ является по определению СПИ-состоянием, что противоречит нашему предположению. Во втором случае пара состояний $$S_{i_1}$$ и $$s_{i_2}$$ является по определению
Продолжим доказательство теоремы. Предположим, что среди состояний $$s_{i_1}*, \dots, s_{i_r}*$$ все попарно различные состояния образуют множество $$\hat S=\{\hat {s_{k_1}}, \dots, \hat {s_{k_f}}\}$$, где $$f \le r$$. Рассматривая $$\hat S$$ в качестве множества допустимых начальных состояний автомата $$A$$, построим для него установочную последовательность $$L$$. Обозначим через $$s$$ состояние, в которое перейдет автомат $$A$$ после подачи слова $$L$$, а выходную последовательность, которую он выдает при этом, обозначим через $$M$$. Если пара $$(L,M)$$ порождается только из одного состояния множества $$\hat S$$ (этот факт легко установить по таблице переходов-выходов автомата $$A$$ ), тогда, очевидно, существует взаимно однозначное соответствие между заключительным состоянием $$s$$ и состоянием $$\hat {s_{k_i}}$$, между $$\hat {s_{k_i}}$$ и $$s_{i_j}*$$ и, наконец, между $$s_{i_j}*$$ и $$pr_{1, \dots, \nu}, \bar {\nu_j}$$. В силу сказанного, знание заключительного состояния $$s$$ позволяет однозначно восстановить проекцию неизвестного входного слова, поданного на автомат $$A$$, по каналам с номерами $$1, \dots, \nu$$.
Если пара $$(L,M)$$ порождается из двух различных состояний множества $$\hat S$$, например $$\hat {s_{k_1}}$$ и $$\hat {s_{k_2}}$$, то им взаимно однозначно соответствуют состояния $$s_{i_a}*$$ и $$s_{i_b}*$$, последним - состояния $$s_{i_a}$$ и $$s_{i_b}$$ из множества $$S_0$$, а состояниям $$S_{i_a}$$ и $$S_{i_b}$$, в свою очередь, взаимно однозначно соответствуют входные слова $$\bar {\nu_a}$$ и $$\bar {\nu_b}$$. В силу выполненных выше построений имеем следующие равенства:
$$\delta (s_{i_a}, \bar {\nu_a}L)= \delta (s_{i_b}, \bar {\nu_b}L), pr_{1, \dots, \mu} \lambda (s_{i_a}, \bar {\nu_a}L)=pr_{1, \dots, \mu} \lambda (s_{i_b}, \bar {\nu_b}L)=\bar w pr_{1, \dots, \mu} M$$Если входные слова $$\bar {\nu_a}$$ и $$\bar {\nu_b}$$ таковы, что $$pr_{1, \dots, \mu} \bar {\nu_a}=pr_{1, \dots, \mu} \bar {\nu_b}$$, то искомая проекция восстанавливается однозначно. Если же выписанные только что проекции различны, то это означает, что пара состояний $$s_{i_a}$$ и $$s_{i_b}$$ является
Заметим, что аналогичные рассуждения справедливы и для случая, когда пара $$(L,M)$$ порождается более чем из двух состояний.
Теорема доказана.
Доказательство теоремы фактически содержит алгоритм распознавания проекции неизвестного входного слова по заданному множеству каналов, который сформулируем в явном виде.
Из множества пар $$(s_{i_1}; \bar {\nu_1}), \dots, (s_{i_r}; \bar {\nu_r})$$ выделяем все те его элементы, для которых $$\delta (s_{i_j}, \bar {\nu_j})=s_{k_f}*, f=1, \dots, b$$. Если этот элемент один, то проекция второго члена выделенной пары по каналам $$1, \dots, \nu$$ и есть искомое входное слово. Если число таких элементов больше двух, то у них упомянутые проекции вторых членов пар совпадают и являются искомым входным словом.
Рассмотрим пример. Пусть ОБПИ-автомат задан графом на рис.3.1. Условимся, что для наблюдения реакции выделен 1-й выходной канал автомата (по нему выдается левый символ выходной пары) и проекция неизвестного входного слова восстанавливается по 1-му входному каналу, т. е. $$\nu =\mu =1$$. Пусть $$S_0=\{1,2\}$$, на автомат подано неизвестное входное слово длиной 3, а по 1-му выходному каналу при этом наблюдалась реакция 0,1,1. Строим последовательность пар "состояние - входное слово", упомянутую в пункте 1 алгоритма: (1;10,00,10), (1;10,00,11), (1;10,00,00), (1;10,00,11), (1;10,01,10), (1;10,01,11), (1;10,01,00), (1;10,01,10), (1;11,00,10), (1;11,00,11), (1;11,00,00), (1;11,00,10), (1;11,01,10), (1;11,01,11), (1;11,01,00), (1;11,01,10), (2;10,10,10), (2;10,10,11), (2;10,11,10), (2;10,11,11), (2;11,10,10), (2;11,10,11), (2;11,11,10), (2;11,11,11).
(рис 3.1) Нетрудно убедиться, что упомянутое в пункте 2 алгоритма множество есть $$\hat S =\{1,2,3\}$$. Установочной последовательностью для рассматриваемого автомата с множеством допустимых начальных состояний $$\hat S$$ является, например, слово длиной два $$L=01,01$$. Пользуясь таблицей 3.1, по действительной реакции автомата на слово $$L$$ находим состояния $$\hat {s_{k_i}}$$, упомянутые в пункте 3 алгоритма.
| Состояние автомата | ВХОДНАЯ ПОСЛЕДОВАТЕЛЬ-НОСТЬ | Реакция автомата | Заключительное состояние |
|---|---|---|---|
| 1 | 01,01 | 00,00 | 1 |
| 2 | 01,01 | 10,10 | 1 |
| 3 | 01,01 | 10,00 | 1 |
Если $$\hat {s_{k_i}}=1$$, то ему соответствуют пары (1;10,00,00), (1;10,00,01), (1;10,01,00), (1;10,01,01), …, (1;11,01,00) и проекцией по 1-му входному каналу неизвестного входного слова является 1,0,0. При $$\hat {s_{k_i}}=2$$ искомая проекция есть 1,0,1 и, например, при $$\hat {s_{k_i}}=3$$ проекция равна 1,1,1.
Хотя теорема 3.1 позволила обосновать метод восстановления искомой проекции неизвестного входного слова, однако ответить с ее помощью на вопрос, является ли конкретный автомат ОБПИ-автоматом, сложно из-за отсутствия эффективного способа проверки условий теоремы. Ввиду этого ниже сформулируем еще одно необходимое и достаточное условие принадлежности автомата классу ОБПИ, но в других по сравнению с теоремой 3.1 терминах, допускающее простую проверку.
С этой целью по аналогии с [74] введем понятие
Аналогичное определение сформулируем и для случая, когда выходной символ $$\bar y$$ наблюдается не по всем, а только по $$\mu$$ выделенным каналам с номерами $$j_1 < j_2 < \dots j_m$$: дуга $$s_i \to s_j$$ имеет пометку $$pr_{j_1, j_2, \dots, j_{\mu}} \bar y$$, если
$$\exists {x \in X} \delta (s_i, \bar x)=s_j pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_j, \bar x)=pr_{j_1, j_2, \dots, j_{\mu}} \bar y$$Понятно, что две вершины графа могут связываться несколькими дугами с разными пометками.
Пусть $$\Gamma \{S_0\}$$ - множество всех состояний автомата $$A$$, достижимых из множества допустимых начальных состояний $$S_0$$ путями любой длины.
По графу автомата $$A$$ построим другой ориентированный конечный граф $$G(A)$$ следующим образом.
В графе $$G(A)$$ две вершины могут быть связаны несколькими дугами с разными пометками.
Пусть неизвестное входное слово необходимо восстановить по каналам с номерами $$i_1, \dots, i_{\nu}$$, где $$i_1<i_2<\dots < i_{\nu}$$.
Дугу $$\{s_k, s_l\} \to \{s_i, s_j\}$$ с пометкой $$pr_{j_1, j_2, \dots, j_mu}}$$ назовем выделенной, если
$$\exists_{x_1, x_2 \in X} \delta (s_k, \bar {x_1})= s_i \delta (s_l, \bar {x_2})=s_j pr_{j_1, \dots, j_{\mu}} \lambda (s_k, \bar {x_1})=pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_l, \bar {x_2})=pr_{j_1, j_2, \dots, j_{\mu}} \bat y \to pr_{i_1, \dots, i_{\nu}} \bar {x_1} \ne pr_{i_1, \dots, i_{\nu}} \bar {x_2}$$Из графа $$G(A)$$ удалим все вершины вида $$\{s,s\}$$ вместе с инцидентными им дугами, если последние, в свою очередь, инцидентны только вершинам такого же вида, а также изолированные вершины. Полученный в результате такого удаления ориентированный конечный граф назовем
Теорема 3.2. Автомат $$T(A)$$ является ОБПИ-автоматом тогда и только тогда, когда все пути в проверочном графе $$T(A)$$, ведущие в вершины вида $$\{s,s\}$$, не содержат выделенных дуг.
Необходимость. Пусть $$A$$ есть ОБПИ-автомат, но в $$T(A)$$ существует путь с выделенной дугой $$\{s_k, s_l\} \to \{s_i, s_j\}$$, ведущий в вершину вида $$\{s,s\}$$. Предположим, что $$\bar p$$ и $$\bar q$$ - два таких входных слова, что $$\delta (s_k, \bar p)=\delta (s_l, \bar q)=s$$, и они соответствуют пути по графу в $$T(A)$$, начинающемуся с упомянутой выделенной дуги. Последнее означает, что
$$\exists_{s_k, s_l \in T|{S_0\}} \exists_{\bar p, \bar q \in X*} pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_k, \bar p)=pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_l, \bar q) \to pr_{i_1, \dots, i_{\nu}} \bar p \ne pr_{i_1, \dots, i_{\nu}} \bar q$$Из сравнения этого высказывания с (3.1) вытекает, что $$A$$ не может быть ОБПИ-автоматом, а это противоречит исходной посылке.
Достаточность. Докажем ее методом от противного. Пусть $$A$$ не является ОБПИ-автоматом. Покажем тогда, что в графе $$T(A)$$ существует путь, ведущий в вершину вида $$\{s,s\}$$, содержащий выделенную дугу. Поскольку $$A$$ не есть ОБПИ-автомат, то
$$\exists {s_k, s_l \in S_0} \exists {p, q \in X*} \delta (s_k, \bar p) = \delta (s_l. \bar q)=s pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_k, \bar p)=pr_{j_1, j_2, \dots, j_{\mu}} \lambda (s_l, \bar q) \to pr_{i_1, \dots, i_{\nu}} \bar p \ne pr-\_{i_1}, \dots, i_{\nu}} \bar q$$Пусть $$\bar {x_p}$$ и $$\bar {x_q}$$ - первые слева символы в словах $$\bar p$$ и $$\bar q$$, проекции которых по каналам $$i_1, \dots, i_{\nu}$$ различны. Пусть при подаче этих символов автомат $$A$$ осуществляет переходы из состояний $$s_1, s_2$$ в состояния $$\hat {s_1}, \hat {s_2}$$ соответственно. Отсюда следует, что в графе $$T(A)$$ существует выделенная дуга, соединяющая вершины $$\{s_1, s_2\}$$ и $$\{\hat {s_1}, \hat {s_2}\}$$. Это означает существование в графе $$T(A)$$ пути из $$\{s_1, s_2\}$$ в $$\{s,s\}$$, первая дуга которого выделенная. Этим завершается доказательство достаточности условий теоремы.
В качестве примера на рис.3.2 изображен проверочный граф для автомата, представленного на рис.3.1, в предположении, что $$\nu = \mu =1$$. На рисунке двойные стрелки соответствуют выделенным дугам, над каждой дугой стоит соответствующая ей пометка. В этом проверочном графе все возможные пути, заканчивающиеся в вершинах вида $$\{s,s\}$$, могут начинаться только в вершинах $$\{1,1\}$$ либо $$\{3/3\}$$, при этом конечной вершиной в любом из этих путей является вершина $$\{1,1\}$$. Из рис.3.2 видно, что ни один из этих путей не содержит выделенных дуг, следовательно, рассматриваемый автомат относится к классу ОБПИ-автоматов.
(рис 3.2) Если задан автомат $$A$$ с $$n$$ входными и $$m$$ выходными каналами, то возникает вопрос: для каких подмножеств входных и выходных каналов он является ОБПИ-автоматом? Очевидно, что $$A$$ может не быть БПИ-автоматом в классическом смысле, но в то же время быть ОБПИ-автоматом, если восстановление входных сигналов производится по некоторому подмножеству входных каналов.
При отыскании всех возможных подмножеств входных и выходных каналов, для которых заданный автомат $$A$$ является ОБПИ-автоматом, в первую очередь представляет интерес случай, когда подмножество входных каналов - максимальное, а подмножество выходных каналов - минимальное по мощности. Далее такой автомат будем называть оптимальным. Это соответствует ситуации, когда при минимальных затратах, определяемых объемом наблюдаемой информации на выходах, удается однозначно восстановить максимальный объем информации, поступившей на вход автомата.
Опишем способ, позволяющий получить ответ на сформулированный выше вопрос. Условимся далее через $$A_M^R$$ обозначать автомат, у которого выходные символы наблюдаются по каналам с номерами из множества $$M$$, а восстановление сигналов ведется по каналам с номерами из множества $$R$$.
По графу автомата $$A$$ построим его проверочный граф $$T(A)$$ при $$\nu = n$$ и $$\mu =m$$, т. е. предполагая, что реакция $$A$$ наблюдается по всем его выходным каналам, а восстановление неизвестного входного слова также ведется по всем каналам. Используя $$T(A)$$, найдем в нем все пути, ведущие в вершины вида $$\{s,s\}$$, и образуем на этой основе множество $$\Gamma=\{\gamma_1, \gamma_2, \dots, \gamma_t\}$$ всех входящих в эти пути выделенных дуг. Если $$\Gamma = \varnothing$$, то по теореме 3.2 автомат $$A$$ есть ОБПИ-автомат, и при $$\mu = m$$ он будет, очевидно, таковым для любого $$\nu$$, где $$1 \le \nu \le n$$. Если $$\Gamma \ne \varnothing$$, то для каждого $$i=\overline {1,t}$$ построим множество $$R_i*$$ целых чисел, представляющих собой номера входных каналов, на которых на дуге $$\gamma_i$$ происходит потеря информации. Последнее означает, что если реакция автомата $$A$$ соответствует отметке дуги $$\gamma_i$$, то в каналах с номерами из множества $$R_t*$$ сигналы могут иметь значения как 0, так и 1. Используя множество $$R*=R_1Y \dots YR_t*$$, построим $$R=\{1, \dots, n\}\r*$$. Из способа построения следует, что, во-первых, $$R$$ содержит все те номера входных каналов, по каждому из которых и по их совокупности рассматриваемый автомат $$A$$ является ОБПИ-автоматом, и, во-вторых, $$R$$ - максимальный по мощности, сохраняющий свойство ОБПИ.
Далее через $$T_Q^R(A)$$ обозначим проверочный граф автомата $$A$$, предполагая, что наблюдение реакций ведется по каналам с номерами из множества $$Q$$, а восстановление неизвестного входного слова - по каналам с номерами из множества $$R$$.
Пусть $$M=\{1, \dots, m\}$$. Для каждого $$j, 1 \le j \le m$$, построим проверочный граф $$T_{M\\{j\}}^R(A)$$. Нетрудно сообразить, что дуги графа $$T_M^R(A)$$ одновременно являются и дугами графа $$T_{M\\{j\}}^R(A)$$, но в последнем, кроме того, могут появиться и новые. Если последний упомянутый граф удовлетворяет условиям теоремы 3.2, то, очевидно, $$j$$ -й выходной канал избыточен в том смысле, что отказ от наблюдения реакции по нему не повлияет на возможности восстановления неизвестного входного слова по каналам из множества $$R$$. Пусть $$M*=\{j_1, j_2, \dots, j_s\}$$ - множество номеров всех избыточных выходных каналов автомата $$A$$. Если $$M*= \varnothing$$, то построенный на 1-м этапе автомат $$A_M^R$$ - искомый. При $$M*\ne \varnothing$$ рассмотрим все возможные сочетания пар каналов из множества $$M*$$, число которых равно $$C_{|M|}^2$$. Для каждой из упомянутых пар каналов $$J+\{j_k, j_l\}$$ построим проверочный граф $$T_{M\J}^R(A)$$ и проверим для него выполнение условий теоремы 3.2. Если ни один из таких графов не удовлетворяет условиям этой теоремы, то автоматы $$A_{M\\{J_i\}}^R, i=\overline {1,s}$$, - искомые оптимальные автоматы. В противном случае формируем все возможные сочетания $$J$$ троек номеров из множества $$M*$$ и ищем среди проверочных графов $$T_{M\J}^R(A)$$ такие, которые удовлетворяют условиям теоремы 3.2. Указанный процесс продолжается до того момента, когда на очередном этапе все графы вида $$T_{M\J}^R(A)$$, где $$1 \le |J| \le s$$, не удовлетворяют условиям теоремы 3.2. Тогда автоматы $$A_{M\J}^R$$, построенные на предыдущем этапе и являющиеся ОБПИ-автоматами, - искомые оптимальные.
Отметим, что для поиска всех оптимальных ОБПИ-автоматов в худшем случае может потребоваться построение $$\sum_{i=1}^{s} C_s^i$$ различных проверочных графов, где $$s$$ - число избыточных выходных каналов автомата $$A$$.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.