О сложности аддитивных вычислений

• Автор: Кочергин, Вадим Васильевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 344 с. : ил.

Оглавление
Введение

1. Задачи Веллмана и Кнута

§ 1.1. Определения. Постановка задачи в общем виде. Задачи Веллмана и Кнута

§ 1.2. Верхние оценки

§ 1.3. Нижние оценки

§ 1.4. Применение задачи Кнута к оценкам сложности схем конкатенации

§ 1.5. Сложность вычислений в конечных группах

2. Общие свойства мер сложности I, Ь, Ь

§ 2.1. Универсальная нижняя оценка

§2.2. Функции Шеннона

3. Вычисление систем одночленов
§3.1. Случай матриц размера 2x2
§3.2. Вспомогательная модель — обобщенные схемы
§ 3.3. Случай матриц размера 3x3
§ 3.4. Сложность одной системы из 2£ одночленов от 2£ переменных
4. Вычисление систем целочисленных линейных форм

5. Вычисление систем элементов свободной абелевой группы
§ 5.1. Случай матриц размера 1хд, рх1и2хд
§ 5.2. Случай матриц размера 3x2
§ 5.3. Сравнение двух мер сложности для одной последовательности систем из 2£ одночленов от 21 переменных
Список литературы

Введение
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Данная работа относится к одной из центральных областей дискретной математики и математической кибернетики — теории синтеза и сложности управляющих систем, получающей постановки задач и находящей многообразные применения в информатике и вычислительной технике.
Проблему синтеза управляющих систем кратко можно сформулировать следующим образом. Задан запас элементов (базис), реализующих некоторые функции. Заданы правила построения из элементов более сложных объектов — схем, а также задан способ нахождения по схеме реализуемой (вычисляемой) ею функции; схема определяет строение, а функция — поведение управляющей системы или модели вычислений. Задача состоит в построении для каждой рассматриваемой функции схемы, которая реализует эту функцию, причем обычно важно не просто построить схему, но и добиться, чтобы она была в каком-то определенном смысле наилучшей. Качество схемы обычно выражается с помощью какой-либо из мер сложности, среди которых рассматриваются, например [58, 17, 50, 123, 57, 4, 14], число элементов, стоимость, занимаемые объем или площадь, глубина, задержка, мощность и др.
Если базис является конечным, то существует тривиальный переборный алгоритм решения этой задачи. Однако реально воспользоваться им чаще всего невозможно, так как с ростом числа элементов в схемах количество схем растет очень быстро и применение тривиального метода

что сразу дает пример нижней оценки, вдвое большей, чем дается теоремой 2.1 — для меры сложности 12 при фиксированных размерах матриц в силу теоремы 4.1 такого эффекта (с точки зрения асимптотики) быть не может, а для меры сложности I — такого эффекта не может быть для матриц малого размера.
В § 5.1 исследуются самые простые случаи — когда матрицы имеют размеры 1 х д, р х 1 и 2 х д. И если в первом случае рост сложности вычисления в третьей модели устанавливается как простое следствие предыдущих результатов, то для последних двух типов матриц при изучении асимптотики роста обнаруживается новый эффект.
Для произвольной матрицы А размера р X д определим величину Т(А) равенством
Т(А) = шах {тах{ан, а2
У- 1<Л<9
Таким образом, Т(А) — это максимум абсолютных величин попарных произведений элементов матрицы А, где максимум берется по всем парам элементов, удовлетворяющим двум условиям — эти элементы должны находиться в одном столбце и иметь разные знаки (если таких пар нет, то
Т(А) = 0).
С использованием теоремы 2.1 в работе устанавливается справедливость для любой целочисленной матрицы А неравенства /р(А) >
ктах{Т(А), 1}. Величина кТ(А) может превосходить величину к.О(А), но не более, чем в 2 раза.
Теорема 5.3. Для произвольной последовательности целочисленных матриц А(п) = (а(п)) размера 2 х д{п), удовлетворяющей условию
д(п)
logmax а(п)
при п —» оо, справедливо асимптотическое равенство 1р(А(п)) ~ logmax{Z>(A(n)), Т(А(п))}.