dmagin Jun 26 at 10:09

Пара слов об алгебре интервалов

Hard

10 min

3.5K

Mathematics*Algorithms*

Tutorial

Основные определения

Пройдемся по основным принципам, которые лежат в основе алгебры интервалов.

Во-первых, что такое интервал. Судя по термину, - это нечто, что находится между (inter) неких величин (values). Пока не очень понятно, о чем речь, но вообще данное определение вполне себе удачно. Бывают хуже.

Values - это границы интервала. Есть левая граница (начало) и есть правая (конец). Границы - это точки на шкале (оси, пространстве).

Шкала - здесь это одномерное пространство, которое имеет направление. Направление означает, что элементы данного пространства могут быть упорядочены. Именно упорядоченность дает возможность определения оператора "между".

Шкала может быть непрерывной (как время):

Может быть дискретной. Например, алфавит: ['а' ,'б', 'в', 'г', ... , 'ю' , 'я']

Интервалы и границы - не одно и то же!

Второе и, пожалуй, главное, что следует уяснить. Интервал и точки - это два разных типа данных.

В чем отличие интервала от точки? В размере, - у интервала есть конечный размер, у точки нет. Точка - это предельная сущность. При этом точка может принадлежать интервалу (находиться внутри), а может и не принадлежать. Например, точка $\pi$ принадлежит числовому интервалу [3, 4]. И даже может быть границей другого интервала, но сама интервалом не является.

Поэтому (внимание!) - вопрос о том, принадлежат ли интервалу его границы - не имеет особого смысла. Я бы давал на такой вопрос ответ Неопределено, - можно считать, что принадлежит, а можно и нет.

Тут может возникнуть законный вопрос. А как же тогда быть со всеми этими "включительно" или "исключительно", которые используются при задании интервалов? Вот, например, интервал "со 2-го по 5-е" включает 5-е число. А интервал "со 2-го до 5-го" - не включает. Вроде как очевидно, что надо указывать - входят границы в интервал или нет.

Ответ тут такой. Зачастую интервал задается не явными границами (точками), а границами других интервалов меньшего размера. И в приведенном выше примере числа 2 и 5 - это не точки, а интервалы. Соответственно, у них есть границы. Первый интервал [2, 5] задан как "от левой границы 2 до правой границы 5", а второй [2, [5 - "от левой границы 2 до левой границы 5".

Числа - интервалы, их границы обозначены синим

Как отличить, является ли некая сущность интервалом или точкой? По вкладу в общую меру (длину) интервала. Дает вклад - интервал. Нет - точка.

Элементы алфавита [а, б, в, г, д, ...] - это интервалы. Потому что каждая буква дает вклад в длину интервала. Например, длина (в буквах) интервала [б, д] равна 4 - суммарная длина всех смежных интервалов. А что же тогда является точками алфавита? Границы его букв. Левая граница буквы 'б' - это точка '[б'. Правая граница буквы 'в' - это точка 'в]'.

На всякий случай уточним, что числа - не всегда интервалы. Могут быть и числовые границы (числа-точки). Примерно так:

Добавили указание точности чисел в виде бесконечно повторяющегося нуля. Так подробно останавливаемся на отличии точек от интервалов, потому что это источник путаницы - как именно задан интервал.

Еще для закрепления. Само множество границ может являться шкалой (поскольку поддается упорядочиванию). В этом случае уже граница (как элемент) является интервалом, а точками такой шкалы будут границы между границами. Но слава богу нам сюда не надо.

Отметим, что языки программирования не очень хорошо ладят с проблемой ~~отцов и детей~~ отличия интервалов от точек. Типичный проблемный вопрос - является ли литерал времени "23.59.59" концом дня или нет? Равен ли он началу дня "00.00.00"?

Смежные интервалы, типы границ

Как уже отмечалось, смежными называют интервалы, имеющие общую границу.

Шкала, образованная смежными интервалами

Но из-за того, что границы большого интервала задают как границы малых возникает проблема идентификации. Человеку понятно, что конец сегодняшнего дня совпадает с началом завтрашнего, но программе это объяснить сложнее. Обычно программы умеют определять эквивалентность, но не смежность. На практике это означает, что все типы границ, заданные как границы неких стандартных (базовых) интервалов, должны быть приведены к одному типу - либо все левые, либо все правые. Это дает возможность программе сворачивать границы в алгебраических выражениях. Примерно так:

[2, 5] + [6, 10] == [2, [6 + [6, [11 == [2 - [6 + [6 - [11 = [2 - [11 == [2, [11

Фактически в данном примере мы использовали векторную алгебру для операций над границами.

Линейные комбинации границ

Основой алгебры границ является представление границ интервала (отрезка) как разности его левой и правой границы. Назовем это граничным представлением интервала.

Пусть левой границей интервала s является [s, а правой s]. Тогда граничным представлением интервала будет выражение:

ds = [s - s]

Здесь '-' - это минус, а не тире.

В общем случае по паре точеки можно построить границу интервала:

В формуле вывели явным образом значение скалярных коэффициентов (1 и -1) перед границами. Данные коэффициенты можно трактовать как координаты [1, -1] в упорядоченном базисе из элементов. Далее мы везде используем первые латинские буквы $a < b < c < d < \dots$ для обозначения границ (не стоит путать их со скалярными коэффициентами - числами).

Вообще выражение, которое представляет собой разность элементов, можно трактовать как аффинный вектор. Особенность аффинных векторов в том, что сумма коэффициентов их линейной комбинации равна нулю. Такие комбинации иногда называют балансовыми. А какие еще бывают? Бывают, например, - барицентрические, - это когда сумма коэффициентов равна 1, - такие комбинации соответствуют точкам (элементам) пространства.

Итак, границы интервала (отрезка) можно трактовать как аффинный вектор (при условии что интервал замкнут, то есть у него есть начало и конец), заданный на множестве границ. Это в свою очередь означает, что все операции над границами интервалов имеют свои аналоги в аффинном пространстве, и наоборот - свойства аффинных векторов применимы к интервалам.

Граничное представление

Границы интервала (как и аффинный вектор) могут состоять не из двух точек, а из произвольного их количества. Лишь бы кратность комбинации оставалась нулевой. Ну например, возможна такая комбинация (интервал):

Есть и отличие интервалов от векторов. Интервал определен на упорядоченной шкале, а аффинный вектор направленности пространства не требует. Упорядоченность позволяет отразить на шкале граничное представление интервала как всплески коэффициентов у его границ:

Отметим также, что для операций сложения/вычитания (и даже умножения, о котором ниже) векторов метрика (шкалы) не требуется. То есть не надо знать длины интервалов (расстояния между границами) для того, чтобы их складывать, объединять и пересекать. Достаточно знать их порядок (уметь сортировать).

В программном коде граничное представление можно реализовать как табличку с двумя колонками. В одной (ключевой) - границы (точки), в другой - их коэффициенты (амплитуды). Операция свертки - суммирует амплитуды по одной и той же границе. Хотя можно сразу предусмотреть колонку и для высот (накопительных амплитуд), - пригодятся при расчете пересечений.

Линейные формы

С одной задачей (сложения интервалов и слияния границ смежных интервалов) разобрались. Но было бы ошибкой сделать вывод, что граничное представление - это и есть каноническое представление множества интервалов. Как уже отмечали выше, интервалы - это независимая сущность. В базе данных, например, мы можем привязывать к интервалам-отрезкам определенные свойства, значения которых будут разными для разных интервалов. Граничное представление такой возможности не дает (тут можно делать всякие оговорки, но не хотим застревать).

Комбинация границ оставляет неопределенным ответ на вопрос, а какие именно интервалы-отрезки тут заданы? Это могут быть два отрезка (a, b) и (c, d) . А могут быть отрезки (a, d) и (c, b) .

Вышесказанное означает, что самому интервалу (а не его границам) должна соответствовать иная алгебраическая сущность (не векторная), из которой можно получить его граничное представление. И конечно, такая сущность есть (поскольку мы тут не первые возимся с линейными пространствами). Называется билинейной формой. Про них я уже писал на хабре, - здесь кратко повторю основные свойства.

Билинейные формы можно трактовать как некое умножение произвольных элементов пространства или способ записи их связывания в пару (аргументы формы):

$F = (a, b), \quad F^T = (b, a)$

Мы используем для простоты записи круглые скобки, хотя это не всегда удобно. Но с выбором типа скобок в алгебре всегда проблемы, - сущностей много, а скобок мало.

Главное свойство билинейной формы - по каждому аргументу форма сохраняет правила линейности:

Что тут видим. Слева - форма, аргументы которой являются линейными комбинациями каких-то элементов. Справа - линейная комбинация самих форм. То есть формы тоже могут образовывать линейные комбинации. Коэффициенты данных комбинаций можно записать в виде матрицы (поскольку в форме - два аргумента). Для нашего примера матрица коэффициентов будет такой:

$\begin{array} {c|c c c c} F & c & d \\ \hline a & 1 & 1 \\b & 1 & 1 \end{array}$

Если оба аргумента формы совпадают, то форма называется квадратичной:

Есть выделенные линейные комбинации. Например, симметричная форма

$\{a, b\} == \{b, a\} == (a, b) + (b, a)$

называется полярной (или поляром). Иногда (а, может, и чаще) используют нормированный вариант поляра - делят его на 2. Такую форму обозначим для простоты знаком произведения:

$a*b = \{a, b\}/2 == ((a, b) + (b, a))/2$

Отметим, что если аргументы совпадают, то нормированный поляр становится квадратичной формой:

a*a == ((a, a) + (a, a))/2 = (a)^2

Это были краткие и скучные сведения про формы, пора применить их к интервалам.

Интервал - это квадратичная форма вектора

Постулируем, что интервалу-отрезку соответствует квадратичная форма вектора, образованная его границами. Для границ a, b форма отрезка будет такой:

Почему именно так? Можно привести пару соображений. Во-первых, именно такая же форма используется для связей в симметричном графе. Связь связывает две вершины, а интервал - две границы. Во-вторых, свойства данной формы позволяют удобным образом вычислять параметры интервала. В частности, находить пересечение двух интервалов.

Граничное представление интервала строится применением направленного граничного оператора $\partial$ к форме интервала:

$ds = \partial(a - b)^2 = a - b$

Направленный граничный оператор определен только на направленной шкале (оси). Мы из меньшей границы вычитаем большую. Этим данный оператор отличается от граничного оператора на симплексах (про который мы рассказывали в статье про внешнюю алгебру).

Таким образом, форма самого интервала- симметрична (не имеет направленности), поскольку квадратична. Форма его границ- ориентирована. Переход от формы к границам выполняется граничным оператором - эквивалент операции дифференцирования.

Отрицательным интервалам соответствует отрицательная форма. Для границ интервалаформа будет такой:

Этим примером мы хотели показать, что для произвольного граничного представления его форманеобязательно совпадет с (ds)^2 .

В программном коде линейная комбинация интервалов-отрезков реализуется как таблица с двумя ключевыми колонками, в которых указаны границы интервала. В остальных колонках таблицы могут быть указаны свойства на данном интервале, в том числе - скалярный коэффициент данной формы (интервала).

Полярная форма интервала

Допустим, есть два аффинных вектора (или что то же самое - два граничных представления интервала): и. На заданном множестве границданные векторы можно представить как:

$dv = g_v^i b_i, \quad du = g_u^i b_i$

где- амплитуды (координаты) данных векторов. По повторяющемуся (немому) индексувыполняется суммирование. Напомним, что сумма амплитуд - нулевая: g_v^i 1_i = g_u^i 1_i = 0 .

Для полярной формы данных векторов есть полезное тождество, которое разлагает поляр по квадратичным формам векторов базиса (b_i - b_j) . Векторы базиса - это все комбинации, которые можно получить на множестве границ b_i . Тождество разложения:

$dv*du = \{dv, du\}/2 = -\sum_{i,j} w^{ij} (b_i - b_j)^2$

где коэффициенты образуют симметричную матрицу: $w^{ij} = (g_v^i g_u^j + g_v^j g_u^i)/2$

Например, для 4-х вершин $\{a, b, c, d\}$ векторы будут такими:

$dv = g_v^a a + g_v^b b + g_v^c c + g_v^d d, \quad du = g_u^a a + g_u^b b + g_u^c c + g_u^d d$

а полярное тождество таким:

$dv * du = -(w^{ab} (ab)^2 + w^{ac} (ac)^2 + w^{ad} (ad)^2 + w^{bc} (bc)^2 + w^{bd} (bd)^2 + w^{cd} (cd)^2)$

Доказательство мы тут не приводим, - оно несложное. Достаточно раскрыть формы и использовать нулевой баланс амплитуд.

Отметим, что полярное тождество никак не связано с направленностью оси - оно действительно для любого пространства. Вообще оно задает форму скалярного произведения векторов, но в интервальной трактовке эта форма соответствует пересечению интервалов. Покажем это.

Пересечение интервалов

Применим к полученной выше полярной форме границ двух интервалов направленный граничный оператор $\partial$ . Это сделать достаточно просто, поскольку мы знаем, что $\partial(b_i - b_j)^2 = b_i - b_j$ при условии, что b_i < b_j . Поэтому результатом взятия границы будет такое выражение:

$\partial(dv*du) = -\sum_{i,j} g^{ij} (b_i - b_j)$

Основное его отличие от предыдущего в том (помимо того, что вместо формы здесь векторы), что здесь матрица коэффициентов $g^{ij}$ является антисимметричной: $g^{ij} = -g^{ji}$ . Понятно почему - при перестановке границ вектор b_i - b_j меняет знак на противоположный.

Полученное выражение справедливо только для направленных пространств, поскольку при его получении используется сравнение границ.

Далее надо от матрицы $g^{ij}$ перейти к амплитудам самого интервала пересечения. То есть нам нужна граница интервала пересечения в виде g^i b_i . Для получения амплитуд g^i достаточно просуммировать матрицу $g^{ij}$ по строкам (или столбцам).

Но предварительно введем еще одно понятие, которое все равно всплывает рано или поздно при работе с границами интервала. А именно - наряду с амплитудой границы введем ее высоту. Возможно несколько определений высоты, - мы используем наиболее простой: высота границы вычисляется как суммирование всех амплитуд всех предыдущих границ, включая данную. Высоту вектораобозначаем как h_v^i :

$h_v^i = \sum_{j=0, i} g_v^j$

Тут суммирование направленное - от первой границы до текущей.

Теперь можно выполнить суммирование матрицы $g^{ij}$ с учетом баланса амплитуд. Получим итоговое выражение амплитуд границ пересечения:

$g^i = \sum_j g^{ij} = g_v^i h_u^i + g_u^i h_v^i - g_v^i g_u^i$

Данная формула позволяет рассчитать границы интервала пересечения (амплитуды g_i на базовом множестве границ) на основании амплитуд и высот исходных интервалов. От корректировочного слагаемого g_v^i g_u^i можно избавиться, выбрав другое определение высоты (учитывать амплитуду текущей границы с коэффициентом 1/2), но это уже нюансы.

Пример

Пусть на шкале есть 6 упорядоченных точек-границ: a < b < c < d < e < f и заданы два интервала: $dv = a - c + d - f, \quad du = b - e$ .

Определим область их пересечения согласно приведенной выше формуле.

Для начала приведем амплитуды к общему базису всех границ, - получим координаты g_v^i, g_u^i . Далее по координатам амплитуд рассчитаем высоты:

$dv: \quad g_v^i = [1, 0, -1, 1, 0, -1], \quad h_v^i = [1, 1, 0, 1, 1, 0]$

$du: \quad g_u^i = [0, 1, 0, 0, -1, 0], \quad h_u^i = [0, 1, 1, 1, 0, 0]$

Далее считаем амплитуды области пересечения, начиная с первой границы:

$g^a = g_v^a h_u^a + g_u^a h_v^a - g_v^a g_u^a = 0 + 0 - 0 = 0 \\ g^b = g_v^b h_u^b + g_u^b h_v^b - g_v^b g_u^b = 0 + 1 - 0 = 1 \\ \dots$

И т.д. В итоге получим g^i = [0, 1, -1, 1, -1, 0] , что в векторной форме означает: $\partial(dv * du) = b - c + d - e$ , что и ожидалось.

Особенности и ограничения

Следует иметь в виду, что определение пересечения интервалов через симметричную форму (произведение) имеет свои особенности.

Как известно, минус на минус - дает плюс. Это означает, что расчет пересечения отрицательного интервала с самим собой даст не отрицательный интервал (как можно ожидать от операции пересечения), а положительный (это мы уже отмечали выше). Поэтому если в исходных множествах интервалов встречаются области отрицательной высоты, то это может дать неожиданный результат.

Например, граница пересечения интервала a - 2b + c с самим собой согласно формулам выше будет такой: a - c . Это выглядит странно, но объяснимо. Дело в том, что исходные границы фактически представляют собой разность двух интервалов:. Между собой данные интервалы не пересекаются (a - b)*(b-c) = 0 , но вот при пересечении с самим собой отрицательный интервал превращается в положительный (b-c) . Ну и при сложении с (a - b) получаем результат a - c .

Другой момент касается трактовки кратности амплитуд. Если рассчитать пересечение с собой интервала с удвоенными амплитудами 2(a - b) , то получим результат как $\partial(2(a - b))^2 = 4(a - b)$ . Это связано с тем, что кратность амплитуд трактуется не как высота интервала, а как их количество. Фактически форма (2(a - b), 2(a - b)) означает, что у нас слева два интервала и справа - два. Всего областей пересечений будет 2*2 = 4.

Можно выделить интервалы, у которых граница от квадратичной формы совпадает с границей исходного интервала $ds = \partial(ds)^2$ , в особый класс. В частности данному классу принадлежат обычные положительные интервалы в виде отрезка. Для всех таких интервалов согласно тождеству имеет место инвариант, связывающий амплитуды g^i и высоты h^i :

g^i = 2g^i h^i - (g^i)^2

откуда следует, что либо амплитуда границы равна нулю g^i = 0 , либо ее высота связана с амплитудой как h^i = (g^i + 1)/2 .

Как правило в прикладных задачах при расчете пересечений интервалы имеют положительную высоту и единичную кратность. Так что можете смело использовать приведенные выше соотношения.

На этом пора закругляться. Надеюсь, смог кое-что прояснить в данном вопросе.

Hubs: