Часть II. Начала дискретной математики. SQL, Комбинаторика, Тервер за 15 минут. SQL, EBNF, XPATH в 480 LOC

07.07.2026 ideipro.ru 1

(Серия: Сельскому учителю в помощь)ВСТУПЛЕНИЕ

┼┼┼┼┼┼┼┼┼▄▀▀▀▄▄▄▄▄▄▄▀▀▀▄┼┼┼┼┼┼┼┼  
┼┼┼┼┼┼┼┼┼█▒▒░░░░░░░░░▒▒█┼┼┼┼┼┼┼┼   
┼┼┼┼┼┼┼┼┼┼█░░█░░░░░█░░█┼┼┼┼┼┼┼┼┼   
┼┼┼┼┼┼─▄▄──█░░░▀█▀░░░█──▄▄─┼┼┼┼┼  
┼┼┼┼┼┼█░░█─▀▄░░░░░░░▄▀─█░░█┼┼┼┼┼  
┼┼┼██░██░████░██░░░██░░░█████┼┼┼  
┼┼┼██▄██░██▄▄░██░░░██░░░██░██┼┼┼  
┼┼┼██▀██░██▀▀░██░░░██░░░██░██┼┼┼  
┼┼┼██░██░████░████░████░█████┼┼┼

Объяснить с

Для строительства компиляторов, нам нужны начала математики. Из них, как мы убедимся, проистекает добрая половина понимания и всех наших работ.
В частности, без начал не понять лямбда-исчисление Чёрча, которое мы рассмотрим и применим на этапе работы с AST.

РАЗДЕЛ: ПЕРЕХОД К МАТЕМАТИКЕ

1. ГЛАЗАМИ МАТЕМАТИКА: ОБЪЯСНЕНИЕ, ГЕНЕЗИС

В 1960-е – нет избыточности. Высчитывается каждый такт процессора и сантиметр бумаги, дороги. Мозг работает как оптимизирующий компилятор.
Ученые того времени (Шеннон, Винер, фон Нейман) были одновременно математиком, инженером и философом. Они верили, что законы логики в ламповой ЭВМ соответствовали законам нейронов в мозгу. Это давало им право писать о технике как о живом организме. Они искали математический скелет во всём: в языке, в клетке мозга, в обществе.
Любое знание детерминировано: при тех же входных данных мы получаем тот же результат. «Объяснение» соответствует направленному графу DAG Directed Acyclic Graph, в узлы которого положены факты и понятия, а в рёбра – связи над ними. Потерю узлов, назовём «пробелами», потерю ребер – «разрывами в логике» объяснения. Если вы не можете начертить маршрут от аксиомы к выводу, вы не знаете предмета.
«Генезис» – это ориентированный граф DAG, показывающий зарождение и видоизменение объекта во времени (эволюцию, мутации, слияния и разделения объекта на временной шкале). В науках графы генезиса применяют: генетики, вирусологи, эволюционные биологи, историки-лингвисты. Инженер-программист каждый день видит граф генезиса проекта в дереве системы контроля версий. «Объяснить» предмет, значит построить его генезис.
«Лаконичность» – это когда нет лишних слов при полной связности.
Само слово происходит от названия древнегреческой области Лакония, со столицей Спарта. Спартанцы сознательно презирали длинные речи. Жителей Лаконии с детства учили говорить кратко, чётко и только по делу. Болтовня в Спарте считалась признаком слабости и дурного тона.
Когда отец Александра Македонского царь Филипп II подошел к границам Лаконии и отправил спартанцам послание: «Если я захвачу Лаконию, я сравняю Спарту с землей», правители Спарты отправили назад свиток с одним словом: «Если».

2. ПРЕДИКАТЫ: ПЕРЕХОД ОТ ОБЪЕКТОВ ФИЗИКИ К ОБРАЗАМ МАТЕМАТИКИ

                __             <}    _hello!  .-.:|.-.  
  ,--./,-.     '--`.          ,--\,-("\     '-.      .-'  
 / #      \       _|,--.     / #     ) )      }      {  
|          |     / `)   \   (       (_/)      }      {  
 \        /      \      |    \        /     .-'      '-.  
  `._,._,'   jgs  '.___/      `._,._,'  hjw   '-_.._-'

Математика (абстракции) и инженерия (предметы) у нас всегда отделены непроницаемой перегородкой. Помесь из терминов – недопустима. Мы строго устанавливаем и отслеживаем взаимно-однозначные переходы над объектами и терминами.
Математика работает с ограниченным количеством образцов, выход за которые – запрещён. Много ли вы видели «точек» – объектов, у которых нет размеров? Или «направленных отрезков» – геометрических «векторов»? В математике не учитывают 99% образцов или «свойств» объектов реального мира, и выделяют оставшийся 1%. Собранные из таких свойств объекты называют «абстракции» или математические «образы».
Множество – первичное понятие. Его не определяют через другие, а вводят, например, перечислением. Кантор объяснял его так: «многое, мысленно взятое целым». Почему «мысленно»?
Корзинка яблок – физический образ числа: яблоки – вполне обособленны и отличимы друг от друга. А при перемещении их в корзинке, ведут себя как целое. Но математик не может назвать корзинку с яблоками «числом», а может лишь поставить ей число в соответствие.
Математикам нужен «мостик», ставящий в соответствие реальным объектам их абстрактные образы – и обратно. Такие «мостики» между произвольными объектами и объектами математики в логике называют «предикатами». Назначение предиката «отбросить» 99% свойств объектов, и поставить в соответствие произвольному объекту физики или математики элемент из множества {0, 1}, или, что эквивалентно, {«нет», «да»}. Для инженера реализацией «предиката» будет датчик, сигнализирующий «идёт дождь» (0/1)?
Ответим на вопросы: «Яблоки в корзинке неделимы, различимы и ведут себя как целое, относительно её перемещения (нет/да)?» перечисленные свойства яблок соответствует свойствам «элементов» дискретного множества (нет/да)? Ну, вот, теперь математик успокоится: возьмёт корзинку, пересчитает яблоки и скажет, что работает с «соответствующей математической моделью». Очень похоже на софистику? Наверное.
Если рискам на линейке соответствуют числа, мы можем ставить им в соответствие цифры, что и сделал Декарт на геометрической плоскости. Ну, вот мы и перешли из «реального мира» в «мир» математики.
Когда Кантор говорил «мысленно», он имел в виду что механизмом, реализующим «предикаты» и сопоставляющим объектам физики объекты математики – и обратно, часто выступают органы – глаза и мозг человека.

3. О ТОЧНОСТИ ЯЗЫКА

Если не следить за языком и точностью логико-математических построений, можно попасть в скверные ситуации.
Современный «математик» очень «гибок» в этом плане: один с пеной у рта будет доказывать, что множества 2, 4 и 4, 2, 2 – эквивалентны, ведь «перечисление элементов не играет роли, а наличие дубликатов не меняет суть множества: элемент либо принадлежит множеству, либо нет (2 ∈ A)», второй – обратное: что и то и другое – важно. Но встретившись они согласятся друг с другом, и разбегутся, оставив вас в дураках.
Дело в том, что в разных разделах математики и инженерных дисциплинах те же термины определены по-разному. Небрежное употребление математических терминов сродни «хождению по минному полю».

***

РАЗДЕЛ: ДИСКРЕТНЫЕ МНОЖЕСТВА

1. ДИСКРЕТНЫЕ МНОЖЕСТВА ИЛИ «АССЕМБЛЕР» ЧИСЛОВОЙ МАТЕМАТИКИ

          _ _                                         _ _  
     _(,_/ \ \____________               ____________/ / \_.)_  
     |`. \_@_@   `.     ,'               `.     ,'   @_@_/ ,'|  
     |\ \ .        `-,-'                   `-.-'        , / /|  
     || |  `-.____,-'                         `-.____,-'  | ||  
     || /  /                                           \  \ ||  
     |/ |  |                                           |  | \|  
`..     /   \                                         /   \     ,,'  
  \\   /    |                                         |    \   //  
  ||  |      \                                       /      |  ||  
   \\ /-.    |                                       |    ,-\ //  
   ||/  /_   |                                       |   _\  \||  
hh \(_____)-'_)                                     (_`-(_____)/  -Sh

Объяснить с

1. Алгебры

Множество S вместе с действиями над ним O называют алгебраической системой (или универсальной алгеброй) А = <S, O>. Частный случай такой системы – классическая арифметика: Ar = <S, {+,-,•,/}>, где S – множество рациональных чисел, а символами {+,-,•,/} обозначены операции сложение, вычитание, умножение, деление (кроме деления на ноль).
Операция соответствует неделимому физическому движению. Сдвинуть две кучи камней в одну – эквивалентно «сложению» +. Для инженера операция – это действие механизма, преобразующего входной сигнал в выходной (а математик скажет «ставит в соответствие сигнал сигналу»).
Далее под «функцией» мы понимаем числовые функции любой арности.

2. Количества («числа») и их обозначения («цифры»)

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

ТАБЛИЦА ЭТАЛОНОВ ЦЕЛЫХ ЧИСЕЛ  
  
+--------------------------+-------------------+  
| КОНЕЧНОЕ МНОЖЕСТВО       | ЗНАК (ЦИФРА)      |  
+--------------------------+-------------------+  
| [*]                      | 1                 |  
| [**]                     | 2                 |  
| [***]                    | 3                 |  
| [...]                    | ...               |  
+--------------------------+-------------------+

Объяснить с

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

3. Дискретные множества

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

***

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

4. Достаточный минимум операций

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

ТАБЛИЦА БИЕКЦИЙ (СООТВЕТСТВИЙ). ОПЕРАЦИИ  
+-------------------------------------------------------------------------------------+  
|       ЭЛЕМЕНТАРНЫЕ МНОЖЕСТВА    |            АРИФМЕТИЧЕСКИЙ ЭКВИВАЛЕНТ              |  
+-------------------------+---------------+-------------------------------------------+  
| ОТОБРАЖЕНИЕ             |    ФОРМУЛА    |                   СУТЬ                    |  
+-------------------------+-------+-------+-------------------------------------------+  
| 1. Объединение          | A U B | A + B | Сложение.  При этом A ∩ B = { }           |  
| 2. Разность             | A \ B | A - B | Вычитание. При этом |B ∩ A| = |B|         |  
| 3. Пересечение          | A ∩ B |       | Нет эквивалента.                          |  
+-------------------------+-------+-------+-------------------------------------------+  
| 4. Прямое («декартово») | A × B | A • B | Получение полного множества пар. A × B    |  
| произведение множеств   |       |       | Базис операции умножения. A • B = |A × B| |  
+-------------------------+-------+-------+-------------------------------------------+  
| 5. Мощность множества   | | S | |       | Отображение произвольного множества       |  
|                         |       |       | в числовое («счет» элементов).            |  
+-------------------------+-------+-------+-------------------------------------------+  
  
ТАБЛИЦА БИЕКЦИЙ (СООТВЕТСТВИЙ). ЧИСЛА – ЭЛЕМЕНТАРНЫЕ МНОЖЕСТВА  
+---------------+-----------+-------------------------------+  
| ОПЕРАЦИЯ      |  ФОРМУЛА  | ЭКВИВАЛЕНТ В ОТОБРАЖЕНИЯХ     |  
| АРИФМЕТИКИ    | (ЗАПИСЬ)  | НАД ДИСКРЕТНЫМИ МНОЖЕСТВАМИ   |  
+---------------+-----------+-------------------------------+  
| Сумма (+)     | 1 + 2 = 3 | [*] U [**] -> [***]           |  
| Вычитание (-) | 3 - 1 = 2 | [***] \ [*] -> [**]           |  
| Умножение (•) | 2 * 3 = 6 | |[**] x [***]| -> [******]    |  
+---------------+-----------+-------------------------------+

Объяснить с

Арифметическое умножение • имеет два шага: взять прямое (или «декартово») произведение x над множествами и взять мощность | | полученного результата:

   ФОРМУЛА: a • b = | A × B|  
   СООТВЕТВУЮЩИЙ АЛГОРИТМИЧЕСКИЙ ГРАФ:  
  
          [ | | ]   <-- Мощность множества (результат: число)  
             |  
          [  ×  ]   <-- Декартово произведение (результат: множество пар)  
           /   \  
        [ A ] [ B ] <-- Входные множества

Объяснить с

5. Двудольные или «бинарные» графы

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

ПРИМЕРЫ:

***

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

2. ИНЖЕНЕРНАЯ МАТЕМАТИКА, ПОЛНОТА И ДЕТЕРМИНИЗМ

Неизвестно что происходит в масштабах микрокосма (атомы) и на границах макрокосма (Вселенной) – нет средств для наблюдения. Но мы умеем исключать неопределённость из техники. Иначе вычислители считали бы «неизвестно что», а самолёты летели «неизвестно куда». Будоражащие умы «парадоксы» печатает жёлтая пресса и пропаганда для обывателя.
Лаплас считал, что «случайность» это следствие и мера нашего незнания деталей. Его тезис звучит так: «Если бы некий Разум в определенный момент знал положение и импульс каждой частицы и все силы во Вселенной, и подверг эти данные анализу, то для него не осталось бы ничего неясного. И будущее, как и прошлое, предстало бы перед его взором». Инженерная система это прямое воплощение «детерминизма» Лапласа: в тех же условиях мы получим тот же результат.
Объектам физического мира всегда будет соответствовать некоторая мера нашего незнания (хотя бы из-за несовершенства приборов измерения), но «неопределенность», как свойство самой математической модели недопустимо.
Знание границ нашего незнания помогает исключать «случай». Теория вероятностей – один из способов ограничить (или локализовать) неопределённость или недостаток сведений. Сочетает комбинаторику (точный просчёт свойств систем дискретных элементов, размещаемых в математических пространствах) и числовую оценку свойств некоторых выборок объектов (произвольные выборки – предмет математической статистики).
Математика начинается с устранения неопределённости самой модели: мы перечисляем и отслеживаем свойства математического объекта, которые на любом этапе вычислений точно и полностью определены. По аналогии с физикой, каждому объекту (например, функции) ставят в соответствие его «пространство состояний». Например, множество с заданной на нем алгебраической структурой.
Под «полнотой» математического объекта далее понимаем совокупность свойств, обеспечивающих его детерминизм в конкретной задаче. Любой не полный объект делает неполной включившую его математическую модель как целое (разрушает целостность).

3. КОЛЬЦА И ПОЛЯ В ЭВМ

░░░(¯`:´¯)⋰  
(¯`•.\|/.•´¯)  
░(¯`•.O.•´¯)(¯`:´¯)⋰  
(_.•´/|\`•._).\|/.•´¯)  
░░░(_.:._)(¯`•.O.•´¯)  
░░░(¯`:´¯)⋰•´/|\`•._)  
(¯`•.\|/.•´¯)_.:._)  
░(¯`•.O.•´¯)░░(¯`:´¯)⋰  
(_.•´/|\`•._)`•.\|/.•´¯)  
░░░(_.:._)░░(¯`•.O.•´¯)  
░░░░░░░░░░░(_.•´/|\`•._)  
░░░░░░░░░░░░░░(_.:._)

Объяснить с

Математика – это особая форма мышления. Каждая буква x, y ... в формулах обозначает объект-множество (аналог в физике «объект с разными состояниями»). Нужно отслеживать полноту объектов-множеств (или «всевозможные состояния объекта») на каждом шаге вычислений, иначе формула «ломается».
Определяя функцию областью значений и определений, полями и кольцами устанавливают диктат полноты над многозначными объектами.
Кольца унифицируют объекты математики, инженерии, и физики с одинаковыми аксиомами. Если теорема доказана для «кольца», она работает для многочленов, матриц, шифров, физических количеств.

***

Кольцо это множество S и две двуместные операции: «сложение» + и «умножение» •. Кольцо формирует и строго ограничивает математическое пространство, где лежат результаты операций над множеством. Если сложить или умножить два элемента кольца, получится элемент того же множества. Это называют «замкнутость». Замкнутость исключает появление «чужеродных» объектов в кольце. Операции можно вкладывать друг в друга: подавать результат сложения в умножение a•(b+c), и обратно a+(b•c). Операции не выйдут за S и не «сломаются».

***

Последовательность из той же «ассоциативной» операции можно выполнять в произвольном порядке. Сложение (3) и умножение (7) ассоциативны.
В «коммутативной» функции порядок следования аргументов произволен. У колец сложение коммутативно (2) и мономы в многочленах можно менять местами. Так, в кольце целых чисел коммутативно сложение и умножение, в кольце квадратных матриц умножение не коммутативно A•B ≠ B•A.
«Обратные» сложению элементы (5) позволяют исключить «вычитание», заменив его сложением.
Если в кольцо с коммутативными сложением и умножением добавить элемент «единица» 1 такой что a•1 = a и «обратные» умножению элементы, исключив ноль (что есть эквивалент операции «поделить»), получим алгебраическое «поле». Так, арифметика над целыми числами – это кольцо, над дробными – и кольцо, и поле.
В ЭВМ компилятор имеет право применить дистрибутивность для поля целых чисел short, int, long и заменить (a*b)+(a*c) более быстрым a*(b+c). Для float и double это запрещено, в стандарте IEEE 754 они не образует даже кольцо: из-за погрешностей округления ассоциативность нарушается, и (a+b)+c и a+(b+c) могут дать разный результат. Это может повлиять, например, на расчет пересечения объектов в геометрии. В стандартах C99/C++98 компилятор не меняет порядок вычислений в float/double выражениях без специальных флагов оптимизации.

***

При оптимизации в формульной математике и в компиляторах берут свойства матричных колец. Так, в 3D вектор положения вершины 1x4 умножают на матрицу «вида» 4x4 и «проекции» 4x4 (4x4*4x4)*1x4, итого 80 умножений и 60 сложений. Эквивалентная формула 4x4*(4x4*1x4) даст 32 умножения и 24 сложения.
В циклических буферах берут кольцо вычетов по модулю размера буфера, исключая выход за границы массива.

4. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ

Правила составления комбинаций (комбинаторика) нужны нам для ввода пространств состояний и установления диктата полноты над математическими объектами.
Берём по очереди каждый элемент из множества A и строим с ним все возможные пары или «комбинации» с элементами множества B.

A = {0,1,2}, B = {3,4}, AxB = {(0,3), (0,4), (1,3),(1,4) ,(2,3) ,(2,4) }

Объяснить с

Эта статичная структура, называемая прямым или «декартовым» произведением» x, заключает полный комбинаторный потенциал множеств A и B. Количество комбинаций равно произведению мощностей множеств |A|*|B|.
В практике декартовое произведение (так же cartesian) применяют повсеместно. Многоместный cartesian занимает строки кода JS.

***

ПРИМЕР 1. ИНЖЕНЕРИЯ

3-разрядный одометр (счётчик километров) – инженерный аналог 3-местного cartesian.

РЕГИСТР (БЛОК РАЗРЯДОВ) ОДОМЕТРА  
  
  Множество A      Множество B      Множество C  
+-----------+    +-----------+    +-----------+  
|     0     |    |     3     |    |     6     |  
|-----------|    |-----------|    |-----------|  
| [   1   ] |    | [   4   ] |    | [   7   ] | <-- Элемент (1,4,7)  
|-----------|    |-----------|    |-----------|  
|     2     |    |     5     |    |     8     |  
+-----------+    +-----------+    +-----------+  
      |                |                |  
      +---------------------------------+  
                    |  
                    V  
    Любая комбинация цифр (напр. 1,4,7) в регистре соответствует элементу  
   (или арифметическому вектору) из декартового произведения AxBxС

Объяснить с

***

ПРИМЕР 2. МАТЕМАТИКА

ТАБЛИЦА СЛУЧАЕВ ПРИМЕНЕНИЯ CARTESIAN  
  
+------------------------------------------------------------------------+  
| 1. База операции умножения чисел A • B = |A × B|                       |  
+------------------------------------------------------------------------+  
| Эквивалентные записи:                                                  |  
| |{a,b} x {c,d,e}| = |{ (a,c), (a,d), (a,e), (b,c), (b,d), (b,e) }| =   |  
| |[**]| • |[***]| = 2 • 3 = 6                                           |  
+------------------------------------------------------------------------+  
| 2. База правила дистрибутивности a(b+c) = ab+ac                        |  
+------------------------------------------------------------------------+  
| Частные случаи:                                                        |  
+------------------------------------------------------------------------+  
| 2.1 Не нужно запоминать формулы умножения многочленов, включая         |  
|     "сокращенные" для возведения многочленов в степень                 |  
|                                                                        |  
| (b+c)^3 = (b+c)(b+c)(b+c) = (bb+bc+cb+cc)(b+c) =                       |  
| = bbb + bbc + bcb + bcc + cbb + cbc + ccb + ccc =                      |  
| = b^3 + 3b^2c + 3bc^2 + c^3                                            |  
+------------------------------------------------------------------------+  
| 2.2 База построений «квадриков» (поверхностей 2 порядка)               |  
|                                                                        |  
| Строим многочлен на полноте комбинаций элементов множества {x,y,z,1}   |  
| и добавляем к мономам коэффициенты A-L:                                |  
| (x+y+z+1)*(x+y+z+1) =                                                  |  
| = x^2 + y^2 + z^2 + 2xy + 2xz + 2yz + 2x + 2y + 2z + 1 = 0             |  
|                                                                        |  
| A*x^2 + B*y^2 + C*z^2 + 2D*x*y + 2E*x*z + 2F*y*z + 2G*x + 2H*y +       |  
| + 2K*z + L = 0                                                         |  
|                                                                        |  
|                 | A  D  E  G |   | x |                                 |  
| [x, y, z, 1]  * | D  B  F  H | * | y | = 0                             |  
|                 | E  F  C  K |   | z |                                 |  
|                 | G  H  K  L |   | 1 |                                 |  
+------------------------------------------------------------------------+  
| 3. База матричного умножения                                           |  
+------------------------------------------------------------------------+  
| Взять за множество A строки первой матрицы, за B – столбцы второй,     |  
| выполнить AxB, и скалярно умножить полученные пары векторов почленным  |  
| умножением и сложением их компонент (это объясняет почему размер строк |  
| и столбцов при произведении матриц должен быть одинаков).              |  
+------------------------------------------------------------------------+  
| 4. База для формул теории вероятностей и комбинаторики                 |  
+------------------------------------------------------------------------+  
| 5. База для просчета пространств состояний объектов в инженерии        |  
+------------------------------------------------------------------------+  
| Фиксация полноты комбинаций алфавитов системы. Если у автомата         |  
| |A| = 2 режима работы, а на вход подается |B| = 3 типа сигналов,       |  
| то мощность пространства состояний |AxB| = 2 • 3 = 6.                  |  
| Необработанных (undefined) аппаратных прерываний не будет.             |  
+------------------------------------------------------------------------+  
| 6. Вложенные циклы for в программировании                              |  
+------------------------------------------------------------------------+  
| Декартово произведение в императивных языках. Выполняет пошаговый      |  
| перебор декартова произведения индексов. Даёт полноту перебора таблиц  |  
| и элементов многомерных массивов в памяти без пропусков и повторений.  |  
+------------------------------------------------------------------------+

Объяснить с

ПРИМЕР 3

Построим XxY, где X= {1,2,3,4,5,6,7,8}, Y= {1,2,3,4,5,6,7,8} и разместим на декартовой плоскости, ставя в соответствие парам знаки на цифровых осях. Результат связал комбинаторное множество, матрицы, геометрию.

***

5. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ. БУЛЕАН

Булеан P – множество всех подмножеств исходного множества S (или объединение всех возможных сочетаний разной длины). Размер |P(S)| = 2^|S|.
Как оператор булеан находит все возможные способы выбрать элементы из одного множества (включая вариант не брать ничего или взять всё).
Элементы внутри подмножеств булеана не имеют порядка и не повторяются. Этим они отличаются от кортежей и векторов – строго упорядоченных последовательностей элементов, где могут быть дубликаты.

Исходное множество S = {1,2,3}, |P(S)| = 2^3 = 8, |S x S| = 3*3 = 9  
  
+------------------------------------+------------------------------------------+  
| Булеан (Множество подмножеств) P(S)| Декартов квадрат S x S (Кортежи)         |  
+------------------------------------+------------------------------------------+  
| P(S) = {                           | S^2 = {                                  |  
|   {},                              |   (1, 1), (1, 2), (1, 3),                |  
|   {1}, {2}, {3},                   |   (2, 1), (2, 2), (2, 3),                |  
|   {1, 2}, {1, 3}, {2, 3},          |   (3, 1), (3, 2), (3, 3)                 |  
|   {1, 2, 3}                        | }                                        |  
| }                                  |                                          |  
+------------------------------------+------------------------------------------+  
| Элементы: Подмножества (без по-    | Элементы: Кортежи длины 2 (строгий       |  
| рядка). {1, 2} и {2, 1} — это      | порядок). Кортеж (1, 2) не равен         |  
| один и тот же элемент булеана.     | кортежу (2, 1). Повторения разрешены.    |  
+------------------------------------+------------------------------------------+

Объяснить с

Булеаны нужны: при контроле доступа для определения всех возможных комбинаций битовых масок прав/привилегий субъектов; в лексерах (алгоритм Томпсона NFA -> DFA); в компиляторах для расчета множеств «живых» переменных Live Variables для распределения их по регистрам процессора.

***

6. ОТНОШЕНИЕ

____________________██████  
_________▓▓▓▓____█████████  
__ Ƹ̵̡Ӝ̵̨̄Ʒ▓▓▓▓▓=▓____▓=▓▓▓▓▓  
__ ▓▓▓_▓▓▓▓░●____●░░▓▓▓▓  
_▓▓▓▓_▓▓▓▓▓░░__░░░░▓▓▓▓  
_ ▓▓▓▓_▓▓▓▓░░♥__♥░░░▓▓▓  
__ ▓▓▓___▓▓░░_____░░░▓▓  
▓▓▓▓▓____▓░░_____░░▓  
_ ▓▓____ ▒▓▒▓▒___ ████  
_______ ▒▓▒▓▒▓▒_ ██████  
_______▒▓▒▓▒▓▒ ████████  
_____ ▒▓▒▓▒▓▒_██████ ███  
_ ___▒▓▒▓▒▓▒__██████ _███  
_▓▓X▓▓▓▓▓▓▓__██████_ ███  
▓▓_██████▓▓__██████_ ███  
▓_███████▓▓__██████_ ███  
_████████▓▓__██████ _███  
_████████▓▓__▓▓▓▓▓▓_▒▒  
_████████▓▓__▓▓▓▓▓▓  
_████████▓▓__▓▓▓▓▓▓  
__████████▓___▓▓▓▓▓▓  
_______▒▒▒▒▒____▓▓▓▓▓▓  
_______▒▒▒▒▒ _____▓▓▓▓▓  
_______▒▒▒▒▒_____ ▓▓▓▓▓  
_______▒▒▒▒▒ _____▓▓▓▓▓  
________▒▒▒▒______▓▓▓▓▓  
________█████____█████

Объяснить с

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

***

7. ОПРЕДЕЛЕНИЕ ФУНКЦИИ ОТНОШЕНИЕМ

Определим функцию F тройкой F = <D,W,S>, где D, W – множества (или области) определения и значений функции, а S отношение над их элементами.

***

ПРИМЕР

Биекция над графиком (геометрическая кривая) и подмножеством D×W, через сетку декартовых координат. Последние связывают геометрические объекты (перпендикулярные прямые) с метками числел.

***

8. ВЫЧИСЛИМОСТЬ ФУНКЦИИ

«Вычислить» – значит поставить в соответствие произвольной символьной записи (или формуле на листе бумаги) число.
Выше мы поставили в соответствие символьной записи функции таблицу S. Теперь можно заменить первичные функции математики соответствующими им таблицами чисел, и двигаясь по цепочке «композиции» функций f•g•h... сводить любые формулы механической подстановкой к числам.
Теперь «вычисление» любой математический функции сводится к операциям формальной подстановки цифр (или символов) из таблиц. Функции, для которых можно создать такие таблицы, называют «вычислимыми».
Ниже мы посмотрим, как это прямо соответствует лямбда-исчислению Чёрча. Любая числовая функция в записи Чёрча – это в прямом смысле число, записанное не в десятичной, а иной системе исчисления.
Философский аспект: математика «статична», в ней нет понятия «движение». Отобразим элементарное движение парой (объект до движения -> объект после движения). Это соответствует определению «отношение» и «функция». Отношение не исключает из математики понятие физики «движение». Но оно сводит всё многообразие «движений» физики к минимуму: «взять значение на пересечении строки и столбца таблицы». Более мы не «вычисляем» функции, а берём «ответ» из таблиц.

9. КОМПОЗИЦИЯ ФУНКЦИЙ В АЛГОРИТМАХ И СХЕМОТЕХНИКЕ

Для математика «функция» это отображение, для инженера – «черный ящик» со «входом» и «выходом». Многоместная функция эквивалентна одноместной, получившей вектор тех же значений f(x,y,z) = f([x,y,z]).
«Композиция» – функция, составленная механической «подстановкой» одних функций аргументами других.

1. Композиция в алгоритмах

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

Синтаксис Lisp прямо соответствует композиции функций.

***

Синтаксис языка C прямо соответствует записи алгебраических формул математики.

ПРИМЕР

***

Язык Lisp

***

2. Композиция в схемотехнике

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

МАТЕМАТИЧЕСКАЯ ЗАПИСЬ ФУНКЦИИ  
  
f5(x,y,z) = f4(f1(x),f2(y),f3(z))  
  
ВЗАИМНО ОДНОЗНАЧНАЯ ИНЖЕНЕРНАЯ СХЕМА  
  
   ОДНОМЕСТНЫЕ ФУНКЦИИ f1, f2, f3  
             |  
      Вход   |    Выход  
       |     V     |  
       V  +----+   V  
[ x ] --->| f1 |------+  
          +----+      |  
                      |       +-----------+         
                      +------>| u = f1(x) |       +----+  
          +----+              +-----------+       |    |  
[ y ] --->| f2 |------------->| v = f2(y) |------>| f4 |----> [ Выход ]  
          +----+              +-----------+       |    |  
                      +------>| w = f3(z) |       +----+  
                      |       +-----------+         
          +----+      |               
[ z ] --->| f3 |------+         ^                   ^   
          +----+                |                   |   
                             ВЕКТОР             ТРЁХМЕСТНАЯ  
                     (с компонентами u,v,w)      ФУНКЦИЯ

Объяснить с

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

РАЗДЕЛ: ГРАФЫ

1. ГРАФЫ

         *  
     *  *r*  *  
  * *a* ^Y^ *i* *  
 *m*^Y^*^\^*^Y^*s*  
 ^Y^*\*e*/*l*/*^Y^  
 *\*t*|Y^\^Y|*l*/*  
*s*|Y^\\^/^//^Y|*a*  
^Y^\\_^\\\//^_//^Y^  
^\_^\_\_\//_/_/^_/^  
 ^^\_^\_\\/_/^_/^^  
   ^^\_ \// _/^^  
       \_\_/  
        /|\  
       /\\/\

Объяснить с

1. Определение

«Граф» D – объект математики из двух множеств: вершин V и пар вершин, называемых рёбрами E, D = <V, E>. Из определения следует: декартово произведение вершин VxV соответствует всем теоретически возможным рёбрам графа, всякое E – их подмножество.

***

Для инженера граф – это схема распределения движения в «системе» (объекте отображённом графом). Рёбра графа соответствуют физическим каналам проводящим движение (например, проводам, балкам).
Связанные узлы называют «целым»: попав в один узел, движение попадает во все с ним связанные. За границами «целого» (или графа), движение прекращается.
Вершины и рёбра перенумеровывают – ставят им в соответствие уникальные числа или «идентификаторы», и работают с ними.
Граф, узлам и/или рёбрам которого поставлены в соответствие буквы или цифры, называют помеченным или маркированным.
Далее мы работаем только ациклическими, связными графами или «деревьями», где между любыми двумя вершинами лишь один простой путь.

2. Представление

Нам интересны 3 эквивалентные формы задания графа.
2.1 Геометрия: точки (вершины) и линия (рёбра). Для быстрой визуальной оценки логики системы.

       [ 1 ]  <-- v1  
        / \  
      e1   e2 <-- Связи E  
      /     \  
    [ 2 ]   [ 3 ] <-- v2, v3

Объяснить с

2.2 «Список рёбер»: алгебраическое отношение (таблица с двумя колонками) или множество упорядоченных пар D = {(v1, v2), (v2, v3), ...}. Для компактного хранения графа в ЭВМ.
2.3 Матрица или таблица «смежности». Для анализа свойств графа.
Кладём заголовком строк и столбцов таблицы вершины V. В ячейки на пересечении строки и столбца ставим 1 (связь между узлами есть) или 0 (связи нет).

           v1  v2  v3  
         +-----------  
    v1   | 0   1   1  <-- вершина v1 имеет ребро в v2 и v3  
    v2   | 1   0   0  <-- вершина v2 имеет ребро в v1  
    v3   | 1   0   0  <-- вершина v3 имеет ребро в v1  
  
Матрица симметрична, на диагонали – нули.

Объяснить с

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

3. Ориентированные графы, деревья

Слово «ребро» без уточнений закреплено за ненаправленной связью. Рёбра ориентированных графов (орграфов) называют «дуги» или «направленные ребра», их изображают «стрелками».
Словом «дерево» обозначают два разных объекта. В дискретной математике это неориентированный граф, в коде и компиляторах (AST) – ориентированный.

***

4. Связность графа

Построим «полный неориентированный граф»: возьмём матрицу VxV вершин, заполним все ячейки единицами, затем расставим нули на главной диагонали. В физике «полным графом» задают расстояние либо жёсткость между частями или «точками» абсолютно твёрдого тела (камня, металла). Каждый узел связан с другими формой «один-ко-всем», а все узлы связаны «каждый-с-каждым». Общее количество рёбер (|VxV|-|V|)/2.

***

Для инженера связность системы (будь то мост, электросеть или база данных) – гарантия, что носитель либо сигнал дойдет из точки А в точку Б. Связная система едина. Если «дернуть» за узел v1, движение дойдет до v2 и v3.
Для систем с односторонними связями (в одну сторону перегородка проницаема, в другую – нет) берут орграф либо два неориентированных графа.

***

5. Моделирование на графах. Матрица весов

«Топологией» называют геометрию, в которой не учитывают расстояния, углы, площади и форму объекта. В ней изъяты линейка и угломер (измерения запрещены), а объект можно гнуть, растягивать, сжимать, но не рвать или склеивать. Координаты в пространстве игнорируют – сохраняют только непрерывность, количество выбранных точек и связи (соединения между точками). Такими свойствами обладает граф.
Итак, ставим в соответствие объектам реального мира их топологические образы (геометрия), им – графы (дискретная математика), наполняем граф метрикой для вычислений (получаем метрический или нагруженный граф), проводим вычисления – и совершаем обратный переход.
Технически: начертить геометрическую карту, выбрать объекты, которым ставим в соответствие вершины, выбрать пути распространения движения (будут рёбрами). Поставить в соответствие рёбрам конкретные физические величины (длину кабеля, сечение трубы, сопротивление, стоимость). Посчитать результат (затраты энергии, пропускную способность, стоимость прокладки дорог или кабеля, итд).
В 1847 г. немецкий физик Густав Кирхгоф изучал электрические цепи. Он представлял провода линиями, а места их спайки точками. Каждому «ребру» в такой схеме соответствует число – сопротивление или проводимость, показывая насколько «тяжело» току течь по проводу.
В 1930-40 гг. математики начали рассчитать стоимость перевозок грузов между городами. Линиям дорог присваивали стоимость перевозки (в деньгах) или расход топлива (в тоннах). В экономике и логистике эти затраты называли «нагрузкой» или «тяжестью» маршрута.
В 1950 гг. Эдсгер Дейкстра публикует алгоритм поиска кратчайшего пути на графе, обобщив понятия «длина» (length), «стоимость» (cost), «нагрузка» (load) термином «weight» (вес).

6. Моделирование на графах. Нейросети и численное моделирование

1940-50-е гг. Концепция искусственных нейронных сетей (перцептронов). Мак-Каллок, Питтс (1943 г.), Розенблатт (1957 г., проект «Марк-1» на ЭВМ Почтового ведомства США). Мозг представлен графом, где вершины – это вычислительные ячейки (нейроны), а рёбра – каналы передачи данных (синапсы). Машина обходит граф, умножая значение из вершины-источника на числовой «вес» ребра, и суммирует все пришедшие сигналы в вершине-получателе («взвешенная сумма»). «Обучение» – алгоритм подбора весов рёбер.
1950-60-е гг. Численное моделирование сплошных сред. Непрерывному пространству ставят в соответствие дискретный граф (кубическую или произвольную трехмерную сетку). Точкам среды соответствуют вершины, наделяемые скалярной величиной (температурой или потенциалом), а рёбрам – каналы взаимодействия между точками. Шаг сетки по осям (или длина ребра) задан геометрией объекта. Для вычисления градиентов физических полей (тепла, давления, диффузии газов) машина берет вершину, вычитает её значение из смежных по рёбрам («соседних») вершин и делит полученную конечную разность на геометрический шаг ребра. Получается пространственный вектор, указывающий направление максимального изменения (роста) поля в точке.

ПРИМЕР

**
2. СООТВЕТСТВИЕ «ГРАФ (МАТЕМАТИКА) – ЯЗЫКИ (ИНЕЖЕНЕРИЯ)»

В C сершине с двумя рёбрами соответствует ()-if-else, с несколькими – switch-case. switch-case так же реализует «совпадение по образцу» или pattern matching.
Стандарт: явно задаём графы, максимум switch-case в программе.

                                           СООТВЕТСТВИЕ  
                           ИНЖЕНЕРИЯ                         МАТЕМАТИКА  
  
          КАСКАД CASE                   КАСКАД IF                 ГРАФ  
                              |                            |  
switch           // вершина   |                            |  
{                             |                            |  
    case:        // ребро     |   if ()                    |      [()] <- вершина  
        break;                |   { }          // вершина  | [{}] /  \  <- else-if  
    case:        // ребро     |   else if ()               |          [()]  
        break;                |   { }          // вершина  |     [{}] /  \  
    case:        // ребро     |   else if ()               |              [()]  
        break;                |   { }          // вершина  |         [{}] /  \  
    default:     // ребро     |   else                     |          ^       \  
        break;                |   { }          // вершина  |      вершина ->  [{}]  
  
Примечание: () – знак предиката (вершина), if и else – знаки рёбер, ведущих в две вершины. Ребро `else if` вновь идёт в предикат -> ().

Объяснить с

3. ГРАФ НА ЯЗЫКЕ HALFTONE

Код генерации наглядного представления графов займёт несколько строк на С или JS. Идея: обойти граф, сохранить список вершин и рёбер на микро-языке Halftone, и визуализировать в https://arborjs.org/halfviz/ (справка в [1]).
Синтаксис: имя узла 1 -> имя узла 2 { стили }; комментарий. В имени разрешены пробелы и цифры, в стилях – цвет. Пример: имя узла 1 -> имя узла 2.

**
4. ОБХОДЫ ОГРАФА «ДЕРЕВО»

Вершины графа можно перечислять произвольно. «Обходом» графа называют движение по ребрам, с «посещением» каждой вершины один раз.
Алгоритмов обхода ографа в несколько строк кода BFS, DFS (PreOrder, InOrder, PostOrder) достаточно для большинства задач.

***

Порядок обхода DFS Post-order traversal выглядит диковинно, но он прост (3 строки кода) и гарантирует «посещение» «высшей» вершины ветки после «низших». Этого достаточно для построения интерпретатора, выполняющего все математические и вложенные функции, либо компилятора, транслирующего AST в ассемблерный код. Для парсера в AST достаточно DFS Pre-order.
BFS Breadth-First Search (обход в ширину) незаменим для геометрии, поиска расстояний и кратчайших путей. Обходит граф как «круги по воде».
DFS InOrder (центрированный обход) только для бинарных деревьев. Примеры: в СУБД для сортировки по возрастанию Binary Search Trees (левый ребенок всегда меньше родителя, правый – больше); конвертация дерева из постфиксной (машинной) записи 1 2 + 3 4 / * в инфиксную ((1 + 2) * (3 / 4)).

Порядки обхода графов

BFS = [a,b,c,d,e,f,g]
BFS (Breadth-First Search) или Обход в ширину: Двигаться по «уровням». Посетить все узлы на глубине H, затем перейти на глубину H+1

DFS PreOrder = [a,b,d,e,c,f,g]
DFS PreOrder: Двигаться вглубь по ветке до «дна» по левому поддереву, затем возврат и обработка правых веток. В частных случаях BFS и DFS дают тот же порядок посещений.

DFS InOrder = [d,b,e,a,f,c,g]
DFS InOrder (симметричный обход): Левое поддерево -> Корень -> Правое поддерево.

DFS PostOrder = [d,e,b,f,g,c,a]
DFS PostOrder (обратный обход): Левое поддерево -> Правое поддерево -> Корень

Проектирование графов и обходчиков

Функция walk(root, options, CTX_user) обходит граф, и вызывает функцию обратного вызова iteratee(node, CTX_walk, CTX_user) при «визите» узла. Обходы специфичны, и аргументы iteratee не универсальны.
CTX_user это ваш контейнер, передаваемый без изменения из walk в iteratee. Содержит состояние, обрабатываемое с обходом графа. В интерпретаторе это таблица символов (хранилище переменных), в компиляторе – буфер для ассемблерного кода.
Проектируйте граф грамотно. Если в iteratee нужен доступ к «родителям», в узле должен быть соответствующий указатель. В «дереве» у узла один предок (parent указатель), в графах типа «сеть» – несколько (parents массив).
Параметры options задают состав контекста CTX_walk формируемого алгоритмом (например «уровень вложенности» в BFS).

Обходы графа на С

***

РАЗДЕЛ: КОМБИНАТОРНАЯ МАТЕМАТИКА

__●__ ●  
 _ █___█  
 __ █__ █_  
 __ █__ █  
 __ ███____________█████ 　　　  
 _█▒░░█_________██▓▒▒▓██ ☆  
 █▒░●░░█___ ██▓▒██▓▒▒▓█　　 ★  
 █░█▒░░██_ ██▓▒██▓▒░▒▓█  
 _██▒░░██ ██▓▒░██▓▒░▒▓█ 　　　★  
 ____█▒░██ ██▓▒░░ ████▓█  
 ___█▒░██__██▓▓▒▒░░░██ 　 ★★  
 ____█▒░██___████████████  
 _____█▒░█▒▒▒▒▒▒▒▒▒▒▒▒█  
 ______██████████████████.•°*”˜҈.•°*”˜҈.

Объяснить с

1. РЕЛЯЦИОННАЯ АЛГЕБРА. SQL ЗА 15 МИНУТ

История SQL

В 1960 гг. СУБД строились на графово-списковых моделях (в IBM IMS – тип графа «дерево», в CODASYL – тип «сеть»). Для извлечения данных писали процедурный код («навигатор»), перемещающий указатель по узлам графа и цикл вычитывающий списки (записи), из этих узлов.
В 1970 г. Эдгар Кодд в IBM формально описал логику комбинаторики, введя понятия «кортеж» (упорядоченное конечное множество), «реляционное отношение» (конечный набор кортежей). В 1974 IBM разработала синтаксис SEQUEL (в будущем – SQL) для реализации на ЭВМ названной «реляционной алгебры».
В 1977 г. ушлый программист Ларри Эллисон прочел открытые статьи IBM, бросил учебу в Йельском университете, и, имея на руках 1200 долларов создал на троих с Оутсом и Майнером фирму. До этого троица делала для ЦРУ проект под названием… Oracle. ЦРУ стало их первым клиентом и разрешило использовать это название для продукта [6]. В 1979 г. фирма Relational Software, Inc. (в будущем – Oracle) раньше IBM захватит рынок коммерческих СУБД на SEQUEL. При этом Эллисон проявит «маркетинговую смекалку»: вышла сразу вторая версия Oracle 2. Это «как бы давало заказчику понять», что система надежна и прошла проверку временем [7].
Встречаются бесплодные дискуссии и софистика «является ли SQL алгеброй». Они не имеют прикладного значения. Таблицы записей лежат изолировано, а связи вычисляются динамически – через декартово произведение строк и фильтрацию по предикатам запроса.

SQL

Математик учит SQL со скоростью чтения технической документации. Инженер освоит ядро языка до уверенного практического применения за 10-20 часов. Цель: привыкнуть к «декларативному» подходу – думать в операциях математики множеств, а не в терминах итерационных циклов.
Таблицы называют «реляционное отношение» Relation, их строки – «кортежи» Tuple, а столбцы – «атрибуты» Attribute , «домен» Domain – диапазон допустимых значений в ячейках столбца.
Противопоказано учить SQL по стандартным учебникам перегруженным «водой». Отсекаем шум ключевых слов старше стандарта SQL-89 (содержит базовые операции Кодда) и видим запросы как математику по этому алгоритму.
Ядро SQL-вычисления это три последовательно выполненные операции:

БИЕКЦИЯ. ЗАПИСЬ В СИНТАКСИСЕ SQL – МАТЕМАТИЧЕСКОЕ СООТВЕТСТВИЕ  
+---+--------+-------------------------------------------------------------------+  
| # | Блок   | Математика                                                        |  
+---+--------+-------------------------------------------------------------------+  
| 1 | FROM   | Декартово произведение множеств кортежей («строк») из таблиц:     |  
|   |        | `R_1 x R_2 x ... x R_n`                                           |  
+---+--------+-------------------------------------------------------------------+  
| 2 | WHERE  | Исключить из результата кортежи (или «фильтрация», предикат №1).  |  
|   |        | Комбинация предикатов кортежей `=, !=, >, <` и логики `AND,OR,NOT`|  
+---+--------+-------------------------------------------------------------------+  
| 3 | SELECT | Исключить из результата «столбцы» (или «проекция», предикат №2).  |  
|   |        | Прямо перечислить сохраняемые атрибуты `a,b,c,d`.                 |  
+---+--------+-------------------------------------------------------------------+

Объяснить с

***

Ядра SELECT-FROM-WHERE достаточно для всех вычислений SQL, но код с UNION, INTERSECT, EXCEPT, DISTINCT, IN, NOT IN, EXISTS, NOT EXISTS математически выразительней и короче.

***

SQL логику реализуют в несколько строк на JavaScript

+--------+--------------+------------------------------------------+  
| SQL    | Математика   | JavaScript / Underscore.js               |  
+--------+--------------+------------------------------------------+  
| FROM   | Дек. произв. | `cartesianProduct(tableA, tableB, ...)`  |  
|        | A x B x C    |                                          |  
+--------+--------------+------------------------------------------+  
| WHERE  | Подмножество | `_.filter(relation, function(row) {...})`|  
|        | (кортежи)    | Выделить подмножества по предикату.      |  
+--------+--------------+------------------------------------------+  
| SELECT | Проекция     | `_.map(relation, function(row) {...})`   |  
|        | (атрибуты)   | Выделить по предикату в `_.pick`.         |  
+--------+--------------+------------------------------------------+

Объяснить с

ПРИМЕР 1. SELECT-FROM-WHERE

SQL

***

JAVASCRIPT

***

ПРИМЕР 2. SELECT-UNION-SELECT

SQL

***

JAVASCRIPT

***

ПРИМЕР 3. SELECT-WHERE-IN

SELECT-WHERE-IN исключает из таблицы кортежи (строки), значение атрибута (столбца) которых не лежит в множестве, перечисленном в IN(...)

SQL

***

JAVASCRIPT

***

2. КОМБИНАТОРИКА НА SQL ЗА 15 МИНУТ

░░░░░░░░░░░░░░░▄▄▄▄▄▄▄▄░░░░░░░░░░░░░░  
░▄█▀███▄▄████████████████████▄▄███▀█░  
░█░░▀████████████████████████████░░█░  
░░█▄░░▀████████████████████████░░░▄▀░  
░░░▀█▄▄████▀▀▀░░░░██░░░▀▀▀█████▄▄█▀░░  
░░░▄███▀▀░░░░░░░░░██░░░░░░░░░▀███▄░░░  
░░▄██▀░░░░░▄▄▄██▄▄██░▄██▄▄▄░░░░░▀██▄░  
▄██▀░░░▄▄▄███▄██████████▄███▄▄▄░░░▀█▄  
▀██▄▄██████████▀░███▀▀▀█████████▄▄▄█▀  
░░▀██████████▀░░░███░░░▀███████████▀░  
░░░░▀▀▀██████░░░█████▄░░▀██████▀▀░░░░  
░░░░░░░░░▀▀▀▀▄░░█████▀░▄█▀▀▀░░░░░░░░░  
░░░░░░░░░░░░░░▀▀▄▄▄▄▄▀▀░░░░░░░░░░░░░░

Объяснить с

Комбинаторикой называют методы точного просчёта свойств систем дискретных элементов в математических пространствах пятью базовыми операциями теории множеств. Инженерный эквивалент: распределение объектов по ячейкам. Прямо реализовано в SQL.
Противопоказано учить предмет по стандартным учебникам. Они скрывают суть за арифметикой. Учить в базовых операциях над множествами, через SQL, на интуитивно понятных примерах (расставить парты и рассадить людей в комнате, разместить коробки на складе, итд).
Базовые операции над множествами учат за день. В них SQL любой сложности пишется за несколько минут. («Inside DBMS development, text SQL doesn’t exist. Everything is a Relational Algebra tree»).
Корень формул комбинаторики: декартово произведение множеств, на которое последовательно накладывают фильтры.
Суть тривиальных комбинаторных задач сведена к одной формуле: (N x N x ... x N) \ B, где N x N x ... x N взятое |M| раз декартово произведение даёт все теоретически возможные варианты «размещения» конечного множества элементов N в множестве различимых (пронумерованных) «ячеек» M, а B – подмножество N x N x ... x N, удаляемое по условиям задачи.
По другому: суть задач дать все варианты размещения некоторого количества элементов N={n0, n1, n2, ...} в компонентах алгебраических векторов вида M = (m0, m1, m2, ...). Инженерный эквивалент: дать варианты размещения деталей по ячейкам коробки. Варьируют состав, количество деталей и правила размещения их в ячейках: например, допустимы ли аналогичные детали (или «повторы») в ячейках или нет? Количество ячеек фиксировано, их порядок задан нумерацией.
Далее под N понимаем конкретный набор объектов, например, корзинку с известным количеством фруктов, а под «базовым множеством» N1=support(N) «склад» с «бесконечным множеством» фруктов каждого типа, итого |N1|<=|N|.
Эта эквилибристика слов делает текст математически непротиворечивым: в декартово произведение всегда подставляют N1, но результат может не соответствовать условиям реального мира.
Устраним логические противоречия между математикой и объектами реального мира. Пусть N = {яблоко, банан} и ячейки M = (m0, m1, m2). Отображаем N->support(N)=N1={яблоко, банан} и строим пространство состояний S = N1 x N1 x N1. Там будут тройки R = (яблоко, яблоко, яблоко), что некорректно: в физической корзинке одно яблоко и один банан. Случаи, где яблок или бананов больше 1 отсечём в B.
Теперь N = {яблоко, яблоко, банан} и M = (m0, m1, m2). Объекты с «повторными» элементами (яблоко, яблоко в нашем случае), называют «мультимножества». От них избавляются двумя эквивалентными путями.
Путь 1 (наивный). Отобразим «мультимножество» (встречаются кратные элементы) в «базовое множество» (все элементы уникальны) N->support(N)=N1={яблоко, банан} (для сравнения, мощности: |N|=3, |N1|=2). Берём S = N1 x N1 x N1, и отсекаем в B случаи, где количество любого фрукта больше его физического запаса в корзинке (яблок больше 2 или бананов больше 1).
Путь 2 (промышленный). Перенумеруем каждый фрукт в корзинке уникальным числом N->N2 ={0,1,2}. Строим «базовое множество» N->support(N)=N1={яблоко, банан} (для сравнения: |N|=3, |N1|=2, |N2|=3). Берём S = N2 x N2 x N2, и исключаем дубликаты физических объектов отсечением всех троек с повторами чисел. В оставшихся тройках заменяем числа на названия фруктов (то есть отображаем N2->N1) и получаем все физически возможные раскладки фруктов по ячейкам.
Путь 2 демонстрирует: в комбинаторике мы всегда работаем со счётными множествами. Из-за |M|=const и |N2|=const количество размещений известно, и не выйдет за рамки N1 x N1 ... взятого |M| раз.
В учёбе наглядны явные пары «ячейка – предмет» {(место1, предмет а), (место2, предмет b), ...}. Можно взять R = M x N, построить R x R x ... |M| раз а в B отсечь случаи по условию: в наборе пар нет одинаковых ячеек (в правильном наборе ячейка коробки встречается один раз), и количество фруктов не превышает их реальный запас.
Поэтому довольствуемся многоместным декартовым произведением N1 x N1 ..., помня, что каждой позиции (или «атрибуту») в его кортежах соответствует элемент из множества M.
«Базовые» случаи комбинаторики (перестановки, размещения, сочетания) различаются только правилами отсечения вариантов B из N x N ....

***

ПРИМЕРЫ

Размещения с повторением

Размещения с повторением: это декартово произведение множеств.
На двери 3-х разрядный кодовый замок, нажатием кнопки в его разрядах R = { r0, r1, r2 } устанавливают цифру из множества N = {0,1,2,3,4,5,6,7,8,9}. Сколько комбинаций C в кодовом замке?
Решение: имеем набор ячеек R, в каждую можно поочерёдно «поместить» N чисел.

***

Сколько коробок K можно промаркировать 4-х значным кодом из букв N = {A, B, С}? Итого позиций для маркировки R = { p1, p2, p3, p4 }, и решение как в предыдущей задаче.

Размещения без повторений

Размещения без повторений для кодового замка – это все возможные варианты кода, в которых все цифры разные. Код 5-6-7 – подходит (все цифры уникальные), коды 5-6-5 и 7-7-7 – нет. Имеем C = | R1 x R2 x R3 \ B |, где B – множество комбинаций для исключения. Его громоздко строить базовыми операциям над множествами, но просто средствами реляционной алгебры (то есть SQL).

***

Перестановки без повторений

Найдём все возможные комбинации размещения элементов конечного множества N в конечном множестве ячеек M.
Перестановки без повторений это частный случай размещений без повторений: в них |N| = |M|.
Типичная задача: рассадить N человек на M стульях. Пусть M = N = 3, итого M = { m0, m1, m2 } N = {0,1,2}

***

Сочетания с повторением

Купить 3 пирожных в магазине, где их 4 вида.

***

3. ТЕОРИЯ ВЕРОЯТНОСТЕЙ НА SQL ЗА 15 МИНУТ

Название «теория вероятностей» – обманчиво. Это модели на жёсткой комбинаторике полных множеств и численная оценка их свойств. Предмет приложения теории вероятностей – пространство состояния предметов.
Классическая теория построена на 5 базовых операциях теории множеств. Противопоказано учить эту дисциплину по стандартным учебникам, скрывающим их за алгебраическими формулами. Теорию вероятностей учить в операциях теории множеств, задачи решать через SQL.
Вероятность P=|A|/|D| это отношение мощностей двух конечных множеств, где множество A строго подмножество D. Для инженера это пропорция нужных состояний A в пространстве состояний D. Частный случай: доля нужных комбинаций (или «вариантов») среди всех возможных.

ПРИМЕР

Имеем 2 кубика с пронумерованными гранями K1 = {1,2,3,4,5,6}, K2 = {1,2,3,4,5,6}. Все возможные пары при одном броске двух кубиков или «пространство конфигураций»: D = K1 x K2.
В какой пропорции при броске на кубиках будут цифры больше 3? Нужные нам состояния или цифры первого кубика A1 = {4,5,6}, второго A2 = {4,5,6}, итого A = A1 x A2. Итого P=|A|/|D| = |A1 x A2|/| K1 x K2 | = (3*3)/(6*6) = 1/4.

***

В какой пропорции при броске выпадает пара {5,6}? Нужные нам состояния или цифры первого кубика A1 = {5,6}, второго A2 = {5,6}. Итого из A = A1 x A2 исключаем B = { {5,5}, {6,6} } (если отобразить A матрицей, элементы B будут на её диагонали). Итого P=|A|/|D| = |(A1 x A2) \ B|/| K1 x K2 | = (2*2-2)/(6*6) = 1/18.

***

В какой вероятностной пропорции при броске трёх кубиков выпадут цифры больше 3? Это аналог первой задачи, достаточно, добавить аналогичные K3 и A3 в формулу:

P = |A| / |D| = |A1 x A2 x A3| / |K1 x K2 x K3| = (3*3*3)/(6*6*6) = 1/8.

Объяснить с

РАЗДЕЛ: JAVASCRIPT

_'▀█║────────────▄▄────────────▄──▄_  
──█║───────▄─▄─█▄▄█║──────▄▄──█║─█║  
──█║───▄▄──█║█║█║─▄║▄──▄║█║─█║█║▄█║  
──█║──█║─█║█║█║─▀▀──█║─█║█║─█║─▀─▀  
──█║▄║█║─█║─▀───────█║▄█║─▀▀  
──▀▀▀──▀▀────────────▀─█║  
───────▄▄─▄▄▀▀▄▀▀▄──▀▄▄▀  
──────███████───▄▀  
──────▀█████▀▀▄▀  
────────▀█▀

Объяснить с

1. ИСТОРИЧЕСКАЯ СПРАВКА

История Netscape Navigator

Все началось в Национальном центре суперкомпьютерных приложений NCSA при Иллинойсском университете. Молодой студент Марк Андриссен и штатный программист Эрик Бина в 1992-93 гг. создали NCSA Mosaic – первый браузер с графическим интерфейсом. В 1994 г. Андриссен закончил университет и познакомился в Калифорнии с Джимом Кларком, основателем Silicon Graphics. Они основывают компанию Mosaic Communications Corporation. Кларк вложил деньги, а Андриссен переманил из университета команду разработчиков Mosaic.
Netscape Navigator вышел в 1994 г., и к 1995 г. занял 80% рынка браузеров. Интернет ассоциировался исключительно с этой компанией. Она вышла на биржу без чистой прибыли, что было нонсенсом для того времени, и в 1995 г. провела легендарное IPO. Акции сразу взлетели с $28 до $75, компанию оценили в $3 миллиарда, а 24-летний Андриссен появился на обложке журнала Time босиком на золотом троне. Это событие запустило «Бум доткомов».
Microsoft поняла, что упускает интернет, и начала первую браузерную войну. В 1997 г. она стала бесплатно встраивать Internet Explorer 4.0 в каждую копию Windows и запретила производителям ПК его удалять.
Это практически уничтожило Netscape. К тому же код её браузера раздулся и был полон ошибок. Как писал в дневнике ненавидевший бюрократию и маркетологов Джейми Завински, сотрудник в Netscape под номером 20, хакер и бунтарь с фиолетовыми волосами: «Менеджмент сошел с ума. Мы начали выпускать откровенный мусор и выпускать его с опозданием». Инженеры понимали, что компания идет на дно.
Завински стал главным рупором безумной по меркам 1997 г. идеи: сделать браузер бесплатным и открыть его исходный код. Термина «Open Source» тогда не существовало (его формулируют в 1998 г. как раз на фоне этих событий). Завински вел подпольную агитацию среди инженеров, собирал единомышленников, и давил на руководство Netscape. Крупный бизнес считал бесплатную раздачу кода коммерческим самоубийством, но руководство Netscape, искавшее выход из финансового тупика, решилось на этот шаг.
Для подготовки открытого кода Эйх и Завински основали организацию mozilla.org. Команда Mozilla несколько месяцев работала и жила в офисе Netscape в условиях «аквариума» (inside a fishbowl) из-за стеклянных стен и постоянного публичного внимания. Исходный код опубликовали в 1998 г., и это вызвало шок в индустрии.
Вскоре корпорация AOL поглощает Netscape. Код браузера так плох, что его переписывают с нуля. Но Netscape 6.0 вышел настолько нестабильным, что окончательно похоронил доверие пользователей. К 2002 г. Internet Explorer занимает 96% рынка.
Из-за потери веры в проект и в знак протеста против корпораций и бюрократии увольняется Завински. Он рвёт с компьютерной индустрией, сообщает «я ушёл в более честный бизнес – продавать пиво», и открывает ночной панк-рок клуб DNA Lounge. А Эйх упорно тащит проект Mozilla сквозь годы скепсиса индустрии. В 2004 г. появляется браузер Mozilla Firefox, нанесший Internet Explorer сокрушительный удар и спасший интернет от монополии.

Генезис JavaScript

JavaScript или JS от Brendan Eich сделан по науке, прямо соответствует объектам дискретной математики, и это причина его успеха.
Эйх – классический хакер 1960-70-х с большим опытом разработки компиляторов, операционных систем, ядра Unix в Silicon Graphics, цифровых сигнальных процессоров и ядер в MicroUnity. «Частично художник, частично хакер, и штатный программист», писала о нём Нью-Йорк Таймс.
В мае 1995 г. Netscape нанимает Эйха добавить в браузер язык Scheme (диалект Lisp). В те же дни Sun Microsystems представляет Java как «язык для Internet» и раздувает истерию в прессе. Руководство Netscape тут же требует сделать язык «похожим на Java», и Эйх совершает инженерный маневр. За легендарные 10 дней он упаковал ядро Scheme и идеи объектов языка Self (динамические прототипы) в С-подобный синтаксис.
Под оболочкой JavaScript оказывается гибкий функциональный язык, опередивший время на десятилетия. Мейнстримные языки (включая С++) заимствуют у него замыкания и функции высшего порядка только в 2010 гг.
В 2015 г. JS ещё больше математизовали, добавив в prototype удачную микро-библиотеку дискретных множеств underscore.js от Jeremy Ashkenas.
История с же с Java-апплетами закончилась плачевно. То, что в презентациях называлось «революцией интерактивного веба», стало кошмаром для пользователей и программистов. Слоган «Write Once, Run Anywhere» иронично перекрестили в «Write Once, Debug Everywhere» (Напиши один раз, отлаживай везде). Апплет, кое-как работавший в браузере HotJava от Sun, намертво вешал Netscape Navigator в Windows и не запускался на Macintosh. Пользователи постоянно качали ломающие сайты обновления виртуальной машины JVM. Из-за колоссального количества дыр в безопасности, ведущие браузеры заблокировали Java. В 2016 г. Oracle объявила технологию апплетов устаревшей, и она удалена в браузерах.

2. КЛЮЧЕВЫЕ ИДЕИ

JavaScript это ключевые слова и синтаксис С без типов, плюс возможности Scheme и Self. Эту идею мы повторим в доменных языках.
Кодируя, берут удачное подмножество языка и исключают неудачное deprecated.

«Функция это действие f применённое к алгебраическому вектору (x,y,z)», формульная запись f(x,y,z).

***

Переменные без типов. Хранят число, строку, функцию, массив [], map {}, regex, bool, null. Оператор == неявно приводит тип и сравнивает значения, === строго проверяет типы и значения переменных.

***

Оператор typeof возвращает тип переменной.

***

Не способным отследить даже соответствие типов, не следует писать код.

Функции синтаксически равноправны с другими типами данных (числами, строками). Их можно хранить в переменных (1), передавать аргументами в другие функции (2), возвращать как результат вычислений (3).

***

Expression (Выражение) это вычислимая и присваиваемая величина, цель Expression вычислиться в значение, Statement (Инструкция) – это действие. Expression всегда можно присвоить переменной, Statement – никогда. Они дают разные деревья в BNF. Expression задают каскадной структурой правил в BNF, они могут вкладываться в другие, включать рекурсию и приоритеты операторов 1 + 2 * 3 / (4 - x). Для Statements – пишут фиксированные шаблоны, распознающие код сравнением по образцу pattern matching. Синтаксический анализатор видит ключевое слово if и знает: дальше скобка, выражение, тело.

+-----------------+----------------------------+-------------------------+  
| СРАВНЕНИЕ       | STATEMENT (ИНСТРУКЦИЯ)     | EXPRESSION (ВЫРАЖЕНИЕ)  |  
+-----------------+----------------------------+-------------------------+  
| Метод разбора   | Pattern Matching (Шаблон)  | Спуск по каскаду правил |  
+-----------------+----------------------------+-------------------------+  
| Особенность AST | Фиксированное число ветвей | Рекурсивная вложенность |  
+-----------------+----------------------------+-------------------------+  
| Грамматическая  | Ключевое слово-маркер      | Код графа вычислений    |  
| форма           | (`if`, `while`, `return`)  | ((a+b)*sin(c)/d)        |  
+-----------------+----------------------------+-------------------------+  
| Действие        | Изменение состояния ЭВМ    | Помещение значения в    |  
|                 | (Регистры, RAM, Контроль)  | регистр или стек        |  
+-----------------+----------------------------+-------------------------+

Объяснить с

Функцию можно объявить statement и тут же вызвать, превратив в expression. Случаи: (...), if(...), case(...), func(...).

if(function(a,b) { return a+b; }(1,2) == 3) { console.log("OK"); } // выведет: OK

Объяснить с

Замыкания Closure. При объявлении функция сохраняет доступ к контексту видимости (лексическому окружению) на момент объявления (хранит ссылки на внешние переменные).

***

Видимость переменных var ограничена функцией, let – блоком { }.

Идеи Self. Всякий «объект» в JS ([], {}, Regex, function) – это Slot или набор ячеек (полей) с данными и методами. Поля в Slot добавляются в runtime режиме. В поле prototype можно указать другой объект, где ищутся поля, которых нет в объекте. Цепочка prototype.prototype.prototype... позволяет двигаться по графу «родителей» объекта. instanceof проверяет, есть ли в цепочке прототипов указанный объект. Добавление метода в слот делает доступным его для всех ссылающихся на него через prototype объектов.

***

Слот JS стал стандартом обмена данными JSON или JavaScript Object Notation. Контейнеры {} [] сохраняют базовые типы любых языков (числа, строки, массивы, отношения), а вложенность соответствует графу.

***

Берём стандартом строго подмножество ES3, ключевое слово let и параметры функций по умолчанию. Другие нововведения – запрещены. «Наследование», ООП, «классы», new, конструкторы – запрещены и неудачны, их ввели «маркетологи» «чтобы язык был похожим на Java». Исключения try-catch – запрещены (можно как аналог блока switch-goto). Прототипы – запрещены. Для переносимости кода межу языками брать исходную underscore.js.

3. ПОЛНОЦЕННЫЙ SQL, EBNF, XPATH В 80-480 СТРОК КОДА

JavaScript так удачен, что порождает множество доменных микро-языков.
SQL реализован Thomas Frank в 480 строк кода. SQLike делает из объектов JSON SQL таблицы.
Stefan Goessner реализовал языки jsonT и JSONPath в 70 и 88 строк соответственно. JSONPath – прямой аналог языка XPath XML Path Language [2] для работы с объектами языка, как с деревьями.
Calder Coalson в 300 строк кода реализовал генератор парсеров OmNom.js, отдающий AST по грамматике EBNF и соответствующему ей исходному коду.
Есть микро-языки Embedded JavaScript, mustache.js и другие для встройки JavaScript в HTML.
Код перечисленных проектов размещён в [3] и [4].

РАЗДЕЛ: ПРАКТИКА

۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩  
۩.░░░░░.█░█░▄▀▄░█▀▄░█▀▄░█░█░░░░░۩  
۩.░░░░░.█▀█░█▀█░█▀░░█▀░░░█░░░░░░۩  
۩.░░░░░.▀░▀░▀░▀░▀░░░▀░░░░▀░░░░░░۩  
۩.░█░░░█ █▀▀ █▀▀ █░▄▀ █▀▀ █▄░█ █▀▄░۩  
۩.░█░█░█ █▀▀ █▀▀ █▀▄░ █▀▀ █░▀█ █░█░۩  
۩.░░▀░▀░ ▀▀▀ ▀▀▀ ▀░▀▀ ▀▀▀ ▀░░▀ ▀▀░░۩  
۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩๑๑۩

Объяснить с

ПРАКТИКА

Исходный код взять с репозитория [5]. С код выполнить пошагово в IDE Code::Blocks [8], JavaScript – в отладчике браузера Chromium [9].

Прочесть документацию главная -> иконка ? и выполнить примеры главная -> examples на https://arborjs.org/halfviz/
Получить на С граф на языке Halftone graph_walk_orders.cpp
Получить граф на языке Halftone: js_graph_lib.html -> js_graph_lib.js
Обойти граф разными обходами: js_graph_lib.html -> js_graph_lib.js
Повторить SQL логику: js_sql.html -> js_sql.js
Прочесть документацию и js_micro_dsl/SQLike.README.md и выполнить примеры: js_sqlike.html -> js_sqlike.js
Построить булеаны boolean.cpp.