Comments 91
Почему третий пример (шестиугольник с двумя диагоналями) не является решёткой?
Потому, что я несколько напортачил с определением (исправил). Нужно наличие точной верхней и нижней граней.
Для будущих читателей поясню: например у пары детей верхнего (максимального) элемента есть точная верхняя грань, но нет точной нижней - нижними гранями являются минимум и два его отца, но в этом трех элементном множестве нет наибольшего элемента.
Странный факт - в индексе поисковиков всего одно вхождение по запросам "для будущих читателей поясню" и "для будущих читателей поясняю", наверное я косноязычно выразился.
Реально статья написана ради последних двух разделов, которые обещаны паре людей. Просто если я начал бы с конца, кмк, были бы замечания.
Раз уж меня впервые упомянули в статье, я теперь просто обязан её прочитать разобраться :) Хотя у меня большие сомнения, что я когда-нибудь в жизни буду применять эти знания :)
Так в ЧУМе не все элементы можно сравнивать между собой.
В конце текста есть примеры с иерархиями. Для иерархии не важно, сколько килограммов в конкретном узле, потому что узел - абстрактный, то есть вмещает любое количество экземпляров (представителей вида). Абстрактная "морковь вообще" может быть одна штука, может быть десять, и может быть два кило, но общее для всех этих кучек - это морковь. То есть от параметров цвет, вес, длина, толщина и т.д. мы абстрагируемся, или забываем о них. Остаётся лишь название. Классификацию же продуктов на морковь и прочее мы отдаём столь же абстрактному классификатору, устройством которого не интересуемся. Ну и за одно нам не интересно, есть ли он в природе, потому что для нас главное - типы, и то, что в голове мы их можем выделить, а могут ли это сделать реальные классификаторы, нам безразлично. Таковы свойства абстракции, как, собственно, и всей математики.
Хотя да, отношение "больше или равно" действительно не задано для упомянутых в тексте иерархий. Оно подразумевается. Примерно задать можно так - элемент множества с более высоким уровнем абстракции находится в отношении "больше или равно" с элементом с менее высоким уровнем абстракции со стороны "больше". Если в иерархию добавить "морковь мытую" и "морковь немытую", получим, что оба этих элемента множества узлов в иерархии находятся в отношении со стороны "меньше" если вторым в отношении будет узел (элемент множества) "морковь", ну или "морковь" "больше или равна" чем "мытая морковь" (что точнее, поскольку отношение "меньше" в системе нами не задано).
В целом - текст не для тех, кто ожидает строгости. Но никто не мешает ввести строгость самостоятельно в качестве упражнения. Для остальных же строгость будет большой помехой (до поры до времени).
Взгляд на графы через решётки - вот и вся разница.
Ценное - новый взгляд часто упрощает какие-то моменты из взгляда по старому.
Теория групп, например, подходит для множества случаев, от теории чисел до геометрии, тем самым обобщая наш взгляд на эти задачи. Решётки - частный случай общей алгебры, как и группы.
Что сказать конкретно? Да не знаю. Потому что и сам автор лишь переводит стрелки на произведение, ссылку на которое даёт в начале статьи. Видимо нужно прочитать то произведение, что бы указать вам на конкретику.
Хотя да, автор мог бы быть более щедрым на пояснения. Но он написал в конце, что статья для кого-то конкретного, а все остальные - так, довесок, поймёте - хорошо, нет - автор не будет против.
Хотя да, автор мог бы быть более щедрым на пояснения.
Автор не настолько крут, чтобы излагать достаточно новую для него вещь в популярном ключе. Надо писать, да. Но Хабр завален спамом и политикой (в которой, азм грешен, сам принимаю участие — см историю моей кармы :-) ).
Напишите хотя бы просто обзор той книги, где активно используются решётки. По ходу обзора станет видно, что именно решётки дают нам в контексте анализа программ. Затем это нечто можно слегка допилить своими домыслами, чем ещё более расширить понимание полезности закономерностей, выведенных для решёток.
Хотя я вполне допускаю, что автор той книги просто использовал привычную ему терминологию, не привнеся в собственно анализ ничего полезного из общей алгебры.
ЧУМ и рисуется через DAG. При этом, он не обязательно связан, у этого DAG не обязательно есть начало и конец. У DAG для решёток такие два места обязательно есть.
То есть, это просто два представления одного и того же. Вы же изучали теорию представлений групп? Вы же знаете, что у одной и той же группы есть мало того, что бесконечное количество матричных представлений, так даже неприводимых бесконечно много.
Ну сколько вы жить собираетесь? Вполне будет время добрать математические курсы.
Я, видимо, вас перепутал.
Вот например, умножение комплексных чисел можно представить как умножение матрицы на вектор, но какой в этом смысл?
Это вам открывает возможности использовать инструкции SIMD для комплексных чисел! Кстати, поздравляю, я об этом даже и не думал.
Ну я и добираю, вот только в некоторых вещах не вижу смысла.
Отлично! Я тоже не видел в йуности смысла во всех этих алгебрах, которых нам "агрономам" преподавали.
А сейчас я понимаю, что раз понятие зубодробительно абстрактное, значит его можно применить ко всему. Ну будет оно полезно или нет — это другое дело. Но, поскольку оно абстрактное, а значит, торчит везде, как в бочке затычка, то в огромном кол-ве мест оно будет полезно.
Вы ведь знаете, что нам непосредственно в мозг "прошивали" теорию множеств в дет. саду? На яблоках? Ну и практически все "индустриальные люди" её используют повседневно. Вы можете прочитать про отличие нашего сознания от первобытного — где эта теория множеств не прошита. Ну для них нет чисел: пять яблок никак не соотносятся с пятью апельсинами.
В SIMD матрицы ещё не завезли, хотя было бы неплохо. Переформулирую вопрос: как вывести матрицу поворота для 2D векторов, опираясь только на положения линейной алгебры, без привлечения тригонометрии или комплексных чисел?
Для ответа вы должны подумать, как в линейной алгебре определена операция "поворот"?
На вскидку
линейное преобразование, сохраняющее норму вектора
(ну и что-то там надо добавить про положительно определённую матрицу, чтобы отсечь отражения)
???
Повернуть вектор невозможно. У него же нет ориентации — это не палка с продольными метками.
Если в про поворот, главная ось которого параллельна вектору (1, 1, 1), то их бесконечно много. Но я не очень понимаю, зачем я должен мучаться и предоставлять вам матрицу такого поворота. Чем это поможет?
Вообще, у меня такое ощущение, что у вас не было двухсеместрового курса линейной алгебры. Так?
В данном случае вы используете неправильную модель. Если вам нужно обязательно описать объект, похожий на палку со сторонами, то один вектор для этого, очевидно, не подходит.
Ну ровно также не подходит точка для описания объекта, когда его форма критична.
Но это — мат. моделирование реального мира проходят на физике. А физику, насколько я понимаю, в РФ нормально преподают в одной школе.
Вы имели ввиду "написать матрицу вращения, которое данный вектор оставляет неизменным"?
У нас ниже/выше трёп, по результатам которого оказалось, что ув Refridgerator хочет, чтобы модель описывала раскрашенную ракету, а не просто направление.
У нас ниже/выше трёп, по результатам которого оказалось, что ув Refridgerator хочет, чтобы модель описывала раскрашенную ракету, а не просто направление.
Так ортонормированный базис годится для описания любого твердого тела.
Ну, значит в этом случае вам надо взять другую абстракцию.
Мы же в любом случае не можем в программе закодировать цельное сверло, как оно есть — там 10E23 атомов. Это я ещё не говорю, что там кванты.
Ну, а дальше мы выбираем просто подходящую абстракцию, которая описывает то, что нам нужно и ничего более. То есть, в вашем случае сверла нужно 6 степеней свободы для положения в пространстве.
А это уже не вектор. Две таких массива даже не сложить толком (т.е. можно поэлементно, но физического смысла нет).
И еще скалярные произведение любых пар векторов? Cм. https://ru.wikipedia.org/wiki/Унитарная_матрица
Из википедии:
Ве́кторное простра́нство (лине́йное пространство) — математическая структура, представляющая собой набор элементов, называемых векторами, для которых определены операции сложения друг с другом и умножения на число — скаляр
Оттуда же:
Эти операции подчинены восьми аксиомам
Итого:
Определение операции "поворот" в списке допустимых отсутствует.
Но вы можете сузить толкование математической структуры добавкой вашего определения операции "поворот" (сузить в плане уменьшения количества переходов между элементами множества посредством введения новых ограничений (аксиом)).
Любой математический инструмент опирается на набор аксиом. Линейные преобразования на то и линейны, что бы не выходить за предписанные рамки.
Или по другому - вы задались не тем вопросом. Или выбрали не тот инструмент.
Правильный подход - пояснить, зачем вам вообще понадобилось вдруг исключить тригонометрию и комплексные числа.
Интерпретация есть внематематическое действие. Математике нужны аксиомы, множества, операции. Где в этой троице интерпретации?
Поворот при возведении в квадрат i является геометрической интерпретацией. Для введения в математику такая операция требует указания перехода от геометрии к комплексным числам. Но даже представив такое отображение вы будете противоречить сами себе, ведь вы потребовали "без тригонометрии и комплексных чисел".
Задайте какую-то основу, затем задайте отображение из неё на геометрию, так получите углы, а без углов все преобразования будут лишь наборами чисел, каким-либо строгим образом не связанным с понятием "поворот", которое всегда предполагает наличие угла.
Определение операции "поворот" в списке допустимых отсутствует.
Это же линейное преобразование, матрица кoторого унитарная (ортогональная).
Если кто-то использует молоток для забивания шурупов, это не значит, что именно так все и должны делать.
Прощу прощения, не могли бы вы уточнить, что вы подразумеваете под "шурупами", а что под "молотком"?
Пока что я вижу, что вы согласны с вашим оппонентом, что в векторных пространствах операция вращения отсутствует?
Эта операция там не определена. Так точнее.
Странно, Марья Иванна... (С) анекдот.
(Может быть) определена, как умножение на унитарную матрицу. Естественно, это никакая не аксиома.
Рассмотрим для примера простейшую задачу на поворот: определить, слева или справа от вектора ВС находится точка A:
Решение в комплексных числах выглядит так же просто:
r=sgn(im((A-B)/(C-B))), где приr==1 значит слева,r==-1 значит справа,r==0 значит лежит на прямой принадлежащей вектору,r==неопределённость значит вектор имеет нулевую длину и задача не имеет решения.Здесь всякие косинусы и арктангенсы отсутствуют не потому что они сократились, а потому что их не было изначально.
Ну а теперь покажите Ваше решение через матрицы, а главное — в чём будет его преимущество.
У вращения и поворота в геометрии есть вполне конкретные определения и матрицы в них отсутствут.
Да ну? См.https://en.wikipedia.org/wiki/Rotation_matrix
Далее:
Для начала, а не могли бы вы дать определение, что такое "слева" и что такое "справа"? С точки зрения геометрии. Для простоты - без особых случаев. Докажите, что ваша формула с использованием комплексных чисел соответствует этому определению.
У вас или BC не вектор, или А - не точка, а тоже вектор BA - при параллельном сдвиге начала системы отсчета вектора не меняются, а вот точки сдвигаются. Т.е.или крестик снимите, или штаны оденьте :)
Легко проверить, что ваше r = sign((BC x BA) / |BC|^2), где "x" это "векторное" произведение векторов (а кавычках, потому что 2D и результат скаляр, или можно считать, что это Z-координата векторного произведения в 3D). Знак знаменателя неотрицательный, ноль - рассматриваем отдельно, тогда в остальных случаях про знаменатель можно забыть, и ответ упрощается до:
r = sign((cx - bx) * (ay - by) - (cy - by) * (ax - bx)) Итого 5 вычитаний и 2 умножения. Ваш вариант - еще 2 умножения, одно сложение и одно деление. Как бы не в 2 раза дольше.
Решение, полученное с использованием матриц, я дам после того, как увижу ваше определение "слева/справа" и желательно еще доказательство, что ваша формула ему соответствует. Ну, или свое определение приведу.
Ну и давайте теперь расширим задачку, т.е. перейдем в 3D. Пусть есть многоугольник на произвольно ориентированной плоскости и точка. Внешней будем считать ту сторону многоугольника, где направление обхода контура - против часовой стрелки. Определить, где точка - с внешней стороны или с внутренней.
Ну типа правда, нужно расписывать чем «лево» от «право» отличаются?
На самом деле нужно. Помните фантастический рассказ, где земляне прилетели на марс, не сумели открыть люк, а с Земли по радио пытались объяснить аборигену, куда гайку откручивать?
Но если не смогли, дам я. Слева, это когда мы переходим в такую повернутую систему отсчета, где у вектора BC X-компонента положительная, Y-компонента нулевая, а точка А находится в верхней полуплоскости.
А теперь решение. Легко проверить, что в 2D ортогональная матрица имеет вид [[c, -s],[c, s]], где с^2+s^2=0. Теперь переводим исходный вектор и точку в повернутую систему координат (для упрощения расчетов я помещаю точку B начало координат), такую что выполняются вышеуказанные условия для вектора BC, т.е. находим c и s и Y-координату точки А в такой системе:
Y= (BC x BA) / |BC|
Можно было бы и сразу написать с=cos(phi), s=sin(phi), но все равно тригонометрия исчезла бы из конечной формулы.
А теперь добро пожаловать в 3-х мерный мир. Я повторю все свои вычисления в 3D (воспользовавшись SVD для нахождения ориентации плоскости в пространстве и таки векторным умножением для поиска той стороны, где обход против часовой стрелки) и найду высоту точки в повернутой системе координат. А что бвы
А теперь решение. Легко проверить, что в 2D ортогональная матрица имеет вид [[c, -s],[c, s]], где с^2+s^2=0.Э нет, подождите. Откуда взялись c,s и равенство с^2+s^2=0? В условиях задачи ничего такого не было. Там были 3 точки A,B,C и один вектор BC в понимании "направленный отрезок".
Э нет, подождите.
Ой, я там фигню два раза написал, как правильно, см.ниже:
[[c, -s],[s, c]], где с^2+s^2=1
Ладно, чуть подробнее.
В соответствии с определением лево/право, нам сначала надо найти ту систему отсчета, где вектор BC направлен вдоль положительного направления оси X.
Вращение системы отсчета описывается ортогональной матрицей (см. Википедию) у которой a) детермининт 1 и b) транспонированная матрица равна обратной (или траспонированная матрица, умноженная на исходную равна единичной, единички по диагонали, остальные нули). Можно показать, что у таких матриц (Maple/Mathematica в помощь) диагональные элементы равны, недиагональные равны по абсолютной величине и обратны по знаку и сумма квадратов коэффициентов по любой строке или столбцу равна единице, т.е. матрицу можно записать в виде, указанном в начале сообщения.
Теперь поворачиваем с помощью этой пока неизвестной матрицы вектор BC, решаем уравнение rotated(BC)[y]=0, Rotated(BC)[x]>0 и находим с и s, и подставляем их в матрицу.
Поворачиваем теперь вектор BA, вычисляем Rotated(BA)[y].
Смотрим на знак.
Для тех, кто знает линейную алгебру, понятно, что векторное произведение в 2D инвариантно относительно поворота системы отсчета, т.е. "высота" точки относительно вектора равна векторному произведению единично вектора на вектор из нуля в точку.
Я привел строгое математическое доказательство, что конечная формула дает ответ на точно сформулированный (мною) вопрос. Пропустив только то, что преобразование с помощью ортогональной матрицы сохранаяет скалярные произведения произвольных пар векторов. Так-то конечная формула пишется не глядя левой ногой.
Ну и не во всех языках программирования комплексные числа есть из коробки. В той же java нет. в javascript наверняка та же фигня. PHP?
#pragma once
#include <math.h>
struct complex
{
double a;
double b;
complex::complex()
{
a = 0;
b = 0;
}
complex::complex(double* data, int a, int b)
{
this->a = data[a];
this->b = data[b];
}
complex::complex(double a, double b)
{
this->a = a;
this->b = b;
}
void complex::set(double ampl, double phase)
{
this->a = ampl*cos(phase);
this->b = ampl*sin(phase);
}
void complex::set(complex& f)
{
this->a = f.a;
this->b = f.b;
}
void complex::copy(double* data, int a, int b)
{
data[a] = this->a;
data[b] = this->b;
}
void complex::import_ampl(complex& f)
{
double ampl = sqrt(f.a*f.a+f.b*f.b);
double phase = atan2(b,a);
this->a = ampl*cos(phase);
this->b = ampl*sin(phase);
}
void complex::import_ampl(double ampl)
{
double phase = atan2(b,a);
this->a = ampl*cos(phase);
this->b = ampl*sin(phase);
}
void complex::import_phase(complex& f)
{
double ampl = sqrt(a*a+b*b);
double phase = atan2(f.b,f.a);
this->a = ampl*cos(phase);
this->b = ampl*sin(phase);
}
void complex::import_phase(double phase)
{
double ampl = sqrt(a*a+b*b);
this->a = ampl*cos(phase);
this->b = ampl*sin(phase);
}
void complex::multiply(double c, double s)
{
double aa = a*c - b*s;
double bb = a*s + b*c;
this->a = aa;
this->b = bb;
}
double complex::phase()
{
return atan2(b,a);
}
double complex::ampl()
{
return sqrt(a*a+b*b);
}
complex& complex::operator +=(const complex& v)
{
a += v.a;
b += v.b;
return (*this);
}
complex& complex::operator -=(const complex& v)
{
a -= v.a;
b -= v.b;
return (*this);
}
complex& complex::operator *=(const double& v)
{
a *= v;
b *= v;
return (*this);
}
complex complex::operator -(void) const
{
return (complex(-a, -b));
}
complex complex::operator +(const complex& v) const
{
return (complex(a + v.a, b + v.b));
}
complex complex::operator -(const complex& v) const
{
return (complex(a - v.a, b - v.b));
}
complex complex::operator *(double v) const
{
return (complex(a * v, b * v));
}
complex complex::operator /(double v) const
{
double f = 1.0 / v;
return (complex(a * f, b * f));
}
};Если нет — то либо вручную, либо в Mathematica и прочих калькуляторах разбить решение на действительную и мнимую части.
Предлагаете перейти в 3D? Давайте, будет интересно. Только теперь Вы первый с готовым решением, которое можно объективно проверить. Чтобы на этот раз обойтись без формулировок типа «очевидно что у вас тут векторное умножение». И формулировку чуть поточнее пожалуйста, с картинкой, потому как описывать ориентацию плоскости тоже можно по-разному.
И формулировку чуть поточнее пожалуйста, с картинкой, потому как описывать ориентацию плоскости тоже можно по-разному.
А просто заданы (x,y,z) координаты точек контура по порядку. Пусть их будет больше трех, чтобы интереснее было. Но я уже описал решение.
Если вершины многоугольника в 3D-пространстве произвольно заданы через (x,y,z) координаты — они совсем не обязательно будут лежать в одной плоскости при их количестве больше 3-х, равно как и точка, для которой нужно найти вхождение.
Исходное условие - есть многоугольник на плоскости. С точки зрения математики, я имею право задать его координатами вершин. Численно - да, будут невязки. Потому и SVD (или метод наименьших квадратов, что одно и то же).
Предлагаете перейти в 3D? Давайте, будет интересно.
Вдогонку, если треугольник, то просто скалярно-векторное произведение.
Стоит задать аксиомы. Можно использовать комплексные числа? Можно синусы? Можно углы?
Началось всё с поворота без тригонометрии и комплексных чисел. Поворот выполняется в пространстве. Пространство описывается, в том числе, векторами (векторное пространство), но это не единственный способ описания. Смысл поворота в любом пространстве задаётся авторами. Либо нужно создать пространство, где поворот является его основой (аксиомой, порождающей операцией), но опять смысл задаётся автором.
Вы в итоге всё равно возвращаетесь к смыслу, а не к математике. Поэтому и важно задать ограничения, в которых смысл определён. Например - минимум операций (вычислительная сложность) - это ограничение по разному может выглядеть для разных определений пространства. Хотя вполне возможно, что после ряда преобразований, не выходя за рамки аксиом, определяющих выбранное пространство, мы получим тот же набор операций, то есть выполним ограничение на минимум действий сразу в нескольких пространствах. Отсюда спор о матрицах против комплексных чисел становится бессмысленным, если в обоих случаях мы можем получить один и тот же результат (в рамках одних ограничений).
С другой стороны, скорее всего, вами двигала какая-то дополнительная мысль, которую мы не знаем. Начать стоит именно с неё, ибо она - суть то самое ограничение.
Могу предположить, что вы искали простоту, но тогда требуется определение простоты. Минимум операций - одно из определений. Вывод о бессмысленности сравнения двух подходов можно доказать, найдя преобразования, сводящие набор операций к указанному минимуму в обоих случаях. Сложнее доказать, что в каком-то из случаев минимум недостижим.
В общем - начинайте от основ. В математике это аксиомы. Без них спор будет гулять по неведомым и бессмысленным траекториям, пока спорщики всё равно не вернутся к мысли об аксиомах.
В решение оппонента можно только поверить
Я кратко посмотрел, логично - поворачиваем систему и смотрим плюс или минус по координате Y у точки.
Но это всё беллетристика, потому что сначала было "не все абстракции полезны", потом возник "поворот", потом перешли к точке над вектором (многоугольником и т.д.). То есть погружение вдаль от абстрактного начала привело куда-то в абсолютные частности, которые непонятно как связаны с исходным тезисом.
Попробуйте забыть про "моё решение" и все исключительно психологические моменты, связанные с его обоснованием. Это всё лирика, если нет связи с исходным посылом.
Какие абстракции вредны и какие полезны для описания операции "поворот"? Так, скорее всего, мы будем ближе к отправной точке.
Давайте, на java ;)
В решение оппонента можно только поверить
Ну, конечно, заклинание, такое заклинание.
Я не хочу на эту тему беседовать — она уводит меня от решёток.
Мне искренне интересно узнать, почему для некоторых людей набор файлов с отношением вложенности, явно прописанным как "#include", более естественно представить в виде абстрактной алгебраической группы с отношением «меньше или равно или вообще несравнимо». Как это поможет например выявлять циклические ссылки?
Этот набор естественно рассматривать, как граф. И я не протестую, что это именно так. Это, кстати, просто направленный граф без каких-либо ограничений.
А вот давайте рассмотрим множество Сшных сущностей, добавляемое в пространство имён каждым из этих заголовков, S_i.h. Как вы эти множества опишете? Каким таким графом?
Если вы про то, что такое "Сшные сущности", то ну глобальные переменные, типы, объявления функций и т.д. Всё то, что вы можете поместить в заголовок. Скажем
int zz(int);
extern int tau;
struct A { ... };
typedef A struct A;Тут не нужен граф вообще.
Понятно, что эти множества S_i.h вкладываются друг в друга, как матрёшки. А значит, там можно ввести операцию ≤. Это будет просто операция из теории множеств ⊆. Она опеределена не совсем между любыми двумя заголовочными файлами => это не линейное упорядочение, а ЧУМ.
А дальше вы это соображение в каком-нибудь языке программирования можете закодировать графом, какими-то SET'ами и т.д. Можете закодировать десятком разных способов, например с помощью разниц.
Если, конечно, это вам вообще нужно кодировать. Может быть просто достаточно этой огрублённой информации, чтобы понять какой-же именно S_i.h вам нужен.
Какую задачу? Задачи разные, о моей вы почти ничего не знаете, кстати.
Да, очевидно, что абстракции нужны под задачу, а не просто так.
Конкретно решётки массово используются для подподзадачи компилирования, для анализа кода в middle-end, внутри оптимизаторов. Если вы пишете компилятор без оптимизаций или они относительно простые, то можете написать без формализации и без решёток.
Это же просто абстракция, которая в определённых ситуациях позволяет выбросить ненужные детали, упростив картину мира => сделав её проще для осмысления и разных действий поверх.
Так вы сами в статье отошли, все примеры - это деревья.
P.S. Я ожидал что-то типа MRO в питоне: https://data-flair.training/blogs/python-multiple-inheritance/
Каждый столбец в матрице трансформации показывает, в какой вектор перейдет соответствующий базисный вектор при этой трансформации.
Например непонятно, что больше: килограмм мясо-рыбы или две морковки?
Про килограммы не упоминалось => их нет, забудьте. В другом примере, возможно, они будут, но тут их нет, нет, нет.
ЧУМ — частично-упорядоченное множество на то и частично, что не между всеми объектами есть сравнение ≤. Вы же наверняка у папы спрашивали в детстве, какая машина круче? Я своим детям рассказываю про Феррари и КРАЗ-самосвал. И показываю, что их нельзя упорядочить: в одних задачах лучше Феррари, а в других — КРАЗ. То есть, там нет ≤.
Аналогично, например, кто круче — первая красавица класса или самый крутой парень? Они не сравнимы: женская иерарахия и мужская независимы.
Полурешётки и законы Мерфи