Алгоритм Флойда

Постановка задачи: имеем непyстой взвешенный гpаф G=(V, E) с пpоизвольными весами ребер (дуг). Требуется найти длины кpатчайших пyтей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров.

Инициализация:

1. Построим матрицу D⁰ размерности |V| x |V|, элементы которой определяются по правилу:

1. d_ii⁰= 0;

2. d_ij⁰= Weight(v_i, v_j), где i<>j, если в графе существует ребро (дуга) (v_i, v_j);

3. d_ij⁰= бесконечность , где i<>j, если нет ребра (дуги) (v_i, v_j).

2. m:=0.

Основная часть:

1. Построим матрицу D^m+1 по D^m, вычисляя ее элементы следующим образом:

d_ij^m+1=min{d_ij^m, d_i(m+1)^m + d_(m+1)j^m}, где i<>j; d_ii^m+1=0 (*).

Если d_im^m + d_mi^m < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину v_i; ВЫХОД.

2. m:=m+1; если m<|V|, то повторяем шаг (1), иначе элементы последней построенной матрицы D^|V| равны длинам кратчайших путей между соответствующими вершинами; ВЫХОД.

Понятие отношения, атрибута отношения, домена атрибута, кортежа. Связь с теоретико-множественной моделью.

Отношение. Отношением R степени n, называют подмножество декартовa произведения множеств D₁, D₂, ..., D_n(n≥1), не обязательно различных.

Исходные множества D₁,D₂,...,D_n называются доменамии представляют собой множества допустимых значений.

Атрибут отношения есть пара вида <Имя_атрибута : Имя_домена>.Имена атрибутов должны быть уникальны в пределах отношения. Часто имена атрибутов отношения совпадают с именами соответствующих доменов.

Домен атрибута – это мн-во всех возможных значений данного атрибута.

Кортежотношения— это множество упорядоченных пар вида <Имя_Атрибута, Значение>, по одной такой паре для каждого атрибута в отношении. Значение должно являться допустимым значением типа данных или домена данного атрибута.

Билет 8

Крутое восхождение по поверхности отклика (в планировании эксперимента).

В планировании эксперимента поверхностью отклика называют уравнение связи выхода объекта с его входами.

В 1951 году Бокс и Уилсон предложили использовать последовательный "шаговый" метод движения к экстремуму выхода объекта. Вначале ставится небольшая серия опытов (ортогональный план I порядка) для локального описания небольшого участка поверхности отклика полиномом первой степени. Коэффициенты линейной модели являются оценками составляющих градиента: . Далее движение осуществляется по поверхности отклика в направлении оценки градиента: .

Здесь – величина шага. Это движение сопровождается одновременным изменением всех факторов (рис. 3.3.1). Если одного шага окажется недостаточно, то в новой точке ставится новая небольшая серия опытов и находится новое направление на экстремум для движения по поверхности отклика. Шаговый процесс движения по поверхности отклика продолжается до тех пор, пока исследователь не попадет в "почти стационарную область" (окрестность экстремума), где линейное приближение оказывается уже недостаточным для описания поверхности отклика. Здесь ставится большая серия опытов и поверхность отклика описывается полиномом второго, а иногда и третьего порядка.