О сложности вычисления систем элементов конечных абелевых групп

Кочергин, В.В.

Автор: Кочергин В.В.
Журнал: Вестник Московского университета. Серия 1: Математика. Механика
Номер: 4
Год издания: 2023
Издательство: Изд-во Моск. ун-та
Местоположение издательства: М.
Первая страница: 22
Последняя страница: 29
DOI: 10.55959/MSU0579-9368-1-64-4-4
Аннотация: Исследуется сложность реализации систем элементов конечных абелевых групп. Подсложностью реализации системы элементов над заданным базисом понимается минимальное число применений групповых операций для вычисления элементов системы по базисным элементам, при этом допускается многократное использование результатов промежуточных вычислений. Для функции Шеннона L(n, m), характеризующей максимальнуюсложность системы из m элементов, где максимум берется по всем абелевым группам порядка не более n, по всем их базисам и по всем реализуемым системам, установлено, чтов случае выполнения условия m = o(log log n) при n → ∞ справедливо асимптотичскоеравенство L(n, m) ∼ log2 n. Кроме того, при тех же условиях установлена асимптотикамаксимально возможного отличия сложности вычисления системы элементов конечнойабелевой группы и сложности реализации системы одночленов, соответствующих представлениям этих элементов через базисные элементы.
Добавил в систему: Кочергин Вадим Васильевич

	ИСТИНА	Войти в систему Регистрация
	Интеллектуальная Система Тематического Исследования НАукометрических данных
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

Интеллектуальная Система Тематического Исследования НАукометрических данных

О сложности вычисления систем элементов конечных абелевых группстатья

Прикрепленные файлы