Нахождение - покрытие
Cтраница 1
Нахождение минимального кольцевого покрытия для множества F-зависимостей G начинаем с нахождения минимального покрытия F для G. Далее группи-руем F-зависимости с эквивалентными левыми частями в одну CF-зависимость. При этом возникает вопрос: является ли редуцированное минимальное кольцевое множество одновременно редуцированным минимальным множеством F-зависимостей. [1]
 |
Инфракрасный спектр поглощения пленки ПИЛ. [2] |
С увеличением глубины нахождения покрытия в грунте концентрация указанных кислородсодержащих функциональных групп уменьшается, но во всех случаях она больше, чем в исходных образцах. [3]
Теперь можно легко получить алгоритм нахождения редуцированных покрытий. [4]
Поскольку самой трудной частью алгоритма является нахождение редуцированного, минимального, кольцевого покрытия для входного множества F-зависимостей, создаваемый алгоритм будет иметь полиномиальную временную сложность. Таким образом, устраняется первая проблема, упомянутая в предыдущем разделе. [5]
Нетрудно понять, что вопрос о нахождении минимальных е-сетей в пространстве Z) jg упирается в задачу о нахождении наиболее экономного покрытия подмножеств пространства Dn параллельно сдвинутыми телами eS, а задача о нахождении максимальных 2е - различимых множеств сводится к задаче о наиболее удачном размещении в Dn параллельно сдвинутых непересекающихся тел & S с центрами на заданном множестве. [6]
Сравнивая решение, полученное при таком подходе, и точное решение, можно провести аналогию между приближенным и точным решениями задачи покрытия: для нахождения приближенного покрытия таблица разбивается на части, каждая из которых покрывается отдельно. В этом причина того, что получаемое решение не минимально. Вместе с тем очевиден выигрыш во времени реализации. [7]
Стояла задача построения на основании полученных экспериментальных данных математической модели сложного процесса, слагающегося из отдельных частных процессов, которая заключается в анализе каждого из них и составлении математических уравнений, описывающих их на протяжении длительного времени нахождения покрытия в грунтовых средах. Основное внимание при этом было сосредоточено на выделении наиболее существенных сторон данного процесса и установлении их взаимной связи. [8]
Первый шаг модификации алгоритма SYNTHESIZE состоит в добавлении к F F-зависимости U - - С, где С - атрибут, не содержащийся в U. При нахождении кольцевого покрытия G для F зависимость U - С не будет исключена как избыточная, поскольку в F не существует другой F-зависимости с С в правой части. При нахождении минимального покрытия для F зависимость U - С можно комбинировать с F-зависимостями Х - Y, но тогда X - U и X должен быть универсальным ключом. [9]
Первый шаг модификации алгоритма SYNTHESIZE состоит в добавлении к F F-зависимости U - - С, где С - атрибут, не содержащийся в U. При нахождении кольцевого покрытия G для F зависимость U - - С не будет исключена как избыточная, поскольку в F не существует другой F-зависимости с С в правой части. При нахождении минимального покрытия для F зависимость U - С можно комбинировать с F-зависимостями Х - Y, но тогда X - U и X должен быть универсальным ключом. [10]
Для этой цели предложены приборы20, состоящие из хладо - стата и приспособления для сгибания испытуемых образцов во время испытания. Морозостойкость характеризуется временем нахождения покрытия в хладостате при заданной температуре до растрескивания при изгибе на стержне определенного диаметра. [11]
Изменения механических свойств покрытий при низких температурах обусловлены не только температурными факторами, но и условиями проведения испытания, строгое выполнение которых необходимо для получения надежных результатов. Главными условиями являются: скорость деформации, сроки нахождения покрытий в деформированном состоянии и длительность воздействия низких температур. [12]
То, что в литературе называют наименьшим покрытием, представляет собой множество Е ребер графа 6 ( X, А), такое, что каждая вершина графа С инцидентна по крайней мере одному ребру из Е и мощность множества Е - минимально возможная. Таким образом, поскольку Е можно рассматривать как доминирующее над вершинами графа О, то множество Е - наименьшее из таких множеств - можно назвать, согласно терминологии, использованной в этой главе, наименьшим доминирующим множеством ребер. Известна иная задача о нахождении наименьшего покрытия: нужно отыскать специальное множество М ребер графа О - в М не должно быть смежных ребер. Множество М называют паросочетанием, а множество М - с наибольшей мощностью - является наибольшим паросочетанием, его можно называть также наибольшим независимым множеством ребер. Эквивалентность задач о наибольшем паросочетании и о наименьшем покрытии демонстрируется в гл. Обратно, если М есть наибольшее паросочетание и для каждой вершины х1 с с д м ( VI) 0 добавляется ребро, инцидентное яг, то получающееся множество ребер образует наименьшее покрытие. [13]
То, что в литературе называют наименьшим покрытием, представляет собой множество Е ребер графа G ( X, А, такое, что каждая вершина графа G инцидентна по крайней мере одному ребру из Е и мощность множества Е - минимально возможная. Таким образом, поскольку Е можно рассматривать как доминирующее над вершинами графа G, то множество Е - наименьшее из таких множеств - можно назвать, согласно терминологии, использованной в этой главе, наименьшим доминирующим множеством, ребер. Известна иная задача о нахождении наименьшего покрытия: нужно отыскать специальное множество М ребер графа G - в М не должно быть смежных ребер. Множество М называют паросочетанием, а множество М - с наибольшей мощностью - является наибольшим паросочетанием, его можно называть также наибольшим независимым множеством ребер. Эквивалентность задач о наибольшем паросочетании и о наименьшем покрытии демонстрируется в гл. Там устанавливается, в частности, следующее утверждение: пусть в наибольшем покрытии Е степень вершины Xi есть 2Е () ( рассматриваются только ребра из Е), тогда, если для каждой вершины xt с dE ( xt) 1 удалить dE ( xt) - 1 ребер, инцидентных xt, то оставшееся множество ребер образует наибольшее паросочетание. Обратно, если М есть наибольшее паросочетание и для каждой вершины Xi с с dM ( xi) 0 добавляется ребро, инцидентное Х (, то получающееся множество ребер образует наименьшее покрытие. [14]
На первом этапе с использованием описанного выше алгоритма решается задача синтеза логической структуры ЛБД для фиксированных корневых точек входа в каноническую структуру. С учетом полученного решения на втором этапе решается задача выбора оптимального состава точек входа в сформированную логическую структуру. В качестве критерия оптимизации рассматривается минимум общего времени доступа к синтезированным записям, содержащим корневые группы деревьев поиска по всем запросам. Поставленная задача сводится к задаче нахождения наименьшего покрытия вершин ( записей), содержащих корневые группы деревьев поиска, возможными точками входа в структуру. Для решения данной задачи предлагается использовать известные алгоритмы. [15]
Страницы: 1