Введение к работе
>"'
Пі;. '-
Актуальность теш
^ В последние годы возрос знтерес к ясследвваляо различных алгебраических объектов мвтодамя математической кибернетики. В иастоящвй работе рассматривается задача о сложности реализации элементов конечной абелевой группы схемами из функциональных элементов уаногекая, на еходы которой подаются представители некоторого порождающего эту группу множества элементов (задача о слезностя стиснений в конечных абедевых группах).
Класс схем из функциональных элементов является одним из основных классов в теорта синтеза управлявших систем. Он является хорошей математической моделью днскрет-йк преобразователей специального вида, занимающих а современной технике управляющих и вычислительных устройств важное место, так как этот класс наиболее адекватно отра-іает работу реальных вычислительных устройств.
Цель работы
Целью данной работы является получение асиштотячес-сих оценок сложности реализации элементов конечной абеле-гай группы схемами из функциональных элементов умножения іад произвольным порождающим множеством, а также изучение їсимптотического поведения соответствующей данной поста-говке задачи функции Шеннона.
Научная новизна
В работе разработаны методы вычисления элементов конечных абелевых групп над произвольным порождащим мне жествоы и ыетод построения вентильных схем, учитывающий некоторые свойства реализуемых булевых матриц.
Все основные полученные результаты являются новыми.
Практическая ценность
Полученные результаты о сложности вычисления элементов конечных абелевых групп схемами из функциональных элементов умножения могут найти, применение в теории вычислений одночленов и многочленов от многих переменных, в теории линейных преобразователей, а также в неко^ торых других областях.
В силу того, что результаты вентильного уровня (низшего по мощности применяемых средств, несущего наибольшую топологическую нагрузку) в теории схем могут быть промоделированы во всех более высоких уровачх -теории контактных схем, схем из функциональных элементо (как, например, в настоящей работе), теории автоматов,-разработанный метод построения асимптотически оптимальных вентильных схем для классов булевых матриц специаль ного вида может быть использован во многих разделах теории синтеза и сложности управляющих систем.
Методика исследования
В работе используются методы математической кибернетики, математического анализа и теории групп.
Апробация результатов
Результаты настоящей работы докладывались и обсуждались на IX Всесоюзной конференции по проблемам теоретической кибернетики (Волгоград, 1990), на Ломоносовских чтениях (1991), на III Всесоюзной школе-семинаре по синтезу и сложности управляющих систем (Ташкент, 1991), а также на семинарах и школах- семинарах в МГУ им. М.В.Ломоносова.
Публикации
Основные результаты диссертации содержатся в работах автора, список которых помещен а конце автореферата.
Объем и структура работы
Диссертация состоит из введения, трех глав, разбитых на 9 параграфов и списка литературы, включающего 27 наименований. Общий объем работы составляет 100 страниц машинописного текста. Изложение материала проиллвстрировано 13 рисунками.