English
!

Архив публикаций

Тезисы

XV-ая конференция

Оценки сложности реализации групповых автоматов

Карасёв К.Е.

МГТУ СТАНКИН, Россия, 127994, Москва, Вадковский пер., 1

1  стр.

Рассмотрим следующую задачу, обобщающую задачу об оптимальной реализации функции алгебры логики схемой: каким может быть минимальное число L(G) элементов в схеме автомата (из стандартных функциональных элементов и элементов памяти - «задержек»), внутренняя группа которого есть данная конечная группа G? Каково поведение функции L(n) (аналогичной функции Шеннона), равной максимальному L(G) для всех групп G порядка не менее n?

Нижняя оценка L(n)≥log2 n достигается для циклических групп. Универсальная верхняя оценка имеет порядок n log2 n.

Назовём классов просто реализуемых групп группы, допускающие реализацию автоматов схемами порядка логарифма от числа элементов группы. К таким группам относятся коммутативные группы, группы подстановок, чётных подстановок, группы, реализуемые линейными автоматами.

Многие группы, описаны с помощью линейных представлений, поэтому автоматные представления удобно строить на их основе. Система из N линейных операторов размерности n в поле порядка q еализуется схемой из элементов в количестве порядка Nn2/log Nn*log2q.С помощью этой оценки можно показать, что простые группы Шевалле с полями, у которых степень порождающего многочлена ограничена, образуют класс просто реализуемых групп.



© 2004 Дизайн Лицея Информационных технологий №1533