Аннотация:
Исследуется задача о сложности вычисления системы одночленов схемами композиции. Под сложностью в такой модели понимается минимальное число операций композиции, достаточное для вычисления системы по переменным. Установлено, что рассматриваемая мера сложности может быть значительно меньше известных мер сложности, соответствующих моделям, допускающим, например, либо только операцию умножения, либо операции умножения и деления, либо операцию умножения с возможностью использования величин, обратных к переменным. Однако это свидетельство значительной “вычислительной силы” изучаемой модели не носит универсальный характер, что подтверждено соответствующим примером. Кроме того, для системы, состоящей из двух одночленов от двух переменных, получено точное значение сложности. Также установлено, что при вычислениях с использованием операции композиции не работают (или работают в недостаточной мере) соображения двойственности.
Ключевые слова:
система мономов, схема композиции, схема из функциональных элементов, сложность схемы.
Образец цитирования:
Е. Н. Трусевич, “О сложности вычисления некоторых систем одночленов схемами композиции”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2014, № 5, 18–22; Moscow University Mathematics Bulletin, 69:5 (2014), 193–197
\RBibitem{Tru14}
\by Е.~Н.~Трусевич
\paper О сложности вычисления некоторых систем одночленов схемами композиции
\jour Вестн. Моск. ун-та. Сер.~1. Матем., мех.
\yr 2014
\issue 5
\pages 18--22
\mathnet{http://mi.mathnet.ru/vmumm344}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3372789}
\transl
\jour Moscow University Mathematics Bulletin
\yr 2014
\vol 69
\issue 5
\pages 193--197
\crossref{https://doi.org/10.3103/S0027132214050039}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84926622281}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm344
https://www.mathnet.ru/rus/vmumm/y2014/i5/p18
Эта публикация цитируется в следующих 5 статьяx:
С. А. Корнеев, “О сложности реализации системы из трёх мономов от двух переменных схемами композиции”, Дискрет. матем., 34:4 (2022), 36–51; S. A. Korneev, “On the complexity of implementation of a system of three monomials of two variables by composition circuits”, Discrete Math. Appl., 34:2 (2024), 89–101
С. А. Корнеев, “О сложности реализации системы мономов от двух переменных схемами композиции”, ПДМ, 2021, № 53, 103–119
С. А. Корнеев, “О поведении функции Шеннона сложности реализации систем мономов схемами композиции”, Интеллектуальные системы. Теория и приложения, 25:3 (2021), 173–188
С. А. Корнеев, “О сложности реализации системы из двух мономов схемами композиции”, Дискрет. матем., 32:2 (2020), 15–31; S. A. Korneev, “On the complexity of implementation of a system of two monomials by composition circuits”, Discrete Math. Appl., 31:2 (2021), 113–125
С. А. Корнеев, “Об асимптотическом поведении функций шенноновского типа, характеризующих сложность вычисления систем мономов”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 162, № 3, Изд-во Казанского ун-та, Казань, 2020, 300–310
Цитирование в формате AMSBIB
Обратная связь: