При исследовании различных видов экспериментов с автоматами в классической теории чаще всего рассматриваются задачи построения минимальных по длине входных последовательностей. Других критериев, кроме длины, для сравнения различных экспериментов в этой теории не используется. Это обстоятельство объясняется тем, что по умолчанию предполагаются равными затраты на подачу различных входных символов, из которых составлена соответствующая входная последовательность, подаваемая в процессе проведения эксперимента.
Вместе с тем упомянутые затраты в действительности могут быть различны, и при подаче двух последовательностей одинаковой длины, отличных по составу входных символов, суммарные затраты могут существенно отличаться. Это, в частности, происходит в том случае, когда моделью автомата описывается некоторый технологический процесс, включающий в качестве входных воздействий разного рода механические действия. Последние могут потребовать выполнения значительной работы, измеряемой, к примеру, в эргах, или затрат мощности, измеряемой в ваттах, и т. п.
В силу сказанного возникает проблема оптимального управления экспериментом по критериям минимизации общих затрат. Заметим, что некоторые эксперименты с автоматами, в частности, эксперименты по распознаванию состояний, можно рассматривать как процессы управления. Например, синхронизацию автомата можно трактовать как процесс управления автоматом путем подачи входной последовательности, устанавливающей автомат в известное заключительное состояние независимо от того, в каком начальном состоянии он находился.
В теории оптимального управления как непрерывными [38], [40], [41], так и дискретными системами [14] [42], входные воздействия, обеспечивающие достижения цели управления, оцениваются по различным содержательным критериям.
Вообще говоря, подобного рода критерии могут быть использованы и при построении теории экспериментов с автоматами.
Хотя линейный автомат и является дискретной системой, однако его задание над конечным полем $$GF(p)$$ исключает возможность использования результатов упомянутой теории оптимального управления, поскольку последняя развита для случая вещественного и комплексного полей.
В этом разделе рассматриваются ЛА, фазовые пространства которых состоят из обобщенных состояний (ОС), определенных в лекции 3. Условимся считать, что в вектор-столбце, представляющем ОС, неопределенными являются последние $$\mu$$ его координат.
Напомним, что ЛА, для которого существует обобщенная синхронизирующая последовательность (ОСП), называется обобщенно синхронизируемым. Состояние, в котором рассматриваемый ЛА оказывается после подачи ОСП, называется
Поскольку перевод ЛА в одно и то же
Каждому входному символу $$\bar u$$ ЛА поставим в соответствие действительное число $$W(\bar u)$$, называемое весом символа. Весом входной последовательности $$u=\bar u(0), \bar u(1), \dots, \bar u(k)$$ назовем величину
$$W(\hat u)=\sum_{t=0}^kW(\bar u(t))$$Содержательно вес входной последовательности $$u$$ можно интерпретировать как суммарные затраты на ее подачу.
Рассмотрим следующую задачу. Пусть задан обобщенно синхронизируемый ЛА и некоторые
Прежде чем перейти к решению этой задачи, исследуем некоторые
Условимся ОСП наименьшей длины для ЛА называть далее минимальной ОСП и обозначать ее длину через $$k_{min}$$.
Теорема 18.1. Если ЛА является обобщенно синхронизируемым, то для любого $$k \ge k_{min}$$ множество синхросостояний, порождаемых всеми ОСП длины $$k$$, совпадает с множеством синхросостояний, порождаемых всеми ОСП длины $$k_{min}$$.
Доказательство. Предположим, что ОСП $$\bar u(0), \bar u(1), \dots, \bar u(k-1)$$ длины $$k$$ переводит ЛА в
Поскольку $$\bar u(0), \bar u(1), \dots, \bar u(k-1)$$ есть ОСП, то по теореме 1.18 $$[A^k]_{\mu}=[0]$$ и тогда (18.1) примет вид
$$[A^{k-1}B]_{\mu}\bar u(0)+\dots + [B]_{\mu}\bar u(k-1)=[\bar s]_{\mu}$$или
$$Q(k)u=[\bar s]_{\mu}$$где
$$Q(k)=[A^{k-1}B, \dots, B]_{\mu}, u=[\bar u(0), \dots, \bar u(k-1)]'$$Далее (18.2) будем интерпретировать как СЛАУ относительно неизвестных, являющихся координатами вектора $$\hat u$$ Как известно из алгебры [33], необходимым и достаточным условием разрешимости СЛАУ является представление столбца свободных членов $$[\bar s]_{\mu}$$ в виде линейной комбинации линейно независимых столбцов матрицы $$Q(k)$$ системы (18.2).
Поскольку для любого $$k \le k_{min}$$
$$[A^k}_{\mu}=[A^{k_{min}}A^{k-k_{min}}]_{\mu}=[A^{k_{min}}]_{\mu} A^{k-k_{min}}=[0]$$то
$$Q(k)=[[0], \dots, [0], A^{k_{min}-1}B, \dots, B]_{\mu}$$Таким образом, вектор $$[\bar s]_{\mu}$$ является линейной комбинацией линейно независимых столбцов матрицы (18.3) или, что то же самое, линейно независимых столбцов матрицы $$Q(k_{min})$$.
Следствие 1. Мощность множества всех различных синхросостояний ЛА, заданного над полем $$GF(p)$$, равна величине $$p^{\rank Q(k_{min})}$$.
Заметим, что нулевое
Следствие 2. Если $$[B]_{\mu} \ne [0]$$, то обобщенно синхронизируемый ЛА имеет ненулевое
Это вытекает из того, что если $$[B]_{\mu} \ne [0]$$, то $$\rank [A^{k_{min}-1}B, \dots, B]_{\mu} \ge 1$$, но тогда $$p^{rank Q(k_{min})}$$ для любого р.
Что касается определения множества всех обобщенных синхросостояний, то, как это следует из теоремы 18.1, оно сводится к нахождению линейного подпространства, порожденного базисом матрицы $$Q(k$$ ).
Теорема 18.2. Пусть $$\hat {u_{min}}$$ - минимальная ОСП, а $$u$$ - произвольная ОСП длины $$k \ge k_{min}$$, переводящая ЛА в одно и то же синхросостояние, и пусть $$W(\bar u) \ge 0$$ для любого входного символа этого ЛА. Тогда $$W(u_{min}) \le W(\hat u)$$.
Доказательство. Предположим, что ОСП $$\bar u(0), \bar u(1)m \dots, \bar u(k-1)$$, где $$k \ge k_{min}$$ переводит ЛА в
Учитывая, что в силу обобщенной синхронизируемости для всех $$k \ge k_{min}$$ справедливо равенство $$[A^k]_{\mu}=[0]$$, получаем
$$[0]+\dots +[0]+[A^{k_{min}-1}B]_{\mu}\bar u(k-k_{min})+ \dots +[B]_{\mu} \bar u(k-1)=[\bar s]_{\mu}$$где слагаемые, содержащие $$A_i$$ при $$I \ge k_{min} -1$$, равны [0]. Из полученного равенства следует, что ОСП $$\bar u(k-k_{min}), \dots, \bar u(k-1)$$ длины $$k_{min}$$ переводит ЛА в
Из этой теоремы вытекает следующий вывод: если весовая функция $$W(\bar u)$$ является неотрицательной, то минимальную по весу ОСП рассматриваемого обобщенно синхронизируемого ЛА следует искать среди ОСП минимальной длины.
В случае, когда весовая функция $$W(\bar u)<0$$ по крайней мере для одного входного символа ЛА, сформулированная в начале этого раздела задача имеет решение только тогда, когда длина искомой ОСП предполагается заранее заданной. Легко показать, что если на длину ОСП ограничений не накладывать, то для этого ЛА можно построить ОСП, вес которой будет меньше любого наперед заданного отрицательного числа.
Далее предполагается, что весовая функция $$W(\bar u)$$ является неотрицательной и матрица $$Q(k)$$ в СЛАУ (18.2), обозначаемая далее как $$Q$$, соответствует $$k=k_{min}$$.
Вернемся теперь к рассматриваемой задаче. Множество всех ОСП, переводящих ЛА в обобщенное состояние $$[\bar s]_{min}$$, как это следует из сказанного выше, должно удовлетворять равенству
$$D \hat u=[\br s]_{\mu}$$Здесь вектор-столбец $$\hat u=[u_1(0), \dots, u_l(0), \dots, u_1(k_{min}), \dots, u_l(k_{min})]'$$. В соответствии с формулировкой задачи искомое решение должно доставлять минимум весовой функции $$W(\hat u)$$. Учитывая, что переменные $$u_i(j), i= \overline {1,l}, j=\overline {0, k_{min}}$$ по смыслу задачи являются целыми неотрицательными числами, не превосходящими характеристику $$p$$ поля $$GF(p)$$, рассматриваемую задачу можно описать в следующем виде:
$$W(\hat u) \to min$$ $$D\hat u=[\bar s]_{\mu},\\ 0 \le u_i(j) \le p-1, 1 \le I \le l, 0 \le j \le k_{min}$$Условимся для упрощения обозначений координаты вектора $$\hat u$$ считать перенумерованными сверху вниз натуральными числами от 1 до $$lk_{min}$$. Тогда последнее неравенство примет вид
$$0 \le u_i \le p-1, 1 \le i \le lk_{min}$$Сформулированная задача относится к классу задач
Перепишем систему ограничений (18.5) в виде системы сравнений
$$Q\hat u=[\bar s]_{\mu} mod p$$Как известно, сравнение $$a \equiv b mod p$$ эквивалентно равенству $$a-b=pd$$ для некоторого целого $$d$$. Поэтому (18.7) эквивалентна СЛАУ в целых числах:
$$Q\hat u=[\bar s]_{\mu}+p\bar d$$где $$\bar d=(d_1, \dots, d_{\mu})'$$ - вектор-столбец, число координат которого равно числу уравнений в системе (18.7). Таким образом, поставленная задача эквивалентна следующей задаче
Заметим, что из (18.9) нетрудно установить диапазон изменения координат вектора $$\bar d$$:
$$0 \le d_i \le lk_{min}(p-1), 1 \le i \le \mu$$Подведя итоги изложенного, сформулируем следующее утверждение.
Теорема 18.3. Задача построения ОСП минимального веса, переводящей обобщенно синхронизируемый ЛА в заданное
В настоящее время известен ряд методов решения задач
Напомним кратко идею метода разветвленного поиска посредством разделения и оценки, относящегося к группе
Предположим, что поставлена следующая задача:
$$W(\hat u) \to min при \hat u \in U$$где $$U$$ - некоторое конечное множество целочисленных векторов. Используя верхние оценки для координат вектора $$\hat u$$, можно с помощью известных методов [28] свести задачу к двоичной. Поэтому далее будем считать, что $$U$$ есть множество двоичных векторов.
Используя дискретность множества $$U$$, представим его в форме некоторого разветвления. Вершине нулевого уровня, т. е. корню ветвления, соответствует все множество $$U$$ Для построения вершины уровня 1 выберем некоторую переменную $$u_i$$. Этот уровень содержит две вершины, которые соответствуют следующим подмножествам $$U$$: подмножество векторов $$U_{i_0},$$ для которых $$u_i=0$$, и подмножество $$U_{i1}$$, для которых $$u_i=1$$. Понятно, что эти два подмножества образуют
Перейдем теперь к понятию оценки. Предположим, что для каждой вершины $$U'$$ разветвления удалось получить оценку снизу для лучшего решения из множества $$U'$$:
$$f(U') \le min_{\hat u \in U'}W(\hat u)$$Функцию $$f$$ будем называть далее функцией оценки. Построим шаг за шагом, начиная с уровня 0, разветвления множества $$U$$. Пусть для некоторого допустимого вектора $$u_0$$ известно значение $$W(u_0)$$. Предположим, что для некоторой вершины $$U'$$ построенного разветвления имеет оценку
$$f(U') > W(u_0)$$Следовательно, по определению $$f$$ множество $$U'$$ не содержит
Заметим, что выбор множества, которое необходимо разделить на очередном этапе, и выбор переменной для разделения в общем случае произволен. Вместе с тем осуществлять такой выбор в каждом конкретном случае необходимо с учетом специфики задачи. Для получения оценок весовой функции часто решается соответствующая непрерывная
Ниже рассматривается задача, аналогичная задаче предыдущего раздела, где вместо минимизации весовой функции $$W(u)$$ будет осуществляться минимизацией иной функции.
Предварительно дадим краткое содержательное пояснение. Известно, что для цифровых устройств, реализованных с применением так называемой К-МОП- технологии, из двух равных по длине входных последовательностей более предпочтительной является та из них, у которой меньше число перепадов. Под перепадом сигналов в последовательности понимается наличие ситуации, когда два соседних символа в этой последовательности инверсны друг другу. К примеру, последовательность 00101011 имеет 5 перепадов.
Введем в рассмотрение следующую функцию:
$$G(a,b)= \begin {cases} 0,\ если a=b,\\ 1,\ если a \ne b \end {cases}$$Если $$a$$ и $$b$$ - два символа некоторой входной последовательности, то по значению $$G(a,b)$$ можно судить о наличии или отсутствии перепада сигналов. Тогда задача построения ОСП $$\hat u=u_1, u_2, \dots, u_{lk_{min}-1}$$ с минимальным числом перепадов сигналов, переводящей обобщенно синхронизируемый автомат в заданное ОС $$[\bar s]_{\mu}$$, формулируется следующим образом:
$$\sum_{i=1}^{lk_{min}-1}G(u_i, u_{i+1}) \to min$$ $$Q \hat u=[\bar s]_{\mu}+p\bar d$$ $$0 \le u_i \le p-1, 1 \le I \le lk_{min}$$Заметим, что количество переменных в этой задаче может быть уменьшено. Действительно, некоторые элементы матрицы $$Q$$ могут быть нулевыми и потому в левой части системы (18.12) соответствующие переменные будут отсутствовать. Далее эти переменные будем именовать независимыми, а остальные переменные - зависимыми. Предположим, что в оптимальном плане $$\hat u$$ задачи (18.11)-(18.13) $$u_i$$ и $$u_j$$ есть значения зависимых координат, а координаты с номерами $$i+1, i+2, \dots, j-1$$ являются независимыми. Тогда если $$u_i=u_j$$, то на участке ( $$u_i, u_{i+1}, \dots, u_{j-1}, u_j$$ ) входной последовательности $$\hat u$$ перепады сигналов отсутствуют, а если $$u_i \ne u_j$$, то имеется ровно один перепад. Понятно, что если на упомянутом участке входной последовательности $$\hat u$$ исключить переменные $$u_i, u_{i+1}, \dots, u_j-1}$$, то значение целевой функции (18.11) на укороченной таким образом входной последовательности не изменится. Поэтому целевую функцию (18.11) можно рассматривать на множестве векторов, составленных только из зависимых координат вектора $$\hat u$$. Видоизмененную таким образом целевую функцию будем называть приведенной, так же будем называть и соответствующую задачу.
Ясно, что
Из вида целевой функции (18.11) следует, что она не является линейной. Вместе с тем покажем, что исходная задача (18.11)-(18.13) может быть сведена к линейной задаче за счет введения дополнительных переменных.
Рассмотрим задачу
$$\sum_{i=1}^{lk_{min}-1}g_i \to min$$со следующими ограничениями:
$$Q\hat u=[\bar s]_{\mu}+p \bar d$$ $$- \le u_i \le p-1, 1 \le i \le lk_{min}$$ $$-g_i(p-1) \le u_i -u_{i+1} \le g_i(p-1), g_i \in \{0,1\}, 1 \le i \le lk_{min}-1$$Введем следующее обозначение: $$\bar g=(g_1, g_2, \dots, g_{lk_{min}-1})$$.
Теорема 18.4. Если $$(\hat u, \bar d, \bar g)$$ -
Доказательство. Пусть $$(\hat u, \bar d)$$ есть
При ограничении (18.16) на значения $$u_i$$ последнее неравенство также выполняется. Таким образом, поскольку ограничения на вектор $$\hat u$$ в задачах (18.11)-(18.13) и (18.14)-(18.17) совпадают, то для последней задачи $$(\hat u, \bat d, \bar g)$$ является допустимым планом, причем значения целевых функций соответствующих задач на двух приведенных планах совпадают.
Итак, всякому допустимому плану $$(\hat u, \bar d)$$ задачи (18.11)-(18.13) соответствует допустимый план $$(\hat u, \bar d, \bar g)$$ задачи (18.14)-(18.17) с одинаковыми значениями целевых функций, а на всяком оптимальном плане $$(\hat u, \bar d, \hat g)$$ задачи (18.14)-(18.17) значение целевой функции (18.14) совпадает со значением целевой функции (18.11) на плане $$(\hat u, \bar d)$$ задачи (18.11)-(18.13). Отсюда следует, что если $$(\hat u, \bar d, \bar g)$$ есть
Из теоремы 18.4 следует, что рассматриваемая нами задача (18.11)-(18.13) может быть сведена к линейной задаче и по найденному
Проиллюстрируем изложенное на примере ЛА, заданного над полем $$GF(2)$$ следующими характеристическими матрицами:
$$A= \left [ \begin {matrix} 0000\\ 1000\\ 1100\\ 1110 \end {matrix} \right ], B= \left [ \begin {matrix} 1000\\ 0100\\ 0010\\ 0001 \end {matrix} \right ] $$Система уравнений перехода в координатной форме для этого ЛА имеет следующий вид:
$$s_1(t+1)=u_1(t),\\ s_2(t+1)=s_1(t)+u_2(t),\\ s_3(t+1)=s_1(t)+ s_2(t)+u_3(t),\\ s_4(t+1)=s_1(t)+s_2(t)+s_3(t)+u_4(t).$$Пусть $$\mu =3$$ и требуется установить этот ЛА в обобщенное состояние $$\bar s=(1,1,1,x)'$$. Начнем с проверки того, является ли заданный ЛА обобщенно синхронизируемым. Вычислим с этой целью матрицы
$$A^2= \left [ \begin {matrix} 0000\\ 0000\\ 1000\\ 0100\\ \end {matrix} \right ] A^3= \left [ \begin {matrix} 0000\\ 0000\\ 0000\\ 1000 \end {matrix} \right ] $$Отсюда видно, что необходимое условие обобщенной синхронизируемости $$[A]_{\mu}$$ выполняется при $$k=3$$ и не выполняется при $$k<3$$. Следовательно, минимальная ОСП для данного ЛА имеет длину 3.
Найдем матрицу линейных ограничений на допустимый план
$$Q=[A^2B,AB,B]_3= \left [ \begin {matrix} 000000001000\\ 000010000100\\ 100011000010 \end {matrix} \right ] $$Система сравнений $$Q \hat u=[\bar s]_{\mu} mod 2$$, представляя собой линейные ограничения на переменные задачи, принимает вид
$$Q\hat u=(1,1,1) mod 2$$где
$$\hat u=(u_1(0), \dots, u_4(0), u_1(1), \dots, u_4(1), u_1(2), \dots, u_4(2))'=(u_1, u_1, \dots, u_{12})'$$Перепишем эту систему в координатной форме:
$$u_1(2) \equiv 1 mod 2\\ u_1(1)+u_2(2) \equiv 1 mod 2\\ u_1(0)+u_1(1)+u_2(1)+u_3(2) \equiv 1 mod 2$$В соответствии с изложенным выше эквивалентная
где $$u_j \in \{0,1\}, d_i$$ - целые неотрицательные числа, $$2 \le i \le 3, 1 \le j \le 12$$.
Из полученных уравнений вытекает, что $$d_1=d_2=0, d_3 \le 1.$$ Тогда исходная задача построения ОСП с минимальным числом перепадов сигналов для заданного ЛА эквивалентна задаче целочисленного
Заметим, что в данном случае линейность задачи не столь существенна, поскольку на этапе оценки решать непрерывные задачи большой размерности с помощью
где $$d_3, u_j \in \{0,1\}, d_i$$ - целые неотрицательные числа, $$1 \le i \le 12$$. Формально эта задача имеет 13 переменных.
Способом, описанным выше, сократим количество переменных до 6, оставляя для рассмотрения лишь зависимые переменные
$$u_1, u_5, u_6, u_9, u_{10}, u_{11}$$Таким образом, приведенная задача примет вид
$$W(\hat u)=G(u_1, u_5)+G(u_5, u_6)+G(u_6, u_9)+G(u_9, u_{10})+G(u_{10}, u_{11}) \to min,\\ u_9-2d_1=1,\\ u_5+u_{10}-2d_2=1,\\ u_1+u_5+u_6+u_{11}-2d_3=1,\\ $$где
$$d_3, u_i \in \{0,1\}, 1 \le i \le 12$$Из условия $$u_5+u_{10}=1$$ следует, что $$u_5 \ne u_{10}$$, поэтому среди пар $$(u_5, u_6),(u_6, u_9),(u_9, u_{10})$$ соседних координат вектора приведенной задачи имеется не менее одного перепада.
Таким образом, получаем оценку $$W(\hat u*) \ge 1$$ для
Разделим множество двоичных векторов задачи относительно переменной $$d_3$$. При $$d_3=1$$ получаем $$u_1+u_5+u_6+u_{11}=3$$, из чего следует, что ровно одно из чисел равно 0, остальные равны 1.
Если $$u_1 \ne u_5$$, то среди пар $$(u_1, u_5), (u_5, u_6),(u_6, u_9), (u_9, u_{10})$$ имеется не менее двух перепадов сигналов, поэтому рассмотрим случай $$u_1=u_5$$. Тогда получаем $$u_1=u_5=1, u_{10}=0, u_6 \ne u_{11}$$.
Если $$u_{10} \ne u_{11}$$, то снова получается по крайней мере два перепада сигналов среди пар $$(u_1, u_5), (u_5, u_6),(u_6, u_9), (u_9, u_{10}), (u_{10}, u_{11})$$, в случае же $$u_{10}=u_{11}$$ получаем $$u_{11}=0, u_6=1$$ и среди пар соседних координат вектора (1,1,1,1,0,0) имеется один перепад сигналов. Это значение соответствует минимальной оценке функции $$W$$, поэтому последний план является оптимальным планом приведенной задачи.
Для получения решения исходной задачи дополним полученный вектор значениями независимых координат так, как это было описано выше:
$$\hat u*=(\mathdf 1,1,1,1, \mathdf 1, \mathdf 1,1,1, \mathdf 1,0,0,0)'$$Значения зависимых координат, по которым достраивался
Из полученного
Заметим в заключение, что специфика области применения предложенных методов в большинстве случаев позволяет понизить размерность задачи оптимизации путем сокращения количества ее переменных.
Что касается этапа оценки при решении задачи в используемом методе ветвей и границ, то в общем случае он сводится к решению соответствующих непрерывных задач.
Однако при $$p=2$$ их решение значительно упрощается, поскольку коэффициенты в ограничениях этих задач равны 0 или 1. Таким образом, специфика рассматриваемой задачи значительно сокращает трудность ее решения по сравнению со многими другими задачами, решаемыми с помощью
При исследовании различных видов экспериментов с автоматами в классической теории чаще всего рассматриваются задачи построения минимальных по длине входных последовательностей. Других критериев, кроме длины, для сравнения различных экспериментов в этой теории не используется. Это обстоятельство объясняется тем, что по умолчанию предполагаются равными затраты на подачу различных входных символов, из которых составлена соответствующая входная последовательность, подаваемая в процессе проведения эксперимента.
Вместе с тем упомянутые затраты в действительности могут быть различны, и при подаче двух последовательностей одинаковой длины, отличных по составу входных символов, суммарные затраты могут существенно отличаться. Это, в частности, происходит в том случае, когда моделью автомата описывается некоторый технологический процесс, включающий в качестве входных воздействий разного рода механические действия. Последние могут потребовать выполнения значительной работы, измеряемой, к примеру, в эргах, или затрат мощности, измеряемой в ваттах, и т. п.
В силу сказанного возникает проблема оптимального управления экспериментом по критериям минимизации общих затрат. Заметим, что некоторые эксперименты с автоматами, в частности, эксперименты по распознаванию состояний, можно рассматривать как процессы управления. Например, синхронизацию автомата можно трактовать как процесс управления автоматом путем подачи входной последовательности, устанавливающей автомат в известное заключительное состояние независимо от того, в каком начальном состоянии он находился.
В теории оптимального управления как непрерывными [38], [40], [41], так и дискретными системами [14] [42], входные воздействия, обеспечивающие достижения цели управления, оцениваются по различным содержательным критериям.
Вообще говоря, подобного рода критерии могут быть использованы и при построении теории экспериментов с автоматами.
Хотя линейный автомат и является дискретной системой, однако его задание над конечным полем $$GF(p)$$ исключает возможность использования результатов упомянутой теории оптимального управления, поскольку последняя развита для случая вещественного и комплексного полей.
В этом разделе рассматриваются ЛА, фазовые пространства которых состоят из обобщенных состояний (ОС), определенных в лекции 3. Условимся считать, что в вектор-столбце, представляющем ОС, неопределенными являются последние $$\mu$$ его координат.
Напомним, что ЛА, для которого существует обобщенная синхронизирующая последовательность (ОСП), называется обобщенно синхронизируемым. Состояние, в котором рассматриваемый ЛА оказывается после подачи ОСП, называется
Поскольку перевод ЛА в одно и то же
Каждому входному символу $$\bar u$$ ЛА поставим в соответствие действительное число $$W(\bar u)$$, называемое весом символа. Весом входной последовательности $$u=\bar u(0), \bar u(1), \dots, \bar u(k)$$ назовем величину
$$W(\hat u)=\sum_{t=0}^kW(\bar u(t))$$Содержательно вес входной последовательности $$u$$ можно интерпретировать как суммарные затраты на ее подачу.
Рассмотрим следующую задачу. Пусть задан обобщенно синхронизируемый ЛА и некоторые
Прежде чем перейти к решению этой задачи, исследуем некоторые
Условимся ОСП наименьшей длины для ЛА называть далее минимальной ОСП и обозначать ее длину через $$k_{min}$$.
Теорема 18.1. Если ЛА является обобщенно синхронизируемым, то для любого $$k \ge k_{min}$$ множество синхросостояний, порождаемых всеми ОСП длины $$k$$, совпадает с множеством синхросостояний, порождаемых всеми ОСП длины $$k_{min}$$.
Доказательство. Предположим, что ОСП $$\bar u(0), \bar u(1), \dots, \bar u(k-1)$$ длины $$k$$ переводит ЛА в
Поскольку $$\bar u(0), \bar u(1), \dots, \bar u(k-1)$$ есть ОСП, то по теореме 1.18 $$[A^k]_{\mu}=[0]$$ и тогда (18.1) примет вид
$$[A^{k-1}B]_{\mu}\bar u(0)+\dots + [B]_{\mu}\bar u(k-1)=[\bar s]_{\mu}$$или
$$Q(k)u=[\bar s]_{\mu}$$где
$$Q(k)=[A^{k-1}B, \dots, B]_{\mu}, u=[\bar u(0), \dots, \bar u(k-1)]'$$Далее (18.2) будем интерпретировать как СЛАУ относительно неизвестных, являющихся координатами вектора $$\hat u$$ Как известно из алгебры [33], необходимым и достаточным условием разрешимости СЛАУ является представление столбца свободных членов $$[\bar s]_{\mu}$$ в виде линейной комбинации линейно независимых столбцов матрицы $$Q(k)$$ системы (18.2).
Поскольку для любого $$k \le k_{min}$$
$$[A^k}_{\mu}=[A^{k_{min}}A^{k-k_{min}}]_{\mu}=[A^{k_{min}}]_{\mu} A^{k-k_{min}}=[0]$$то
$$Q(k)=[[0], \dots, [0], A^{k_{min}-1}B, \dots, B]_{\mu}$$Таким образом, вектор $$[\bar s]_{\mu}$$ является линейной комбинацией линейно независимых столбцов матрицы (18.3) или, что то же самое, линейно независимых столбцов матрицы $$Q(k_{min})$$.
Следствие 1. Мощность множества всех различных синхросостояний ЛА, заданного над полем $$GF(p)$$, равна величине $$p^{\rank Q(k_{min})}$$.
Заметим, что нулевое
Следствие 2. Если $$[B]_{\mu} \ne [0]$$, то обобщенно синхронизируемый ЛА имеет ненулевое
Это вытекает из того, что если $$[B]_{\mu} \ne [0]$$, то $$\rank [A^{k_{min}-1}B, \dots, B]_{\mu} \ge 1$$, но тогда $$p^{rank Q(k_{min})}$$ для любого р.
Что касается определения множества всех обобщенных синхросостояний, то, как это следует из теоремы 18.1, оно сводится к нахождению линейного подпространства, порожденного базисом матрицы $$Q(k$$ ).
Теорема 18.2. Пусть $$\hat {u_{min}}$$ - минимальная ОСП, а $$u$$ - произвольная ОСП длины $$k \ge k_{min}$$, переводящая ЛА в одно и то же синхросостояние, и пусть $$W(\bar u) \ge 0$$ для любого входного символа этого ЛА. Тогда $$W(u_{min}) \le W(\hat u)$$.
Доказательство. Предположим, что ОСП $$\bar u(0), \bar u(1)m \dots, \bar u(k-1)$$, где $$k \ge k_{min}$$ переводит ЛА в
Учитывая, что в силу обобщенной синхронизируемости для всех $$k \ge k_{min}$$ справедливо равенство $$[A^k]_{\mu}=[0]$$, получаем
$$[0]+\dots +[0]+[A^{k_{min}-1}B]_{\mu}\bar u(k-k_{min})+ \dots +[B]_{\mu} \bar u(k-1)=[\bar s]_{\mu}$$где слагаемые, содержащие $$A_i$$ при $$I \ge k_{min} -1$$, равны [0]. Из полученного равенства следует, что ОСП $$\bar u(k-k_{min}), \dots, \bar u(k-1)$$ длины $$k_{min}$$ переводит ЛА в
Из этой теоремы вытекает следующий вывод: если весовая функция $$W(\bar u)$$ является неотрицательной, то минимальную по весу ОСП рассматриваемого обобщенно синхронизируемого ЛА следует искать среди ОСП минимальной длины.
В случае, когда весовая функция $$W(\bar u)<0$$ по крайней мере для одного входного символа ЛА, сформулированная в начале этого раздела задача имеет решение только тогда, когда длина искомой ОСП предполагается заранее заданной. Легко показать, что если на длину ОСП ограничений не накладывать, то для этого ЛА можно построить ОСП, вес которой будет меньше любого наперед заданного отрицательного числа.
Далее предполагается, что весовая функция $$W(\bar u)$$ является неотрицательной и матрица $$Q(k)$$ в СЛАУ (18.2), обозначаемая далее как $$Q$$, соответствует $$k=k_{min}$$.
Вернемся теперь к рассматриваемой задаче. Множество всех ОСП, переводящих ЛА в обобщенное состояние $$[\bar s]_{min}$$, как это следует из сказанного выше, должно удовлетворять равенству
$$D \hat u=[\br s]_{\mu}$$Здесь вектор-столбец $$\hat u=[u_1(0), \dots, u_l(0), \dots, u_1(k_{min}), \dots, u_l(k_{min})]'$$. В соответствии с формулировкой задачи искомое решение должно доставлять минимум весовой функции $$W(\hat u)$$. Учитывая, что переменные $$u_i(j), i= \overline {1,l}, j=\overline {0, k_{min}}$$ по смыслу задачи являются целыми неотрицательными числами, не превосходящими характеристику $$p$$ поля $$GF(p)$$, рассматриваемую задачу можно описать в следующем виде:
$$W(\hat u) \to min$$ $$D\hat u=[\bar s]_{\mu},\\ 0 \le u_i(j) \le p-1, 1 \le I \le l, 0 \le j \le k_{min}$$Условимся для упрощения обозначений координаты вектора $$\hat u$$ считать перенумерованными сверху вниз натуральными числами от 1 до $$lk_{min}$$. Тогда последнее неравенство примет вид
$$0 \le u_i \le p-1, 1 \le i \le lk_{min}$$Сформулированная задача относится к классу задач
Перепишем систему ограничений (18.5) в виде системы сравнений
$$Q\hat u=[\bar s]_{\mu} mod p$$Как известно, сравнение $$a \equiv b mod p$$ эквивалентно равенству $$a-b=pd$$ для некоторого целого $$d$$. Поэтому (18.7) эквивалентна СЛАУ в целых числах:
$$Q\hat u=[\bar s]_{\mu}+p\bar d$$где $$\bar d=(d_1, \dots, d_{\mu})'$$ - вектор-столбец, число координат которого равно числу уравнений в системе (18.7). Таким образом, поставленная задача эквивалентна следующей задаче
Заметим, что из (18.9) нетрудно установить диапазон изменения координат вектора $$\bar d$$:
$$0 \le d_i \le lk_{min}(p-1), 1 \le i \le \mu$$Подведя итоги изложенного, сформулируем следующее утверждение.
Теорема 18.3. Задача построения ОСП минимального веса, переводящей обобщенно синхронизируемый ЛА в заданное
В настоящее время известен ряд методов решения задач
Напомним кратко идею метода разветвленного поиска посредством разделения и оценки, относящегося к группе
Предположим, что поставлена следующая задача:
$$W(\hat u) \to min при \hat u \in U$$где $$U$$ - некоторое конечное множество целочисленных векторов. Используя верхние оценки для координат вектора $$\hat u$$, можно с помощью известных методов [28] свести задачу к двоичной. Поэтому далее будем считать, что $$U$$ есть множество двоичных векторов.
Используя дискретность множества $$U$$, представим его в форме некоторого разветвления. Вершине нулевого уровня, т. е. корню ветвления, соответствует все множество $$U$$ Для построения вершины уровня 1 выберем некоторую переменную $$u_i$$. Этот уровень содержит две вершины, которые соответствуют следующим подмножествам $$U$$: подмножество векторов $$U_{i_0},$$ для которых $$u_i=0$$, и подмножество $$U_{i1}$$, для которых $$u_i=1$$. Понятно, что эти два подмножества образуют
Перейдем теперь к понятию оценки. Предположим, что для каждой вершины $$U'$$ разветвления удалось получить оценку снизу для лучшего решения из множества $$U'$$:
$$f(U') \le min_{\hat u \in U'}W(\hat u)$$Функцию $$f$$ будем называть далее функцией оценки. Построим шаг за шагом, начиная с уровня 0, разветвления множества $$U$$. Пусть для некоторого допустимого вектора $$u_0$$ известно значение $$W(u_0)$$. Предположим, что для некоторой вершины $$U'$$ построенного разветвления имеет оценку
$$f(U') > W(u_0)$$Следовательно, по определению $$f$$ множество $$U'$$ не содержит
Заметим, что выбор множества, которое необходимо разделить на очередном этапе, и выбор переменной для разделения в общем случае произволен. Вместе с тем осуществлять такой выбор в каждом конкретном случае необходимо с учетом специфики задачи. Для получения оценок весовой функции часто решается соответствующая непрерывная
Ниже рассматривается задача, аналогичная задаче предыдущего раздела, где вместо минимизации весовой функции $$W(u)$$ будет осуществляться минимизацией иной функции.
Предварительно дадим краткое содержательное пояснение. Известно, что для цифровых устройств, реализованных с применением так называемой К-МОП- технологии, из двух равных по длине входных последовательностей более предпочтительной является та из них, у которой меньше число перепадов. Под перепадом сигналов в последовательности понимается наличие ситуации, когда два соседних символа в этой последовательности инверсны друг другу. К примеру, последовательность 00101011 имеет 5 перепадов.
Введем в рассмотрение следующую функцию:
$$G(a,b)= \begin {cases} 0,\ если a=b,\\ 1,\ если a \ne b \end {cases}$$Если $$a$$ и $$b$$ - два символа некоторой входной последовательности, то по значению $$G(a,b)$$ можно судить о наличии или отсутствии перепада сигналов. Тогда задача построения ОСП $$\hat u=u_1, u_2, \dots, u_{lk_{min}-1}$$ с минимальным числом перепадов сигналов, переводящей обобщенно синхронизируемый автомат в заданное ОС $$[\bar s]_{\mu}$$, формулируется следующим образом:
$$\sum_{i=1}^{lk_{min}-1}G(u_i, u_{i+1}) \to min$$ $$Q \hat u=[\bar s]_{\mu}+p\bar d$$ $$0 \le u_i \le p-1, 1 \le I \le lk_{min}$$Заметим, что количество переменных в этой задаче может быть уменьшено. Действительно, некоторые элементы матрицы $$Q$$ могут быть нулевыми и потому в левой части системы (18.12) соответствующие переменные будут отсутствовать. Далее эти переменные будем именовать независимыми, а остальные переменные - зависимыми. Предположим, что в оптимальном плане $$\hat u$$ задачи (18.11)-(18.13) $$u_i$$ и $$u_j$$ есть значения зависимых координат, а координаты с номерами $$i+1, i+2, \dots, j-1$$ являются независимыми. Тогда если $$u_i=u_j$$, то на участке ( $$u_i, u_{i+1}, \dots, u_{j-1}, u_j$$ ) входной последовательности $$\hat u$$ перепады сигналов отсутствуют, а если $$u_i \ne u_j$$, то имеется ровно один перепад. Понятно, что если на упомянутом участке входной последовательности $$\hat u$$ исключить переменные $$u_i, u_{i+1}, \dots, u_j-1}$$, то значение целевой функции (18.11) на укороченной таким образом входной последовательности не изменится. Поэтому целевую функцию (18.11) можно рассматривать на множестве векторов, составленных только из зависимых координат вектора $$\hat u$$. Видоизмененную таким образом целевую функцию будем называть приведенной, так же будем называть и соответствующую задачу.
Ясно, что
Из вида целевой функции (18.11) следует, что она не является линейной. Вместе с тем покажем, что исходная задача (18.11)-(18.13) может быть сведена к линейной задаче за счет введения дополнительных переменных.
Рассмотрим задачу
$$\sum_{i=1}^{lk_{min}-1}g_i \to min$$со следующими ограничениями:
$$Q\hat u=[\bar s]_{\mu}+p \bar d$$ $$- \le u_i \le p-1, 1 \le i \le lk_{min}$$ $$-g_i(p-1) \le u_i -u_{i+1} \le g_i(p-1), g_i \in \{0,1\}, 1 \le i \le lk_{min}-1$$Введем следующее обозначение: $$\bar g=(g_1, g_2, \dots, g_{lk_{min}-1})$$.
Теорема 18.4. Если $$(\hat u, \bar d, \bar g)$$ -
Доказательство. Пусть $$(\hat u, \bar d)$$ есть
При ограничении (18.16) на значения $$u_i$$ последнее неравенство также выполняется. Таким образом, поскольку ограничения на вектор $$\hat u$$ в задачах (18.11)-(18.13) и (18.14)-(18.17) совпадают, то для последней задачи $$(\hat u, \bat d, \bar g)$$ является допустимым планом, причем значения целевых функций соответствующих задач на двух приведенных планах совпадают.
Итак, всякому допустимому плану $$(\hat u, \bar d)$$ задачи (18.11)-(18.13) соответствует допустимый план $$(\hat u, \bar d, \bar g)$$ задачи (18.14)-(18.17) с одинаковыми значениями целевых функций, а на всяком оптимальном плане $$(\hat u, \bar d, \hat g)$$ задачи (18.14)-(18.17) значение целевой функции (18.14) совпадает со значением целевой функции (18.11) на плане $$(\hat u, \bar d)$$ задачи (18.11)-(18.13). Отсюда следует, что если $$(\hat u, \bar d, \bar g)$$ есть
Из теоремы 18.4 следует, что рассматриваемая нами задача (18.11)-(18.13) может быть сведена к линейной задаче и по найденному
Проиллюстрируем изложенное на примере ЛА, заданного над полем $$GF(2)$$ следующими характеристическими матрицами:
$$A= \left [ \begin {matrix} 0000\\ 1000\\ 1100\\ 1110 \end {matrix} \right ], B= \left [ \begin {matrix} 1000\\ 0100\\ 0010\\ 0001 \end {matrix} \right ] $$Система уравнений перехода в координатной форме для этого ЛА имеет следующий вид:
$$s_1(t+1)=u_1(t),\\ s_2(t+1)=s_1(t)+u_2(t),\\ s_3(t+1)=s_1(t)+ s_2(t)+u_3(t),\\ s_4(t+1)=s_1(t)+s_2(t)+s_3(t)+u_4(t).$$Пусть $$\mu =3$$ и требуется установить этот ЛА в обобщенное состояние $$\bar s=(1,1,1,x)'$$. Начнем с проверки того, является ли заданный ЛА обобщенно синхронизируемым. Вычислим с этой целью матрицы
$$A^2= \left [ \begin {matrix} 0000\\ 0000\\ 1000\\ 0100\\ \end {matrix} \right ] A^3= \left [ \begin {matrix} 0000\\ 0000\\ 0000\\ 1000 \end {matrix} \right ] $$Отсюда видно, что необходимое условие обобщенной синхронизируемости $$[A]_{\mu}$$ выполняется при $$k=3$$ и не выполняется при $$k<3$$. Следовательно, минимальная ОСП для данного ЛА имеет длину 3.
Найдем матрицу линейных ограничений на допустимый план
$$Q=[A^2B,AB,B]_3= \left [ \begin {matrix} 000000001000\\ 000010000100\\ 100011000010 \end {matrix} \right ] $$Система сравнений $$Q \hat u=[\bar s]_{\mu} mod 2$$, представляя собой линейные ограничения на переменные задачи, принимает вид
$$Q\hat u=(1,1,1) mod 2$$где
$$\hat u=(u_1(0), \dots, u_4(0), u_1(1), \dots, u_4(1), u_1(2), \dots, u_4(2))'=(u_1, u_1, \dots, u_{12})'$$Перепишем эту систему в координатной форме:
$$u_1(2) \equiv 1 mod 2\\ u_1(1)+u_2(2) \equiv 1 mod 2\\ u_1(0)+u_1(1)+u_2(1)+u_3(2) \equiv 1 mod 2$$В соответствии с изложенным выше эквивалентная
где $$u_j \in \{0,1\}, d_i$$ - целые неотрицательные числа, $$2 \le i \le 3, 1 \le j \le 12$$.
Из полученных уравнений вытекает, что $$d_1=d_2=0, d_3 \le 1.$$ Тогда исходная задача построения ОСП с минимальным числом перепадов сигналов для заданного ЛА эквивалентна задаче целочисленного
Заметим, что в данном случае линейность задачи не столь существенна, поскольку на этапе оценки решать непрерывные задачи большой размерности с помощью
где $$d_3, u_j \in \{0,1\}, d_i$$ - целые неотрицательные числа, $$1 \le i \le 12$$. Формально эта задача имеет 13 переменных.
Способом, описанным выше, сократим количество переменных до 6, оставляя для рассмотрения лишь зависимые переменные
$$u_1, u_5, u_6, u_9, u_{10}, u_{11}$$Таким образом, приведенная задача примет вид
$$W(\hat u)=G(u_1, u_5)+G(u_5, u_6)+G(u_6, u_9)+G(u_9, u_{10})+G(u_{10}, u_{11}) \to min,\\ u_9-2d_1=1,\\ u_5+u_{10}-2d_2=1,\\ u_1+u_5+u_6+u_{11}-2d_3=1,\\ $$где
$$d_3, u_i \in \{0,1\}, 1 \le i \le 12$$Из условия $$u_5+u_{10}=1$$ следует, что $$u_5 \ne u_{10}$$, поэтому среди пар $$(u_5, u_6),(u_6, u_9),(u_9, u_{10})$$ соседних координат вектора приведенной задачи имеется не менее одного перепада.
Таким образом, получаем оценку $$W(\hat u*) \ge 1$$ для
Разделим множество двоичных векторов задачи относительно переменной $$d_3$$. При $$d_3=1$$ получаем $$u_1+u_5+u_6+u_{11}=3$$, из чего следует, что ровно одно из чисел равно 0, остальные равны 1.
Если $$u_1 \ne u_5$$, то среди пар $$(u_1, u_5), (u_5, u_6),(u_6, u_9), (u_9, u_{10})$$ имеется не менее двух перепадов сигналов, поэтому рассмотрим случай $$u_1=u_5$$. Тогда получаем $$u_1=u_5=1, u_{10}=0, u_6 \ne u_{11}$$.
Если $$u_{10} \ne u_{11}$$, то снова получается по крайней мере два перепада сигналов среди пар $$(u_1, u_5), (u_5, u_6),(u_6, u_9), (u_9, u_{10}), (u_{10}, u_{11})$$, в случае же $$u_{10}=u_{11}$$ получаем $$u_{11}=0, u_6=1$$ и среди пар соседних координат вектора (1,1,1,1,0,0) имеется один перепад сигналов. Это значение соответствует минимальной оценке функции $$W$$, поэтому последний план является оптимальным планом приведенной задачи.
Для получения решения исходной задачи дополним полученный вектор значениями независимых координат так, как это было описано выше:
$$\hat u*=(\mathdf 1,1,1,1, \mathdf 1, \mathdf 1,1,1, \mathdf 1,0,0,0)'$$Значения зависимых координат, по которым достраивался
Из полученного
Заметим в заключение, что специфика области применения предложенных методов в большинстве случаев позволяет понизить размерность задачи оптимизации путем сокращения количества ее переменных.
Что касается этапа оценки при решении задачи в используемом методе ветвей и границ, то в общем случае он сводится к решению соответствующих непрерывных задач.
Однако при $$p=2$$ их решение значительно упрощается, поскольку коэффициенты в ограничениях этих задач равны 0 или 1. Таким образом, специфика рассматриваемой задачи значительно сокращает трудность ее решения по сравнению со многими другими задачами, решаемыми с помощью
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.