5. Соседние интервалы. Утверждение о соседних интервалах.

Соседние интервалы

Рассмотрим пару интервалов булева пространства Bⁿ: I₁ (₁, ₁)  и I₂ (₂, ₂) .

Интервалы I₁, I₂ называют соседними, если они совпадают по номерам внешних компонент, но различаются по значению одной из них; ее называют ортогональной компонентой, а интервалы I₁, I₂ - соседями по данной компоненте.

Примеры. Рассмотрим три пары интервалов

Интервалы I₁, I₂ являются соседями (по первой компоненте), I'₁, I'₂ не являются соседями (различаются по двум внешним компонентам), I''₁, I''₂ также не соседи (различаются по номерам внешних компонент).

Утверждение о соседних интервалах

Два соседних интервала ранга r (размерности s)  не пересекаются, а их объединение образует интервал ранга r -1 (размерности s +1).

Доказательство. Соседние интервалы   I₁  и  I₂  не пересекаются, как так их ортогональная компонента во всех векторах одного интервала равна 0, а в векторах другого равна 1. Мощность объединения таких интервалов равна сумме их мощностей: / I / = / I₁  I₂ / = / I₁ / + / I₂ / = 2^s + 2^s = 2^s+1, т.е. она оказывается целой степенью двойки (s+1-й). Количество компонент в векторах множества   I , претендующих быть внутренними, тоже равно s +1, так как к   s внутренним компонентам интервалов   I₁  и  I₂ добавляется еще одна, ортогональная, компонента. Это равенство означает, согласно рассмотренному ранее алгоритму, что множество  I  образует интервал размерности  s +1 (ранга  r -1, так как r + s = n ).

Определение. Операцию объединения двух интервалов I₁ и I₂, соседних по i – й компоненте, назовем склеиванием интервалов i-ой компоненте, а результат их склеивания I = I₁  I₂  - расширением каждого из интервалов I₁ и I₂ по i – й компоненте.

Пример. Соседние интервалы ранга 3 склеивания, образуя интервал I = 0 - - -1 ранга 2 (он является расширением интервалов I₁ и I₂  по третьей компоненте).

Очевидно, что на матрице в коде Грея соседние по i-й компоненте интервалы располагаются симметрично относительно оси симметрии этой компоненты.

6. Алгоритм распознавания интервала, заданного перечислением векторов.

Задано множество  A  булевых векторов длины  n. Требуется определить, образует ли множество  A  интервал и, если образует, найти его границы:  .

Шаг 1: если  мощность множества A не является целой степенью двойки, т.е. |A|  2^c, где c —  целое, то  A  —  не интервал, идем на конец.

Шаг 2: Считаем число  s несовпадающих компонент в векторах множества A, т.е. число компонент, претендующих быть внутренними; Если s  c, то A - не интервал, идем на конец; иначе A -  интервал,  s -  его размерность, r=n-s  - ранг;

Шаг 3: Находим границы интервала  и  Вектор минимального веса (из всех векторов множества A) является наименьшим элементом  интервала (), а вектор максимального веса  — его наибольшим элементом (), т.е.  и  - границы интервала.

Конец.

Примеры.

А = {010, 011, 001}: множество не образует интервал, так как его мощность, равная 3, целой степенью двойки не является.

А = {010, 011, 001}: множество не образует интервал – мощность является целой степенью двойки, но показатель степени c = 2 не совпадает с количеством компонент s = 3, претендующих быть внутренними (это первая, третья и четвертая компоненты).

А = {010, 011, 001,000}: множество образует интервал, так как его мощность является целой степенью двойки (c=2), и эта степень совпадает с количеством компонент s=2, претендующих быть внутренними (это вторая и третья компоненты). Границы интервала:  = 000,  = 011.

7. Распознавание интервалов на матрице в коде Грея. Типы интервалов.

Начало: задана матрица Грея с отмеченными клетками, которые образуют множество А.

Шаг 1: Если число клеток множества А не являются целой степенью двойки, т.е. |А|2^с, то А – не интервал, идем на конец.

Шаг 2: Если множество А лежит симметрично относительно осей симметрии с компонент (его можно «разрезрезать» осями на симметричные половины, затем четвертины на симметричные осьмушки и так далее до тех пор, пока множество А не «разрежется» на отдельные клетки), то А – интервал, идем на конец, иначе А не интервал.

Конец.

Примеры.

На левой матрице задан интервал – 0 - - 1 (8 клеток и оси симметрии трех компонент), на правой – не интервал (4 клетки и ось симметрии лишь одной компоненты).

Очевидно, что интервалами являются следующие множества:

- каждая отдельная клетка,

- любая пара симметричных клеток, в том числе радом лежащих,

- любая строка и любой столбец,

- любая пара симметричных строк и столбцов, в том числе рядом лежащих,

- любой «квадрат» размером 2x2,

- любая половина или четвертина матрицы,

- четверка клеток, лежащих в углах матицы,

- и не только они.

Определение. Интервал I_max(f) назовем максимальным для булевой функции f (x₁, x₂, ..., x_n), если он является допустимым для этой функции и не существует другого допустимого интервала I (f), такого что I_max(f)  I(f), другими словами, если после расширения интервала по любой компоненте он становится не допустимым.

Пример. I₁ (f) = - 1 1 — максимальный интервал,

I₂ (f) = 1 1 1— не максимальный.