Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №8, Москва, 1999
Авторы: Кочергин В.В.
О мультипликативной сложности двоичных слов с заданным числом единиц
Аннотация:
Мультипликативная сложность двоичного слова α - это длина m самой короткой цепочки двоичных слов τ−1 = 0, τ0 = 1, τ1, . . . , τm = α, где каждое τi может быть представлено в виде конкатенации двух предшествующих слов: τi = τj τk, −1 ≤ j, k < i. Через l(k, n) обозначается максимальная мультипликативная сложность слов длины n с k единицами. Установлены интересные связи между величиной l(k, n) и наименьшим числом операций умножения, достаточным для вычисления набора степеней xn1,..., xnk. Основным результатом работы является асимптотическое соотношение l(k,n) = (1 + o(1))(log n + log Cnk / loglog Cnk) при n→∞.
Ключевые слова:
цепочка слов, схема конкатенации, схемная сложность, функция Шеннона
Язык публикации: русский, страниц: 14 (с. 63-76)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Кочергин Вадим Васильевич,  ,  Механико-математический факультет МГУ, Кафедра дискретной математики, Институт теоретических проблем микромира им. Н. Н. Боголюбова МГУ