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

С.А. Корнеев

Московский государственный университет имени М.В. Ломоносова, г. Москва, 119991, Россия

Институт прикладной математики им. М.В. Келдыша Российской академии наук, г. Москва, 125047, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2020.3.300-310

Для цитирования: Корнеев С.А. Об асимптотическом поведении функций шенноновского типа, характеризующих сложность вычисления систем мономов // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 300–310. – doi: 10.26907/2541-7746.2020.3.300-310.

For citation: Korneev S.A. On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 300–310. doi: 10.26907/2541-7746.2020.3.300-310. (In Russian)

Аннотация

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

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

Ключевые слова: система мономов, сложность вычисления, схемная сложность, функция Шеннона

Литература

1. Кочергин В.В. О сложности совместного вычисления трех одночленов от трех переменных // Математические вопросы кибернетики. – М.: ФИЗМАТЛИТ, 2006. – Вып. 15. – С. 79–154.
2. Ширшов А.И. Некоторые алгоритмические проблемы для алгебр Ли // Сиб. матем. журн. – 1962. – Т. 3. – С. 292–296.
3. Мерекин Ю.В. О порождении слов с использованием операции композиции // Дискрет. анализ и исслед. операций. Сер. 1 – 2003. – Т. 10, № 4. – С. 70–78.
4. Трусевич Е.Н. О сложности вычисления некоторых систем одночленов схемами композиции // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. – 2014. – № 5. – С. 18–22.
5. Корнеев С.А. О сложности реализации системы из двух мономов схемами композиции // Дискрет. матем. – 2020. – Т. 32, Вып. 2 – С. 15–31. – doi: 10.4213/dm1604.
6. Кочергин В.В. Задачи Р. Беллмана и Д. Кнута и их обобщения (Сложность аддитивных вычислений). – Saarbrucken: Palmarium Acad. Publ., 2012. – 396 с.

Поступила в редакцию 15.07.2020

Корнеев Сергей Александрович, аспирант кафедры дискретной математики; инженер-исcледователь

Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия

Институт прикладной математики им. М.В. Келдыша Российской академии наук Миусская пл., д. 4, г. Москва, 125047, Россия

E-mail: korneev.sa.42@gmail.com

Контент доступен под лицензией Creative Commons Attribution 4.0 License.