Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

О сложности вычислений в конечных абелевых группах Кочергин, Вадим Васильевич

Данная диссертационная работа должна поступить в библиотеки в ближайшее время
Уведомить о поступлении

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Кочергин, Вадим Васильевич. О сложности вычислений в конечных абелевых группах : автореферат дис. ... кандидата физико-математических наук : 01.01.09 / МГУ им. М. В. Ломоносова.- Москва, 1991.- 12 с.: ил. РГБ ОД, 9 92-1/603-8

Введение к работе

>"'

Пі;. '-

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

Публикации

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

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

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