![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Алгоритм ФлойдаПостановка задачи: имеем непyстой взвешенный гpаф G=(V, E) с пpоизвольными весами ребер (дуг). Требуется найти длины кpатчайших пyтей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров. Инициализация: 1. Построим матрицу D0 размерности |V| x |V|, элементы которой определяются по правилу: 1. dii0= 0; 2. dij0= Weight(vi, vj), где i<>j, если в графе существует ребро (дуга) (vi, vj); 3. dij0= бесконечность , где i<>j, если нет ребра (дуги) (vi, vj). 2. m:=0. Основная часть: 1. Построим матрицу Dm+1 по Dm, вычисляя ее элементы следующим образом: dijm+1=min{dijm, di(m+1)m + d(m+1)jm}, где i<>j; diim+1=0 (*). Если dimm + dmim < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину vi; ВЫХОД. 2. m:=m+1; если m<|V|, то повторяем шаг (1), иначе элементы последней построенной матрицы D|V| равны длинам кратчайших путей между соответствующими вершинами; ВЫХОД.
Понятие отношения, атрибута отношения, домена атрибута, кортежа. Связь с теоретико-множественной моделью. Отношение. Отношением R степени n, называют подмножество декартовa произведения множеств D1, D2, ..., Dn(n≥1), не обязательно различных. Исходные множества D1,D2,...,Dn называются доменамии представляют собой множества допустимых значений. Атрибут отношения есть пара вида <Имя_атрибута : Имя_домена>.Имена атрибутов должны быть уникальны в пределах отношения. Часто имена атрибутов отношения совпадают с именами соответствующих доменов. Домен атрибута – это мн-во всех возможных значений данного атрибута. Кортежотношения— это множество упорядоченных пар вида <Имя_Атрибута, Значение>, по одной такой паре для каждого атрибута в отношении. Значение должно являться допустимым значением типа данных или домена данного атрибута. Билет 8 Крутое восхождение по поверхности отклика (в планировании эксперимента). В планировании эксперимента поверхностью отклика называют уравнение связи выхода объекта с его входами. В 1951 году Бокс и Уилсон предложили использовать последовательный "шаговый" метод движения к экстремуму выхода объекта. Вначале ставится небольшая серия опытов (ортогональный план I порядка) для локального описания небольшого участка поверхности отклика полиномом первой степени. Коэффициенты
Здесь
|