Cтраница 2
Стабильность важна, поскольку некоторые алгоритмы применительно к стабильным правилам могут существенно упрощаться. В качестве примера можно рассмотреть алгоритм редукции констант, который описан в разд. [16]
Каковы преимущества и недостатки специального представления tuple - З, предложенного в разд. Предложите, как можно модифицировать алгоритм редукции графов, описанный в разд, 11.3, чтобы реализовать вычисление аппликативного порядка. [17]
Доказательство леммы 13.2 сводится к доказательству четырех предложений. Из них первые два показывают, что алгоритм редукции не создает и не разрушает блоков. Остальные два показывают, что к ациклическому гиперграфу всегда применимо одно из двух правил удаления. [18]
Теперь мы покажем, как работает реверсирование указателей при редукции графов, обрисовав в общих чертах алгоритмы и дав два примера, иллюстрирующие их основные особенности. После этого нам будет просто расширить данный выше алгоритм редукции, чтобы включить в него реверсирование указателей. [19]
Качество ИП как измерительной компоненты ИВП и качество ИВП как средства измерения в теории ИВ С определяется точностью измерения, выполняемого на ИВП, то есть точностью оценивания измеряемого сигнала или некоторых его параметров. Поэтому ниже, изучая свойства ИВП как средства измерения, мы будем считать, что в ВП реализован алгоритм редукции, минимизирующий погрешность интерпретации измерения в классе линейных преобразований выходного сигнала ИП, см. гл. [20]
Качество ИП как измерительной компоненты ИВП и качество ИВП как средства измерения в теории ИВС определяется точностью измерения, выполняемого на ИВП, то есть точностью оценивания измеряемого сигнала или некоторых его параметров. Поэтому ниже, изучая свойства ИВП как средства измерения, мы будем считать, что в ВП реализован алгоритм редукции, минимизирующий погрешность интерпретации измерения в классе линейных преобразований выходного сигнала ИП, см. гл. [21]
Однако он не гарантирует сходимости. Объясняется это тем, что используемый в нем критерий хоть и имеет минимум, но он является относительно плоским в различных направлениях. Алгоритмы редукции, основанные на минимизации L2 - нормы дают хорошие результаты, тем не менее, им свойственны следующие недостатки. [22]
Кодда состоит в том, что любая информационная система общего назначения должна по меньшей мере обладать способностью отвечать на любые запросы альфа-языка. Существование алгоритма редукции показывает, что база данных, в которой реализована реляционная алгебра, обладает необходимой селективной силой. [23]
Пусть теперь Я получается из Я удалением вершины А по правилу УВ. Предположим, что Hjf обладает множеством сочленения, в то время как Я д представляет собой блок. Поскольку правила УР и УВ не порождают новых блоков, их не порождает и алгоритм редукции. [24]
Пусть теперь Я получается из Я удалением вершины А по правилу УВ. Предположим, что Я обладает множеством сочленения, в то время как Я представляет собой блок. Поскольку правила УР и УВ не порождают новых блоков, их не порождает и алгоритм редукции. [25]
Доказательство леммы 13.2. Согласно предложению 13.2, редуктивный алгоритм Грэхема сохраняет ацикличность. Если в процессе редукции ациклического гиперграфа Я, выполняемой с помощью этого алгоритма, на каком-либо шаге окажется, что промежуточный гиперграф нередуцирован, то к нему можно применить правило УР. Если же этот промежуточный гиперграф редуцирован, то либо мы уже достигли гиперграфа с единственным ребром, либо выполняется предложение 13.4, и мы можем использовать правило УВ для удаления некоторой терминальной вершины. Поскольку при применении правил редукции в алгоритме Грэхема общее количество ребер и вершин уменьшается, то этот алгоритм постепенно редуцирует Я до пустого гиперграфа. С другой стороны, алгоритм редукции не может завершиться успешно в случае циклического гиперграфа Я. Действительно, такой гиперграф должен иметь по крайней мере три ребра. Если бы редукция Я завершалась успешно, то одним из ее промежуточных результатов оказался бы гиперграф, обладающий в точности двумя ребрами и тем самым ациклический. [26]