Изоморфность: Недопустимое название | Математика | Fandom

подход на основе анализа NB-Paths / Хабр

Всем привет.

Есть такая задача – проверить, являются ли два графа изоморфными друг другу. Т.е., говоря по-простому, узнать, являются ли оба эти графа «одним и тем же» графом, но с разной нумерацией вершин и, в случае задания графов графически, с разным их пространственным расположением. Решение этой задачи не является таким уж очевидным, как может кому-то показаться на первый взгляд: даже для небольших графов взгляд на их графическое представление не всегда даст однозначный ответ. См., например, рисунок в той же Вики: ru.wikipedia.org/wiki/Изоморфизм_графов#Пример.

Ну как, очевидно?

А есть и более сложная задача: поиск в некотором «большом» графе всех подграфов, изоморфных некоторому другому графу «поменьше». Это еще более «темный лес». То есть, конечно, не совсем темный, но задача, согласитесь, не самая простая.

Итак, что же мы имеем?

1. Зачем вообще все это надо

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

2. Как решают эту задачу?

Классический подход к решению данной задачи был заложен Дж. Ульманом в 1976 году [3], впоследствии он существенно доработал свой алгоритм [4]. Также данный подход получил дальнейшее развитие в работах многих других авторов, например, Корделлы и соавторов [2] (алгоритм VF2), Бонници и соавторов [1] (алгоритм RI), и др.

Если кратко, то суть этого подхода заключается в «умном переборе» возможных соответствий вершин графа-образца B и графа A, в котором идет его поиск. «Умным» этот перебор делает ввод различных условий и ограничений, которые позволяют как можно раньше отсечь неподходящие варианты. Также для этих целей может проводиться различная предварительная обработка исходных данных.

Не будем здесь заниматься пересказом данных работ, а предложим читателю познакомиться с ними самостоятельно. Однако «показ лучше наказа», и, нужно отметить, что в Сети есть и неплохие графические примеры и объяснения этих алгоритмов. См., например, следующие:
coderoad.ru/17480142/Есть-ли-простой-пример-для-объяснения-алгоритма-Ульмана – очень хорошее и понятное объяснение с примером,
issue.life/questions/8176298 – шаги алгоритма VF2 с примером.

Однако возникает вопрос – возможны ли также еще какие-либо иные пути и подходы для решения этой задачи, пусть и для каких-то частных случаев? И вот с одним из возможных ответов на этот вопрос и хотелось бы Вас познакомить.

3. Изоморфизм графов и NB-пути

Давайте сразу договоримся: под NB-путями (и не из англомании, а просто потому, что так – короче) мы будем называть maximal non-branching paths, т.е. максимально протяженные неразветвляющиеся пути некоторого графа.

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

• для ориентированных графов соответствующие друг другу пути будут сонаправлены,
• степени соответствующих друг другу вершин для неориентированных графов (а для ориентированных – количества входящих и исходящих ребер соответственно) будут равны,
• при «совмещении» таких представлений в результате мы будем иметь соответствие вершин первого и второго графов.

Пример. Граф A = {1->2, 1->6, 4->5, 5->1, 3->3}. Граф B = {3->4, 3->5, 1->2, 2->3, 6->6}
PathsA (maximal non-branching paths of A ): 1->2, 1->6, 4->5->1, 3->3
PathsB (maximal non-branching paths of B): 3->4, 3->5, 1->2->3, 6->6
Соответствие вершин: 1(A):3(B), 2(A):4(B), 6(A):5(B), 4(A):1(B), 5(A):2(B), 3(A):6(B).

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

A: 1, 2, 6, 4, 5, 3
B: 3, 4, 5, 1, 2, 6

Матрица смежности для A для заданного порядка вершин:

Матрица смежности для B для заданного порядка вершин:

Матрицы равны, следовательно, графы A и B – изоморфны.

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

4. Ну хорошо, проверили изоморфизм графов. А что же с поиском подграфов?

А тут, честно признаюсь, все значительно сложнее. Тут у нас будет следующее ограничение: исходя из самой сути метода можно находить не любые, но лишь «вписанные» подграфы. А «вписанным» подграфом графа A мы будем называть такой его подграф, который может быть «приклеен» к другим частям графа A только за счет ребер, инцидентных лишь граничным вершинам его (подграфа) неразветвляющихся путей максимальной длины (при этом граф A может содержать и иные компоненты связности). Не волнуйтесь, ниже будет пример, и все будет понятней. Прим. С 12.2020 все же удалось доработать данный метод для поиска всех (а не только «вписанных») подграфов, изоморфных данному. Но об этом в самом конце (см. Раздел 8. Вместо послесловия – Продолжение).

Кроме того, при решении данной задачи, помимо поиска соответствий NB-путей графов A и B по длине (как это было в рассмотренном выше примере с проверкой изоморфизма), также необходимо отдельно искать и следующие возможные соответствия между ними:

• Соответствия NB-путей – простых цепей из графа B NB-путям – простым цепям/ простым из циклам графа A. При этом изначально такие пути в графе A могут быть длиннее – в этом случае берутся их отрезки, равные по длине искомому пути из B.
• Соответствия NB-«концевых» путей графа B каким-либо NB-путям графа A (при этом пути из графа A также могут быть длиннее – в этом случае берутся их отрезки, равные по длине искомому пути из графа B).

Разберемся на примере:

При поиске «вписанного» изоморфного подграфа графа B в графе A (см. рис. выше) будут обнаружены следующие соответствия:

• внутренний путь 2->3->4 графа B: внутренний путь 2->3->4 графа A,
• концевые пути 1->2 и 10->2 графа B: концевой путь 0->2 графа A и фрагмент концевого пути 7->1->2 графа A, а именно 1->2,
• простая цепь 7->8 графа B: отрезки простой цепи 9->10->11 графа A, а именно 9->10 и 10->11, а также отрезки простого цикла 12->13->14->12 графа A, а именно 12->13, 13->14, и 14->12.

Таким образом, в качестве «изоморфных графу B «вписанных» подграфов графа A могут быть найдены следующие 5 вариантов:

A1 = {0->2, 1->2, 2->3, 3->4, 4->5, 4->6, 9->10}
A2 = {0->2, 1->2, 2->3, 3->4, 4->5, 4->6, 10->11}
A3 = {0->2, 1->2, 2->3, 3->4, 4->5, 4->6, 12->13}
A4 = {0->2, 1->2, 2->3, 3->4, 4->5, 4->6, 13->14}
A5 = {0->2, 1->2, 2->3, 3->4, 4->5, 4->6, 14->12}

Однако, если мы добавим к графу A дополнительное ребро 3->8, у нас получится граф A’ (ниже на том же рисунке). И в A’ уже будет не найти «вписанных» подграфов, изоморфных графу B. Действительно: ребро 3->8 «разбивает» путь 2->3->4 графа A на два и, значит, путей-кандидатов для внутреннего пути 2->3->4 графа B обнаружено не будет.

5. Теперь сам алгоритм

Теперь мы можем перейти к более детальному рассмотрению алгоритма поиска «вписанных» в граф А подграфов, изоморфных некоторому графу B.

Итак, алгоритм будет состоять из 4-х этапов:

• Препроцессинг,
• Сопоставление,
• Прореживание,
• Заключение.

Этап I. Препроцессинг

На данном этапе мы находим все NB-пути по каждому из графов, а также оцениваем факторы, ограничивающие пространство выбора при переборе. Т.е. мы делаем следующее:

1. Находим все NB-пути в графе A и заносим их в динамический массив (в С++ – в вектор) PathsA
2. Находим все NB-пути в графе B и заносим их в динамический массив (вектор) PathsB
3. Вычисляем и запоминаем кратность всех ребер графов A и B. Дальнейшие действия по этапам II-IV проводятся исходя из допущения, что кратности всех ребер равны 1. Однако на финальной стадии производится сравнение кратности ребер подграфа графа A-кандидата на изоморорфизм с графом B и кратности ребер самого графа B: все ребра подходящего графа-кандидата должны иметь кратность не меньшую, чем сопоставляемое им ребро графа B.
4. Подсчитываем степени всех вершин графов A и B (для ориентированных графов степени по входящим и исходящим ребрам учитываются отдельно).
5. Вычисляем матрицы кратчайших путей между каждой парой вершин в A и в B: назовем их DA и DB соответственно.
6. Формируем матрицу смежности – назовем ее B0 – для графа B таким же образом, как мы это делали выше, когда проверяли изоморфизм двух графов.

Итак, у нас есть NB-пути по обоим графам и параметры-ограничители из п.п. 3-5.

Этап II. Сопоставление

На данном этапе мы будем подбирать NB-пути-кандидаты (далее – просто «пути-кандидаты») из графа A для каждого из NB-путей графа B. Отметка о каждом пути-кандидате из PathsA для каждого i-го пути PathsB[i] будет записываться в двумерный динамический массив (в C++ – в вектор векторов) NPaths – соответственно в i-й вектор (i-ю строку) – в виде упорядоченного триплета чисел: номер соответствующего пути в PathsA – номер стартовой позиции в нем – длина пути.

Например, PathsB[2] = {1, 0, 3, 3, 1, 3} означает, что пути PathsB[2] сопоставлено 2 пути-кандидата из A: из PathsA[1] – 3 первых элемента пути начиная с нулевого (начального), и из PathsA[3] – также 3 элемента начиная с первого (следующего за начальным).

При этом поиск (подбор) путей-кандидатов мы будем производить по 4-м направлениям:

1. Поиск путей-кандидатов для всех внутренних NB-путей графа B из PathsB, т.е. тех, обе граничных вершины которых соединены в графе B как минимум с 2-мя другими вершинами (независимо от направления такой связи) и при этом такой путь не является простым циклом (ориентированным – для ориентированных графов).
2. Поиск путей-кандидатов для концевых NB-путей из PathsB.
3. Поиск путей-кандидатов для NB-путей – простых циклов из PathsB.
4. Поиск путей-кандидатов для NB-путей – простых цепей из PathsB.

При отборе путей-кандидатов для каждого i-го пути из PathsB сравниваются (вот тут-то нам и начинают пригождаться некоторые из вычисленных ранее параметров-ограничителей):

• его длина и длина пути-кандидата (должны быть равны для случаев 1 и 3, а для случаев 2 и 4 путь-кандидат из PathsA также может быть длиннее),
• степени его граничных вершин и соответствующих им вершин пути-кандидата (у вершин из пути-кандидата данные значения должны быть не менее чем у пути из PathsB),
• кратность ребра пути-кандидата должна быть не менее, чем у пути из PathsB,
• другие возможные ограничения (например, совпадения меток вершин, если мы говорим о тех же химических соединениях, когда вершины можно маркировать соответствующими атомами, и т.д.)

Если по результатам этапа II для какого-либо из путей в PathsB не найдено ни одного пути-кандидата из PathsA, то считается, что A не содержит «вписанных» подграфов, изоморфных графу B.

Предварительное прореживание

Теперь давайте попробуем «ужать» граф A. Оставим в нем лишь те ребра, которые вошли в найденные нами пути-кандидаты. Если при этом граф A потерял хоть бы одно ребро по сравнению с его изначальным состоянием – возвращаемся на этап I “Препроцессинг”: степени вершин графа A и, соответственно, перечень путей-кандидатов может быть уменьшен и, соответственно, может быть сокращено пространство поиска.

Этап III. Прореживание перечня путей-кандидатов

Целью настоящего этапа является дальнейшее максимально возможное исключение неподходящих путей кандидатов. Для этого осуществим следующие действия.

1. Исключение заведомо неподходящих путей-кандидатов исходя из минимальных расстояний между вершинами в графе B. Исключению подлежит тот путь-кандидат по каждому PathsB[i], для которого хотя бы по одному PathsB[j] не нашлось ни одного такого пути-кандидата, чтобы кратчайшие расстояния между их граничными вершинами в графе A было меньше или равно кратчайшему расстоянию между соответствующими им граничными вершинами путей PathsB[i] и PathsB[j] из графа B.
2. Исключение для всех циклов из PathsB сопоставленных им нециклических путей-кандидатов и наоборот.
3. Аналогичное п. 1 исключение путей-кандидатов, но не по критерию кратчайшего расстояния между граничными вершинами, а их (граничных вершин) взаимному равенству либо неравенству.

Например, если:

• начальный элемент пути PathsB[i] не равен начальному элементу пути PathsB[j], и
• конечный элемент пути PathsB[i] не равен конечному элементу пути PathsB[j], и
• начальный элемент пути PathsB[i] равен конечному элементу пути PathsB[j], и
• начальный элемент пути PathsB[j] не равен конечному элементу пути PathsB[i],

то исключению подлежит тот путь-кандидат по пути PathsB[i], для которого хотя бы по одному PathsB[j] не нашлось ни одного пути-кандидата, удовлетворяющего приведенному выше условию относительно равенства/ неравенства соответственно их (путей-кандидатов) начальных и конечных вершин.

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

Если по результатам этапа III хотя бы 1 путь-кандидат был удален из PathsA, то – опять же – обновляется граф А – в нем остаются только те ребра, которые вошли в оставшиеся пути-кандидаты. И, опять же, если при этом граф A «похудел» хотя бы на одно ребро – снова возвращаемся на этап I “Препроцессинг”: степени вершин графа A и, соответственно, перечень путей-кандидатов может быть уменьшен и, соответственно, может быть сокращено пространство поиска.

Этап IV. Заключение

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

Если они равны, то сравниваются кратности ребер (см. п. 3 Этапа I Препроцессинг). Если все эти условия выполнены – найденный подграф считается изоморфным графу B и добавляется в множество найденных результатов.

При проведении этапа IV “Заключение” возможно применение различных дополнительных проверок, ускоряющих выявление и отбрасывание неподходящего подграфа.

6. Как все запутано… Рассмотрим пример работы алгоритма

Не знаю как Вам, а мне без примера было бы непонятно. Давайте рассмотрим все на примере.

На рис. ниже приведены графы A = {1->2, 2->5, 5->15, 16->15, 5->5, 5->5, 5->4, 5->6, 7->6, 6->8, 6->6, 6->9, 9->10, 9->11, 12->0, 0->12, 4->13, 13->14, 14->4} и B = {1->1, 4->5, 5->1, 1->3, 3->3, 3->2, 2->7, 2->8, 9->10, 10->9, 1->6, 6->11, 11->12, 12->6}. Нашей задачей является нахождение в графе A всех «вписанных» подграфов, изоморфных графу B. Результат также отражен на рисунке: найденные вершины и ребра графа A выделены толстой линией, а номера соответствующих вершин графа B указаны в скобках (если вариантов несколько – они указываются через дробь).

При решении задачи поиска в графе A «вписанных» подграфов, изоморфных графу B, имеем следующие результаты работы алгоритма.

Этап I: Выполнены все действия и расчеты по п.п. 1-5 данного этапа, ниже приводятся полученные PathsA и PathsB.

PathsA:

1->2->5
4->13->14 4
5->4
5->5
5->6
5->15
6->6
6->8
6->9
7->6
9->10
9->11
16->15
0->12->0

PathsB:

1->1
1->3
1->6
2->7
2->8
3->2
3->3
4->5->1
6->11->12->6
9->10->9

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

PathsA:

1->2->5
4->13->14->4
5->4
5->5
5->6
6->6
6->9
9->10
9->11
0->12->0

PathsB:

1->1
1->3
1->6
2->7
2->8
3->2
3->3
4->5->1
6->11->12->6
9->10->9

Итоговое сопоставление NPaths имеет вид:
NPaths:

i=0: 3 0 2
i=1: 4 0 2
i=2: 2 0 2
i=3: 7 0 2 8 0 2
i=4: 7 0 2 8 0 2
i=5: 6 0 2
i=6: 5 0 2
i=7: 0 0 3
i=8: 1 0 4
i=9: 9 0 3

Здесь самое время вспомнить, что каждый упорядоченный триплет чисел в NPaths[i] задает соответствующий PathsB[i] путь-кандидат из A в формате: номер соответствующего пути из PathsA – стартовая позиция отрезка из данного пути – длина отрезка. Таким образом, нетрудно убедиться, что пути PathsB[0] = {1->1} (i=0: 3 0 2) соответствует единственный путь из A, а именно: отрезок из пути PathsA[3], начинающийся с его самого начала и имеющий длину 2.

Этап IV. В результате в графе A был найден единственный подграф A1, изоморфный графу B. A1 = {0->12, 1->2, 2->5, 4->13, 5->4, 5->5, 5->6, 6->6, 6->9, 9->10, 9->11, 12->0, 13->14, 14->4}.

7. Что же дальше?

А, дальше, в принципе, и все. Хотя не совсем: автор должен признаться, что алгоритм может еще дорабатываться и дорабатываться. Что тут нужно добавить?

1. При введении дополнительных признаков вершин графов A и B (например, при задании графами химических соединений каждой вершине может быть сопоставлен числовой код, соответствующий одному и только одному атому (изотопу)) процесс поиска может быть ускорен за счет большей точности сопоставлений по Этапу II: дополнительным условием отбора путей-кандидатов будет соответствие меток вершин.
2. Скорость работы представленного алгоритма очень сильно зависит от структур исходных графов и их взаимного соответствия. Алгоритм будет работать тем быстрее, чем более «уникальную», «нестандартную» и несимметричную структуру имеет граф-образец B.
3. Исходя из этого, одним из возможных путей использования представленного алгоритма может являться, в том числе, «скриннинговый» поиск решения по любому из направлений:
   (1) поиск именно «вписанных» подграфов, изоморфных данному,
   (2) проверка изоморфности двух различных графов.
   «Скрининг» здесь подразумевает «предварительный экспресс-поиск решения», для чего необходимо задать некоторое предельное время его работы, по истечении которого при отсутствии результата можно считать, что данная задача подлежит решению другим алгоритмом.
4. Возможно, для кого-то представленный алгоритм может оказаться полезным как при решении различных практических задач, так и при разработке новых алгоритмов решения задачи об изоморфном подграфе.

8. Вместо послесловия – Продолжение

В декабре 2020 случилось то, что должно было случиться: удалось как адаптировать данный подход для поиска всех (а не только «вписанных») подграфов в графе по образцу, так и воплотить это на практике. Решение, в принципе, лежало на поверхности: вместо non-branching paths (нет короткого аналога термина по-русски) были взяты сами ребра графов. И с января 2021 также на практике была реализована функция, позволяющая искать изоморфные подграфы с учетом меток вершин, причем произвольного типа (в т.ч. — строкового, что позволяет использовать «многогранные» метки; возможно, это может оказаться полезным для различных задач, в том числе, в области химии).

Литература

Общее по проблематике:
1. Bonnici, V., Giugno, R., Pulvirenti, A. et al. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinformatics 14, S13 (2013). doi.org/10.1186/1471-2105-14-S7-S13.
2. Cordella L, Foggia P, Sansone C, Vento M: A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2004, 26 (10): 1367-1372. 10.1109/TPAMI.2004.75.
3. Ullmann Julian R.: An algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery. 1976, 23: 31-42. 10.1145/321921.321925.
4. Ullmann Julian R.: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. J Exp Algorithmics. 2011, 15 (1.6): 1.1-1.6. 1.64

Написанный более официальным языком препринт автора про это самый «алгоритм на основе анализа NB-Paths», содержащий также инфу о предпринятой попытке его реализации на C++:
5. Черноухов С.А. 2020. Preprints.RU. Проверка изоморфности двух графов и поиск изоморфных подграфов: подход, основанный на анализе максимально протяженных неразветвляющихся путей / Maximal non-branching paths approach to solve (sub)graph isomorphism problem. DOI: dx.doi.org/10.24108/preprints-3111977

Полезные интернет-источники по теме:
6. coderoad.ru/17480142/Есть-ли-простой-пример-для-объяснения-алгоритма-Ульмана
7. issue.life/questions/8176298.
8. github.com/chernouhov/CBioInfCpp-0- — репозиторий свободной библиотеки функций для работы со строками и графами на C++, алгоритм реализован с помощью функции SubGraphsInscribed.

4. Изоморфность графов

Изоморфизм

Графы g₁(V₁,X₁) и g₂(V₂,X₂) называются изоморфными, если существует биективное отображение  : V₁V₂ , сохраняющее смежность, т.е.

{ a,b}  X₁  { (a), (b) }  X₂ .

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

Имеют место следующие утверждения.

1 Необходимым условием изоморфности графов A и B является одинаковое число вершин и одинаковое число ребер.

2 Графы изоморфны в том и только в том случае, если изоморфны их дополнительные графы.

3 Отношение изоморфности на множестве графов является отношением эквивалентности.

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

Существует два пути строгого установления изоморфности графов: использование полных инвариантов и прямая проверка изоморфности графов.

Рассмотрим 3 алгоритма проверки изоморфности:

— полный перебор;

— ПНВ-алгоритм;

— модифицированный ПНВ-алгоритм.

Полный перебор

Осуществляется перебор и проверка всех возможных функций подстановки (v). Эта функция ставит в соответствие каждой вершине v графа A некоторую вершину графа B (значение функции (v)). Т.к. функция (v) определена на дискретном множестве с числом элементов n и функция является биективной, то всего разных функций подстановки (v) существует n!. Для проверки одной подстановки требуется сравнить поэлементно две матрицы смежности размером nn. Операция сравнения одной пары элементов двух матриц смежности включает в себя два этапа: вычисление значения функции (v) и собственно сравнение двух значений. Из приведенных фактов следует, что время установления изоморфности будет равно:

t  Const n! n².

Символ «» появляется от того, что при обнаружении первого изоморфизма выполнение алгоритма завершается. Однако, если исходные графы не изоморфны, будут проверены все возможное варианты функций (v). Т.о. функция сложности для рассматриваемого алгоритма равна:

F^t(n) = ( n²n!) .

Программная реализация

Для перечисления функций подстановок (v) можно использовать функцию permut:

int permut(int n, int* p)

При каждом вызове эта функция формирует очередную перестановку для последовательности целых чисел, сохраняемой в массиве p. Возвращаемое значение: номер полученной перестановки.

ПНВ-алгоритм

Рассмотрим ПНВ-алгоритм, он относится к разряду т.н. back-tracking (поиск с возвратом). Суть алгоритма состоит в последовательном наложении (установлении соответствия) вершин графа A на вершины графа B таким образом, чтобы формируемые подмножества вершин в одном и другом графах имели одинаковые отношения смежности. Таким образом, в A и B строится общий, с точностью до изоморфизма, подграф, число вершин в котором на каждом шаге увеличивается. При этом, если на очередном шаге никакая из оставшихся вершин графа B не подходит для включения ее в выделенное подмножество, делается шаг назад и выполняется попытка заменить последнюю вершину из включенных в указанное подмножество на другую. Алгоритм завершается если формируемое подмножество покрывает все вершины графа (с выдачей результата «ДА») либо при исчерпании всех возможных вариантов наложения (с выдачей результата «НЕТ»).

Ниже приведено описание алгоритма в виде С++-функции iso(A,B).

Изоморфизм — Isomorphism — qaz.wiki

В математике обратимый гомоморфизм

В математике , изоморфизм представляет собой структуру , сохраняющих отображение между двумя структурами одного и того же типа , который может быть обратным путем обратного отображения . Две математические структуры являются изоморфными , если существует изоморфизм между ними. Слово изоморфизм происходит от древнегреческого : ἴσος isos «равный», а μορφή morphe «форма» или «форма».

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

Автоморфизм является изоморфизмом от структуры к себе. Изоморфизм между двумя структурами является каноническим изоморфизмом ( каноническим отображением, которое является изоморфизмом), если существует только один изоморфизм между двумя структурами (как это имеет место для решений универсального свойства ), или если изоморфизм гораздо более естественный (в некотором смысле), чем другие изоморфизмы. Например, для каждого простого числа p все поля с p элементами канонически изоморфны с единственным изоморфизмом. {+}} exp ⁡ ( Икс + y ) знак равно ( exp ⁡ Икс ) ( exp ⁡ y ) {\ Displaystyle \ ехр (х + Y) = (\ ехр х) (\ ехр у)} Икс , y ∈ р {\ displaystyle x, y \ in \ mathbb {R}}

Идентичность и показать , что и являются обратными друг друга. Поскольку является гомоморфизмом, имеющим обратный, который также является гомоморфизмом, является изоморфизмом групп. бревно ⁡ exp ⁡ Икс знак равно Икс {\ Displaystyle \ журнал \ ехр х = х} exp ⁡ бревно ⁡ y знак равно y {\ Displaystyle \ ехр \ журнал у = у} бревно {\ displaystyle \ log} exp {\ displaystyle \ exp} бревно {\ displaystyle \ log} бревно {\ displaystyle \ log}

Функция есть изоморфизм , который переводит умножение положительных действительных чисел в дополнение действительных чисел. Это средство позволяет умножить действительные числа , используя линейку и таблицу логарифмов , или используя логарифмическую линейку с логарифмической шкалой. бревно {\ displaystyle \ log}

Целые числа по модулю 6

Рассмотрим группу , целые числа от 0 до 5 со сложением по модулю  6. Также рассмотрим группу , упорядоченные пары, где координаты x могут быть 0 или 1, а координаты y могут быть 0, 1 или 2, где добавление в Координата x определяется по модулю 2, а сложение координаты y — по модулю 3. ( Z 6 , + ) {\ Displaystyle (\ mathbb {Z} _ {6}, +)} ( Z 2 × Z 3 , + ) {\ Displaystyle (\ mathbb {Z} _ {2} \ times \ mathbb {Z} _ {3}, +)}

Эти структуры изоморфны по сложению по следующей схеме:

(0,0) ↦ 0

(1,1) ↦ 1

(0,2) ↦ 2

(1,0) ↦ 3

(0,1) ↦ 4

(1,2) ↦ 5

или вообще ( a , b ) ↦ (3 a + 4 b ) mod 6.

Например, (1,1) + (1,0) = (0,1) , что переводится в другой системе как 1 + 3 = 4 .

Хотя эти две группы «выглядят» по-разному, поскольку наборы содержат разные элементы, они действительно изоморфны : их структуры абсолютно одинаковы. В более общем случае прямое произведение двух циклических групп и изоморфна тогда и только тогда , когда т и п являются взаимно простыми , согласно теореме китайского остатка . Z м {\ displaystyle \ mathbb {Z} _ {m}} Z п {\ displaystyle \ mathbb {Z} _ {n}} ( Z м п , + ) {\ Displaystyle (\ mathbb {Z} _ {mn}, +)}

Изоморфизм, сохраняющий отношения

Если один объект состоит из множества X с бинарным отношением R, а другой объект состоит из множества Y с бинарным отношением S, то изоморфизм из X в Y является биективной функцией ƒ: X → Y, такой что:

S ⁡ ( ж ( ты ) , ж ( v ) ) ⟺ р ⁡ ( ты , v ) {\ Displaystyle \ OperatorName {S} (е (и), е (v)) \ iff \ OperatorName {R} (и, v)}

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

Например, R — это порядок ≤, а S — порядок , тогда изоморфизм из X в Y — это биективная функция ƒ: X → Y такая, что ⊑ {\ Displaystyle \ scriptstyle \ sqsubseteq}

ж ( ты ) ⊑ ж ( v ) ⟺ ты ≤ v . {\ displaystyle f (u) \ sqsubseteq f (v) \ iff u \ leq v.}

Такой изоморфизм называется изоморфизмом порядка или (реже) изотонным изоморфизмом .

Если X = Y , то это автоморфизм, сохраняющий отношения .

Приложения

В алгебре изоморфизмы определены для всех алгебраических структур . Некоторые из них более подробно изучены; Например:

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

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

В теории графов изоморфизм между двумя графами G и H — это биективное отображение f из вершин G в вершины H, которое сохраняет «структуру ребер» в том смысле, что существует ребро из вершины u в вершину v в G тогда и только тогда, когда в H есть ребро из ƒ ( u ) в ƒ ( v ) . См. Изоморфизм графов .

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

В ранних теориях логического атомизма Бертран Рассел и Людвиг Витгенштейн полагали, что формальные отношения между фактами и истинными предложениями изоморфны. Пример такого мышления можно найти во введении Рассела в математическую философию .

В кибернетике утверждается , что хороший регулятор или теорема Конанта – Эшби: «Каждый хороший регулятор системы должен быть моделью этой системы». Независимо от того, регулируется он или саморегулируется, требуется изоморфизм между регулирующей и обрабатывающей частями системы.

Теоретический взгляд на категории

В теории категорий для данной категории C изоморфизм — это морфизм f : a → b, который имеет обратный морфизм g : b → a , то есть fg = 1 _b и gf = 1 _a . Например, биективное линейное отображение — это изоморфизм между векторными пространствами , а биективная непрерывная функция , обратная к которой также непрерывна, — это изоморфизм между топологическими пространствами , называемый гомеоморфизмом . {2} <2 \ right \}} а также B знак равно { — 1 , 0 , 1 } {\ Displaystyle B = \ {- 1,0,1 \} \,}

являются равными ; они просто разные представления — первое интенсиональное (в нотации построителя множеств ), а второе экстенсиональное (посредством явного перечисления) — одного и того же подмножества целых чисел. Напротив, наборы { A , B , C } и {1,2,3} не равны — в первом есть элементы, которые являются буквами, а во втором — числа. Они изоморфны как множества, поскольку конечные множества определяются с точностью до изоморфизма своей мощностью (числом элементов), и оба они имеют три элемента, но есть много вариантов изоморфизма — один изоморфизм

А ↦ 1 , B ↦ 2 , C ↦ 3 , {\ displaystyle {\ text {A}} \ mapsto 1, {\ text {B}} \ mapsto 2, {\ text {C}} \ mapsto 3,} в то время как другой А ↦ 3 , B ↦ 2 , C ↦ 1 , {\ displaystyle {\ text {A}} \ mapsto 3, {\ text {B}} \ mapsto 2, {\ text {C}} \ mapsto 1,}

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

Иногда изоморфизмы могут показаться очевидными и убедительными, но все же не являются равенствами. В качестве простого примера, генеалогические отношения между Джо , Джоном и Бобби Кеннеди в реальном смысле такие же, как и у защитников американского футбола в семье Мэннинга : Арчи , Пейтона и Эли . Пары отец-сын и пары старший-брат-младший-брат полностью соответствуют друг другу. Это сходство между двумя семейными структурами иллюстрирует происхождение слова « изоморфизм» (греч. Iso — «тот же» и — морф , «форма» или «форма»). Но поскольку Кеннеди — не те люди, что и Мэннинги, эти две генеалогические структуры просто изоморфны и не равны. {**}}

Однако есть случай, когда различие между естественным изоморфизмом и равенством обычно не проводится. То есть для объектов, которые можно охарактеризовать универсальным свойством . Фактически, существует уникальный изоморфизм, обязательно естественный, между двумя объектами, обладающими одним и тем же универсальным свойством. Типичным примером является набор действительных чисел , который может быть определен посредством бесконечного десятичного расширения, бесконечного двоичного расширения, последовательностей Коши , сокращений Дедекинда и многих других способов. Формально эти конструкции определяют разные объекты, которые являются решениями с одним и тем же универсальным свойством. Поскольку эти объекты обладают одинаковыми свойствами, можно забыть о методе построения и считать их равными. Это то , что делает все , когда речь идет « о множестве действительных чисел». То же самое происходит с факторпространствами : они обычно строятся как наборы классов эквивалентности . Однако обращение к набору наборов может быть нелогичным, и поэтому факторные пространства обычно рассматриваются как пара из набора неопределенных объектов, часто называемых «точками», и сюръективного отображения на это множество.

Если кто-то хочет различать произвольный изоморфизм (тот, который зависит от выбора) и естественный изоморфизм (тот, который может быть выполнен последовательно), можно написать ≈ для неестественного изоморфизма и ≅ для естественного изоморфизма, как в V ≈ V * и V ≅ V **. Это соглашение не соблюдается повсеместно, и авторы, которые хотят различать неестественные изоморфизмы и естественные изоморфизмы, обычно явно указывают это различие.

Обычно утверждение, что два объекта равны , зарезервировано для случаев, когда существует понятие большего (окружающего) пространства, в котором эти объекты живут. Чаще всего говорят о равенстве двух подмножеств данного набора (как в примере с целым набором выше), а не двух абстрактно представленных объектов. {*} \ right)}

— это три разных описания математического объекта, все из которых изоморфны, но не равны, потому что они не все подмножества одного пространства: первое — это подмножество R ³ , второе — C ≅ R ² плюс дополнительная точка, а третий является частичным от C ² .

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

Смотрите также

Заметки

Рекомендации

дальнейшее чтение

Внешние ссылки

Изоморфизм векторных пространств » ProcMem.Ru Линейная Алгебра

Определение. Пусть V и W – произвольные векторные пространства над полем К. Отображение  называют гомоморфизмом (или линейным отображением) векторного пространства  в векторное пространство , если  , :

1) ;

2) .

Определение. Пусть V и W – произвольные векторные пространства над полем К. Гомоморфизм  называют изоморфизмом векторного пространства  в векторное пространство , если отображение  является биекцией (т.е. взаимно однозначным соответствием).

Определение. Если существует изоморфизм , то векторное пространство  называют изоморфным векторному пространству .

Обозначение: .

Теорема. На множестве векторных пространств над одним и тем же полем K отношение изоморфизма является отношением эквивалентности, т.е. это отношение обладает свойствами рефлексивности, симметричности и транзитивности:

1) свойство рефлексивности:  – любое векторное пространство  изоморфно самому себе;

2) свойство симметричности: ;

3) свойство транзитивности: .

Следствие. Если V – векторное пространство над полем K и , то векторное пространство V изоморфно арифметическому векторному пространству столбцов высоты n: .

Доказательство. Отображение , определенное правилом  ,

,

где Х – столбец координат вектора х относительно фиксированного базиса  векторного пространства V над полем K, является:

1) гомоморфизмом векторных пространств, т.е.

,  верны равенства

 и ;

2) биекцией.

Отсюда по определению изоморфизма векторных пространств следует, что , ч.т.д.

Следствие доказано.

Отсюда и из следствия легко получить следующий результат.

Теорема. Два конечномерных векторных пространства над одним и тем же полем изоморфны тогда и только тогда, когда равны их размерности.

Доказательство предоставляется читателю.

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

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

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

Еще записи по теме

Одной из особенностей графов является то, что при их изображении на плоскости совершенно не важно, как расположены вершины друг относительно друга. Поэтому одному и тому графу могут соответствовать различные его изображения. Кроме того, именно такие рисунки, представляющие собой простейший способ задания графа, зачастую и называют графами. Чтобы отличать рисунки, отвечающие одному и тому же графу, от рисунков, изображающих различные графы, введем следующее понятие. Определение. Два графа G и H называются Изоморфными, если существует биекция F: V(G) ® V(H), сохраняющая смежность, т. е. такое биективное отображение, при котором образы вершин V и U графа G смежны в H тогда и только тогда, когда U и V смежны в графе G. Отображение F, обладающее указанным свойством, называется Изоморфизмом. Если графы G и H изоморфны, то пишут G @ H. Например, все три графа на следующих рисунках изоморфны друг другу (изоморфизм определяется нумерацией вершин) А на следующих трех рисунках представлены попарно неизоморфные графы. Очевидно, что отношение изоморфности на множестве графов является отношением эквивалентности (оно рефлексивно, симметрично и транзитивно). Следовательно, множество всех графов разбивается на классы изоморфных графов так, что разные классы не пересекаются. Все графы, попадающие в один класс естественно отождествлять, т. е. считать совпадающими (они могут отличаться лишь рисунком или природой своих элементов). В тех случаях, когда нужно подчеркнуть, что рассматриваемые графы отличаются лишь с точностью до изоморфизма, принято говорить об «Абстрактных графах«. По сути дела, абстрактный граф — это класс изоморфных графов. В некоторых ситуациях все же приходится различать изоморфные графы и тогда возникает понятие «Помеченный граф«. Граф порядка N называется помеченным, если его вершинам присвоены метки, например, номера 1, 2, 3, …, N. В этом случае вершины графа G отождествляют с их номерами, т. е. полагают, что V(G) = {1, 2, 3, …, N}. Помеченные графы G и H считаются совпадающими (изоморфными) при дополнительном условии, что E(G) = E(H). На следующих рисунках изображены три попарно неизоморфные помеченные графы (которые, очевидно, совпадают друг с другом, если убрать пометки). Для мульти-, псевдо — и ориентированных графов понятие изоморфности определяется аналогично, как биективность, при которой помимо смежности вершин и ребер сохраняются также кратность ребер, петли и направления дуг. < Предыдущая   Следующая >

Программный метод проверки изоморфизма деревьев.

Программный метод проверки изоморфизма деревьев.

Программный метод проверки изоморфизма деревьев.

  

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

На рисунке 1 отчетливо видно, что оба дерева имеют одинаковую структуру, но различный внешний вид. Соответствие вершин таково: 1-1, 2-3, 3-2, 4-4.

1. Алгоритм сравнения.

Задача алгоритма сравнения состоит в том, чтобы суметь «увидеть» структуру деревьев и сравнивать именно её, а не конкретные значения вершин.

Каждой вершине в соответствие ставится ряд чисел {x,y,{a1,a2,a3,…,an}}, где

x — уровень вершины по высоте;

y — ее «отцовый» уровень, т.е. длина максимальной линии потомков;

{a1,…,an} — ряд «отцовых» уровней её сыновей. (*)

В нашем примере вершинам дерева №1 соответствуют такие числа:

1 — {2, 2, {0, 1}}, 2 — {1, 0, {0}}, 3 — {1, 1, {0}}, 4 — {0, 0, {0}}.

Вершинам дерева №2:

1 — {2, 2, {1, 0}}, 2 — {1, 1, {0}}, 3 — {1, 0, {0}}, 4 — {0, 0, {0}}.

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

1. при сравнении этих массивов не важен порядковый номер элемента, т.е. элементу 2 одного массива может соответствовать элемент 3 второго массива;
2. не важен порядок элементов ряда «отцовых» уровней сыновей (*)

Т.е. учитывая вышеприведенные условия сравнения можно сказать, что элемент 2 — {1, 0, {0}} соответствует элементу 3-{1, 0, {0}}, а элемент 1 — {2, 2, {0, 1}} — элементу 1 — {2, 2, {1, 0}}.

2. Алгоритм переопределения вершин.

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

У первого дерева находим концевую вершину (ту, у которой нет сыновей), и делаем её корневой, т.е. дерево как бы вытягивается наверх за одну из вершин (см. рис. 3). Такой «вытяжки» можно достичь путем замены имени отца вершины именем одного из ее сыновей, и наоборот имени этого сына именем ее отца. Полученное дерево мы принимаем за эталонное.

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

Если алгоритм сравнения хотя бы один раз дал положительный результат, то деревья изоморфны.

Сложностью такого алгоритма проверки изоморфизма является величина порядка N2, где N — количество вершин в любом из сравниваемых деревьев.

Алгоритмы непосредственно в виде программы или блок-схемы слишком громоздки, и поэтому здесь не приводятся, но желающие могут скачать исходные тексты программы.(13Kb)

Литература.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

---

slot/conception.md at master · 2gis/slot · GitHub

Slot — изоморфный js-фрейворк для масштабируемых web-приложений.

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

Изоморфность

При создании web-приложений, особенно одностраничных, часто возникает проблема дублирования кода: клиентский js-код приходится дублировать серверным кодом. Изоморфные фреймворки, такие как Slot, решают эту проблему, стирая грани между front-end и back-end разработкой — один и тот же код работает как на сервере, так и на клиенте. Это позволяет, например, делать одностраничное веб-приложение, которое “из коробки” может быть полноценно проиндексировано поисковыми машинами.

Рассмотрим изоморфность более подробно на примере.

Допустим, вы зашли на главную страницу одностраничного новостного портала по адресу

На этом портале есть список анонсов новостей. При клике на анонс новости номер 168, эта новость разворачивается: появляется её полный текст. С точки зрения кода меняется состояние приложения (в частности DOM-дерево) (подробнее о состоянии см. ниже) так, чтобы на экране появилась выбранная новость. При этом новое состояние попадает в url при помощи History API браузера, и в адресной строке пользователя уже будет:

Важно отметить, что браузер не делает запрос по этому url, он просто приводит его в соответствие с состоянием приложения, в котором теперь развёрнута новость за номером 168. Если посмотреть в отладчике html-код страницы, то в нём будет код этой новости, хотя в исходном ответе сервера его не было: он был сгенерирован браузерным js-кодом после смены состояния приложения, и вставлен в DOM-дерево. Эта смена состояния инициирована действием пользователя.

Если теперь в новой вкладке перейти по этому url (example.com/news/168), то с сервера придёт тот же самый html код, который есть в предыдущей вкладке: разница между ними только в том, что, в первом случае html получился в результате модификации первоначального html-кода, а во втором случае он целиком пришёл с сервера.

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

Раньше эти два пути реализовывали два разных разработчика: front-end и back-end. Чаще это были даже разные языки программирования (например js и php). В изоморфных фреймворках одинаковый html-код генерируется клиентом или сервером одним и тем же js-кодом. Именно эта особенность позволяет назвать фреймворк, в частности Slot, изоморфным.

Состояние

Состояние — это максимально краткое описание представления приложения. В Slot состояние представлено js-объектом. Из этого объекта однозначным образом восстанавливается html-код. Изменять этот объект могут действия пользователя или, например, переходы по истории браузера. Важно, что состояние управляет приложением, а не наоборот.

В других фреймворках (например Ember) часто под состоянием понимают url; в случае со Slot это не так — состояние реализовано абстрактно и может работать с url, только с его хэшбэнгом, или вообще без него. Есть и другие существенные отличия, о которых речь пойдёт ниже.

Разберём пример с новостным порталом с точки зрения состояния. Для простоты будем считать, что состояние синхронизированно с url при помощи History API. Начальное состояние будет описываться пустым объектом:

Этому состоянию соответствует пустой url. А состояние выбранной новости, будет описываться, например, таким объектом:

и ему соответствует “/news/168”.

При любом изменении, новое значение состояния записывается в History браузера, и может быть полностью восстановлено при движении по истории браузера кнопками “назад” и “вперёд”. То есть, если в рассматриваемом примере, находясь в state2 пользователь нажмёт кнопку “назад”, History API скажет трекеру состояния приложения о том, что состояние изменилось, и новое состояние — это state1. Синхронно с этим вернётся и url.

Приложение реагирует на смену состояния, а не на причину, которая привела к этому изменению. Иными словами, если пользователь находится в state1 и нажимает “вперёд” — это запустит ровно тот же управляющий код, как если бы он кликнул по кнопке “раскрыть новость” в интерфейсе приложения. Смену состояния приложения обрабатывает один и тот же код, независимо от причины этой смены.

Состояние может быть надмножеством url.

Вернёмся к раскрытой новости, то есть к состоянию state2. Допустим, у новости есть комментарии, и находясь на странице конкретной новости, можно раскрыть какой-то конкретный комментарий. Раскрытие первого комментария приведёт к изменению состояния приложения на:

state3 = {
    news: 168,
    comment: 1
}

Slot позволяет сделать так, чтобы раскрытие комментария записывалось в историю, но не попадало в url. В этом случае url останется прежним:

Однако движение по истории кнопкой “назад” (state3 -> state2 -> state1) будет доступно пользователю. Это позволяет делать более тонкую seo-оптимизацию без ущерба для UX.

Состояние в Slot реализовано абстрактно.

Состояние можно связать с историей и url, полностью или частично, но способ и конкретная реализация этой связи не имеют существенного значения. Например, если у браузера нет поддержки History API, переход может быть связан с хэшбэнгом (url с якорем типа /#!news/168), либо вообще не использовать url . В последнем случае, правда, перестанут работать нативные браузерные кнопки “назад” и “вперёд”.

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

Модуль

Кирпичик, из которых состоит веб-приложение на Slot. Минимально модуль состоит из 1 js-файла, который определяет его интерфейс и внутреннюю логику. Однако, с модулем могут быть ассоциированы html-шаблоны, css и картинки. С точки зрения пользователя, модуль это всегда некий виджет, прямоугольная область приложения. С точки зрения DOM-дерева, это нода, логически связанные с ней дочерние ноды и логика.

Модуль имеет следующие поля:

init. Изоморфный метод, вызываемый при инициализации модуля.

bind. Клиентский метод, выполняемый при навешивании событий на html-элементы модуля.

viewContext. Изоморфный метод, возвращающий объект-контекст главного шаблона. В зависимости от реализации, объект может быть моделью.

elements. Декларативное описание элементов модулей, и ассоциированных с этими элементами обработчиков событий.

interface. Методы модуля. dispatcher. Диспетчер модуля, который отлавливает события от дочерних модулей.

slot

Кроме строгой иерархичности, в модульной архитектуре приложения на слоте есть ещё одна особенность: модули ничего не знают о других модулях, кроме дочерних, как и об инстансе приложения. Внешним миром для них является объект slot, персональная копия которого “выдаётся” каждому инстансу модуля в момент его инициализации.

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

init. Создание нового дочернего модуля.

mod. Без аргументов работает как геттер объекта модификаторов. При передаче объекта в качестве аргумента выставляет модификаторы по каждой паре ключ-значение переданного объекта.

notify. Единственный способ общения с неизвестным для модуля “внешним миром”. Генерирует сообщение, которое будет проброшено вертикально вверх по цепочке родительских модулей.

broadcast. Генерирует сообщение вертикально вниз модулям-потомкам (по-умолчанию — всем).

БЭМ

Слот не привязан ни к какой методологии верстки: писать html и css код можно как угодно, без ограничений. Однако, в слоте есть целый ряд вспомогательных систем, объединяющих js- и css-код в контексте методологии БЭМ. Использование методологии БЭМ упрощает разработку приложения на Slot.

Плагин

В объект slot можно добавлять свои методы.

Компонент

Логическая единица кода, используемая одним или несколькими модулями, не имеющая представления в виде html / css кода. От обычных вспомогательных библиотек, компонент отличается тем, что он может зависеть от app и / или других компонентов.

app

Главный объект, связывающий модули, компоненты и прочий код в единое приложение. Не доступен внутри модулей.

Отметим некоторые ключевые моменты жизни app:

1. Создание инстанса app. Подключается конструктор slot/app.js и создаётся инстанс приложения — app.
2. Инициализация. На этом этапе читаются все конфиги, выбирается главный модуль при помощи ключа конфига mainModule, который может быть функцией.
3. Инициализация модулей. Асинхронная сквозная инициализация всех модулей, начиная с главного модуля. На этом этапе вызывается метод init всех инициализируемых модулей, который в зависимости от модуля может быть асинхронным. Этот этап заканчивается только после вызова всех колбеков модулей.
4. Колбек app.init. Здесь можно вызвать render главного модуля и записать получившийся результат например в document.body.
5. На клиенте внутри колбека app.init необходимо вызвать app.bind() для выполнения клиентской инициализации и навешивания всех событий на DOM-элементы всех модулей.
6. Приложение готово для работы.

Стоит отметить, что пункт 1, 2 и 4 могут иметь разную реализацию для клиентской и серверной частей приложения, а пункт 5 выполняется только на клиенте.

Определение изоморфизма по Мерриам-Вебстеру

изоморфизм | \ ˌĪ-sə-ˈmȯr-ˌfi-zəm \ 1 : качество или состояние изоморфности: например,

а : сходство организмов разного происхождения в результате конвергенции

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

2 : взаимно однозначное соответствие между двумя математическими множествами. особенно : гомоморфизм, взаимно однозначный — сравните эндоморфизм Терминология

— Что означает «изоморфный» в линейной алгебре?

Два векторных пространства $ V $ и $ W $ называются изоморфными, если существует обратимое линейное преобразование (также известное как изоморфизм) $ T $ из $ V $ в $ W $.

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

$ 1 $. Скалярное умножение и сложение векторов в $ V $ переносится на скалярное умножение и сложение векторов в $ W $:

Для любых векторов $ x, y $ в $ V $ и скаляров $ a, b $ из нижележащего поля $ T (ax + by) = aT (x) + bT (y) $.

$ 2 $. Элемент идентичности $ V $ переносится на элемент идентичности $ W $:

Если $ 0_V $ — это единичный вектор в $ V $, то $ T (0_V) $ — это единичный вектор в $ W $.

$ 3 $. Инверсия вектора в $ V $ переносится на инверсию вектора.

$ T (-v) = — T (v) $ для всех $ v $ в $ V $.

$ 1 $ — это в точности свойство, определяющее линейные преобразования, а $ 2 $ и $ 3 $ являются избыточными (они следуют из $ 1 $).Итак, линейные преобразования — это гомоморфизмы векторных пространств.

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

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

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

Изоморфизм

в nLab

СОДЕРЖАНИЕ

Контекст

Теория категорий

теория категорий

Концепции

Конструкции универсальные

Теоремы

Расширения

Приложения

Равенство и эквивалентность

эквивалент

• равенство (дефиниционное, пропозициональное, вычислительное, оценочное, экстенсиональное, интенсиональное, разрешимое)

• тождественный тип, эквивалентность в теории гомотопических типов

• изоморфизм, слабая эквивалентность, гомотопическая эквивалентность, слабая гомотопическая эквивалентность, эквивалентность в (∞, 1) -категории

• естественная эквивалентность, естественный изоморфизм

• эквивалент датчика

• Примеры.

принцип эквивалентности

уравнение

• волокнистый продукт, откат

• гомотопический откат

• Примеры.

  • линейное уравнение, дифференциальное уравнение, обыкновенное дифференциальное уравнение, критическое геометрическое место

  • уравнение Эйлера-Лагранжа, уравнение Эйнштейна, волновое уравнение

  • Уравнение Шредингера, уравнение Книжника-Замолодчикова, уравнение Маурера-Картана, квантовое главное уравнение, уравнение Эйлера-Арнольда, уравнение Фукса, уравнение Фоккера-Планка, уравнение Лакса

Идея

Концепция изоморфизма обобщает концепцию биекции из категории «Набор множеств» на общие категории.

Изоморфизм — обратимый морфизм, следовательно, морфизм с обратным морфизмом.

Два объекта категории называются изоморфными , если между ними существует изоморфизм. Это означает, что они «одинаковы для всех практических целей» до тех пор, пока не нарушается принцип эквивалентности.

Но учтите, что два объекта могут быть изоморфными более чем по одному изоморфизму. В частности, отдельный объект может быть изоморфен самому себе нетривиальными изоморфизмами, отличными от тождественного морфизма.Часто имеет значение конкретный выбор изоморфизма.

Каждый изоморфизм, в частности, является эпиморфизмом и мономорфизмом, но обратное не обязательно.

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

Определения

Изоморфизм , или для краткости iso , является обратимым морфизмом, то есть морфизмом с двусторонним обратным.

Морфизм может называться isic (после более распространенных «monic» и «epic»), если это изоморфизм, но чаще его называют просто обратимым . Два объекта xx и yy являются изоморфными , если существует изоморфизм от xx до yy (или, что эквивалентно, от yy до xx). Автоморфизм — это изоморфизм одного объекта самому себе.

Недвижимость

Очевидно, что изоморфизмы удовлетворяют свойству два из трех.Но они также удовлетворяют свойству два из шести.

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

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

Группоид — это в точности категория, в которой каждый морфизм является изоморфизмом. В более общем смысле, ядро ​​любой категории CC — это подкатегория, состоящая из всех объектов, но только изоморфизмов; это своего рода группоид, лежащий в основе CC. Подобным образом автоморфизмы любого данного объекта xx образуют группу, группу автоморфизмов xx.

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

Примеры

Ди Маджио и Пауэлл — Институциональный изоморфизм

Ди Маджио и Пауэлл — Институциональный изоморфизм

П. Дж. Ди Маджио и У. Пауэлл, «Возвращение в железную клетку» институциональный изоморфизм и коллективная рациональность в организационных поля », American Sociological Review, 48 (1983), 147-60.

---

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

«По мере распространения инновации достигается порог, за которым обеспечивает легитимность, а не повышает производительность «.

Изоморфизм — это «ограничивающий процесс, который заставляет одну единицу в население, чтобы походить на других юнитов, которые сталкиваются с тем же набором экологических условий ».« Существует два типа иссморфизма: соревновательный и институциональные: «Организации конкурируют не только за ресурсы и клиентов, но для политической власти и институциональной легитимности, для sicoal а также экономическая пригодность «.

Три механизма институциональных изоморфных изменений

Коэрцитивный изоморфизм

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

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

Миметические процессы

Неопределенность поощряет подражание. Организационные модели можно распространять через миграцию сотрудников или через консалтинговые фирмы.

Нормативное давление

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

Люди с одинаковым образованием подойдут к решению проблем в примерно так же. Социализация на работе усиливает эти соответствия.

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

Предикторы изоморфных изменений

Предикторы организационного уровня

A-1: ​​Чем больше зависит от другой организации, тем больше она будет стать

A-2: Чем больше централизация поставок ресурсов, тем больше изменится, чтобы напоминать организации, от которых он зависит

A-3: Чем больше неопределенность, тем больше организация будет моделировать свою структуру после успешных фирм

A-4: Чем более неоднозначны цели, тем больше организация будет имитировать успешный для установления легитимности

A-5: Чем больше вероятность использования академических данных для выбора персонал, тем больше будет похож на другие организации.Также больший участие членов в профессиональных организациях, чтобы больше Организации будут.

Предикторы уровня поля

B-1: Чем больше поле зависит от одного источника, высший уровень изомофизма.

B-2: Чем больше поле взаимодействует с состоянием, тем больше изоморфизм.

B-3: Чем меньше количество организационных моделей, тем быстрее изоморфизм

B-4: Чем больше технологическая неопределенность или неоднозначность цели, тем больше скорость изоморфизма

B-5: Больше профессионализма в этой области, больше изоморфизма

изоморфных JavaScript: будущее веб-приложений | от AirbnbEng | Airbnb Engineering & Data Science

Автор: Спайк Брем

Этот пост был размещен на сайте VentureBeat.

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

Этот подход сегодня является обычным явлением и в библиотеках, подобных Backbone.js, Ember.js и Angular.js упростили разработчикам создание этих многофункциональных приложений JavaScript. Однако мы обнаружили, что у этих типов приложений есть некоторые критические ограничения. Чтобы объяснить почему, давайте сначала кратко рассмотрим историю веб-приложений.

JavaScript растет

С момента зарождения Интернета работа в Интернете работала следующим образом: веб-браузер запрашивал определенную страницу (скажем, «http://www.geocities.com/»), вызывая сервер где-нибудь в Интернете, чтобы сгенерировать HTML-страницу и отправить ее обратно по сети.Это хорошо сработало, потому что браузеры были не очень мощными, а HTML-страницы представляли документы, которые в основном были статичными и самодостаточными. JavaScript, созданный для того, чтобы веб-страницы были более динамичными, не позволял ничего больше, чем слайд-шоу изображений и виджеты выбора даты.

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

Одностраничное приложение

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

Библиотеки, такие как Backbone.js, Ember.js и Angular.js, часто называют клиентскими библиотеками MVC (Model-View-Controller) или MVVM (Model-View-ViewModel).Типичная клиентская архитектура MVC выглядит примерно так:

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

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

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

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

SEO

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

Производительность

Точно так же, если сервер не отображает полную страницу HTML, а вместо этого ждет, пока клиентский JavaScript сделает это, пользователи испытают несколько критических секунд пустой страницы или загрузочного счетчика, прежде чем увидят контент на странице. Существует множество исследований, показывающих резкое влияние медленного сайта на пользователей и, следовательно, на доход. Amazon утверждает, что сокращение времени загрузки страницы на каждые 100 мс увеличивает доход на 1%. Twitter потратил год, и 40 инженеров перестроили свой сайт для рендеринга на сервере, а не на клиенте, заявив о пятикратном улучшении воспринимаемого времени загрузки.

Ремонтопригодность

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

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

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

С этой целью мы в Airbnb экспериментировали с приложениями «Изоморфный JavaScript», которые представляют собой приложения JavaScript, которые могут работать как на стороне клиента, так и на стороне сервера.

Изоморфное приложение может выглядеть так, здесь оно называется «клиент-серверный MVC»:

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

Благодаря Node.js, быстрой и стабильной серверной среде выполнения JavaScript, мы можем воплотить эту мечту в реальность. Создавая соответствующие абстракции, мы можем написать логику нашего приложения так, чтобы оно работало как на сервере, так и на клиенте — определение изоморфного JavaScript.

Изоморфный JavaScript в дикой природе

Эта идея не нова — Nodejitsu написал отличное описание изоморфной архитектуры JavaScript в 2011 году, но она медленно внедрялась.Уже появилось несколько изоморфных структур.

Mojito был первым изоморфным фреймворком с открытым исходным кодом, получившим любую прессу. Это продвинутая полнофункциональная среда на основе Node.js, но ее зависимость от специфических особенностей YUI и Yahoo! Не привела к большой популярности в сообществе JavaScript с тех пор, как они открыли исходный код в апреле 2012 года.

Meteor, вероятно, самый известный изоморфный проект на сегодняшний день. Meteor построен с нуля для поддержки приложений в реальном времени, и команда создает целую экосистему вокруг своего диспетчера пакетов и инструментов развертывания.Как и Mojito, это крупный и самоуверенный фреймворк Node.js, однако он намного лучше привлекает внимание сообщества JavaScript, и его долгожданная версия 1.0 не за горами. Meteor — это проект, за которым нужно следить — у него есть звездная команда, и он привлек 11,2 миллиона долларов от Andreessen Horowitz — неслыханное явление для компании, полностью сосредоточенной на выпуске продукта с открытым исходным кодом.

Asana, приложение для управления задачами, основанное соучредителем Facebook Дастином Московицем, имеет интересную изоморфную историю.Принимая во внимание статус Московица как самого молодого миллиардера в мире, не пострадав от финансирования, Asana потратила годы в исследованиях и разработках, разрабатывая свой фреймворк Luna с закрытым исходным кодом, один из самых передовых примеров изоморфного JavaScript. Luna, изначально построенная на v8cgi за несколько дней до появления Node.js, позволяет запускать полную копию приложения на сервере для каждого отдельного сеанса пользователя. Он запускает отдельный серверный процесс для каждого пользователя, выполняя тот же код приложения JavaScript на сервере, который работает в клиенте, обеспечивая целый класс расширенных оптимизаций, таких как надежная автономная поддержка и мгновенные обновления в реальном времени.

Ранее в этом году мы запустили собственную изоморфную библиотеку. Он называется Rendr и позволяет создавать одностраничное приложение Backbone.js + Handlebars.js, которое также может полностью отображаться на стороне сервера. Rendr — это результат нашего опыта перестройки мобильного веб-приложения Airbnb для значительного сокращения времени загрузки страниц, что особенно важно для пользователей мобильных подключений с высокой задержкой. Rendr стремится быть библиотекой, а не фреймворком, поэтому он решает меньше проблем для вас по сравнению с Mojito или Meteor, но его легко модифицировать и расширять.

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

Маршрутизация

Нам нужен единый набор маршрутов, которые сопоставляют шаблоны URI с обработчиками маршрутов. Наши обработчики маршрутов должны иметь доступ к HTTP-заголовкам, файлам cookie и информации URI, а также указывать перенаправления без прямого доступа к окну.местоположение (браузер) или req and res (Node.js).

Получение и сохранение данных

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

Рендеринг представления

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

Сборка и упаковка

Оказывается, написание изоморфного кода приложения — это только половина дела. Такие инструменты, как Grunt и Browserify, являются важными частями рабочего процесса, необходимого для запуска и запуска приложения. Может быть несколько этапов сборки: компиляция шаблонов, включая зависимости на стороне клиента, применение преобразований, минификация и т. Д. Простым случаем является объединение всего кода приложения, представлений и шаблонов в один пакет, но для более крупных приложений это может в результате будут загружены сотни килобайт.Более продвинутый подход — создание динамических пакетов и внедрение отложенной загрузки ресурсов, однако это быстро усложняется. Инструменты статического анализа, такие как Esprima, могут позволить амбициозным разработчикам попробовать расширенную оптимизацию и метапрограммирование для сокращения шаблонного кода.

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

Оказывается, большинство модулей JavaScript уже можно использовать изоморфно, практически без изменений. Например, на сервере можно использовать популярные библиотеки, такие как Underscore, Backbone.js, Handlebars.js, Moment и даже jQuery.

Чтобы продемонстрировать это, я создал пример приложения под названием isomorphic-tutorial, которое вы можете проверить на GitHub.Объединив вместе несколько модулей, каждый из которых можно использовать изоморфно, легко создать простое изоморфное приложение всего в несколько сотен строк кода. Он использует Director для маршрутизации на основе сервера и браузера, Superagent для HTTP-запросов и Handlebars.js для создания шаблонов, все они построены на основе базового приложения Express.js. Конечно, по мере роста сложности приложения необходимо вводить больше уровней абстракции, но я надеюсь, что по мере того, как все больше разработчиков экспериментируют с этим, появятся новые библиотеки и стандарты.

По мере того, как все больше организаций привыкают использовать Node.js в производственной среде, неизбежно, что все больше и больше веб-приложений начнут совместно использовать код между клиентским и серверным кодом. Важно помнить, что изоморфный JavaScript — это спектр: он может начинаться с простого обмена шаблонами, постепенно превращаться в уровень представления всего приложения, вплоть до большей части бизнес-логики приложения. То, что и как код JavaScript разделяется между средами, полностью зависит от создаваемого приложения и его уникального набора ограничений.

Nicholas C. Zakas дает хорошее описание того, как, по его мнению, приложения начнут перетаскивать свой уровень пользовательского интерфейса на сервер от клиента, обеспечивая оптимизацию производительности и удобства обслуживания. Приложению не нужно вырывать свой бэкэнд и заменять его на Node.js, чтобы использовать изоморфный JavaScript, по сути, выбрасывая ребенка вместе с водой из ванны. Вместо этого, создавая разумные API и ресурсы RESTful, традиционный бэкэнд может жить рядом с уровнем Node.js.

В Airbnb мы уже начали переоснащать процесс сборки на стороне клиента для использования Node.js-инструменты, такие как Grunt и Browserify. Наше основное приложение Rails, возможно, никогда не будет полностью вытеснено приложением Node.js, но благодаря использованию этих инструментов становится все проще обмениваться некоторыми фрагментами JavaScript и шаблонами между средами.

Вы впервые услышали это здесь — через несколько лет редко можно будет увидеть продвинутое веб-приложение, в котором на сервере не выполняется какой-либо JavaScript.

Если эта идея вас вдохновляет, приходите на семинар по изоморфному JavaScript, который я буду преподавать на DevBeat во вторник, 12 ноября, в Сан-Франциско, или на Генеральной Ассамблее в четверг, 21 ноября.Мы вместе разберемся в образце изоморфного учебного приложения Node.js, которое я создал, чтобы продемонстрировать, насколько легко начать писать изоморфные приложения.

Также следите за развитием веб-приложений Airbnb, подписавшись на меня на @spikebrehm и на команду инженеров Airbnb на @AirbnbEng.

Изоморфизм: абстрактные и конкретные представления

Аркави, А. (2003). Роль визуальных представлений в изучении математики. Образовательные исследования по математике, 52 , 215–241.

Артикул Google Scholar

Беновски, Дж. (2016). Двойной аспектный монизм. Философские исследования, 39 (4), 335–352.

Артикул Google Scholar

Боб П. (2011). Мозг, разум и сознание: достижения в области нейробиологии . Springer Science & Business Media.

Бут, Р. Л., и Томас, М.Дж. (1999). Визуализация в обучении математике: решение арифметических задач и трудности учащихся. Journal of Mathematical Behavior, 18 (2), 169–190. https://doi.org/10.1016/s0732-3123(99)00027-9.

Артикул Google Scholar

Бреннер, М. Э., Майер, Р. Э., Мозли, Б., Брар, Т., Дуран, Р., Рид, Б., и Уэбб, Д. (1997). Обучение через понимание: роль множественных представлений в изучении алгебры. Американский журнал исследований в области образования, 34 (4), 663–689. https://doi.org/10.2307/1163353.

Артикул Google Scholar

Кобб П. (2002). Рассуждения инструментами и надписями. Journal of the Learning Sciences, 11 (2), 187–215. https://doi.org/10.1207/s15327809jls11,2-3n_3.

Артикул Google Scholar

Дисесса А. А. (2000).Мета-представление: введение. Journal of Mathematical Behavior, 19, (4), 385–398. https://doi.org/10.1016/s0732-3123(01)00051-7.

Артикул Google Scholar

Дисесса А.А. (2004). Метапрезентация: врожденная компетентность и цели для обучения. Познание и обучение, 22 (3), 293–331. https://doi.org/10.1207/s1532690xci2203_2.

Артикул Google Scholar

Дюваль, Р.(2006). Когнитивный анализ проблем понимания при изучении математики. Образовательные исследования по математике, 61 , 103–131.

Артикул Google Scholar

Эпштейн, В. и Хэтфилд, Г. (1994). Гештальт-психология и философия разума. Философская психология, 7 (2), 163–181.

Артикул Google Scholar

Фанселоу, М.С., Зеликовский М., Перузини Дж., Баррера В. Р. и Херсман С. (2013). Изоморфизмы между психологическими процессами и нервными механизмами: от элементов стимула до генетических маркеров активности. Нейробиология обучения и памяти, 108 , 5–13.

Артикул PubMed PubMed Central Google Scholar

Фрали, Дж. Б. (2003). Первый курс абстрактной алгебры (7-е изд.). Сэдл-Ривер, Нью-Джерси: Пирсон.

Google Scholar

Грей, Э., Питта, Д., и Толл, Д. О. (2000). Объекты, действия и изображения: взгляд на раннее развитие числа. Journal of Mathematical Behavior, 18 (4), 401–413. https://doi.org/10.1016/s0732-3123(00)00025-0.

Артикул Google Scholar

Джадсон, Т. У. (2012). Абстрактная алгебра: теория и приложения .Ортогональное издательство L3C.

Кандел, Э. Р., & Сквайр, Л. Р. (2000). Неврология: устранение научных барьеров на пути изучения мозга и разума. Science, 290 (5494), 1113–1120.

Артикул PubMed Google Scholar

Хатин-Заде, О., и Вахдат, С. (2015). Абстрактные и конкретные представления в структурном отображении и включении классов. Когнитивные лингвистические исследования, 2 (2), 349–360.

Артикул Google Scholar

Хатин-Заде, О., Вахдат, С., & Яздани-Фазлабади, Б. (2016). Алгебраическая перспектива неявного и явного знания. Когнитивные лингвистические исследования, 3 (1), 151–162. https://doi.org/10.1075/cogls.3.1.08kha.

Артикул Google Scholar

Хатин-Заде, О., Ярахмадзехи, Н., и Банаруэ, Х. (2018).Нейропсихологический взгляд на глубокую или абстрактную однородность между конкретно разными системами. Activitas Nervosa Superior, 60 (2), 68–74.

Артикул Google Scholar

Мармолехо-Рамос, Ф., Хатин-Заде., О., Яздани-Фазлабади, Б., Тирадо, К., & Саги, Э. (2017). Отображение воплощенных концепций: сочетание структурных отображений и теорий воплощения. Прагматика и познание , 24 (2), 164–185.

Москкович, Я.Н. (2008). «Я ходил по двое, он — по одному»: множественные интерпретации надписей как ресурсов для математических дискуссий. Journal of the Learning Sciences, 17 (4), 551–587. https://doi.org/10.1080/10508400802395077.

Артикул Google Scholar

Маллиган, Дж. Т. (2011). На пути к пониманию происхождения трудностей детей в обучении математике. Австралийский журнал трудностей обучения., 16 (1), 19–39. https://doi.org/10.1080/19404158.2011.563476.

Артикул Google Scholar

Маллиган, Дж. Т., Митчелмор, М. К., Инглиш, Л. Д. и Робертсон, Г. (2010). Внедрение программы ознакомления с образцами и структурой (PASMAP) в детском саду. В L. Sparrow, B. Kissane, & C. Hurst (Eds.), Формирование будущего математического образования: Материалы 29-й Ежегодной конференции Исследовательской группы математического образования Австралазии, (стр.797–804). Фримантл: МЕРГА.

Google Scholar

Питта-Пантази, Д., Грей, Э., и Кристу, К. (2004). Мысленные представления учащихся начальной школы о дробях. В M. J. Høines & A. Fuglestad (Eds.), Труды 28-й ежегодной конференции Международной группы психологии математического образования (том 4, стр. 41–48). Берген: Университетский колледж Бергена.

Google Scholar

Группа изучения математики РАНД.(2003). Знание математики для всех учащихся . Санта-Моника: РЭНД.

Google Scholar

Роллс, Э. Т. (2012). Нейрокультура: значение науки о мозге . Оксфорд: Издательство Оксфордского университета.

Google Scholar

Rolls, E. T., & Deco, G. (2010). Шумный мозг: стохастическая динамика как принцип работы мозга .Оксфорд: Издательство Оксфордского университета.

Google Scholar

Продам С.К. (2016). Учимся представлять, представляем, чтобы учиться. Journal of Mathematical Behavior, 41, , 191–209. https://doi.org/10.1016/j.jmathb.2015.10.003.

Артикул Google Scholar

Thomas, N., & Mulligan, J. T. (1995). Динамическая образность в детских представлениях числа. Научно-исследовательский журнал математического образования, 7 (1), 5–25. https://doi.org/10.1007/bf03217273.

Артикул Google Scholar

Уоррен, Э. (2005). Способность маленьких детей обобщать правило закономерностей для моделей роста. В Х. Чике и Дж. Винсенте (ред.), Труды 29-й конференции Международной группы психологии математического образования (том 4, стр. 305–312). Мельбурн: Программный комитет.

Google Scholar

Уайт, Т., и Пи, Р. (2011). Распространяется по дизайну: о перспективах и подводных камнях совместного обучения с несколькими представлениями. Journal of the Learning Sciences, 20 (3), 489–547. https://doi.org/10.1080/10508406.2010.542700.

Артикул Google Scholar

Равенство, часть 3: канонический изоморфизм.

Я не планировал писать третий пост о равенстве, но мой доклад на Big Proof 2019 (см. Слайды здесь) закончился огромным разделом о «равенстве математиков», и я понял, что могу сказать об этом больше.Вот еще несколько подробных мыслей по этому поводу.

Примеры канонических изоморфизмов.

Канонический изоморфизм — это магический вид равенства, очевидно доступный математикам, которые «думают о вещах правильно». У него есть несколько определений; у него нет определения. Однако мы узнаем это, когда видим это, мы почти все согласны по этому поводу, и, следовательно, мы, кажется, не оспариваем друг друга по этому поводу. Изоморфизм между конечномерным векторным пространством и его двойным двойным является каноническим — мы все это знаем.Изоморфизм теории полей классов каноничен (по крайней мере, с точностью до знака) — это мы тоже знаем. Даже соответствие Ленглендса считается каноническим — именно по этой причине мы верим в группу Ленглендса. Если говорить более обыденно, то канонически изоморфно. Мы вообще перестаем думать, что означают эти вещи? Формализация заставила меня задуматься об одном из них и привела к удивительному выводу.

Википедия также определяет каноническую карту — ну, почему бы вам просто не взглянуть.Там вообще нет формального определения. Страница помечена тегом «математическая терминология», но можно возразить, что это растягивает суть, если только вы не считаете «карту, сохраняющую самый широкий объем структуры» или «условно согласованную, наиболее полезной для дальнейшего анализа». иметь какое-то математическое значение.

Но что я здесь говорю? Нет ли в математике места для руководящих принципов и не полностью сформированных идей о том, как все должно сочетаться друг с другом? Разве мы не можем экспериментировать с концепциями и беспокоиться о том, чтобы расставить точки над i и пересечь их позже? Из конечно мы можем делать эти вещи! Это и есть искусство математики! На самом деле, это больше, чем просто дозволено — математикам разрешено проявлять творческий подход и придумывать блестящие идеи карт между явно несвязанными объектами, такими как представления Галуа и автоморфные представления, а затем предполагать, что эти конструкции существуют. в некотором роде каноническим и начинаем выяснять, к каким еще наблюдениям может привести нас такая идея.Такой образ мышления необходим для развития математики.

Одна вещь, которую я недавно понял, это то, что здесь есть две независимые тонкости, поэтому в этом посте я разделю их. Первое хорошо известно, второе мне кажется менее известным.

Выпуск 1: Ползучая миссия.

Первая проблема — это множество контекстов, в которых используется слово «канонический». Иногда люди используют его в ситуации, когда его можно легко строго формализовать. В теории категорий есть совершенно строгое определение естественного изоморфизма .Например, в категории конечномерных комплексных векторных пространств мы могли бы рассмотреть функтор, отправляющий векторное пространство самому себе, и мы могли бы рассмотреть второй функтор, отправляющий векторное пространство в его двойное двойственное. Между этими двумя функторами существует естественный изоморфизм , отправляющий векторное пространство в его двойное двойное. Можно найти определение естественного изоморфизма в Википедии; это утверждение, что точный набор диаграмм коммутирует. Люди говорят, что очевидное отображение векторного пространства в его двойное двойное является «каноническим», но вместо этого они могли бы сказать, что это естественное преобразование.Другой пример: два объекта удовлетворяют определенному универсальному свойству. Затем кусок абстрактной чепухи доказывает, что существуют уникальные изоморфизмы в обоих направлениях между этими двумя объектами, и снова оба заставляют коммутируют связку диаграмм. Снова математик мог бы сказать, что возникающие таким образом изоморфизмы являются «каноническими», и снова существует эквивалентный теоретико-категориальный язык, который они могли бы использовать вместо этого, чтобы точно сказать, что они означают.

Однако в математике бывают случаи, когда это слово используется за пределами этой компетенции.Некоторые теоретики чисел сказали бы, что изоморфизмы глобальной теории полей классов «каноничны». Я считаю, что это другое употребление этого слова. Может не быть какой-то формальной теоретико-категориальной структуры, за которой можно было бы спрятаться (хотя люди, пытающиеся категоризировать программу Ленглендса, вполне могут поверить, что такая структура существует). Здесь происходит то, что Артин создал некоторую конструкцию, изоморфизм между двумя абелевыми группами, присоединенными к числовому полю (одна с использованием аделей, а другая с использованием групп Галуа), и эта карта, которую он построил, подчинялась красивому длинному списку свойств, которые были явно определены записано (например, поведение карты при переходе от одного поля к конечному расширению), и нетрудно показать, что может быть не более одной конструкции с этими свойствами.Такая конструкция действительно существует (жесткая теорема), и эта конструкция затем получила название «каноническая», что здесь, кажется, является специализированным и другим использованием этого слова. Заметим, однако, что конструкция Артина дает изоморфизм между двумя абелевыми группами, и можно составить этот изоморфизм с отображением, отправляющим элемент абелевой группы к ее обратному, что дает нам второй канонический изоморфизм между этими двумя группами, который удовлетворяет аналогичному — но -не-точно-тот же красивый длинный список свойств, возможно, неотличимый от первого списка в том смысле, что неясно (по крайней мере, для меня), какой список «лучше».Однако эти два списка различимы в том смысле, что они разные, и их можно разделить. В этой ситуации трудно сказать, какая из конструкций является «наиболее канонической». Конструкции получили разные названия, и обе используются в литературе. Одна называется «теория полей классов, нормализованная классическим способом, отправляющая униформизаторы в арифметику Фробени», а другая — «теория полей классов, нормализованная способом Делиня / Ленглендса / Карайоля, отправляющая униформизаторы в геометрический Фробени».Геометрический Фробениус — это просто обратный арифметическому Фробениусу. Этот пример довольно неприятен, по крайней мере, в контексте определения канонической карты в Википедии, потому что обе карты полезны (классическая нормализация при выполнении конкретных вещей, таких как точки Хегнера, более современная нормализация при выполнении когомологий многообразий Шимуры), и в сообществе теории чисел нет особого согласия относительно того, какой вариант «лучший» — это просто зависит от того, что вы делаете.

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

Выпуск 2: каноничность вне универсального свойства.

Тем не менее, есть вторая проблема, о которой я начал думать, когда готовился к моему докладу о большом доказательстве, и это когда математики видят изоморфизм, который является «каноническим» в том смысле, который определенно можно сделать полностью точным, а затем решают, что изоморфизм настолько канонически каноничен, что просто использовать обозначение для него не составит труда.Дж. С. Милн в своей книге «Etale cohomology» даже объясняет в своих условных обозначениях, что канонические изоморфизмы будут обозначаться. [Что, все они? Даже два различных канонических изоморфизма теории полей классов? Нетрудно придумать очень правдоподобное доказательство этого, поскольку при абелианизации абсолютной группы Галуа рациональных чисел с использованием этого соглашения; конечно, это не то, что Милн хочет сказать (хотя было бы интересно услышать его определение «канонического» в этом контексте, если оно действительно у него было)].Милн, конечно, профессиональный математик, который знает, о чем говорит, и поэтому разумно использует это соглашение. Он не единственный. Даже Гротендик принимает это соглашение в EGA (EGA I, раздел 1.3.3), хотя он, кажется, не так четко об этом говорит. Контекст здесь заключается в том, что if — кольцо, и — два элемента со свойством, которое содержит простой идеал тогда и только тогда, когда он содержит (например, мы могли бы иметь или), то можно проверить наличие уникальной -алгебры изоморфизмы и чья композиция в обоих направлениях тождественна.Сам Гротендик использует французское слово «canoniquement» в приведенной выше ссылке, когда говорит об этом отождествлении, а пятью строками позже использует в качестве обозначения при утверждении утверждение того же характера, что и претензия. Если это область целостности, то можно построить и как явные подмножества поля дробей, и тогда они действительно будут равными подмножествам. Однако в общем случае такой роскоши нет. Что даже означает , чтобы сказать? Гротендик прямо написал.Что это даже означает ? Они вообще не равны в формальном смысле, как мы сейчас увидим — но они определенно канонически изоморфны — любой математик, знакомый с этой областью, скажет вам это.

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

Вот мое возражение против такого использования. В тот момент, когда два математических объекта равны , очевидно, что можно заменить один на другой в любой аргумент без каких-либо обоснований.Вот явный пример, который сильно укусил меня год назад. Это стандартный аргумент в базовой алгебраической геометрии на уровне выпускников, по которой я прочитал много трактовок, и я не совсем удовлетворен ни одним из них. Для простоты я расскажу об обращении в проекте stacks, потому что его проще всего процитировать. В теге 01HR говорится (немного перед определением 25.5.3): «Таким образом, мы можем применить алгебру, лемму 10.23.1 к модулю , и элементам». Но на самом деле это невозможно, строго говоря, с формалистической точки зрения.Потерпите меня, это не придирчивый педантичный момент, здесь есть кое-что еще. Цитируемая лемма находится в теге 00EK, который представляет собой некоторое утверждение о точной последовательности модулей. К сожалению, здесь есть два модуля, один в 01HR и один в 00EK, и они не совпадают. Для простоты предположим, что в 01HR, что означает, что в 00EK. Чтобы упростить задачу, предположим, что элементы на самом деле являются элементами, и назовем их так, чтобы они совпадали с обозначением в 01HR, поэтому, используя обычные обозначения для открытых множеств, прикрепленных к элементам.Даже с этими упрощениями все еще остается тонкая, почти невидимая проблема, которую формализация вот-вот нам покажет.

Проблема в том, что 00EK — это утверждение о точной последовательности, относящейся к, и. Теперь мы хотим применить это, чтобы доказать результат, относящийся к, и. Теперь из-за предположений мы знаем это и канонически изоморфны. Если мы теперь просто предположим, что они равны , и, кроме того, мы просто предположим, что карты равны для карт (т.е. схемы все коммутируют), то вообще никаких проблем! Это именно то, чем занимается проект stacks, это то, что делает Гротендик в EGA, это то, что делает Хартсхорн, это то, что делают все.

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

Но знаете что — карта в 00EK не является морфизмом колец . не может быть определен напрямую через универсальное свойство . Универсальное свойство действительно не , а говорит нам сразу о том, что диаграмма коммутирует! Мы здесь как бы жульничают; есть диаграмма, мы не можем ее увидеть из-за этой уловки использования для обозначения изоморфизма, изоморфизм является естественным, но из естественности , а не , сразу следует, что диаграмма, которую нам нужно коммутировать, коммутирует. Мы немного перешагнули отметку . Нам нужны два применения универсального свойства, а затем нам нужно взять их различие и наблюдать что-то вроде следующего: если два квадрата с четырьмя абелевыми группами коммутируют и вертикальные отображения одинаковы в каждом квадрате, то вычитание горизонтальных отображений дает поднимитесь к третьей диаграмме, которая также коммутирует.Здесь есть несколько недостающих аргументов. Я никогда не замечал этого аргумента, пока не попытался формализовать его. Как только я понял, что с формалистической точки зрения 00EK на самом деле слишком слаб для использования в 01HR, мне пришлось затем доказать набор лемм, показывающих, что 00EK (доказательство которого было большой работой, проделанной Крисом Хьюзом) плюс Ужасная погоня за диаграммой, доказательство которой здесь опущено, но которое нельзя было опустить в Lean , было достаточно, чтобы вывести 01HR. Меня беспокоило то, что в какой-то момент мне пришлось выйти «за пределы универсального свойства».Мало того, это усложнило отслеживание этой части кода. Я втянул нас в эту неразбериху, посоветовав Крису Хьюзу доказать 00EK, не проверив заранее, что этого достаточно для приложений — я, естественно, предположил, что в литературе нет тонких дыр. Рамон Фернандес Мир переписал всю базу кода с нуля, и не доказал 00EK вручную, а вместо этого доказал более инвариантную версию, используя кольца, изоморфные и т. д., вместо самих колец. Вместо использования универсального свойства (которое могло вызвать проблемы с вселенными) он использовал предикат, введенный Стриклендом, который точно характеризует, когда гомоморфизм колец превращается в -алгебру, изоморфную -алгебру.Все работает намного лучше — но мы не доказываем 00EK в его нынешнем виде; мы доказываем кое-что более общее. Доказываем дело, что нам действительно нужно .

Выводы.

Таким образом, я хотел бы утверждать, что это ленивое использование термина «канонический изоморфизм» на самом деле ослепляет некоторых математиков. Равенство — это очень мощная вещь. Если два канонически изоморфных объекта теперь считаются равными, потому что они оба подчиняются некоторому универсальному свойству, то внезапно мы можем манипулировать ими, как если бы они равны , независимо от того, используем мы универсальное свойство или нет .Это очень полезный трюк, потому что он позволяет нам эффективно обмануть, чтобы наши коллеги не заметили этого. Под «обманом» здесь я подразумеваю то, что он позволяет нам отбросить утомительные аргументы. Никакого математика не волнуют эти утомительные аргументы , если они действительно существуют . В случае схем они действительно существуют. Конечно есть! Если бы была какая-то фундаментальная проблема со структурными связками, люди, очевидно, заметили бы это несколько десятилетий назад. Но как насчет всех других значений канонического изоморфизма? Мы действительно их проверяем? Узнаем ли мы точно, возникнет ли какая-то тонкость?

Представьте себе следующую ситуацию.Скажем, в вашем аргументе есть два объекта и. Скажем, хорошо известно, что они канонически изоморфны. Теперь, может быть, есть какие-то конструкции, которые можно легко сделать. И, может быть, есть еще какие-то конструкции, которые можно легко сделать. Конструкции действительно включают в себя практическое построение и, в частности, выходят «за рамки» функториальности или универсальности изоморфизма, однако они «вызывают у них то же чувство», поэтому они явно «равны» — по крайней мере, они чувствуют как «равны» как и «равны».Разве не легко было бы просто отказаться от утверждения, что эти конструкции также «равны», даже если это не может быть формально выведено из известных функториальных свойств, порождающих изоморфизм? Может ли такое случаться в литературе или это всего лишь абстрактное пристальное наблюдение за пупком?

Это совсем бывает! И вот очень важный момент, когда математику это почти сошло с рук! В основополагающей статье Дика Гросса 1990 г. о сопутствующих формах («Критерий приручения представлений Галуа, связанных с модульными формами (mod p)», Duke Math Journal Vol 61 № 2, октябрь 1990 г.) Гросс канонически определяет несколько теорий когомологий модульных кривых и затем утверждает без каких-либо оснований, что операторы Гекке, определенные на этих группах когомологий, также отождествлены.Группы когомологий были известны как «канонически изоморфные», однако это был один из тех «канонических изоморфизмов», который имел форму «посмотрите на это аккуратное отображение; сейчас все работает, кроме того, чтобы это оправдать, нужно много страниц ».