Математика, которой я пользуюсь

http://pub.gajendra.net/2012/10/mathematics_i_use
  • Перевод


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

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

Далее, я часто занимаюсь анализом трудоемкости алгоритмов. Размеры наборов данных, подвергаемые обработке в наши дни, просто колоссальны. В 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-профессионалом не есть то же самое, что быть специалистом в области теории вычислительных систем, и как многие верно замечают, такой специалист гораздо ближе к прикладному математику, нежели к специалисту-ремесленнику. Я ни в коем случае не хочу умалять важность таких профессионалов, поскольку они полезны и пользуются всеобщим уважением, но лишь хочу отметить, что компьютерные науки — это нечто другое.

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

image
Wirex 60,93
Мобильный банкинг нового поколения
Поделиться публикацией
Комментарии 19
    +3

    Бо́ льшая часть перечисленного к математике не относится, или описывается ее простейшими правилами.
    Работаю ИТ специалистом в энергосбытовой компании. Вчасти математики и математического анализа приходилось сталкиваться с прогнозированием потребления миллионника в каждый час на несколько дней вперед, анализом и прогнозированием сбора денег от потребителей и т.п.
    Так например проведение финального футбольного матча чемпионата Росии приводит к росту потребления на 10% в 3-й час после начала матча. Казалась бы ничего, но если это правильно учесть то дополнительная прибыль примерно 17 миллионов рублей.
    Так как тариф для населения жестко регулируется, то затраты на телефонную связь приходится планировать с учетом нормального распределения и прогнозировать методом экстраполяции на основе регрессионного анализа. Это позволяет уложиться в погрешность 2-3 процента.

    +2

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

      0
      Типы в компьютерных языках программирования грубо соответствуют категориям

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

        Многое объясняет…
        Когда у тебя в руках молоток — все выглядит как гвозди.
        1. Да, программисты используют математику хотя бы в булевой алгебре в любом if/do/while/че-там-нынче-модно на уровне первой лабораторки. Но стоит ли говорить о столь очевидных вещах?
        2. Чуть позднее студенты узнают о сложности и P?NP. Кстати, удивительно, что математик/программист упустил этот важный момент. Потому что не так важны конкретные алгоритмы, как понимание в какую сложность ты вляпался (и можно ли с разумным допущением избежать решения задачи рюкзака).
        3. Ну, о том, какой список алгоритмов и предметные области «надо знать» — это уже реально холивар. Бессмысленный и беспощадный.
        Я могу выкинуть многое из этого списка и нарисовать другой список не меньше, и относительно честно считать себя Дартаньяном. Но вот толку…
          –2
          1. Да, программисты используют математику хотя бы в булевой алгебре в любом if/do/while/че-там-нынче-модно на уровне первой лабораторки. Но стоит ли говорить о столь очевидных вещах?

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


          Чуть позднее студенты узнают о сложности и P?NP. Кстати, удивительно, что математик/программист упустил этот важный момент

          Третий абзац сверху — не?


          могу выкинуть многое из этого списка и нарисовать другой список не меньше, и относительно честно считать себя Дартаньяном. Но вот толку…

          Херак, херак и в продакшн. Но вот толку…

          0

          Ещё можно добавить про embedded software, которое взаимодействует с железом и реальным миром. Если идти глубже мигания светодиодом и метеостанции — то можно дойти до real time control systems, где часто пригождается теория автоматического управления, а также вообще вкус к математическому моделированию и числам.

            0

            Вы когда нибудь делали что-то сложнее пид регулятора с нелинейными коэффициентами? И какого-нибудь фильтра Калмана. По моему этим все ограничивается на практике.

              +3

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

            +2
            «В моих условиях работы все перечисленное востребовано, значит оно востребовано в условиях работы любого реального программиста.»
              +1
              Ну он нигде этого не утверждал — в первом и последних абзацах автор как раз подчёркивает, что говорит исключительно о своём опыте.
                0
                Ну так вопрос-то был про среднестатистического программиста.

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

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

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

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

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

                Так сложилось что многие математики думают что программирование без математики невозможно. Да и вообще что угодно в мире. Но реальность показывает что всё совсем не так.
                Достаточно здравого смысла и понимания. А излишне усложненный и формализованный аналог этого здравого смысла записанный через жопу — им не нужен и скорее мешает. Как бы сильно это не нравилось кому-то.

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


                      Звучит как пафосный сценарный монолог из Крепкого орешка 4, так и вспомнилась сразу сцена где он через допотопный смартфон взламывает всю энергосистему США.
                      Зачем эта статья?
                        +1
                        Я знаю много слов… очень умных очень много

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

                        Самое читаемое