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

(Серия: Сельскому учителю в помощь)

Оглавление

ВСТУПЛЕНИЕ

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

Для строительства компиляторов, нам нужны начала математики. Из них, как мы убедимся, проистекает добрая половина понимания и всех наших работ.
В частности, без начал не понять лямбда-исчисление Чёрча, которое мы рассмотрим и применим на этапе работы с 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)», второй – обратное: что и то и другое – важно. Но встретившись они согласятся друг с другом, и разбегутся, оставив вас в дураках.
Дело в том, что в разных разделах математики и инженерных дисциплинах те же термины определены по-разному. Небрежное употребление математических терминов сродни «хождению по минному полю».

МНОЖЕСТВА    +-------------------+-----------------------+---------------------------+  | Контекст (Модель) | Свойства              | Математическое основание  |  +-------------------+-----------------------+---------------------------+  | Теория множеств   | Эквивалентны          | Порядок не важен.         |  | (Кантор, ZF)      | '2, 4' = '4, 2, 2'    | Дубликаты игнорируются.   |  +-------------------+-----------------------+---------------------------+  | Мультимножества   | Различны              | Разная кратность          |  | (например, в SQL) | '2, 4' ≠ '4, 2, 2'    | элемента '2'.             |  +-------------------+-----------------------+---------------------------+  | Векторы           | Различны              | Разная длина и порядок    |  | (Списки в ЭВМ)    | '2, 4' ≠ '4, 2, 2'    | следования элементов.     |  +-------------------+-----------------------+---------------------------+  

ВЕКТОР    +-------------------------------+-------------------------------------+  | Геометрия                     | Алгебра                             |  +-------------------------------+-------------------------------------+  | Прямой направленный отрезок в | Конечное упорядоченное множество    |  | аффинном или евклидовом       | элементов, называемых компонентами  |  | пространстве.                 | вектора, записывают как (x, y, z)   |  +-------------------------------+-------------------------------------+  | Определяется длиной (модулем) | Определяется размерностью n (числом |  | и направлением (углами с      | компонент), порядком следования     |  | осями координат).             | компонент, и полем их значений.     |  +-------------------------------+-------------------------------------+  

ТАБЛИЦА СООТВЕТСТВИЯ МАТЕМАТИЧЕСКИХ СКОБОК И ИХ ЗНАЧЕНИЙ    +--------+-------------------------------------------------------------------+  | Скобки | Значение                                                          |  +--------+-------------------------------------------------------------------+  | ()     | Упорядоченные последовательности элементов                        |  |        | (кортежи, векторы, координаты).                                   |  +--------+-------------------------------------------------------------------+  | {}     | Неупорядоченные структуры данных (классические множества, булеан).|  +--------+-------------------------------------------------------------------+  | <>     | Читаем: «Состоит из компонент» (порядок следования не важен).     |  +--------+-------------------------------------------------------------------+  | [a,b]  | Числовой диапазон, включая границы: `a <= x <= b`.                |  +--------+-------------------------------------------------------------------+  | ]a,b[  | Числовой диапазон, исключая границы: `a < x < b`.                 |  +--------+-------------------------------------------------------------------+  

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

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

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

1. Алгебры

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

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

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

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

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

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

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

ГЕНЕЗИС ПОНЯТИЯ «ЭЛЕМЕНТ» В НАУКЕ    +----------------+---------------------------------------+  | ЭПОХА          | ТРАКТОВКА                             |  +----------------+---------------------------------------+  | Античность     | Возникновение термина. Элементы это   |  |                | Стихии (земля, вода, огонь, воздух).  |  +----------------+---------------------------------------+  | XVII-XVIII вв. | Химически неделимое вещество.         |  +----------------+---------------------------------------+  | XIX-XX вв.     | Элементарные частицы (физика),        |  |                | элементарные множества (математика).  |  +----------------+----------------------------------------  

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

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. Двудольные или «бинарные» графы

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

ПРИМЕРЫ:

АРИФМЕТИЧЕСКОЕ ВЫРАЖЕНИЕ / ЭКВИВАЛЕНТ В ЭЛЕМЕНТАРНЫХ МНОЖЕСТВАХ    Случай А. Элементарная числовая операция  1 + 2                 [ U ]                       /     \                     [*]     [**]    Случай Б. Композиция числовых операций  2 • (3 + 4)           [ | x | ]                       /     \                     [**]    [ U ]                            /     \                         [***]   [****]    Случай В. Символьная запись  a • (b + c)           [ • ]                       /     \                     [a]     [ + ]                            /     \                          [b]     [c]    Эквивалент математической записи функции  формулой f(a,b,c) = a • (b + c)  

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

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

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

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

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

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

+-----------------------------------------------------------------------+  |                  ТЕОРЕМА, ДОКАЗАННАЯ ДЛЯ АБСТРАКТНОГО КОЛЬЦА          |  +-----------------------------------------------------------------------+         |                    |                    |                    |         v                    v                    v                    v  +--------------+     +--------------+     +--------------+     +--------------+  | Многочлены   |     | Квадратные   |     | Криптография |     | Физика       |  | (Компиляторы)|     | матрицы (3D) |     | (AES/RSA)    |     |              |  +--------------+     +--------------+     +--------------+     +--------------+  

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

СВОЙСТВА КОЛЬЦА    +-------------------+---------------------------------------------------+  | Операция          | Свойства операции (Аксиомы)                       |  +-------------------+---------------------------------------------------+  | Сложение (+)      | 1. Замкнутость: +: S x S -> S                     |  |                   |   Если a, b в S, то (a + b) в S                   |  |                   | 2. Коммутативность: a + b = b + a                 |  |                   | 3. Ассоциативность: (a + b) + c = a + (b + c)     |  |                   | 4. Наличие нуля: a + 0 = a                        |  |                   | 5. Наличие обратного элемента: a + (-a) = 0       |  +-------------------+---------------------------------------------------+  | Умножение (*)     | 6. Замкнутость: *: S x S -> S                     |  |                   |    Если a, b в S, то (a * b) в S                  |  |                   | 7. Ассоциативность: (a * b) * c = a * (b * c)     |  +-------------------+---------------------------------------------------+  | Дистрибутивность  | 8. Раскрытие * через декартово произведение       |  |                   |    A x (B U C) = (A x B) U (A x C)                |  |                   |    a * (b + c) = (a * b) + (a * c)                |  +-------------------+---------------------------------------------------+  

Последовательность из той же «ассоциативной» операции можно выполнять в произвольном порядке. Сложение (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 выражениях без специальных флагов оптимизации.

ОПТИМИЗАЦИЯ СКОРОСТИ ВЫЧИСЛЕНИЙ ЧЕРЕЗ ДИСТРИБУТИВНОСТЬ        Исходный граф             Оптимизированный граф  (2 умножения, 1 сложение)   (1 умножение, 1 сложение)        [ + ]                      [ * ]       /     \                    /     \    [ * ]   [ * ]                a      [ + ]   /   \   /   \                       /     \  a     b a     c                     b       c  

При оптимизации в формульной математике и в компиляторах берут свойства матричных колец. Так, в 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.

function cartesianProduct()  {      return Array.from(arguments).reduce(function(a, b)      {          return a.map(function(x)          {              return b.map(function(y) { return x.concat([y]); });          }).flat(1);      }, [[]]);  }    cartesianProduct([0,1,2], ['a','b','c','d'], ['I', 'II', 'III', 'IV', 'V']);  

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

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

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

ТАБЛИЦИЦА БИЕКЦИЙ ФИЗИКА, МАТЕМАТИКА, ИНЖЕНЕРИЯ    +---------------+---------------------+-------------------------+  | Физика        | Математика          | Конечный автомат        |  | (Механика ЭВМ)| (Дискретные мн-ва)  | (Мат. модель)           |  +---------------+---------------------+-------------------------+  |                      АВТОМАТ КОЛЕСО                           |  +---------------+---------------------+-------------------------+  | Колесо        | Конечное            | Множество состояний     |  |               | множество S         | S = {s0, s1, ...s9}     |  +---------------+---------------------+-------------------------+  | Знаки         | Цифры               | Символы алфавита        |  | на колесе     | 0,1,2,3,4,5,6,7,8,9 | состояний               |  +---------------+---------------------+-------------------------+  |               | Мощность множества  | Размер пространства     |  |               | состояний |S| = 10  | состояний автомата      |  +---------------+---------------------+-------------------------+  |     АВТОМАТ ОДОМЕТР. КАСКАД (СЕТЬ) АВТОМАТОВ КОЛЕСО           |  +---------------+---------------------+-------------------------+  | Колёса        | Множества A,B,C     | Три автомата            |  | (3 штуки)     | одинаковой мощности |                         |  +---------------+---------------------+-------------------------+  | Блок сцеплен- | Декартово           | Пространство состояний  |  | ных колес     | произведение AxBxC  | автомата одометра       |  +---------------+---------------------+-------------------------+  | Блок разрядов | Конкретный вектор   | Вектор текущего         |  | одометра      | (a, b, c) из AxBxC  | состояния               |  +---------------+---------------------+-------------------------+  |               | Мощность AxBxC      | Размер пространства     |  |               | |A|*|B|*|C| = 1000  | состояний автомата      |  +---------------+---------------------+-------------------------+  

ПРИМЕР 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} и разместим на декартовой плоскости, ставя в соответствие парам знаки на цифровых осях. Результат связал комбинаторное множество, матрицы, геометрию.

  Y    ^    | ----------------------------------------------------------  8 | | (1,8)  (2,8)  (3,8)  (4,8)  (5,8)  (6,8)  (7,8)  (8,8)*|  7 | | (1,7)  (2,7)  (3,7)  (4,7)  (5,7)  (6,7)  (7,7)* (8,7) |  6 | | (1,6)  (2,6)  (3,6)  (4,6)  (5,6)  (6,6)* (7,6)  (8,6) |  5 | | (1,5)  (2,5)  (3,5)  (4,5)  (5,5)* (6,5)  (7,5)  (8,5) |  4 | | (1,4)  (2,4)  (3,4)  (4,4)* (5,4)  (6,4)  (7,4)  (8,4) |  3 | | [1,3]  (2,3)  (3,3)* (4,3)  (5,3)  (6,3)  (7,3)  (8,3) |  2 | | [1,2]  (2,2)* (3,2)  (4,2)  (5,2)  (6,2)  (7,2)  (8,2) |  1 | | (1,1)* [2,1]  [3,1]  (4,1)  (5,1)  (6,1)  (7,1)  (8,1) |  --+------------------------------------------------------------> X  0 |     1      2      3      4      5      6      7      8          a      b      c      d      e      f      g      h  

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 для распределения их по регистрам процессора.

Исходное множество: S = { a, b, c }    +-------------------+----------------------+------------------------------------+  | Подмножество (P)  | Кортеж битов (V)     | Пояснение структуры кортежа        |  +-------------------+----------------------+------------------------------------+  | { }               | (0, 0, 0)            | Нет ни одного элемента             |  | { c }             | (0, 0, 1)            | Включен только элемент 'c'         |  | { b }             | (0, 1, 0)            | Включен только элемент 'b'         |  | { b, c }          | (0, 1, 1)            | Элементы {b, c} равны битам 1, 1   |  | { a, b, c }       | (1, 1, 1)            | Все элементы включены              |  +-------------------+----------------------+------------------------------------+  

// boolean.cpp    #include <conio.h>  #include <locale.h>    #define LOG printf    /* Вывод подмножества по битовой маске */  void print_subset(const char* set[], int set_size, int mask)  {      LOG("{ ");        /* i-й бит установлен ? */      for (int i = 0; i < set_size; ++i) { if (mask & (1 << i)) LOG("%s ", set[i]); }        LOG("}\n");  }    /* Генератор булеана через битовые маски */  void generate_powerset(const char* set[], int set_size)  {      int total_subsets = 1 << set_size; /* Общее количество подмножеств 2^set_size */      for (unsigned int mask = 0; mask < total_subsets; ++mask) print_subset(set, set_size, mask);  }    int main(void)  {      LOG("BOOLEAN = \n\n");        const char* S[] = { "A", "B", "C", "D" }; /* Тестовое множество (строки) */      int N = 4; /* Генерируем булеан для первых 3 элементов: { "A", "B", "C" } */        generate_powerset(S, N);        getch();      return 0;  }  

6. ОТНОШЕНИЕ

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

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

       МНОЖЕСТВА A = {a1, a2}, B = {b1, b2}         ДЕКАРТОВО ПРОИЗВЕДЕНИЕ (A x B)         [ (a1,b1), (a1,b2), (a2,b1), (a2,b2) ]                           |        +------------------+------------------+        |                  |                  |        v                  v                  v   СЛУЧАЙ 1: Пустое    СЛУЧАЙ 2: Частичное   СЛУЧАЙ 3: Полное (все пары)     отношение            отношение              отношение        +----+----+        +----+----+        +----+----+   | A  | B  |        | A  | B  |        | A  | B  |   +----+----+        +----+----+        +----+----+   |    |    |        | a1 | b2 |        | a1 | b1 |   +----+----+        | a2 | b1 |        | a1 | b2 |                      +----+----+        | a2 | b1 |                                         | a2 | b2 |                                         +----+----+        |                  |                  |        v                  v                  v     Граф без           Частичный            Полный      ребер                граф               граф          a1    b1          a1 ---> b1         a1 ---> b1                                           \     ^                                            \   /                                              X                                             /   \                                           /     V    a2    b2          a2 ---> b2         a2 ---> b2  

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

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

ОПРЕДЕЛЕНИЕ ФУНКЦИИ F = <D,W,S>    +-----------+-----------------------+---------------------------------------+  | Компонент | Название              | Суть (математическая роль)            |  +-----------+-----------------------+---------------------------------------+  |     D     | Область определения   | Все допустимые значения на "входе"    |  +           |                       | функции.                              |  +-----------+-----------------------+---------------------------------------+  |     W     | Область значений      | Все допустимые значения на "выходе"   |  +           |                       | функции.                              |  +-----------+-----------------------+---------------------------------------+  |     S     | Отношение             | Подмножество D × W. Набор пар (d, w). |  +           |                       | Связи входное -> выходное значение.   |  +-----------+-----------------------+---------------------------------------+  

ПРИМЕР

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

Функция f = x*x, определена на областях D = {1,2,3}, W = {1,4,9}  Отношение S = { (1,1), (2,4), (3,9) }    ДЕКАРТОВА ПЛОСКОСТЬ                                АЛГЕБРА  Область значений (W)                       +----------------------+      ^                                      | ОТНОШЕНИЕ S          |      |                                      +----------------------+    9 |               *  (3, 9)              | Множество пар (d, w) |      |                                      +----------------------+    ...                                      | ФУНКЦИЯ  F           |      |                                      +----------------------+    4 |          *  (2, 4)                   | Вход      | Выход    |      |                                      | d ∈ D     | w ∈ W   |    ...                                      +----------------------+      |                                      | 1         | 1        |    1 |     *  (1, 1) <-- Элемент            +----------------------+      |                   отношения S        | 2         | 4        |    0 +---------------------------->         +----------------------+            1    2    3    4                 | 3         | 9        |          Область определения (D)            +----------------------+  

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

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

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

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

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

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

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

ТАБЛИЦА БИЕКЦИЙ МАТЕМАТИКА - СИНТАКСИС LISP    +--------------+---------------------------------------------------+  | Математика   | Синтаксис S-выражения                             |  +--------------+---------------------------------------------------+  | Функция f    | Первый элемент списка: `(f ...)`                  |  |              | (Голова списка или «CAR»)                         |  +--------------+---------------------------------------------------+  | Аргументы    | Последующие элементы: `(... x, y, z)`             |  | x, y, z      | (Хвост списка или «CDR»)                          |  +--------------+---------------------------------------------------+  | Композиция   | Вложенный список: (f (g ...))                     |  | (f g)        | (Вершина графа содержит список дочерних вершин)   |  +--------------+---------------------------------------------------+  | «Аппликация» | Рекурсивный спуск по графу вида «дерево»          |  | (Вычисление) | (Оператор EVAL)                                   |  +--------------+---------------------------------------------------+  

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

ПРИМЕР

Определение функций  f1(x) = x*2   f2(y) = y+1   f3(z) = z*z     f4(x,y,z) = u+v+w  Последовательность вызовов функций  u = f1(x)   v = f2(y)   w = f3(z)   r = f4(u,v,w)  Соответствующая композиция  f5(x,y,z) = f4(f1(x),f2(y),f3(z))  Вызов  r = f5(1,2,3)  

/* Определение базовых функций */  float f1(float x) { return x * 2.0f; }  float f2(float y) { return y + 1.0f; }  float f3(float z) { return z * z;    }  float f4(float u, float v, float w) { return u + v + w; }    /* Композиция (свернутый граф вычислений) */  float f5(float x, float y, float z)  {      return f4(f1(x), f2(y), f3(z));  }    int main(void)  {    /* Последовательный вызов (линейный код) */      float u = f1(1.0f);      float v = f2(2.0f);      float w = f3(3.0f);      float r = f4(u, v, w);        /* Вызов композиции f5 c вектором аргументов (x=1, y=2, z=3) */      float r_composition = f5(1.0f, 2.0f, 3.0f);        return 0;  }  

Язык Lisp

;; Определение базовых функций  (defun f1 (x)     (* x 2))  (defun f2 (y)     (+ y 1))  (defun f3 (z)     (* z z))  (defun f4 (u v w) (+ u v w))    ;; 1. Композиция функций (Граф вычислений)  (defun f5 (x y z)    (f4       (f1 x)       (f2 y)       (f3 z)    )  )    ;; 2. Последовательный вызов (Развертка графа через промежуточные узлы u,v,w)  (defun execute-linear (x y z)    (let*       (        (u (f1 x))        (v (f2 y))        (w (f3 z))      )      (f4 u v w)    )  )    ;; --- ТОЧКА ВХОДА ---    ;; Вызов 1: Вычисление свернутого графа в композиции f5  (f5 1 2 3)    ;; Вызов 2: Вычисление линейной развертки графа  (execute-linear 1 2 3)  

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 – их подмножество.

ТАБЛИЦА БИЕКЦИЙ ТЕРМИНЫ МАТЕМАТИКИ <-> ТЕРМИНЫ ИНЖЕНЕРИИ    +-------------------------+--------------------------+  | Математика (Абстракции) | Инженерия (Предметы)     |  +-------------------------+--------------------------+  | Граф (G = <V, E>)       | Сеть (граф с признаками) |  +-------------------------+--------------------------+  | Вершины (V)             | Узлы                     |  +-------------------------+--------------------------+  | Рёбра (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.

Матрица полного неориентированного графа для |V| = 4         v0   v1   v2   v3  v0 [ +0+   1    1    1  ]  v1 [  1   +0+   1    1  ]  v2 [  1    1   +0+   1  ]  v3 [  1    1    1   +0+ ]  

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

+------------------------------------+------------------------------------+  | Инженерная / Физическая система    | Алгебраическая структура матрицы   |  +------------------------------------+------------------------------------+  | Абсолютно твёрдое тело, полная     | Полный неориентированный граф.     |  | связность "каждый-с-каждым".       | Все `M[i][j] == 1`, кроме `i == j`.|  +------------------------------------+------------------------------------+  | Единый связный "организм" (мост,   | Связный граф. Существует путь      |  | общая шина данных ЭВМ).            | между любыми `v_i` и `v_j`.        |  +------------------------------------+------------------------------------+  | Односторонние шлюзы, диоды,        | Орграф (асимметричная матрица)     |  | однонаправленные каналы связи.     | либо два раздельных графа.         |  +------------------------------------+------------------------------------+  

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

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

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

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

ПРИМЕР

Топология сети с узлами v1, v2, v3              [v1] 1           /    \     10 мс/      \15 мс  <-- Веса рёбер W         /        \     2 [v2]      [v3] 3    В список рёбер D добавляют третье значение W, D = { (1, 2, 10), (1, 3, 15) }  

           v1    v2    v3           +-----------------      v1   |  ∞    10    15  <-- От v1 до v2 10 мс, от v1 до v3 15 мс      v2   | 10     ∞     ∞  <-- От v2 до v1 те же 10 мс, связи с v3 нет      v3   | 15     ∞     ∞  <-- От v3 до v1 те же 15 мс, связи с v2 нет  

+---------------+----------------------------------------------------------------+  | Свойство      | Комментарий                                                    |  +---------------+----------------------------------------------------------------+  | «Цена»        | Нужно передать сигнал из `v1` в `v3`. Инженер смотрит в ячейку |  | действия      | `(v1, v3)` и сразу называет «цену» этого действия – `15 мс`.   |  +---------------+----------------------------------------------------------------+  | Маршрут       | Время отклика при транзите пакетов `v2->v3`, это сумма весов   |  | и «цена»      | на пути: `(v2->v1) + (v1->v3) = 10 + 15 = 25 мс`.              |  +---------------+----------------------------------------------------------------+  | Бесконечность | Прямой связи между исполнителями нет.                          |  | Ячейки (v2,v3)| Сигнал из `v2` в `v3` обязан пройти через `v1`.                |  | (v3,v2)  -> ∞ |                                                                |  +---------------+----------------------------------------------------------------+  | Симметрия     | Сигнал между центральным и рабочим узлами идет 10 мс в обе     |  | Ячейка (v1,v2)| стороны.                                                       |  | равна (v2,v1) |                                                                |  +---------------+----------------------------------------------------------------+  | Оптимизация   | При наличии нескольких путей из `v1` в `v3` сравнивают суммы   |  | Выбор маршрута| весов по их маршрутам. Минимальная сумма даст кратчайший путь. |  |               | Пути между вершинами графа взять алгоритмами обхода            |  |               | `Поиск в ширину` `BFS` либо `Поиск в глубину` `DFS`.           |  +---------------+----------------------------------------------------------------+  

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.

roast beef -> ray  ray -> teodor  teodor -> roast beef  pat ; pat is all alone  

// js_graph_lib.html js_graph_lib.js    var __each = function(obj, callback, context) { [].forEach.call(obj, callback, context); };    // граф в JSON  var graphJson = {      "id": "a",      "child": [          {              "id": "b",              "child": [                  { "id": "d" },                  { "id": "e" }              ]          },          {              "id": "c",              "child": [                  { "id": "f" },                  { "id": "g" }              ]          }      ]  };    var halftone = "; halftone lang sample \n";  // Генерация узлов  function halftone_print_node(node, CTX)  {      if(Math.random() < 0.5) halftone += (node.id + "\n");      else  halftone += (node.id + ' { color:red }; random >= 0.5\n');  }  // Генерация рёбер  function halftone_print_edge(node, CTX)  {      halftone += (CTX.parent.id + ' -> ' + node.id + '\n');  }    // Обход графа  function halftone_walkPreOrder(node, iteratee, CTX)  {      if (!node) { return; }        iteratee(node, CTX ? CTX : { parent : { id: 'null' } });            __each(node.child || [], function(child) {          halftone_walkPreOrder(child, iteratee, { parent:node });      });  }    // Генерация графа на языке Halftone  halftone_walkPreOrder(graphJson, halftone_print_node);  halftone_walkPreOrder(graphJson, halftone_print_edge);  LOG(halftone);    /*    ; halftone lang sample, copy & past to https://arborjs.org/halfviz/    a { color:red }; random >= 0.5  b { color:red }; random >= 0.5  d { color:red }; random >= 0.5  e  c { color:red }; random >= 0.5  f  g  null -> a  a -> b  b -> d  b -> e  a -> c  c -> f  c -> g    */  

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

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

НАЗНАЧЕНИЕ АЛГОРИТМОВ ОБХОДА  +-------+-------------------------+------------------------------+  | ОБХОД | МАШИННАЯ МОДЕЛЬ         | ПРИМЕНЕНИЕ                   |  +-------+-------------------------+------------------------------+  | DFS   | Стековый автомат        | Генерация машинного кода,    |  | Post  | (Схлопывание операндов) | расчет смещений, вычисления. |  +-------+-------------------------+------------------------------+  | DFS   | Нисходящий автомат      | Синтаксический анализ (LL),  |  | Pre   | (Парсинг токенов)       | копирование/клонирование AST.|  +-------+-------------------------+------------------------------+  | DFS   | Монотонный обход        | Сортировка данных (СУБД),    |  | In    | упорядоченного множества| декомпиляция в читаемый вид. |  +-------+-------------------------+------------------------------+  | BFS   | Очередь FIFO            | Поиск кратчайшего пути,      |  |       |                         | оптимизация сетевых роутов.  |  +-------+-------------------------+------------------------------+  

Порядок обхода 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).

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

// graph_walk_orders.cpp    #include <conio.h>  #include <locale.h>    #define LOG printf  #define MAX_QUEUE_SIZE 256    typedef struct node  {      int id;      int child_count;      struct node** child; /* Массив указателей на узлы-потомки */      struct node*  parent;  } node_t;    void iteratee(node_t* n)  {      if(n->parent) LOG("%d->%d\n", n->id, n->parent->id);      else  LOG("%d\n", n->id);  }    void walkPostOrder(node_t* root, void (*visit)(node_t*))  {      if (root == NULL) return;        /* Спуск по потомкам  */      for (int i = 0; i < root->child_count; ++i) walkPostOrder(root->child[i], visit);        visit(root);  }    void walkPreOrder(node_t* root, void (*visit)(node_t*))  {      if (root == NULL) return;        visit(root); /* Вызов обработчика ДО обхода потомков */        for (int i = 0; i < root->child_count; ++i) walkPreOrder(root->child[i], visit);  }    void walkInOrder(node_t* root, void (*visit)(node_t*))  {      if (root == NULL) return;        /* Рекурсивный обход самого первого потомка (индекс 0) */      if (root->child_count > 0) walkInOrder(root->child[0], visit);          visit(root); /* Визит текущего узла */        /* Рекурсивный обход всех последующих потомков (индексы от 1 до N-1) */      for (int i = 1; i < root->child_count; ++i) walkInOrder(root->child[i], visit);  }    void walkBFS(node_t* root, void (*visit)(node_t*))  {      if (root == NULL) return;        node_t* queue[MAX_QUEUE_SIZE];      int head = 0, tail = 0;        queue[tail++] = root;        while (head < tail)      {          node_t* item = queue[head++];          visit(item);            for (int i = 0; i < item->child_count; ++i)          {              if (tail < MAX_QUEUE_SIZE) queue[tail++] = item->child[i];          }      }  }      void init_node(node_t* n, int id, int child_count, node_t** child)  {      n->id = id;      n->child_count = child_count;      n->child = child;      n->parent = NULL;        for (int i = 0; i < child_count; ++i) child[i]->parent = n;  }  int main(void)  {      /*       * Инициализация тестового графа (дерева):       *        [10] (Корень)       *       /    \       *    [20]    [30]       *            /  \       *          [40] [50]       */        node_t n20, n40, n50, n30, root;        /* Сборка графа снизу вверх */      init_node(&n20, 20, 0, NULL);      init_node(&n40, 40, 0, NULL);      init_node(&n50, 50, 0, NULL);        node_t* c30[] = { &n40, &n50 };      init_node(&n30, 30, 2, c30);        node_t* c10[] = { &n20, &n30 };      init_node(&root, 10, 2, c10);        LOG("; --- DFS PostOrder Walk ---\n; This is Halftone lang code. Put it to https://arborjs.org/halfviz/ graph visualizer.\n");      walkPostOrder(&root, iteratee);        LOG("; --- DFS PreOrder Walk ---\n; This is Halftone lang code. Put it to https://arborjs.org/halfviz/ graph visualizer.\n");      walkPreOrder(&root, iteratee);        LOG("; --- DFS InOrder Walk ---\n; This is Halftone lang code. Put it to https://arborjs.org/halfviz/ graph visualizer.\n");      walkInOrder(&root, iteratee);        LOG("; --- BFS Walk ---\n; This is Halftone lang code. Put it to https://arborjs.org/halfviz/ graph visualizer.\n");      walkBFS(&root, iteratee);        getch();      return 0;  }  

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

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

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    ИНЖЕНЕРИЯ                                             МАТЕМАТИКА  +-----------+     +-----------+     +-----------+  | Таблица A |     | Таблица B |     | Таблица C |    <--- Отношения  +-----------+     +-----------+     +-----------+        |                 |                 |        +-----------------x-----------------+                  |        <--- Операция: Декартово произведение x (FROM)                  v  +---------------------+  |  Таблица A x B x C  |   <--- Отношение (Все возможные комбинации строк  +---------------------+                   из таблиц A, B, C )             |             v  +---------------------+  | Фильтр подмножества |  <--- Операция: Отсечь строки предикатом (WHERE)  +---------------------+             |             v  +---------------------+  |    Проекция Pr      |  <--- Операция: Отсечь столбцы предикатом (SELECT)  +---------------------+             |             v  +---------------------+  |  Выходная таблица   |  <--- Отношение  +---------------------+  

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

+----------------+-----------------------+--------------------------+  | Операция над   | Заменяющий предикат   | Смысл операции           |  | множествами    | в SELECT-FROM-WHERE   |                          |  +----------------+-----------------------+--------------------------+  | INTERSECT (U)  | WHERE EXISTS (...)    | Пересечение множеств     |  |----------------|-----------------------|--------------------------|  | EXCEPT (\)     | WHERE NOT EXISTS (...)| Дополнение (Вычитание)   |  |----------------|-----------------------|--------------------------|  | UNION (U)      | WHERE OR / DISTINCT   | Объединение множеств     |  +----------------+-----------------------+--------------------------+  

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

SELECT A.a1, B.b1, B.b2, C.c1, C.c3  FROM A, B, C   WHERE A.a1 < B.b1 AND C.c3 = 301    МАТЕМАТИКА    A x B x C -> { (A.a1 < B.b1) * (C.c1 == 301 ) } -> Pr(A.a1, B.b1, B.b2, C.c1, C.c3)    ДАННЫЕ      Таблица A          Таблица B                Таблица C  +----+             +----+----+              +-----+-----+-----+  | a1 |             | b1 | b2 |              | c1  | c2  | c3  |  +----+             +----+----+              +-----+-----+-----+  | 1  |             | 10 | 11 |              | 100 | 101 | 102 |  +----+             | 20 | 21 |              | 200 | 201 | 202 |                     +----+----+              | 300 | 301 | 302 |                                              +-----+-----+-----+    1. `FROM` вычисляет декартово произведение исходных отношений `AxBxC`, имеем все теоретически возможные комбинации кортежей («строк») исходных множеств.    S1 = A x B x C.  Мощность результирующего множества: |A| * |B| * |C| = 1 * 2 * 3 = 6 кортежей.    +----+----+----+-----+-----+-----+  | a1 | b1 | b2 | c1  | c2  | c3  |      Кортежи  +----+----+----+-----+-----+-----+  | 1  | 10 | 11 | 100 | 101 | 102 |  <-- 1  | 1  | 10 | 11 | 200 | 201 | 202 |  <-- 2  | 1  | 10 | 11 | 300 | 301 | 302 |  <-- 3  | 1  | 20 | 21 | 100 | 101 | 102 |  <-- 4  | 1  | 20 | 21 | 200 | 201 | 202 |  <-- 5  | 1  | 20 | 21 | 300 | 301 | 302 |  <-- 6  +----+----+----+-----+-----+-----+    2. `WHERE` выделяет подмножество, применяя цепочку предикатов к каждому кортежу таблицы.  Предикат A.a1 < B.b1 истинен для всех 6 кортежей (1 < 10 и 1 < 20).  Предикат C.c3 = 202 истинен только для Кортежа 2 и Кортежа 5.    +----+----+----+-----+-----+-----+  | a1 | b1 | b2 | c1  | c2  | c3  |  +----+----+----+-----+-----+-----+  | 1  | 10 | 11 | 200 | 201 | 202 |  <-- Кортеж 2  | 1  | 20 | 21 | 200 | 201 | 202 |  <-- Кортеж 5  +----+----+----+-----+-----+-----+      3. `SELECT` оставляет только указанные столбцы A.a1, B.b1, B.b2, C.c1, C.c3.    +----+----+----+-----+-----+  | a1 | b1 | b2 | c1  | c3  |  +----+----+----+-----+-----+  | 1  | 10 | 11 | 200 | 202 |  | 1  | 20 | 21 | 200 | 202 |  +----+----+----+-----+-----+  

JAVASCRIPT

// js_sql.html js_sql.js    var LOG = function() { console.log.apply(console, arguments); };    // Декартово произведение  function cartesianProduct()  {      return _.reduce(arguments, function(a, b)      {          return _.flatten(_.map(a, function(x)          {              return _.map(b, function(y)              {                  return _.extend({}, x, y);              });          }), true);      }, [{}]);  }    // Исходные множества  var tableA = [{ a1: 1 }];  var tableB = [{ b1: 10, b2: 11 }, { b1: 20, b2: 21 }];  var tableC = [      { c1: 100, c2: 101, c3: 102 },      { c1: 200, c2: 201, c3: 202 },      { c1: 300, c2: 301, c3: 302 }  ];    // 1. FROM (Вычисление AxBxC)  var relationFrom = cartesianProduct(tableA, tableB, tableC);    LOG(relationFrom);    // 2. WHERE (Фильтрация по цепочке предикатов)  var relationWhere = _.filter(relationFrom, function(row)  {      return row.a1 < row.b1 && row.c3 === 202;  });    LOG(relationWhere);    // 3. SELECT (Фильтрация подмножества атрибутов)  var result = _.map(relationWhere, function(row)  {      return _.pick(row, 'a1', 'b1', 'b2', 'c1', 'c3');  });    LOG(result);  

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

SQL

SELECT b1, b2, NULL AS b3 FROM B  UNION  SELECT c1, c2, c3 FROM C       Таблица B (Двумерная)             Таблица C (Трехмерная)        +----+----+                       +-----+-----+-----+        | b1 | b2 |                       | c1  | c2  | c3  |        +----+----+                       +-----+-----+-----+    У таблиц разное количество столбцов, их не объединить. Дополним B третьим столбцом, заполоненным NULL.    1. ПОДЗАПРОС SELECT b1, b2, NULL AS b3 FROM B    ТАБЛИЦА Q1 =    +-----+-----+-----+  | b1  | b2  | b3  |  +-----+-----+-----+  | 10  | 11  | NULL|  | 20  | 21  | NULL|  +-----+-----+-----+    2. ПОДЗАПРОС SELECT c1, c2, c3 FROM C    ТАБЛИЦА Q2 =    +-----+-----+-----+  | c1  | c2  | c3  |  +-----+-----+-----+  | 100 | 101 | 102 |  | 200 | 201 | 202 |  | 300 | 301 | 302 |  +-----+-----+-----+    3. ПОДЗАПРОС Q1 UNION Q2    ТАБЛИЦА Q3 = Q1 U Q2    +-----+-----+-----+  | c1  | c2  | c3  |  +-----+-----+-----+  | 10  | 11  | NULL|  <-- Из Q1  | 20  | 21  | NULL|  <-- Из Q1  | 100 | 101 | 102 |  <-- Из Q2  | 200 | 201 | 202 |  <-- Из Q2  | 300 | 301 | 302 |  <-- Из Q2  +-----+-----+-----+  

JAVASCRIPT

// 1. ПОДЗАПРОС Q1: Проекция таблицы B с алиасами столбцов и добавление NULL  var q1 = _.map(tableB, function(row)  {      return {          c1: row.b1,          c2: row.b2,          c3: null      };  });    LOG(q1);    // 2. ПОДЗАПРОС Q2: Проекция таблицы C  var q2 = _.map(tableC, function(row)  {      return {          c1: row.c1,          c2: row.c2,          c3: row.c3      };  });    LOG(q2);    // 3. ПОДЗАПРОС Q3: Реляционное объединение (UNION)    // Объединить подмножества строк  var q3 = q1.concat(q2);    LOG(q3);    // Удалить если есть дубликаты  var q4 = _.uniq(q3, false, function(row)  {      return _.map(_.keys(row).sort(), function(key)      {          return key + ':' + row[key];      }).join(',');  });    LOG(q4);  

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

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

SQL

SELECT *  FROM q3  WHERE c1 IN (10, 100, 300);    +-----+-----+-----+  | c1  | c2  | c3  |  +-----+-----+-----+  | 10  | 11  | NULL|  <-- Оставит  | 20  | 21  | NULL|  | 100 | 101 | 102 |  <-- Оставит  | 200 | 201 | 202 |  | 300 | 301 | 302 |  <-- Оставит  +-----+-----+-----+  

JAVASCRIPT

// Множество значений для фильтрации строк  var includesMathSet = [10, 100, 300];    // Фильтрация таблицы q3  var filteredResult = _.filter(q3, function(row)  {      return _.contains(includesMathSet, row.c1);  });    LOG(filteredResult);  

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 ....

ТАБЛИЦА ПРАВИЛ «КЛАССИЧЕСКОЙ» КОМБИНАТОРИКИ  `M` – «ЯЧЕЙКИ» (КОЛИЧЕСТВО ФИКСИРОВАНО), `N` – РАЗМЕЩАЕМЫЕ ЭЛЕМЕНТЫ  +------------------------------+---------------------------------------------+  |                              | Условия для результата     |                |  +------------------------------+---------------------------------------------+  | Название                     | Порядок     | Повторы      | Мощности       |  |                              | (a,b)!=(b,a)| (a,a)        |                |  +------------------------------+-------------+--------------+----------------+  | Размещения без повторений    | Да          | Запрет       | |N| >= |M|     |  +------------------------------+-------------+--------------+----------------+  | Разместить N предметов по M местам.                                        |  | (Пример: все варианты рассадить 5 человек на 3 стула).                     |  +------------------------------+-------------+--------------+----------------+  | Размещения с повторением     | Да          | Да           | Не учитывать   |  +------------------------------+-------------+--------------+----------------+  | Заполнить места элементами, которые могут многократно дублироваться.       |  | (Пример: все варианты цифр на кодовом замке 000-999).                      |  +------------------------------+-------------+--------------+----------------+  | Перестановки без повторений  | Да          | Запрет       | |N| == |M|     |  +------------------------------+-------------+--------------+----------------+  | Переставить N предметов по M местам. Это частный случай размещений, где    |  | количество элементов и мест равны |N| = |M|.                               |  | (Пример: все варианты рассадить 4 человека на 4 стула).                    |  +------------------------------+-------------+--------------+----------------+  | Перестановки с повторением   | Да          | Да (из N)    ||N_мульти| = |M||  +------------------------------+-------------+--------------+----------------+  | Поменять местами набор из элементов, где есть повторы (мультимножество).   |  | (Пример: сколько уникальных слов можно получить из букв слова «МОЛОКО»).   |  +------------------------------+-------------+--------------+----------------+  | Сочетания без повторений     | Нет         | Запрет       | |N| >= |M|     |  +------------------------------+-------------+--------------+----------------+  | Выбрать M элементов из N доступных. Порядок внутри группы (кто первый кто  |  | второй) — не учитывается. (Пример: Выбрать в команду 3 человека из 10).    |  +------------------------------+-------------+--------------+----------------+  | Сочетания с повторением      | Нет         | Да           | Не учитывать   |  +------------------------------+-------------+--------------+----------------+  | Выбрать фиксированный набор элементов, из множества, где они могут         |  | дублироваться, без учёта порядка внутри итогового набора (a,b) = (b,a).    |  | (Пример: Купить 3 пирожных в магазине, где их 4 вида).                     |  +------------------------------+---------+---------+-------------------------+  

ПРИМЕРЫ

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

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

R1 = (r0 x N): {(r0, 0), (r0, 1) , (r0, 2) , (r0, 3), ..., (r0, 9)}  R2 = (r1 x N): {(r1, 0), (r1, 1) , (r1, 2) , (r1, 3), ..., (r1, 9)}  R3 = (r2 x N): {(r2, 0), (r2, 1) , (r2, 2) , (r2, 3), ..., (r2, 9)}    `C = | R1 x R2 x R3 | =  | (r0 x N) | *| (r1 x N) | * | (r2 x N) | = 10*10*10=1000`.  

  -- SQL, PostgreSQL      -- Вариант 1  WITH     r0(v) AS (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9)),    r1(v) AS (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9)),    r2(v) AS (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9))    SELECT COUNT(*)AS C FROM r0, r1, r2;      -- Вариант 2  WITH n(v) AS (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9))  SELECT COUNT(*)AS C FROM n AS r0, n AS r1, n AS r2;      -- Вариант 3    WITH     r(reg) AS (VALUES ('r0'),('r1'),('r2')),    n(v)    AS (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9)),        -- Множество всех пар (R x N)    pairs(pos, val) AS (SELECT r. reg, n.v FROM r, n),      -- Разделение множества всех пар на три подмножества    r0(v) AS (SELECT val FROM pairs WHERE pos = 'r0'),    r1(v) AS (SELECT val FROM pairs WHERE pos = 'r1'),    r2(v) AS (SELECT val FROM pairs WHERE pos = 'r2')    SELECT COUNT(*)AS C FROM r0, r1, r2;  

Сколько коробок 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).

  -- SQL, PostgreSQL      -- Вариант 1  -- все размещения без повторений  WITH     n(v) AS (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9))    -- [ R1 x R2 x R3 ] Полное декартово произведение (1000 строк)  SELECT r0.v v0, r1.v v1, r2.v v2  FROM n r0, n r1, n r2    EXCEPT    -- [ B ] Множество всех повторов для вычитания (280 строк)  SELECT r0.v v0, r1.v v1, r2.v v2  FROM n r0, n r1, n r2  WHERE r0.v = r1.v OR r1.v = r2.v OR r0.v = r2.v;      -- Вариант 2  -- количество размещений без повторений (короткий вариант)  WITH n(v) AS (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9))  SELECT COUNT(*)AS C FROM n r0, n r1, n r2  WHERE r1.v != r0.v AND r2.v != r0.v AND r1.v != r2.v;  

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

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

  -- SQL, PostgreSQL  -- количество перестановок без повторений  -- если заменить COUNT(*) на *, получим таблицу возможных рассадок людей  WITH n(v) AS (VALUES (0),(1),(2))  SELECT COUNT(*) AS C FROM n m0, n m1, n m2  WHERE m1.v != m0.v AND m2.v != m0.v AND m1.v != m2.v;  

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

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

  -- SQL, PostgreSQL  WITH n(v) AS (VALUES (0),(1),(2),(3))  -- виды пирожных  SELECT COUNT(*) AS C   FROM n t0, n t1, n t2  -- t0, t1, t2 физические ячейки в коробке для пирожных  WHERE t0.v <= t1.v AND t1.v <= t2.v;  

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.

  -- SQL, PostgreSQL        -- FROM – это декартово произведение x, COUNT – мощность множества | |    WITH     -- Состояния кубиков (K1, K2)    k1(v) AS (VALUES (1),(2),(3),(4),(5),(6)),    k2(v) AS (VALUES (1),(2),(3),(4),(5),(6)),        -- Нужные подмножества состояний (A1, A2)    a1(v) AS (VALUES (4),(5),(6)),    a2(v) AS (VALUES (4),(5),(6))    SELECT       -- |A1 x A2|      (SELECT COUNT(*) FROM a1, a2) * 1.0       /       -- |K1 x K2|      (SELECT COUNT(*) FROM k1, k2)       P;  

В какой пропорции при броске выпадает пара {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.

Матрица состояний всех возможных исходов броска двух кубиков.    Всего в сетке 6 x 6 = 36 символов (знаменатель дроби |D|). Полезных символов [O] ровно 2 (числитель |A|).             K2 (Второй кубик) ->           1   2   3   4   5   6         +---+---+---+---+---+---+     1   | . | . | . | . | . | . |     2   | . | . | . | . | . | . |  K1 3   | . | . | . | . | . | . |     4   | . | . | . | . | . | . |     5   | . | . | . | . | X | O | <-- Точка (5,6) прошла фильтр     6   | . | . | . | . | O | X | <-- Точка (6,5) прошла фильтр         +---+---+---+---+---+---+                           ^   ^                Исключены по 'k1.v != k2.v' (Элементы множества B)    +--------+---------------+-------------------------------+  | Символ | Математика    | Условия задачи                |  +--------+---------------+-------------------------------+  | .      | Элемент D\A   | Ложные исходы. Нарушают       |  |        |               | условие `IN (5,6)`.           |  |        |               | (Пример: выпало 2 и 3).       |  +--------+---------------+-------------------------------+  | X      | Элемент B     | Дубликаты. Нарушают условие   |  |        |               | k1.v != k2.v. Это точки       |  |        |               | диагонали: (5,5) и (6,6).     |  +--------+---------------+-------------------------------+  | O      | Элемент       | Нужные исходы. (5,6) и (6,5)  |  |        | (A1 x A2) \ B |                               |  +--------+---------------+-------------------------------+      -- SQL, PostgreSQL      -- Вариант 1  WITH     -- Состояния кубиков (K1, K2)    k1(v) AS (VALUES (1),(2),(3),(4),(5),(6)),    k2(v) AS (VALUES (1),(2),(3),(4),(5),(6)),        -- Исходные подмножества состояний (A1 и A2)    a1(v) AS (VALUES (5),(6)),    a2(v) AS (VALUES (5),(6))    SELECT       -- |(A1 x A2) \ B|      (SELECT COUNT(*) FROM a1, a2 WHERE a1.v != a2.v) * 1.0       /       -- |K1 x K2|      (SELECT COUNT(*) FROM k1, k2)       P;      -- Вариант 2  WITH     k1(v) AS (VALUES (1),(2),(3),(4),(5),(6)),    k2(v) AS (VALUES (1),(2),(3),(4),(5),(6))  SELECT       (SELECT COUNT(*) FROM k1, k2 WHERE k1.v IN (5,6) AND k2.v IN (5,6) AND k1.v != k2.v) * 1.0       /       (SELECT COUNT(*) FROM k1, k2) P;  

В какой вероятностной пропорции при броске трёх кубиков выпадут цифры больше 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.

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

+------------------+-------------------+---------------------------------+  | Ключевое слово   | Объект дискретной | Описание                        |  |                  | математики        |                                 |  +------------------+-------------------+---------------------------------+  | arguments        | Вектор            | Массив реально переданных       |  |                  |                   | функции аргументов. Позволяет   |  |                  |                   | объявлять функцию без перечня   |  |                  |                   | параметров и вызывать ее с любым|  |                  |                   | количеством аргументов.         |  +------------------+-------------------+---------------------------------+  | arguments.length | Мощность вектора  | Размер (количество элементов)   |  |                  | |arguments|       | массива                         |  +------------------+-------------------+---------------------------------+  | arguments.callee | Вершина графа     | Сама исполняемая                |  |                  |                   | в данный момент функция.        |  +------------------+-------------------+---------------------------------+  | arguments.caller | Вершина графа     | Вызвавшая функция               |  |                  |                   | (можно идти по стеку вызов).    |  +------------------+-------------------+---------------------------------+  | apply            | Отображение       | Метод вызова функции, куда      |  |                  | над вектором      | вектор arguments передается     |  |                  |                   | как единый монолитный массив.   |  +------------------+-------------------+---------------------------------+  | call             | Отображение       | Метод вызова функции, где       |  |                  | (компонентная     | элементы вектора arguments      |  |                  | запись)           | перечисляются в параметрах      |  |                  |                   | через запятую (попозиционно).   |  +------------------+-------------------+---------------------------------+  

var f1 = function() { console.log(arguments); } // определение функции    +------------------------------+--------------------------+  | Синтаксическая конструкция   | Результирующий вывод     |  | (Вызов функции)              |                          |  +------------------------------+--------------------------+  | f1()                         | Ничего не выведет        |  +------------------------------+--------------------------+  | f1(1, true, "str", [1,2,3])  | 1, true, "str", [1,2,3]  |  |                              |                          |  +------------------------------+--------------------------+  | f1.apply(null, [4,5,6])      | 4, 5, 6                  |  +------------------------------+--------------------------+  | f1.call(null, 7,8,9)         | 7, 8, 9                  |  +------------------------------+--------------------------+  

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

1 ==  true // true  (true приводится к числу 1)  1 === true // false (типы разные)  

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

typeof 42           // "number"  typeof true         // "boolean"  

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

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

var sum = function(a, b) { return a + b; }; // (1)  function run_action(action) { action(); }  // (2)  function get_greeter() { return function() { console.log("Hi!"); }; } // (3)  

4. 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  

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

var num= 1; // Переменная во внешнем окружении  function createCounter()  {      var count = 0; // Переменная во внешнем окружении        // Захват ссылки      return function() { count+=num; console.log(count); };  }    var counter = createCounter();  counter(); // Выведет: 1  counter(); // Выведет: 2  

var obj = {}, arr = [], f = function() { console.log(this.a); }  obj.a = 50; arr.a = 60; f.a = 70;  f.apply(obj); f.apply(arr); f.apply(f); // выведет: 50,60,70  

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

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

var arr_a = [], arr_b = [];  // Проверить есть ли слоты Array и Object в цепочке прототипов arr_a  arr_a instanceof Array  // true  arr_a instanceof Object // true  // Добавить новую функцию в слот по указателю prototype  Array.prototype.f = function() { console.log('func_f'); };  arr_a.f(); arr_b.f();// выведет: func_f func_f  

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

console.log(JSON.stringify({a:[1,2,{b:true,c:[4,5,6]},'str']}));  // выведет: {"a":[1,2,{"b":true,"c":[4,5,6]},"str"]}  

7. Берём стандартом строго подмножество 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].

1. Прочесть документацию главная -> иконка ? и выполнить примеры главная -> examples на https://arborjs.org/halfviz/

2. Получить на С граф на языке Halftone graph_walk_orders.cpp

3. Получить граф на языке Halftone: js_graph_lib.html -> js_graph_lib.js

4. Обойти граф разными обходами: js_graph_lib.html -> js_graph_lib.js

5. Повторить SQL логику: js_sql.html -> js_sql.js

6. Прочесть документацию и js_micro_dsl/SQLike.README.md и выполнить примеры: js_sqlike.html -> js_sqlike.js

7. Построить булеаны boolean.cpp.

ЛИТЕРАТУРА

[1] Исходный код и документация Halftone, Arbor.js, https://arborjs.org/halfviz/ , https://github.com/samizdatco/arbor
[2] https://ru.wikipedia.org/wiki/XPath
[3] https://github.com/myfoundation/OmNom.js
[4] https://github.com/myfoundation/EvolutionaryEngineering/tree/main/book_it_begins/ js_micro_dsl
[5] https://github.com/myfoundation/EvolutionaryEngineering/tree/main/book_it_begins
[6] https://en.wikipedia.org/wiki/Oracle_Database
[7] https://nestor.minsk.by/kg/2005/26/kg52614.html
[8] IDE Code::Blocks, https://www.codeblocks.org/downloads/binaries/
[9] Ungoogled Chromium https://github.com/ungoogled-software/ungoogled-chromium