О реализации недоопределенных матриц из двух столбцов вентильными схемами с кратными путями

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Математическое моделирование. Оптимальное управление Вестник Нижегородского университета им. Н. И. Лобачевского, 2012, № 5 (2), с. 113−117
УДК 519. 711
О РЕАЛИЗАЦИИ НЕДООПРЕДЕЛЕННЫХ МАТРИЦ ИЗ ДВУХ СТОЛБЦОВ ВЕНТИЛЬНЫМИ СХЕМАМИ С КРАТНЫМИ ПУТЯМИ
© 2012 г. В.В. Кочергин
Московский госуниверситет им. М.В. Ломоносова
vvkoch@yandex. ru
Поступолн в реднкцою 10. 09. 2012
Исследуется сложность реализации вентильными схемами с кратными путями целочисленных матриц с неотрицательными элементами. Для недоопределенных матриц, состоящих либо из двух столбцов, либо из двух строк, установлена асимптотика роста сложности.
Ключевые словн: вентильные схемы с кратными путями, сложность матрицы, невсюду определенная матрица.
Помимо естественным образом возникающего интереса к задаче о сложности реализации вентильными схемами с кратными путями недоопределенных матриц (матриц, у которых вместо некоторых элементов стоит символ *) как к задаче о сложности реализации невсюду определенных объектов (см., например, [1]), дополнительный интерес в данном случае связан с возможностью посмотреть под несколько другим углом на задачу о сложности реализации всюду определенных матриц с целью исследования асимптотики роста сложности. Для последней задачи найдено [2] асимптотически точное решение только в случае матриц, состоящих из не более чем двух строк (столбцов), и матриц размера 3*3. В данной статье установлена асимптотика роста сложности реализации недоопределенных матриц, состоящих из двух столбцов. В силу двойственности задачи аналогичные результаты справедливы и для недоопределенных матриц, состоящих из двух строк.
Рассматривается реализация целочисленных матриц с неотрицательными элементами посредством возникающей, например, при изучении сложности вычисления систем одночленов, следующей модификации [3] классических вентильных схем [4].
Пусть, А = (ау) — целочисленная матрица размера p*q с неотрицательными элементами. Ориентированный граф 5 без ориентированных циклов будем называть вевтольвой схемой с крнтвымо путямо (или вевтольвой схемой с предпоснввым чослом путей), ренлозующей мнтроцу А, если: в 5 выделено р вершин -входных полюсов и q вершин — выходных по-
люсов- в S нет ориентированных путей от одного входа к другому, от одного выхода к другому, от выхода к входу- для любой пары (i, j), 1 & lt- i & lt- p, 1 & lt- j & lt- q, число ориентированных путей от i-го входа к j-му выходу равно в точности a, j. Через L (S) обозначим число ребер (вентилей) схемы S и положим L (A) = min L (S), где минимум берется по всем схемам, реализующим матрицу A.
Пусть теперь A = (atj) — матрица, элементами которой являются целые неотрицательные числа и элементы * (символ * соответствует неопределенному значению). Такую матрицу будем называть невсюду определенной или недоопределенной (отметим, что формально полностью определенные матрицы являются частным случаем недоопределенных). Матрица B = (bj) называется доопределением матрицы A = (atj) такого же размера, если в матрице B все элементы определены (нет символов *), и для любого определенного элемента aij матрицы A справедливо равенство aj = bj.
Для недоопределенной матрицы A, в которой все определенные элементы целочисленны и неотрицательны, положим L (A) = inf L (B), где инфинум берется по всем доопределениям B матрицы A до целочисленной матрицы с неотрицательными элементами. Очевидно, что инфинум достигается. Без ограничения общности можно считать, что в матрицах нет ни строк, ни столбцов, полностью состоящих из нулей и символов *.
Теперь введем некоторые обозначения для матриц, состоящих из двух столбцов. Пусть A = = (агу) — недоопределенная матрица размера p*2.
Обозначим через Ao = Ao (A) полностью
определенную (возможно пустую) матрицу, получающуюся из матрицы, А путем вычеркивания неполностью определенных строк. Положим ао (А) = 1, если в матрице, А отсутствуют полностью определенные строки, а в остальных случаях полагаем ао (А) = 0(Ао), где величина -О (В) для полностью определенной матрицы В определяется как максимум абсолютных величин миноров матрицы В (максимум берется по минорам всех порядков).
Выделим три подмножества множества {1, 2, …, р} номеров строк матрицы А. Через /1 обозначим множество номеров таких строк, в которых первый элемент является определенным, а второй элемент — символ *, через 12 -множество номеров таких строк, в которых первый элемент является символом *, а второй элемент — определенный, и, наконец, через О -множество номеров строк, оба элемента которых являются определенными.
Далее положим
шах (шах{аг1}, 1)
(А) =---------------- ,
шах (шах{а (1}, 1)
шах (шах{аг 2}, 1)
а 2 (А)=----------------.
шах (шах{а/2}, 1)
Здесь максимумы в числителях (по г) берутся по всем определенным элементам, стоящим в неполностью определенных строках (т.е. в строках, в которых другой элемент — символ *), а максимумы в знаменателях (по у) берутся по всем определенным элементам, стоящим в полностью определенных строках.
Теперь для матрицы А, состоящей из двух столбцов, положим
А) = а0(А)шах{а1(А), йг (А), 1}.
Теорема. Для произвольной последовательности недоопределенных матриц Ап = (ау (и)),
п = 1, 2, …, фиксированного размера рх2, все определенные элементы которых неотрицательны, при условии ^ ау (и) ^ ж (сумма берется по всем определенным элементам матрицы А (п)) выполняется соотношение
ЕВРа (Ап) = (3 + 0(1))1свз Я*(Ап).
Доказательство теоремы опирается на следующие вспомогательные утверждения.
Лемма 1 [5]. Пусть элементы матриц, А = (ау) и В = (Ьу) размера к* к удовлетворяют неравенствам |ау -Ьу |& lt- 1, г = 1, …, к, у = 1,
…, к. Тогда при условии -О (А) & gt- 1 выполняется неравенство
|аег В| & lt- к 1кБ{ А).
Лемма 2 [6]. Пусть
ат (п) = шах{а1 (n), Ь1 (n), к, ат (n), Ьт (n)},
и при п^-& lt-х>- выполняется условие ат (п) ^ ж. Тогда
1(Ха1 /*,…, Хат, уат) & lt-
(т Ьб ат Л
1оЕ1оБ ат
1оЕ (ат + шах| атЬ1 — агЬт |) + 0
ЮаЮа а
т
Лемма 3 [2]. Для любой полностью определенной ненулевой целочисленной матрицы, А с неотрицательными элементами справедливо неравенство
ЕВРа (А) & gt- 310Ез Я (А).
Лемма 4. Для произвольной последовательности недоопределенных матриц
'- а11(п) а12(п)'-'-
Ап = а2Х (п) а22(п), п = 1, 2, … ,
, а31(п) * ,
все определенные элементы которых неотрицательны, при условииагу (п)ж (сумма берется по всем определенным элементам матрицы А (п)) выполняется соотношение
ЕВРа (Ап) & gt-
(
& gt- 310Бз
(
п (Аа (Ап))шах
а31(п)
, 1

шах (а11(п), а21(п), 1)
Доказательство. Если справедливо неравенство а31 & lt- шах (а11(п), а21(п), 1), то требуемая оценка следует из леммы 3:
Цс (Ап) & gt- ЕВа (П (Ао (Ап))) & gt- 310Е3 0(А" (Ап)) =
(
=31об3
В (. Ао (Ап))шах
(
а31(п)
, 1
а21(п), 1)
Пусть теперь выполняется условие а31 & gt- & gt- шах (а11(п), а21(п), 1).
Рассмотрим минимальную вентильную схему ?, реализующую матрицу Ап (точнее говоря, некоторое доопределение матрицы Ап). Выделим в схеме? подсхему ?0, состоящую из всех вершин и ребер, входящих хотя бы в один путь, ведущий от входов к первым двум выходам.
Очевидно, что вентильная схема ?0 реализует матрицу Ао (Ап). Поэтому, в силу леммы 3,
ЕВа (?о) & gt- 310Е3"(Ао (Ап)).
Для произвольной вершины V вентильной схемы? обозначим через а^) число различных путей, ведущих в вершину V от первого входа.
Легко понять, что для любой вершины v схемы S0 выполняется неравенство a1 (v) & lt- & lt- max (a11(n), a21(n), 1).
Схему S можно получить из схемы S0 путем последовательного добавления новых вершин и ребер. Покажем, что при добавлении к схеме S0 не более чем l ребер (и некоторого количества вершин) для любой вершины v получившейся схемы выполняется неравенство
a1(v) & lt- 3l/з max (a11, a21,1).
Докажем этот факт индукцией по числу вершин, в которые входит хотя бы одно добавленное ребро. Такие вершины будем называть помеченными. Помеченные вершины занумеруем естественным образом (чтобы не было путей от вершин с большими номерами к вершинам с меньшими). Если не помечено ни одной вершины, то утверждение очевидно. На каждом шаге обрабатываем очередную помеченную вершину v, в которую ведут ребра из вершин v^…, vr (эти вершины могут повторяться). Используя предположение индукции, получаем
a1 (v) = Z a1 (Vi) & lt- r3° r)/3 max (al1, a21,1) =
= 3l/3 max (a11, a21,1)
1/3
& lt- 3l/3 max (a11, a21,1).
LBPc (S) — LBPc (S0) & gt- 3log3
Л
max (a11, a21,1)
Следовательно,
LBPc (S) & gt-
& gt-3log3
D (Ao (An))max
a31(n) max (a11(n), a21 (n), 1)
, 1
sj
A =
-V+1,1
ur 2 *
аг+5,1 *
* аг+5+1,2
V * аг+*+и2-
где Г & gt- 0, 5 & gt- 0, t & gt- 0, Г + 5 + t = р.
Случай 1. Пусть г = 0.
В этом случае
а0(А) = 1 а!(А) = шах (аг +l& gt-l, к, аг +
а2 (А) = шах (аг + 5+1,2, к, аг+т2).
Следовательно, величина 0*(А) численно равна наибольшему из определенных элементов матрицы А.
Без ограничения общности можно считать, что
ar+11 = max (ar
-, 1),
ar + s+1,2
= max (ar+s+U,-K ar+s+t, 2
).
Доопределим матрицу A до матрицы A, положив
ai1ar + s+1,2
При добавлении не более, чем ЦС (?) —
— Ц? с (?0) ребер получим вершину v0, соответствующую третьему выходу схемы ?, для которой справедливо равенство а0) = а31. Таким образом,
ґ
азі
*r+s+1,2
i = r + 1, к, r + s-
, i = r + s +1,…, r + s + t.
В матрице, А все элементы из первого столбца не превосходят аГ+11, а все элементы
из второго столбца не превосходят а
Лемма 4 доказана.
Доказательство теоремы. Без ограничения общности можно считать, что матрица, А не содержит строк и столбцов, состоящих только из нулей и символов *, и имеет вид
Г + 5 +1,2 —
Кроме того, все строки матрицы, А «почти пропорциональны» (были бы пропорциональны, если бы при доопределении не производилась операция взятия целой части) строке (аГ+11, аГ+5+12). Поэтому, используя леммы 1 и
2, получаем
ЕВС (А)& lt-ЕВ1'с (А)& lt-(3+о (1))1оЕ3шах (аг +1,1, аг+5+1,2). С другой стороны, в силу леммы 3 справедливо неравенство
ЕВс (А) & gt- 3 1о§ 3 шах (аг+1,1, аг + 5+1,2).
a
a
12
a
a
I =1
a
r+1,1
ar+1,1ai2
ai1 =
Поэтому в условиях случая 1
1%с (An) = (3 + o (1))log3 DAn).
Случай 2. Пусть r& gt-1.
Нижняя оценка. При выполнении неравенства max (d1 (A), d2 (A)) & lt- 1 нижняя оценка следует из леммы 3. При выполнении неравенства max (dj (A), d2 (A)) & gt- 1 для доказательства нижней оценки определим по матрице A матрицу A'- размера 32 следующим образом. Первые две строки (они могут быть и одинаковыми) выбираются из первых r строк, а третья строка -из последних 5 + t строк матрицы A, причем первые две строки выбираются из условия d0(A'-) = d0(A), а в качестве третьей строки выбирается та недоопределенная строка матрицы A, которая доставляет максимальное значение величине max (d1(A), d2(A)). Очевидно, что
max (d1(A'-), d2(A'-)) & gt- max (d1(A), d2(A)).
Используя лемму 4, имеем LBC (A) & gt- Щс (A) & gt- 3 log3 (do (A'-)max (d1 (A'-), d2 (A'-))) & gt- & gt- 3 log3 (d0(A) max (d1 (A), d2 (A))) = 3 log3 D* (A).
Верхняя оценка. Отдельно рассмотрим несколько подслучаев.
Случай 2.1. Пусть максимальный элемент среди элементов an,…, ar1 и максимальный элемент среди элементов a12,…, ar2 находятся в одной строке.
Без ограничения общности можно считать, что a11 = max (an,…, ar1), a12 = max (a12,., ar2).
Случай 2.1.1. Пусть aJJaJ2 Ф 0.
Доопределим матрицу A до матрицы A, положив
п п
i = r +1,…, r + 5-
a1 =
a 2an
Таким образом,
A =
i = r + s + 1, к, r + s + t.
12
(ar+1,1 / a11) a11 L (ar+1,1 / a11) a11 J
(ar + 5,1 1 L (ar + 5,1 1 aU) aUj
L (ar+5+1,2 1 a12) a11 J (ar+ 5+1,2 1 a12) a11
vL (ar + 5+t, 2 1 ^211 J (a r+5+t, 2
Поэтому, используя леммы 1 и 2, получаем
Lp (A) & lt- Lp (A) & lt- (3 + o (1))log3
(D (Ao (A)) x
x max
ar + s, 1 ar+s+1,2
V a11
12 J
= 310Е3 О (А).
Случай 2.1.2. Пусть а11а12 = 0.
Без ограничения общности можно считать, что а11 & gt- 0, а12 = 0. Тогда а22 = … = аг2 = 0.
Доопределим матрицу, А до матрицы А, положив
а, 2 = 0, г = г + 1, …, г + 5- аг1 = аг2а11, г = г + 5 +1,…, г + 5 + t.
Таким образом,
(
A =
(ar+1,1 / a11) a11 Lr+1,1 / a11
(ar + s, 1/ a11) a11 Lar+s, 1/ a11
r+s+1,2
r+s+t, 2
Все строки матрицы, А либо пропорциональны строке (а11, 1), либо могут быть получены из строки, пропорциональной строке (а11, 1), путем изменения второго элемента в строке не более, чем на единицу. Поэтому, используя леммы 1 и 2, получаем
ЕВа (А) & lt- 1Ва (А) & lt- (3 + о (1)) х
^ «ЛЛ
х1об3
= (3 + о (1))1оЕ3 О (А).
Случай 2.2. Пусть максимальный элемент среди элементов а11, ., аг1 и максимальный элемент среди элементов а12, ., аг2 находятся в разных строках.
В условиях этого случая г & gt- 2. Без ограничения общности можно считать, что
а11 = шах (а11, к, агД а22 = шах (а12, • • •, аг2).
Также без ограничения общности можно считать, что а11а22 Ф 0 (иначе можно полагать, что максимальные элементы расположены в одной строке).
Доопределим матрицу, А до матрицы А, положив
^ + а22) г = Г +,…Г + 5-
a
a
r+1,1
r+s+t, 2
a
a
12
a
0
a
ar+s+1,2a11
ar+s+t, 2a11
a
a
11
11
a
a
12
a
a
a
a11 + a21
a1 =
ai 2(a11 + a21)
a12 + a2
12 22 Таким образом,
C a11
i = r + s + 1, к, r + s + t.
A =
•v+1,1
*r + s, 1
r+s+1,1
r+s+t, 1
-(a11 + a21)
¦(a11 + a21)
r+1,1
*r+ s, 1
(a11 + a21)
(a» + a21)
r+s+1,1
r+s+t, 1
-(a11 + a21)
¦(a11 + a21)
(a11 + a21)
(a11 + a21)
Поэтому, используя леммы 1 и 2, получаем LBc (A) & lt- LBc (A) & lt-
& lt- (3 + o (1))log3
d0 (A) max
r+1,1
*r+s, 1
V a11 + a21
a11 + a2
r+s+1,2
ыг + s +t, 2
a12 + a22 J
& lt- (3 + o (1))log3 (d0(A)
max
r+1,1
r+s, 1
22
22 J
= (3 + o (1))log3 D*(A).
Теорема доказана.
Работа выполнена при финансовой поддержке РФФИ (проект 11−01−508).
Список литературы
1. Нечипорук Э. И. О сложности вентильных схем, реализующих булевские матрицы с неопределенными элементами II Проблемы кибернетики, вып. 21. М.: Наука, 1969. C. 237−240.
2. Кочергин В. В. О сложности вентильных схем с кратным числом путей II Матер. XVIII Междунар. школы-семинара «Синтез и сложность управляющих систем» им. акад. О. Б. Лупанова (Пенза, 28 сентября — 3 октября 2009 г.). М.: Изд-во механикоматематического ф-та МГУ, 2009. C. 51−56.
3. Pippenger N. The mimimum number of edges in graphs with prescribed paths II Math. Systems Theory. 1979. V. 12, № 4. P. 325−346.
4. Лупанов О. Б. О вентильных и контактновентильных схемах II Доклады А Н СССР. 1956. Т. 111, № 6. С. 1171−1174.
5. Кочергин В. В. Об асимптотике сложности аддитивных вычислений систем целочисленных линейных форм II Дискретный анализ и исследование операций. Серия 1. 2006. Т. 13, № 2. С. 38−58.
6. Кочергин В. В. О сложности вычисления систем одночленов от двух переменных II Труды VII Международной конференции «Дискретные модели в теории управляющих систем» (Покровское, 4−6 марта 2006 г.). М.: МАКС Пресс, 2006. С. 185−190.
a
a
r+s+1,2
r+s+t, 2
a
12
a
a
a11 + a21
a11 + a21
a11 + a21
a11 + a21
a12 + a22
a12 + a22
a12 + a22
a12 + a22
a12 + a22
a
a
ON REALIZATION OF UNDERDETERMINED TWO-COLUMN MATRICES BY GATE CIRCUITS WITH MULTIPLE PATHS
V.V. Kochergin
The realization complexity of non-negative integer matrices by gate circuits with multiple paths is studied. The complexity growth asymptotics for underdetermined matrices consisting of either two columns or two rows has been obtained.
Keywords: gate circuits with multiple paths, complexity of a matrix, underdetermined matrix.

ПоказатьСвернуть
Заполнить форму текущей работой