Cтраница 3
Излагаемый подход будет комбинацией метода ветвей и границ и МСП, который будет использоваться для получения нижних оценок, поскольку переход от дискретных переменных и непрерывным позволяет применять численные методы нелинейного программирования. Общая схема метода ветвей и границ для всех четырех случаев совпадает с описанной выше. [31]
Это наводит на мысль, что в рамках понятия класса Pj t q трудно рассчитывать на получение высоких нижних оценок. Еще больше убеждает в этом пример функции /, построенной Сэвиджем [82] ( как он отмечает), по аналогии с функцией из неопубликованной работы А. [32]
Переменные погрешности, зависящие от времени и не вошедшие в среднюю погрешность, суммируются арифметически для получения нижней оценки стабильности системы Так же суммируются и переменные погрешности, зависящие от температуры, чтобы получить оценку температурного коэффициента подсистемы. [33]
Исследование верхних оценок линейной сложности для А-ЛРП над модулями без кручения, областями целостности и над прямыми суммами колец и модулей будет продолжено в следующем параграфе параллельно с получением нижних оценок линейной сложности. [34]
Поскольку любая поверхность текучести в пространстве тц, 7i2, сг22 может быть изнутри и снаружи аппроксимирована многогранниками, то решения для кусочно линейных поверхностей в соответствии с указанной в [9] теоремой могут быть использованы для получения верхней и нижней оценки веса конструкции. [35]
Используя соотношения (5.6) и формулы возвращения, также удается убедиться, что с уменьшением параметра а застойные зоны в элементе симметрии течения отодвигаются от соответствующего источника, увеличиваясь при этом в размере по аналогии со схемой рис. 5.11. Предельное ( а 0) решение задачи Б может быть использовано для получения нижней оценки размеров застойных зон подобно тому, как это описано на примере задачи А в разделе 2 данного параграфа. [36]
Получение нижних оценок, линейных относительно п - числа аргументов функции ( или в общем случае относительно объема входной информации), обычно все-таки не вызывает больших трудностей. Получение более сильных нижних оценок - - значительно более сложная задача. Наиболее высокие нижние оценки, к-рые к настоящему времени ( 1984) удалось получить, имеют порядок и2, если не считать оценок, получающихся при очень сильных ограничениях на класс у. [37]
Мы рассмотрели примеры формул верхних оценок временной сигнализирующей функции. Процесс получения нижних оценок оказывается более сложным, и пока известна одна такая оценка для частного вида НС-грамматики, которую мы приведем без доказательства. [38]
Тогда из доказательства условия реализуемости в [4] следует, что сложность реализации / не меньше, чем га ( /) - в противном случае можно было бы построить для / уравнение меньшего порядка. Это свойство будет использовано для получения нижних оценок сложности индивидуальных функций. [39]
Известно [2,27], что коммутационная сеть содержит асимптотически не меньше п Iog2 n ребер. Возникает вопрос, не приближает ли это нас к получению нелинейной нижней оценки сложности для какой-нибудь схемы. [40]
Заметим, что Q H в подынтегральном выражении зависит от г. Причем, большему значению этой величины соответствует большее значение скорости. Так как дебит в процессе глушения убывает, то для получения нижней оценки скорости следует принять QH QH ( t) в отличие от плотности, которая оценивается по дебиту в начале шага. [41]
Задача минимизации глубины формул с помощью эквивалентных преобразований формализуется здесь в общеалгебраическом плане. Для одной специфической алгебраической системы 20 разработаны в духе динамического программирования специальные методы получения нижних оценок глубины. Из этих нижних оценок для 20 автоматически вытекают точно такие же нижние оценки для двух систем: ( i) класса арифметических выражений, содержащих только сложение и умножение, и ( Н) класса выражений над конечными языками, содержащих только операции объединения и конкатенации. [42]
Оставалась все-таки надежда, что нелинейную нижнюю оценку сложности можно получить, рассматривая такую сеть с п входами и п выходами, для которой несущественна информация о том, какой именно вход с каким выходом должен соединяться, но зато имеется возможность любое множество входов соединить непересекающимися цепями с любым равномощным множеством выходов. Этим путем пытался идти Э. И. Нечипо-рук, пока не обнаружил, что число ребер такой сети может быть сделано порядка / г, а значит, этот путь для получения нелинейных нижних оценок сложности тоже закрыт. [43]
Наибольшее распространение получили поисковые методы как наиболее гибкие и универсальные. Кроме того, поисковые методы могут быть эффективно использованы при синтезе оптимальной структуры химико-технологических систем, который в общем случае представляет собой задачу дискретно-непрерывного программирования; в частности, они могут быть использованы при получении нижних оценок в методе ветвей и границ ( см. гл. [44]
Этому направлению и посвящен обзор. В нем рассматривается главным образом двузначный случай, когда переменные принимают лишь два значения 0 и 1, а базис Б состоит из булевых функций, Ставилось целью в двузначном случае как можно полнее охватить методы получения нижних оценок сложности, причем не только для схем произвольного вида, но и для схем с некоторыми, правда, лишь наиболее естественными ограничениями. [45]