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

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

Интервалы, интервалы,‑ где тут лево, где тут право...

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

На практике однако встречаются и более сложные задачи. Допустим, например, что в некой гостинице есть два свободных номера. Но один свободен со 2-го по 5-е число, а второй - с 6-го по 10-е. Клиент интересуется, есть ли возможность поселения на 8 дней? Правильный ответ - "да, есть, но с переселением (лесенкой)". Для такого ответа программа должна уметь распознать, что интервалы [2, 5] и [6, 10] являются смежными , а значит, их можно сложить, получив общий доступный интервал [2, 10], длина которого (9) превышает запрашиваемый.

Другая более редкая, но и более интересная задача - определить область пересечения двух множеств интервалов. Сложность в том, что количество интервалов в сравниваемых множествах может быть произвольным. Программист, который умеет только в сравнения "на меньше/больше" (или даже в between), столкнется при реализации с трудностями формализации.

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

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

Перечислим типичные вопросы:

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

Здесь мы сделаем только один шаг - проведем мостик между внешним произведением и формами, покажем связь форм и тензоров. Прикладной аспект продемонстрируем на простейшей задаче определения неизвестных характеристик объекта по известным.

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

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

В данной статье мы расскажем о том, что такое внешняя алгебра, и для чего она нужна. Удивительно, но на Хабре почти нет статей о внешней алгебре при том, что ее прикладная ценность ничуть не меньше, например, реляционной алгебры.

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

Граф минимальной связности

Что такое пространство графа

Мерность пространства и мерность базиса

Дистанционные координаты

Введение

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

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

"Дуэли запрещены в субботу, воскресенье и остальные дни недели."

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

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

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

Спектры невозможных решеток

А не замахнуться ли нам на Эдсгера нашего Дейкстру?