Page 69 - 4336

в строго зростаючому порядку. Таким чином, елементи векторів

k
із R різні та упорядковані в порядку зростання їх величин.
5
Наприклад, вектор (-3, -1, 0, 4, 27) належить R . Наступні вектори
є припустимими: А=(-4, 0, 7, ∞), В=(3, 4, ∞, ∞). З іншого боку,

вектори C=(-4, 3, 3, 9) та D=(-9, 0, ∞, 9) є неприпустимими.

В алгоритмі подвійного пошуку використовуються дві

спеціальні алгебраїчні операції. Вони називаються узагальненими

операціями, оскільки виконуються не над числами, а над

векторами. Перейдемо до розгляду даних операцій. Перша з них

називається узагальненою операцією мінімізації, друга –

узагальненою операцією додавання. Дані операції є двомісними,

тобто вони можуть виконуватися тільки над двома векторами.

Нехай А=(а , а , ..., а ) та B=(b , b , ..., b ) – два вектори із
k
1
2
k
2
1
k
множини R . Узагальнена операція мінімізації (порівняння) для А
та В, що позначається знаком , визначається в такий спосіб:
A  B  min k (a i ,b i : i  , 2 , 1 ..., ) k . (4.9)

Іншими словами, при виконанні узагальненої операції

мінімізації спочатку визначається множина усіх елементи двох

заданих векторів розмірності k, а потім будується третій вектор

такої ж розмірності, складений з k різних найменших по величині

елементів цієї множини, розташованих у строго зростаючому

порядку. Якщо в новому векторі число скінченних елементів

менше його розмірності, то інші елементи приймаються рівними

∞. Як приклад, розглянемо вектори А=(-4, 0, 1, ∞) та В=(1, 7, 8, 9).

Множина, утворена з елементів векторів А та В, є наступною:

{-4, 0, 1, ∞, 1, 7, 8, 9}. Різні по величині елементи цієї множини

можуть бути впорядковані в такий спосіб: {-4, 0, 1, 7, 8, 9, ∞}.

Оскільки розмірність векторів А та В рівна 4, результатом

виконання узагальненої операції мінімізації над ними є вектор

69