[Перевод] Математика, которой я пользуюсь

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

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

Далее, я часто занимаюсь анализом трудоемкости алгоритмов. Размеры наборов данных, подвергаемые обработке в наши дни, просто колоссальны. В 2010 году на конференции Techonomy Эрим Шмидт сказал, что объем данных, создаваемых сегодня человечеством всего за два дня, равен объему всех существовавших в мире данных по состоянию на 2003 год. Мне важно уметь обрабатывать большие сегменты этих объемов и извлекать из них пользу. И в этом смысле понимание пространственно-временной сложности операций, применяемых нами к данным есть ключ к определению того, возможны ли те или иные вычисления в принципе. В отличие от более традиционных видов O-анализа или тета-анализа постоянные множители в таких масштабах оказывают существенное влияние: множитель 2 не меняет асимптотическую временную сложность алгоритма, но потребует увеличения количества процессоров с 10 тыс. до 20 тыс., и такая разница в потреблении ресурсов будет ощутима. В результате вычисления становятся более изощренными. Примеры: могу ли я взять некое линейное вычисление и снизить его в силе до логарифмического? Можно ли снизить потребление памяти в три раза? И так далее.

Часто мне необходимо вычислить наиболее неблагоприятный вариант верхней границы, скажем, размера некоторого набора данных. Во многих случаях такие вычисления могут оказаться нетривиальными. Или же может понадобиться проанализировать какую-нибудь рекуррентную формулу чтобы проверить, как она меняется по мере увеличения глубины рекурсии. Для этого я в числе прочего должен знать основную теорему о рекуррентных соотношениях и как следует понимать принципы анализа числовых рядов. И, возможно, это покажется невероятным, но иногда это означает, что мне надо вычислить интеграл (хотя преимущественно только интегралы Римана). Или могу ли я просто решить рекурсивное соотношение и получить конечное число решений? Придется ли мне прибегнуть к линейной алгебре? Это ведет к таким вещам, как производящие функции, числа Стирлинга, матричные вычисления. Если вам любопытно что входит в набор фундаментальных математических концепций, необходимых для понимания компьютерных наук, обратитесь к первому тому «Искусства программирования» Дональда Кнута, или «Конкретной математике» Кнута, Роналда Грэхема и Орена Паташника.

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

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

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

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

Отличный и подходящий пример — MathJax. Или Gmail. Понимание того, как они работают предполагает некоторый уровень знания символьных вычислений и семантического анализа элементов страниц. Авторам MathJax нужно было написать программу, способную пройти дерево, сгенерированное на основе объектной модели документа, найти математические элементы, «запарсить» их и произвести их динамическую замену новыми отрисованными элементами. Возможно, некоторых пользователей, которые просто видят как это работает, это не очень то и впечатлит, но под капотом там происходят довольно сложные вещи. Мне обычно не приходится делать нечто подобное (не работаю с фронт-эндом), но я все время занимаюсь похожими вещами на Lisp. Обратите внимание, что Lisp был изначально заточен под математическую обработку символьной информации: его макросы целиком и полностью охватывают вопросы обработки символьных выражений.

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

Я много работаю со статистическим анализом данных, не только для определения характеристик производительности, но также и понимания данных как таковых. Вдобавок поиску в упомянутом выше DOM-дерева семантических метаданных (например, микроданных и микроформатов, RDF, других XML-данных с некой определенной схемой), я также пытаюсь осмыслить неструктурированные данные. Какова вероятность, что этот текст представляет собой адрес улицы? Или что это графические координаты? В каком контексте он появляется? Спам ли это? Есть ли в нем вообще смысл? Выглядит ли он как результат работы генератора текста на основе цепей Маркова? Быть может это серия цитат из какого-либо хорошо известного литературного произведения? Или фрагмент литературной дискуссии? Или быть может это дискуссия о спаме, содержащая литературные фрагмент? Я до сих пор усмехаюсь всякий раз когда вспоминаю о спам-письме с рекламой препаратов, завернутую в фрагмент из «Мастера и Маргариты» Булгакова.

Теория категорий. Типы в компьютерных языках программирования грубо соответствуют категориям, а монады и функторы могут быть использованы для серьезного и изящного упрощения некоторых конструкций. К примеру, в функциональном языке программирования Haskell монады применяются для ввода-вывода и для моделирования состояния. Имея дело с упрощенными программами проще сделать так, чтобы они работали. О них легче рассуждать, их проще понять, изменить и так далее. Типы часто могут быть определены на основе логических рассуждений, что приводит к появлению частных случаев (которые также могут быть использованы в общих задачах рассуждения). Подумайте что будет, если использовать выводы для применения логических функций, подобных тем, что используются в prolog, для преобразования графов в распределенных системах.

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

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

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

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

Если мне необходимо написать свой алгоритм рекурсивного спуска для какой-нибудь необычной грамматики и он не может соответствовать LALR(1) (поэтому я не могу просто воспользоваться yacc или bison), мне нужно быть осторожным или поддерживать стек состояния отдельно от процедурной рекурсии. Это понимание также необходимо, если я обхожу DOM-дерево (или любую рекурсивно-определенную структуру данных). Некоторые языки программирования считают это трудностью в работе программиста и обходят ее путем использования сегментированных стеков. Конечно же, было бы здорово, если бы я мог определить свой сборник некоторых анализируемых ресурсов в виде функции (в математическом смысле). И как же было бы здорово, если бы это сводилось всего лишь к какой-нибудь задаче оптимизации линейного программирования?

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

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

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