О сложности вычислений в конечных абелевых группах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи КОЧЕРГИН Вадик Васильевич

УДК 519.714

О СЛОЖНОСТИ ВЫЧИСЛЕНИЙ В КОНЕЧНЫХ АБЕЛЕВЫХ ГРУШАХ

01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-ыате магических наук

МОСКВА - 1991

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета им. М.В.Ломоносова.

Научный руководитель - доктор физико-математических наук,

члек-корреспондент АН СССР, профессор О.Б.Лупанов.

Официальные оппоненты - доктор физико-математических наук,

Ведущая организация - Институт математики Сибирского

отделения АН СССР.

в 16 час. 05 иин. на заседании Специализированного Ученого совета по математике № 2 (Д.053.05.05) при МГУ по адресу: I19899, ГСП,Москва, Ленинские Горы, МГУ, механико-математический факультет, аудитория Г4-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета ЫГУ (Главное здание, 14 этаж).

Автореферат разослан " 2Т " 1992г.

профессор М.М.Глухов,

кандидат физико-математических наук, доцент В.Б.Алексеев.

Защита диссертация состоится

я

/ Ученый секретарь /шецяализированного совета Д.053.05.05 при МГУ, д.ф.ы.н.

В.Н.Чубариков

>"' ОЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

гм;.

Актуальность теш

¡- В последние годы возрос антерес к исследованию раз-яичных алгебраических объектов методаш матештяческой кибернетики. В настоящей работе рассматривается задача о сложности реализации элементов конечной абелевой группы схеуакя из фуикцяокальккх элементов ужагекая, на зходы которой подаются представители некоторого пороядащвго эту группу множества элементов (задача о слеаноста пгслс-иений в конечных абелевах грушах).

Класс схем из функциональных элементов является од-яим из основных классов в теории синтеза управлявших еис-гем. Он является хорошей математической моделью дискрет-*ых преобразователей специального вяда, заяяващнх в современной технике управлящих н вычислительных устройств важное место, так как этот класс наиболее адекватно отра-1ает работу реальных вычислительных устройств.

Цель работы

Целью данной работы является получение асиштотячес-снх оценок сложности реализации элементов конечной абеле-зой группы схемами из функциональных элементов умножения 1ад произвольным порождащим множеством, а также изучение юиыптотического поведения соответствупцей данной поста-говке задачи функции Шеннона.

Научная новизна

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

Все основные полученные результаты являются новыми.

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

Полученные результаты о сложности вычисления элементов конечных абелевых груш схемами из функциональных элементов умножения могут найти, применение в теории вычислений одночленов и многочленов от многих переменных, в теории линейных преобразователей, а также в некоторых других областях.

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

Методика исследования

В работе используются методы математической кибернетики, математического анализа и теории групп.

- 3 -

Апробация результатов

Результаты настоящей работы докладывались и обсуждались на IX Всесоюзной конференции по проблемам теоретической кибернетики (Волгоград, 1990), на Ломоносовских чтениях (1991), на III Всесоюзной школе-семинаре по синтезу и сложности управляющих систем (Ташкент, 1991), а также на сеш-нарех и школах- семинарах в МГУ им. М.В.Ломоносова.

Публикации

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

Объем и структура работы

Диссертация состоит из введения, трех глав, разбитых на 9 параграфов и списка литературы, включающего 27 наименований. Общий объем работы составляет 100 страниц машинописного текста. Изложение материала проиллюстрировано 13 рисунками.

СОДЕРЖАНИЕ РАБОТЫ

Во введении формулируется цель работы и основные результаты, приводится обзор литературы и имеощихся результатов по данной теме, кратко излагается содержание диссертации.

В главе I сначала (§1) вводятся основные понятия.

Пусть G - конечная абелева группа (по умножению), а i ■ №

М ^ - порождающее множество этой группы. Тогда -

наименьшее число операций умножения, достаточное для вычисления (схемой из функциональных эле центов, реализующих групповую операцию) элемента <} б & с использованием элементов из , а ^ = М&), где

максимум берется по «сем элементам д группы & . Для класса всех абелевых групп порядка п. функция Шеннона Ь (ССп) определяется тек: ((Хп) -где максимумы берутся соответственно по всем порождапцим множествам М^ группы -Сг и по всем группам из класса

си.

Далее (52) при некоторых: ограничениях на свойства порождающего множества произвольной конечной абелевой группы & (например, М^ - неприводимое порождающее множество или - базис группы С* ) доказываются нижние оценки величины Ь (Сг, N0) (теоремы I и 2). Первая иг них устанавливается тривиально, а вторая, имещая вид

стандартно доказывается мощностным (энтропийным) методом.

В §3 устанавливается верхняя оценка величины С (О, Сначала определяются две величины, характеризующие порождающее множество М& :

Я - «КнесЫМс,1» г-р

где тткуы берегся по всем перестановкам множества М^ = { ,..., ^ .

Б лемме 2 доказывается, что найдутся целые к,г

- 5" -

и I < . ,

удовлетворяющие условиям ,

и . к* ~ I Сг1 , такие, что произвольный элемент

г и ií -<9

^ ¿О можно представить в виде ■ ■ ^ , где

о ¿-¿и < , с= í, q.

По такому разложению элемента ^ над порождающим множеством М& определяется булева таблица (ступенчатая матрица) , получающаяся при последовательном выписы-

вании столбцов (вообще говоря, различной высоты) двоичных записей чисел £г>. .^ (младшие разряда сверку и на одном уровне). Затем через А (Т^1^) обозначается булева матрица размера ( р = р (М^) , с/ = q (М0)), полу-

чающаяся из таблицы путем доопределения неопреде-

ленных элементов нулями, а через Н - площадь таб-

лицы Т% & (число клеток).

После этого вводится понятие 0-1-вентильной схемы следующим образом. Ориентированный граф 3 называется 0-1-вентильной схемой, реализующей булеву матрицу А размера р х ^ , если: I) в $ выделено ^ вершин - входных полюсов и р вершн - выходных полюсов; 2) в 5 нет ориентированных путей от одного входа к другому, от одного выхода к другому и от выхода к входу; 3) для любой пары (»^ j = » с = • ■•> Р » число ориентированных

путей от у -го входа к I -му выходу равно & - . Через ^вс (&) обозначается сложность 0-1-вентильной схемы £ , т. е. число ребер (вентилей) в ней, а сложность £вс (А) реализации матрицы А 0-1-вентильными схемами определяется так: где минимум берется по всем 0-1-вентильным схемам, реализующим матрицу А .

В леыш 3 задача о нахождении верхней оценки сложности реализации элементов конечной абелевой группы схемами из функциональных элементов умножения сводится к задаче о верхней оценке сложности реализации таблиц (точнее матриц, являющихся вьшеописанными доопределениями этих таблиц), соответствующих этим элементам группы, О-Ï-вентильными схе-

шш: L (<}, М^) < LbJACT^«)) + IpCMj-Z.

Наконец, с использованием соответствующей верхней оценки величины L вс (л(Т^и)) (которая устанавливается позже - в §7) доказывается такое утверждение (теорема 3):

1(се,м&Ь# 4JCtl (иоКЧ'Ч'Ьц'Ш]"*}) +

0(ч(мСе))9

которое вместе с соответствующим! нижними оценками при некоторых ограничениях на свойства порождающего множества M q устанавливает асимптотическое поведение величины L(Q}Mu) (теоремы 4 и 5):

В главе II изучается вопрос о сложности реализации булевых таблиц (ступенчатых матрщ) 0-1-вентильными схемами.

Пусть Т - произвольная булева таблица размера , а А (т) - ее доопределение нулями до обычной матрицы размера р * <? . Информационная часть матрицы А (Т) ' определяется как часть, совпадающая с таблицей

Г

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

только в своей информационной части. Сложность L^ ( реализации класса булевых матриц размера p«(j

0-1-вентильными схемами определяется таким образом: ■ L6c ( sLT) = иллх/х. L 6с(а) » где максимум берется по всем матрицам А из класса .

В §4 ющностныы методом доказывается (теорема б) следующая нижняя оценка:

В §§5-7 рассматривается задача о верхней оценке величины L&c

(Л (Т)) .

Сначала (§5) устанавливается точная по порядку верхняя

оценка. Зтс делается в два этапа. Первоначально с использо-

*0

вашем конструкции О.Б.Лупанова асимптотически наилучшего метода синтеза вентильных схем глубины 2 она доказывается для матриц А От) , информационная часть которых достаточно велика по сравнению со всей матрицей (лемма 5). Затем эта оценка распространяется на произвольный случай (теорема 7) двукратным применением леммы 5 (в случае "малой" информационной части) к предварительно выделенным двум подматрицам матрицы А (Т) , имеющим существенно меньше размеры и содержащим всю ее информационную часть. Полученный в теореме 7 результат в дальнейшем существенно используется при асимптотически оптимальной реализации матрицы А (Т) 0-1-вентильными схемами для реализации подматриц матрицы A (TJ • шлющих информационную часть, существен-

Лупанэв О.Б. О вентильных и контактно-вентильных схемах // ДАН СССР. - 1956.- Т. III, »6.- С. I17I-II74.

- а -

но мзньпув, чем информационная часть всей матрщы А(Т) — это дает не слишком большой вклад в суммарную сложность реализации А(Т) .

§6 содержит вспомогательные и промежуточные результаты (леммы 6-12). В этом параграфе, исходя из асимптотически оптимальной верхней оценки сложности реализации обычных булевых матриц вентильными схемами (Н.Пиппендкер*^), постепенно улучшается (лемш 9-12) верхняя оценка для ступенчатых матриц - таблиц (точнее для их вышеописанных доопределений). Эти лемш носят, в основном, технический характер, а их формулировки и доказательства имеют громоздкий вид.

В §7 доказывается теорема 8: для любой таблицы Т размера р * справедливо неравенство

При доказательстве этой теоремы сначала в течение к этапов, где * = [<о,а ((Цг Н(Т^ HCT))VzJ] - 1, в каждой из полученных на предыдущем этапе подматриц (на первом этапе - самой матрице

ACT) ), имеющих большую (в некотором смысле) информационную часть, в свою очередь ввделяются две подматрицы, объединение которых содержит всю информационную часть исходной подматрицы. После этого с использованием различных лемм из предыдущего параграфа оцениваются сверху сложности реализации 0-1-вентильными схемами

** f^-pp-e^wtjx/t. vA/1. иилстлии С^-

Ccto^ 1ЛЛ (J/UX^Wi \jjiAM, р/Х£^уС/Ы&ие{ pOstfr^ /f

ГПоМ* iysJjbMA ТкщЪу. -1Ы9. - V. 12. - ft ¿25-3^6.

всех выделенных подматриц, в которых, в свою очередь, подматрицы не выделялись. После этого полученные оценки суммируются. Детальный анализ слагаемых этой суммы приводит к требуемой оценке сложности реализации 0-1-вентильньши схемами всей матрицы А (т) .

Далее из теорем 6 и 8, а также очевидных неравенств ^всб^т )~>'Р и г) ^ 9 выводится такое соотноше-

ние: Lßc (Лт) ~ -т^с (HM/еоц ЧСТ) , <ЛГ где - некоторая величина порядка р+у ,

которое устанавливает порядок сложности реализации матриц из произвольного класса , а при некоторых естесвен-

ных ограничениях на размеры таблицы Т - асимптотически точное значение.

Теоремы б, 8 и 9 остаются справедливыми и при реализации булевых матриц вентильными схемами в традиционном смысле, т. е. без ограничения на число путей от произвольного входа к произвольному выходу в случае, когда соответствующий элемент матрицы ке равен 0 , так как верхние оценки остаются справедливыми и для схем без ограничений, а нижняя оценка (теорема б) фактически доказывается для вентильных схем без ограничения на число путей.

В главе III исследуется вопрос о поведении функции Шеннона L (ОСл) сложности реализации конечных абелевых групп при п. оо л Легко понять, что L (СХ. г п-■

С другой стороны, используя лемму 2, нетрудно показать, что L [ ОС^)4 т- . Верхняя оценка, асимптотически совпада-етцая с указанной нижней, устанавливается уже заметно труднее. В этой же главе доказывается более сильный резуьтат

(теорема 10):

¿f<sy = Ц.а . . О ).

В §8 устанавливается соответствующая верхняя оценка величины L(0tK) . Для ее доказательства рассматривается задача о вычислении одночленов от многих переменных.

Через

а х,1 хг 1 ... ж,,ч) обозначается сложность вычисления произведения acf' х^4.. . х^4 , т. е. наименьшее число операций умножения, достаточное для вычисления одночлена

& к k

xi ' г. .. ^ч 4 , исходя из переменных

В лемме 13 доказывается, что при ¿ = ¿,.., «у,

справедливо соотношение

где n, . ., к ч . Основная идея доказательства

этой лемма состоит в следующем. Пусть >„ ... Ч-

Множители из произведения jc/' ас/1... ¿cjji разбиваются

на четыре группы. К первой относятся множители с показате-

^ п о- Л СО / Я (*-)

лямл степени больше 2 7 , где

^x't/^0!«.^! ^ , a Q. - некоторая константа; ко второй - следующие Я(и.)/&^г множитзлей; к треть-

ей - идущие за. ними множите-

лей, где fl-i - произведение" показателей степеней множителей из первой группы; & к четвертой - оставшиеся множители. Одна или несколько групп множителей могут оказаться пустыми. Исходный однэчлен представляется а таком виде:

^•xS.. = X,X3XV , где X: -

.жахетехей ks I -й группы.. Сложность вычисления исходного

одночлена оценивается сверху через сумму сложностей вычисления X, ^ Хг? Х5, • Для каждой группы переменных строится своя схема из элементов умножения.

Для произведения множителей из X* нужная оценка получается при использовании отдельно для каждой степени метода А.Брауэра ^ асимптотически оптимального вычисления степеней. Произведение множителей из оценивается аналогично теореме 3. При оценивании сложности вычисления произведений Х.ь и Х<, рассматривается два случая. В первом случае (когда число множителей в X 3 и в совокупности не очень велико) сложность произведения множителей из У. г оценивается сверху тоже аналогично геореме 3, а множителей из X — через сложность схемы, последовательно вычисляющей все степени. Во втором случае произведение множителей из объединения Ку и Х„ реализуется на основе схемы, последовательно вычисляющей все степени.

к А 6

Такой подход к вычислению произведения х) ' хг г_ зе * дает нужную оценку.

В конце §8 из леммы 13 выводится верхняя оценка теоремы 10.

Нижняя оценка (§9) требуемого теоремой 10 вида доказывается для сложности реализации элементов циклической группы 0 = над порождапцим множеством .Хотя

^ЛлхосЛ А. Окг СкЛ^хЛл^у^. сЬоиспл Ц Ё^М.. ОЦуилл.. МлЛЖ. - (959. - V. - р. tЪQ-Чi 9.

последняя задача близка к задаче о сложности вычисления числа 1- аддитивными цепочками, мощностнуга нижнюю оценку П.Эрдеша непосредственно перенести нельзя. Однако удается модифицировать это доказательство и получить аналогичную, оценку для величины Ь (<<$>п , ^ \ ) ,а следовательно и для Ь (ОС.

В заключение автор пользуется возможностью выразить глубокую благодарность научному руководителю чл.-корр. АН СССР О.Б.Лупанову за постановку задачи, постоянное внимание к работе и ценные советы.

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

1. Кочергин В.В. О реализации ступенчатых матриц вентильными схемами и сложности вычислений в конечных абелевых группах // Проблемы теоретической кибернетики. Тезисы докладов|Х Всесоюзной конференции (сентябрь, 1990). Часть 1(1). - Волгоград, 1990. - С. 62.

2. Кочергин В.В. О сложности вычислений в конечных абелевых грушах // ДАН СССР. - 1991. - Т. 317, №2. - С. 291-294.

£ Р. Яал^ОлЛЛ ЫчхУЪу } Ш ••

О*. сАа^лЛ // (ХсЛа. (ЬиМг. ~ 19СО. -

V. 6. - К