Как стать автором
Обновить
91
0
Дмитрий Малюгин @dmagin

Исследователь

Отправить сообщение

Как измерить кривизну пространства с помощью линейки

Время на прочтение10 мин
Количество просмотров2.3K

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

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

Читать далее
Всего голосов 6: ↑6 и ↓0+6
Комментарии0

Внешняя алгебра, которую мы заслужили. Дополнение

Время на прочтение9 мин
Количество просмотров3K

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

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

Читать далее
Всего голосов 5: ↑5 и ↓0+5
Комментарии6

Внешняя алгебра, которую мы заслужили. Часть 2 — полиформы и графы

Время на прочтение15 мин
Количество просмотров3.2K

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

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

Читать далее
Всего голосов 7: ↑7 и ↓0+7
Комментарии2

Внешняя алгебра, которую мы заслужили. Часть 1 — симплексы и границы

Время на прочтение13 мин
Количество просмотров20K

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

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

Читать далее
Всего голосов 25: ↑24 и ↓1+36
Комментарии48

Экспресс-анализ метрических параметров графов

Время на прочтение11 мин
Количество просмотров5.4K
«А лохматость у меня повысилась.»



Итак, у нас на руках есть граф. Часто анализ графа сводят к его визуализации, поскольку «глаз — лучший инструмент». Не отрицая полезности вывода графа как картинки, отметим все же, что не все свойства графа можно увидеть. Некоторые надо считать.

Можно взять готовый пакет для работы с графами (например, NetworkX) и воспользоваться уже реализованными в нем функциями. Некоторые параметры графов имеют исключительно комбинаторный характер, и поэтому не подходят для графов с дробными значениями связей. Более универсальными характеристиками являются те, которые имеют метрическую основу. Далее мы приведем несколько таких параметров, способы их расчета и примеры использования.
Читать дальше →
Всего голосов 7: ↑7 и ↓0+7
Комментарии8

Как связать несвязанное

Время на прочтение6 мин
Количество просмотров3.4K
Явное лучше неявного.


В данной статье рассматривается задача пересчета неявных связей элементов графа в явные. В общем-то ответом является одна несложная формула, которая приведена под номером 3. Все остальные слова понадобились для того, чтобы рассказать, откуда она берется, и как ею пользоваться. Я написал данную статью для тех, кто интересуется анализом данных вообще и графов в частности.
Читать дальше →
Всего голосов 9: ↑9 и ↓0+9
Комментарии0

О близости вершин

Время на прочтение9 мин
Количество просмотров5.2K
«До того, как вы постигнете это, оно кажется чудом. Но после в нем нет ничего особенного.»

Не, не про горы, — про графы. В математике есть вопросы, формулировка которых доступна каждому, а вот решение нетривиально и без специальной подготовки трудно объяснимо. Одну из подобного рода проблем кратко можно выразить так — как правильно считать расстояния в направленных графах? Данную несколько абстрактную проблему можно свести к вполне конкретной мотивирующей задаче. Она умещается на одном рисунке:


Читать дальше →
Всего голосов 21: ↑18 и ↓3+15
Комментарии16

Геометрия данных 6. Граф-звезда

Время на прочтение7 мин
Количество просмотров8K
Это заключительная статья серии о ди- и би-координатах. Рассмотрим граф простейшей структуры и используем его для небольшого исследования. В качестве данных используем множество целых чисел — это удобное поле для демонстрации идей.



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


Допустим, у нас есть набор элементов, которые выглядят независимыми друг от друга, и могут служить в качестве вершин (реперов) базиса некого пространства. Для того, чтобы на данном базисе можно было определить метрику, элементы должны быть как-то связаны между собой. Как должна выглядеть такая связь, чтобы все элементы оставались равноценными?
Читать дальше →
Всего голосов 13: ↑13 и ↓0+13
Комментарии0

Геометрия данных 5. Преобразование базиса

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



В предыдущей части было рассмотрено определение базиса низкой размерности в пространстве высокой размерности и показано, каким образом можно определять дистанции между вершинами, не принадлежащими пространству базиса. При замене базиса требование сохранения метрических свойств системы координат также является ключевым.
Читать дальше →
Всего голосов 14: ↑14 и ↓0+14
Комментарии0

Геометрия данных 4. Пространство графа

Время на прочтение12 мин
Количество просмотров11K
Особенность координатных систем на точечном базисе (ди- и би-координат) состоит в том, что их можно использовать как в обычном геометрическом пространстве, так и в пространстве графа.



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


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


Мерность пространства графа определяется количеством его связанных вершин (будем считать, что все вершины графа связаны — однокомпонентный граф). Базис пространства задается как подмножество вершин графа с известными дистанциями между ними (метрикой). Подмножество может включать в себя как все вершины графа, так и только часть (подграф). В последнем случае мерность базиса меньше, чем мерность общего пространства графа.
Читать дальше →
Всего голосов 10: ↑10 и ↓0+10
Комментарии5

Геометрия данных 3. Скалярное произведение пар

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



Читать дальше →
Всего голосов 16: ↑16 и ↓0+16
Комментарии6

Геометрия данных 2. Определение ди- и би-координат

Время на прочтение10 мин
Количество просмотров6.4K
В первой статье определен метрический базис на элементах, — набор вершин симплекса или графа с известными значениями скалярных произведений (грамиан) или связей (лапласиан) между ними. Здесь рассмотрим, как на таком базисе определить координаты элементов.



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


Дистанционные координаты представляют собой значения скалярных произведений элемента и реперов — вершин базиса. Будем именовать их ди-координатами.
Читать дальше →
Всего голосов 21: ↑21 и ↓0+21
Комментарии5

Геометрия данных 1. Симплексы и графы

Время на прочтение11 мин
Количество просмотров21K
Звездное небо напоминает, — точки являются фундаментальной абстракцией, основой окружающего пространства.



Введение


Это первая статья серии, посвященной описанию свойств базисов пространств на основе элементов (а не векторов). Базис определяет систему координат — описание элементов пространства в виде набора чисел, характеризующих положение элемента относительно базиса.
Читать дальше →
Всего голосов 22: ↑22 и ↓0+22
Комментарии23

Спектроскоп-калейдоскоп

Время на прочтение4 мин
Количество просмотров6.5K
Это заметка о том, что на основании алгоритма генерации спектров (о котором было рассказано в статье «Спектроскоп Салтана...») создан тестовый сервис, обратиться к которому может любой желающий.

Под катом — инструкция по использованию сервиса и его возможностей.
Читать дальше →
Всего голосов 18: ↑18 и ↓0+18
Комментарии4

Релевантное соединение — атрибуты конкретные и универсальные

Время на прочтение9 мин
Количество просмотров2.9K

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



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

Читать дальше →
Всего голосов 6: ↑6 и ↓0+6
Комментарии0

Элементы, универсумы и регистры правил

Время на прочтение15 мин
Количество просмотров6.1K

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


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



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


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

Читать дальше →
Всего голосов 9: ↑9 и ↓0+9
Комментарии13

Спектроскоп Салтана: лапласианы для фана

Время на прочтение7 мин
Количество просмотров15K
Рождественские дни — время отложить привычные дела и вспомнить забавы — калейдоскопы, мозаики, снежинки… Кто нарисует самую красивую звезду?

Симметрия радует глаз. Создать красоту помогает математика, язык Питон и его библиотеки — математический numpy и графический matplotlib.

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


КДПВ получена визуализацией значений собственных векторов некой симметричной матрицы.
В основе — спектры регулярных решеток. Некоторые их свойства уже рассматривались ранее. Здесь формулы поработают на эстетику.
Далее еще будут картинки...
Всего голосов 66: ↑66 и ↓0+66
Комментарии21

Путь лапласиана. Часть 2

Время на прочтение8 мин
Количество просмотров17K
А не замахнуться ли нам на Эдсгера нашего Дейкстру?



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

В общем случае минимизируемая величина — это необязательно расстояние, — весами ребер графа могут быть стоимости, штрафы, убытки, времена, — любые величины, которые можно складывать. Задача является классической, наиболее простой алгоритм поиска кратчайшего пути дал Э. Дейкстра в 1959 году.
Далее...
Всего голосов 21: ↑18 и ↓3+15
Комментарии0

В поисках пути — царь Салтан осваивает лапласиан

Время на прочтение11 мин
Количество просмотров21K
… Молвит он: «Коль жив я буду, чудный остров навещу, у Гвидона погощу».



В царстве Салтана не без изьяна. Принят закон — не лезть за кордон, да тут князь Гвидон.
Опять прислал поклон, да приглашение на угощение,- надо принимать политическое решение.

Дворцовые интриганки, похожие на поганки, встали стеной — «мол, скажи, что больной». Но прослышал Салтан про Гвидонов кальян, про изумрудную белку, да богатырскую стрелку. А главная новинка — молодая жинка. В общем, ехать решено — «Я не был за морем давно».

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

До ночи решал Салтан задачку, в итоге свалился в спячку. Снились ему матрицы и точки, да на болоте кочки. На кочку прыгнул Нео с острова Борнео.
— Если хочешь добраться ко сроку — плыви по максимальному потоку.
— Чего? — Салтан почти проснулся. Но Нео уже в зайца обернулся.
Плывем дальше
Всего голосов 36: ↑31 и ↓5+26
Комментарии6

Сказ царя Салтана о потенциале лапласиана

Время на прочтение9 мин
Количество просмотров44K
«Три девицы под окном пряли поздно вечерком.»

image

Ну как пряли. Не пряли, конечно, а лайкали друг на друга. По условиям конкурса «мисс Салтан» девицы должны были выбрать меж собой лучшую.

«Какой-то странный конкурс», — беспокоились девицы. И это было правдой. По правилам конкурса вес лайка участника зависел от того, сколько лайков он получает от других. Что это значит, — никто из девиц до конца не понимал.
«Как все сложно», — тосковали девушки и подбадривали себя песней «Кабы я была царицей».

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

Вот что там было:
  • Алена получила 1 лайк от Софьи и 2 лайка от Варвары.
  • Варвара получила по лайку от Алены и Софьи.
  • А Софья получила 2 лайка от Алены и 1 от Варвары.

Царь взял лайки, покрутил гайки, постучал по колесам, пошмыгал носом, причмокнул губами, поскрипел зубами, сгонял в палаты и объявил результаты.

Наибольший вес лайков (7 баллов) получила Софья, но титул «мисс Салтан» достался Алене (15 баллов).

Подробнее о матрице лайков
Для матрицы


вектор потенциалов равен (5, 4, 7), а вектор потоков — (15, 12, 14).

После объявления результатов девицы бросились обратились к царю с просьбой рассказать,- откуда взялись эти странные цифры?
Действительно - откуда?
Всего голосов 67: ↑65 и ↓2+63
Комментарии34
1

Информация

В рейтинге
Не участвует
Откуда
Ижевск, Удмуртия, Россия
Зарегистрирован
Активность