janatem 25 окт 2019 в 04:55

Краткий путеводитель по математике для иностранцев

25 мин

28K

О чем это

А как можно на четвёртом десятке и с аверсией к алгебре наверстать требуемый материал первых курсов университета?

Безумству храбрых поем мы песню!

Целевой аудиторией Путеводителя являются те, кто внезапно заинтересовался математикой или чувствует потребность повысить свою профессиональную эффективность, но по какой-либо причине не имеет возможности отдать несколько лет своей жизни академическому образованию. Если у вас возникла потребность разобраться, но фундаментальных знаний катастрофически не хватает, и вы чувствуете себя иностранцем в стране математики, где говорят на непонятном языке, попробуйте пройти этот путь в качестве туриста. Весь маршрут представляет собой обзорную экскурсию и рассчитан на несколько дней, максимум две недели. Для сравнения: полный академический курс составляет около пяти лет. Конечной целью предлагаемого маршрута является знакомство с принципами одного узкоспециального раздела — эллиптической криптографии. Однако до конца идти не обязательно, если этот раздел лежит вне сферы ваших интересов или вы столкнулись с серьезными трудностями или опасностями. Но, раз уж вы взяли в руки Путеводитель, всё же постарайтесь дойти хотя бы до конца раздела «Язык формул».

Подобно словарю, этот путеводитель можно использовать и для обратного перевода. Возможно, он пригодится математикам, которые вынуждены контактировать и тесно сотрудничать с нематематиками, постоянно преодолевая пропасть непонимания. Дело это представляется настолько трудным, что строчка Максима Горького в эпиграфе является универсальным ответом обеим сторонам. В любом случае я надеюсь на обратную связь и постараюсь пополнять наши знания о том, почему нас не понимают, и как это можно исправлять.

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

Язык формул

Мне сказали, что каждая включенная в книгу формула вдвое уменьшит число покупателей. Тогда я решил вообще обходиться без формул. Правда, в конце я все-таки написал одно уравнение — знаменитое уравнение Эйнштейна E=mc^2. Надеюсь, оно не отпугнет половину моих потенциальных читателей.
Стивен Хокинг — Краткая история времени

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

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

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

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

Лексический анализ

Я раньше знал, как пишутся буквы, я верил в силу слов.
Крематорий — Последний шанс

Для начала спросите у знакомого программиста, что такое лексер и парсер. Углубляться не надо, достаточно на примерах понять, что такое лексема. Если вы услышите непонятные слова вроде «эль-эр-парсер» или «синтаксическое дерево», незаметно покиньте помещение. Скорее всего, вам уже достаточно, программист больше не нужен. Переварите полученные знания. Затем надо научиться выделять лексемы в настоящих математических текстах. Потренируйтесь на случайно скачанных статьях. Избегайте документов в форматах отличных от pdf, а также текстов, сверстанных сразу на веб-страницах. Впрочем, есть сайты, про которые достоверно известно, что они умеют правильно отображать математические тексты (Википедия и Хабр входят в белый список). Бумажные книги тоже, как правило, годятся. Не пытайтесь извлечь смысл из найденных текстов, тренируйтесь просто парсить формулы.

Буквы

Обычно используются буквы двух алфавитов — латинского и греческого, но иногда встречаются кириллические и еврейские буквы. Бывает, что буквы разных алфавитов совпадают по начертанию. На письме это не вызывает проблем, поскольку две разные буквы с одинаковым начертанием не используются в одном тексте. Однако вы можете столкнуться с насмешками математиков, если, например, прочтете вслух B как «бэ», когда имелась в виду «бета». Будьте к этому психологически готовы, придется терпеть.
Заглавные и строчные буквы обозначают разные объекты. (Кому-то это кажется слишком очевидным, но я считаю нужным проговорить это явно. Мне однажды нужно было изложить суть своей работы коллегам из патентного отдела. Когда я почти дошел до состояния персонажа анекдота «папа, где море?», мне вдруг пришло осознание, что девушки полагают мои обозначения m и М относящимися к одному и тому же объекту. Как только недоразумение было снято, весь процесс, благодаря их профессионализму в своем деле, быстро и решительно завершился полным успехом.)
Одна и та же буква, написанная разными шрифтами, обозначает разные объекты.

Как правило (в алгебре), одна буква является самостоятельной лексемой. Если несколько букв записано подряд, то подразумевается умножение. Например, abc означает произведение a, b и c. Однако есть и исключения. Прежде всего — это наименование многих стандартных функций и других обозначений, которые представляют собой многобуквенную лексему: $\sin, \cos, \min, \max, \sup, \lim$ и т.п. Они обычно изображаются прямым (roman) начертанием, в отличие от других буквенных лексем, которые записываются курсивом. Кроме того, в computer science и в некоторых других областях от этого правила отходят, там последовательность букв обозначает единое слово-лексему. Если в конкретном случае есть хоть малейшие сомнения, обратитесь к специалисту.

Скобки

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

Индексы

Обращайте внимание на верхние и нижние индексы. Это то, что в типографике выглядит как superscript и subscript. Верхний индекс проще: как правило, он обозначает возведение в степень. С нижним чуть сложнее. Его можно понимать двояко:

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

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

Другие символы

Математики — эстеты. Они любят, когда красиво не только содержание, но и форма. Им приятно, когда формулы набраны в хорошей, годной типографике. Кнут изготовил вкусный пряник, который называется $\TeX$ . Возьмите учебник по набору и верстке формул и найдите там таблицы символов. Сейчас вам важно, как эти символы классифицированы: буквы, операторы, знаки отношений, стрелки… Не вникая в математический смысл символов, попробуйте понять, как синтаксически используются символы каждого класса. Например, есть класс бинарных операций, для которых справа и слева на равном удалении от символа операции должны стоять какие-то подвыражения.

Цифры

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

Соглашения об обозначениях

Пусть a, b, c, d, e, f — вещественные числа, где e не обязательно равно основанию натуральных логарифмов, хотя может и совпадать с ним.

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

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

Синтаксический анализ

Выражения

Вам, скорее всего, приходилось слышать термин «дерево» не в ботаническом, а в математическом смысле. Это довольно простая штука, при необходимости освежите свои познания. Так вот, математическое выражение имеет структуру дерева. Это значит, что выражение состоит из подвыражений, которые состоят из подвыражений… Но процесс этот не бесконечный, а заканчивается тем, что какие-то подвыражения состоят из лексем.

Некоторые лексемы сами являются элементарными выражениями. Например, числа (точнее, числовые литералы) и переменные. А некоторые требуют, чтобы к ним в определенных позициях были дописаны аргументы, то есть какие-то подвыражения. Тогда они образуют более крупное выражение. Например, символ операции сложения требует, чтобы справа и слева от него были выражения. Можно сказать, что лексема имеет некоторую арность или, если вам больше нравится химия, валентность, — это то, сколько именно и в какие места нужно дописать к лексеме подвыражений, чтобы образовалось выражение. Для операции + арность можно описать так: $\cdot+\cdot$

Немного рекурсии…

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

Эта запись в точности означает, что лексема + требует, чтобы слева и справа от нее были аргументы. Разные лексемы требуют разного количества аргументов, кроме того, местоположение аргументов не ограничивается «справа» и «слева», а может быть, например, «сверху», «снизу», «справа-снизу». Также существуют составные лексемы, которые издавна существовали, но специальное название миксфиксы получили по мере развития языков программирования. Например, скалярное произведение векторов обозначается так: $\langle\cdot,\cdot\rangle$ .

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

Переменные

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

Параметр. Это переменная, про которую сказано, что она чем-то означена, но не сказано, чем именно. Если вам это показалось странным, можете пока пропустить, а когда встретитесь с параметрами, сразу всё поймете на примерах.
Свободная переменная. Если в выражении встретилась переменная, про которую ничего не сказано, то такую переменную называют свободной. Строго говоря, совсем ничего не сказать нельзя. Вы вправе спросить автора формулы, из какого множества берется свободная переменная в ней. Не стесняйтесь спрашивать, это полезно: даже если пояснения окажутся непонятными, к вам будут чуточку серьезней относиться.
Связанная переменная. Если вам не нравится либертинаж свободных переменных, есть несколько способов ограничить их свободу. Можно дописать кое-что к выражению, так что получится новое выражение, в котором ранее свободная переменная окажется запертой. И новое выражение, в отличие от старого, уже не будет зависеть от этой переменной. Если вам любопытно, что это за «кое-что», сходите посмотреть на кванторы или на определенный интеграл. Постарайтесь смотреть только на синтаксис, не углубляясь в смысл, а то, знаете ли, затягивает.

Контекст

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

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

Кстати…

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

Символ равенства

Символ равенства очень важен. Он употребляется в разных смыслах, и нужно уметь их различать.

Означивание переменной значением. Это когда слева стоит переменная, а справа — выражение. В некоторых дисциплинах в таких случаях вместо = пишут := или даже ::= .
Тождество. Слева и справа стоят какие-то выражения, и написавший это утверждает, что оба выражения равны между собой. Также здесь употребляют символ $\equiv$ . Вы сейчас задумались над тем, что означает «равны»? Это заслуживает обсуждения, но может увести вас далеко от маршрута.
Уравнение. Это способ описания принципиально новых сущностей. Математики делают это так: берут несколько свободных переменных, строят над ними выражения и загоняют их в уравнение или даже в систему из нескольких уравнений, чтоб им еще теснее было. А потом смотрят, как эти несчастные переменные мечутся в ограничениях, образуя причудливые множества. И эти множества потом с большим интересом изучают. (Кстати, ваш маршрут проходит по территории теории множеств, вам предстоит познакомиться с ними поближе.) Описать полученное множество — значит решить уравнение. Детям в школе обычно дают уравнения, которые порождают совсем простые множества из одного элемента, иногда из двух или ни одного. Но взрослые ученые в этом деле — большие затейники. А некоторые физики одним уравнением умеют целую вселенную породить.

Извлечение смысла из формул

Что-то написано, а в скобках ОН. Попробовали — и правда, ОН.

Мозг математика по физическим характеристикам принципиально не отличается от мозга типичного представителя интеллектуального большинства. Даже по объему памяти и скорости вычислений разница не так уж велика. Как же математикам удается разбираться в громоздких формулах и понимать их?

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

Even the identity matrix doesn't work normally
Как видите, математики иногда сами не понимают до конца всего смысла, содержащегося в формулах. Но это не мешаем им заниматься преобразованиями и делать корректные суждения.

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

Психологические аспекты

Ротор поля наподобие дивергенции градуирует себя вдоль спина и там, внутре, обращает материю вопроса в спиритуальные электрические вихри, из коих и возникает синекдоха отвечания…
Аркадий и Борис Стругацкие — Сказка о Тройке

То есть XOR в мультипликативной группе точек на кривой будет умножением на скаляр, фактически?

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

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

Хотя математика в целом является гендерно-нейтральной дисциплиной, в данном случае может проявиться синдром леди в поле from. Если ваш пол женский, то, скорее всего, проблема, изложенная в этом разделе, вас коснется в меньшей степени. Однако не обольщайтесь, не пренебрегайте психологической подготовкой.

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

Кто все эти люди?

Бета-тестеры Путеводителя высказали замечание, что Смешариков знают далеко не все. Исправляюсь и даю справку по упомянутым психотипам: Крош — коммуникабельный жизнерадостный оптимист, Лосяш — ученый и популяризатор науки, Пин — механик, сумрачный гений, Ежик — юный ботан.

Разделы математики

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

Если вы увлекаетесь троллингом, попробуйте на профильном форуме набросить тезис о том, что такое-то понятие относится или не относится к такому-то разделу математики. Или что такая-то дисциплина (привет, computer science) является или не является разделом математики. Генерация еды не гарантируется, но шансы есть.

Арифметика

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

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

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

В комплекте с логарифмом идет экспонента, она же показательная функция. Помедитируйте над выражением $inline$ . Вспомните про контекст: если a — переменная, b — параметр, то это степенная функция, если наоборот, то показательная. Посмотрите на графики: степенная функция крута, а экспонента круче.

(*)

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

Загляните в учебник, не трогайте специалистов понапрасну.

Теория множеств

Здесь прежде всего нужно ознакомиться с понятием множества. Тщательно изучите понятия «принадлежит», «не принадлежит» и «является подмножеством», запомните соответствующие обозначения. Текста там мало, и он довольно прост, но важно добиться полного понимания. Проверьте, совпадают ли ваши интуитивные ощущения с определениями. Также важно разобраться с основами, оставаясь в песочнице конечных множеств, ибо за ее пределами вас ждут одни неприятности. Но, раз они ждут, всё же стоит сходить на кратенькую экскурсию и оглядеть окрестности. Благо эта территория размечена поколениями исследователей, и опасные места помечены и огорожены. Прежде всего издали полюбуйтесь на далекую светящуюся бабочку. Вот такую: $\infty$ . Не пытайтесь подойти близко, это невозможно — всё равно что пройти под радугой. Выберите проводника из местных и следуйте его указаниям. Внимание: за пределами песочницы ничего руками не трогать! Не откалывать и не собирать куски породы! Если видите что-то интересное, спросите проводника, быть может он сочтет данный объект достаточно безопасным и разрешит его потрогать. Ниже — неполный перечень объектов, заслуживающих внимания.

Множество всех множеств. Огорожено. Не путайте с совершенно легальным множеством всех подмножеств.
Аллея ординалов. Сопоставьте конечные ординалы натуральным числам. Всё настолько просто, не правда ли? Но не ходите дальше омега-квадрат.
Гряда кардиналов. Потрогайте несколько конечных кардиналов, они не очень мощные и опасности не представляют. Издали посмотрите на алеф-ноль, потом можете рассказать друзьям, что лично видели у математиков букву, которая не латинская и не греческая.
Могила Георга Кантора. Здесь уместно отхлебнуть из фляжки за упокой души. Угостите проводника, и он с удовольствие расскажет кул-стори про какой-нибудь парадокс наивной теории множеств.
Развилка со множеством тропинок, отмеченная указателем «аксиома выбора». Не ходите дальше, даже если проводник будет настаивать. Все тропинки после развилки ведут туда, где отсечена часть реальности. Хотя большинство математиков обитает именно там, у вас пока нет веских причин вводить такие самоограничения.
Континентальный разлом, через который видны основания математики. Если жизнь и рассудок дороги вам, держитесь подальше от этого места. Если ваш проводник настойчиво зовет вас туда, вы имеете дело с неадекватом, немедленно возвращайтесь домой.

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

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

Еще раз про обозначения

как трудно жить среди занудов,
сказал трехлетний Михаил
среди зануд
поправил Игорь, тридцатилетний и в очках

Абелевы группы -> линейное пространство -> операторы -> функционал в линейном пространстве. Зато после докачивания этой ветки можно триггериться на слово «функционал» в описании функциональности ПО.

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

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

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

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

Логика

Вам предстоит работать почти исключительно с конечными объектами. Это значит, что ваши интуитивные представления о логике, скорее всего, достаточны и, главное, не приведут к противоречиям. На всякий случай прочитайте про modus ponens, даже если название вам не знакомо, суть-то вы точно знаете.

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

$\int e^x = f(u_n)$

Это высказывание не истинно и не ложно, оно бессмысленно (по крайней мере с точки зрения математики), потому что написанное слева от знака равенства не является выражением. Можно дописать dx к интегралу, но и тогда останется несколько свободных переменных, из-за которых выражение не является высказыванием. Придется их чем-нибудь означить или сделать связанными, чтобы можно было говорить об истинности.

Хорошо, давайте рассматривать только осмысленные высказывания. Уж они-то должны быть либо истинными, либо ложными? Оказывается, нет. Некоторые высказывания невозможно ни доказать, ни опровергнуть, они называются неразрешимыми. На вашем пути вряд ли встретятся неразрешимые высказывания. Однако наверняка попадутся такие, об истинности которых пока никто из ныне живущих людей не знает.

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

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

— Дезоксирибонуклеиновая, — сказал я. — Это такая кислота. Дезоксирибонуклеиновая.
Он, жалко улыбаясь, поправил пенсне.
— Кислота, — повторил он перехваченным голосом. — А зачем она такая?
— Иначе ее никак не назовешь, — сочувственно сказал я. — Разве что сокращенно — ДНК. Да, вы это пропустите, Федя, читайте дальше.
— Да-да, — сказал он. — Я лучше пропущу.
Аркадий и Борис Стругацкие — Сказка о Тройке

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

Классы смежности. Это один из способов конструирования новых структур из имеющихся. Прочитайте определение, посмотрите несколько примеров. Если непонятно, можно пропустить. Но если всё-таки проникнитесь, то получите некоторый бонус к пониманию других вещей. Например, о кольце $\mathbb{Z}_n$ (эта штука чуть позже понадобится) удобней думать как о классе вычетов, а не как о результате операции взятия остатка от деления. Также школьное определение вектора как отрезка со стрелочкой покажется вам смешным и даже неправильным. Сможете поучать друзей, что вектор — это не отрезок, а класс отрезков.
Морфизмы. Морфизм — это некоторое отношение между парой объектов. Один такой вид морфизмов вы знаете примерно с трехлетнего возраста — это биекция между конечными множествами. Прочитайте определение изоморфизма и осознайте, что это более общий случай биекции. Добейтесь хорошего понимания, это важно. При необходимости проконсультируйтесь со специалистом. Дальше можно почитать про гомоморфизм (не путать с гомеоморфизмом!). Если возникнет гомоморфизмофобия или иные затруднения, можно пропустить.

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

Алгебра

Честное слово, я и не подозревал, что вот уже более сорока лет говорю прозой.
Жан-Батист Мольер — Мещанин во дворянстве

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

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

Внимание! Избегайте тех мест, где явно говорится о структурах с бесконечным носителем. Некоторые такие бесконечные объекты нам всё же понадобятся, но они вам хорошо знакомы. А именно: кольцо целых чисел $\mathbb{Z}$ , поле рациональных чисел $\mathbb{Q}$ и поле вещественных чисел $\mathbb{R}$ . Поиграйте с ними, вспомните школьные правила вроде «от перемены мест слагаемых сумма не меняется» и обоснуйте ими тот факт, что эти структуры действительно являются кольцами/полями. Объясните, почему целые числа не образуют поле.

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

Если геометрия нравится вам больше алгебры, можете сходить посмотреть на эллиптические кривые над полем $\mathbb{R}$ . Но учтите, что, несмотря на название, эти наглядные объекты лежат совсем в стороне от вашего пути.

Ради интереса можете помедитировать также над определениями других алгебраических структур: алгебра (да, алгебра — это такая алгебраическая структура; не пугайтесь, это не рекурсия, а всего лишь омонимия), векторное (линейное) пространство…

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

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

Теория информации

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

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

Теория вероятностей

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

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

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

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

Теория вычислимости

Нельзя ли сделать так, чтобы этот компилятор всегда предупреждал о том, что программа может зациклиться?

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

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

Теория сложности вычислений

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

Математический анализ

Я не бота́н, просто я люблю матан.

Прочитайте определение предела последовательности (предел функции вам не нужен). Все выражения вида «такое-то пространство» заменяйте на «множество вещественных чисел», математики любят обобщать, а вам это не нужно. Убедитесь, что вы способны парсить выражения, в которых есть слово $\lim$ . Скорее всего, у вас возникнут затруднения, это нормально. Поверьте, понятие предела очень интуитивно, вам нужно лишь простимулировать соответствующую часть вашей интуиции. Попросите специалиста прокомментировать текст определения. Рисуйте графики, поиграйтесь с несложными последовательностями. Если время позволяет, сходите на экскурсию посмотреть на второй замечательный предел.

Даже если у вас не возникло полного понимания предела, можно сразу переходить к О-нотации. Вам нужно только «О» большое, но в нагрузку идут «о» малое и всякие теты и омеги. Не перенапрягайтесь, для начала вам достаточно примерно понимать, что из себя представляют $O(1), O(N), O(\log N)$ . Узнайте, а лучше попробуйте догадаться сами, почему у $O(\log N)$ просто логарифм, а не логарифм по какому-то основанию. Потом отдохните немного и подержите в руках $inline$ и $inline$ . Посмотрите на $inline$ (помните о контексте: здесь N — переменная, k — параметр). Подумайте, почему здесь говорят о полиномиальном росте, когда $inline$ — всего лишь моном, то есть частный случай полинома, а полноценных полиномов под «О» большое не засовывают. (Даже если вы не владеете латынью, наверняка уже догадались, что полином — это то же самое, что многочлен, а моном — одночлен.) Подсказка: причина очень похожа на ту, по которой «просто логарифм», а не «логарифм по какому-то основанию». Обратитесь к специалисту, чтобы прояснить эти вопросы. Научитесь сравнивать эти «О» между собой.

Внимание: о-нотация — редкий пример, когда математические обозначения неконсистентны. В записи $inline$ используется знак равенства, в то время как подразумевается нечто иное, а именно: «функция $inline$ принадлежит к классу $inline$ ». То есть следовало бы использовать асимметричный знак $\in$ , но такова традиция. Что ж, теперь вы видите, что математики небезгрешны. Возможно, вам станет немного легче от осознания этого факта.

Теория сложности вычислений — продолжение

Логарифм — функция, в принципе, ограниченная.

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

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

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

Если у вас возник вопрос, почему односторонние функции вообще могут существовать, остановитесь. Не торопитесь, подумайте еще раз. Задумайтесь о своей карьере, пересмотрите принятые ранее решения. Может быть вам следует пойти по стопам Лосяша?

Криповая криптография

Две совершенно одинаковые черные дорожки поуже уходили в бесцветную дымку вправо и влево под углом в две трети «пи». Причем поперек правой дорожки было большими белыми буквами написано «Для умных», а поперек левой — «Для не слишком». <…> Дорога для умных оказалась на удивление короткой. <...> За дверью была все та же знакомая комната. В знакомом кресле храпел во все завертки знакомый дедушка, на знакомом телевизоре валялся знакомый кот Мурзила, со знакомой кровати свешивалось знакомое одеяло.
Аркадий и Борис Стругацкие — Повесть о дружбе и недружбе

Вы дошли до подножия вершины, именуемой эллиптическая криптография. Поздравляю! Перед штурмом отдохните, отделайтесь от рутины, запланируйте оптимальное для вас время суток (например, утро, если вы жаворонок). Еще раз подумайте, нужно ли идти дальше. Вы уже получили ценную ачивку и можете более-менее нормально общаться с математиками на их темы на их языке. Сейчас удобный момент, когда можно вернуться домой без травматического опыта. Решимость идти дальше не покинула вас? Хорошо. А кстати, может быть Лосяшу одиноко без вас?

А дальше?

Здесь хотелось бы написать «продолжение следует», но, в соответствии с принципом Парето, этот раздел потребовал бы 80% усилий читателя, а давал бы лишь 20% пользы. Да и для автора это было бы 80% труда.

Благодарности

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

Теги:

Хабы: