Юмор в программировании: P, NP и машины Тьюринга

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

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

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

    А иногда люди придумывают вещи, сильно оторванные от реальности — типа недетерминированной машины Тьюринга и вопрос — зачем? :-)



    Поможет ли теория?


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

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

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

    Когда-то давно ты восхищался картинками, подобными этой из теории алгоритмов:

    Она завораживала — прогрессивная наука! Черт, научившись решать NP-complete задачку, к ней можно будет свести другие трудные задачки и найти более быстрые алгоритмы! Круто. А если «P=NP», то можно найти полиномиальный алгоритм к переборным и другим космическим задачам и криптография рухнет к чертям.

    Однако со временем все понимается на интуитивном уровне и выражается простыми словами. Почему нас грузили сложными терминами, если можно было объяснить проще? Кто еще не в теме, напомню, что задачи могут быть решены за полиномиальное время «P» на обычной машине Тьюринга (полином помните, квадраты, кубы в сумме могут быть) и, простите за «бред», за полиномиальное время на недетерминированной машине Тьюринга «NP» :-) т.е. если уметь одновременно перебирать все варианты (а это никто не умеет пока и квантовые компьютеры тоже).

    Вспомним сразу, что машина Тьюринга это грубо старый добрый арифмометр:


    И кто-то может наивно верить в возможности квантовых компьютеров — а вдруг они смогут решать NP-задачки лучше (хотя известно, что не все там хорошо, как ожидалось). Но постепенно становится одновременно и страшно и смешно от классики. Расскажите эксперту по производительности или просто хайлоадному разработчику про полином — да он за одно квадратичное время в коде готов пойти на преступление :-)


    Как вообще можно серьезно относиться к возможности выполнять множество задач бесконечно параллельно? Да, MapReduce немного подвинулся в этом направлении, есть Apache Storm, есть с натяжкой Apache Spark — но им очень далеко до идеи недетерминированной машины Тьюринга. Это хорошо заметно, когда данных терабайты и алгоритмы в лоб тупо не работают за разумное время, взять ту же кластеризацию K-means на миллионе сущностей и кластер нам уже слабо поможет.

    NP-hard и зацикливание



    Когда и перебор на «несуществующей параллельной машине» не помогает, проблема становится NP-hard (это неточное определение, но интуитивно понятное). Самое забавное, что, внимание, задача определения зависнет ли программа или нет — является NP-hard.

    Когда первый раз узнаешь про это — уже не до смеха. Люди, слышите? Да программист каждый день решает такие задачи, когда отлаживает код! :-) Куда ушла наука, как же она оторвалась от реальности.

    Машинное обучение



    Да тут тоже весело. С бородатым тервером, логистической регрессией, байесовским классификатором, машинами опорных векторов более-менее разобрались, научились, работают неплохо, да и в реализации не особо сложны. Есть еще модели Маркова с алгоритмами в придачу, но они просты и понятны как трусы за рубль двадцать. А вот с нейронными сетями детективная история получилась… Мало кто хорошо понимает как их правильно обучать в разумное время и как они потом принимают решения. И они регулярно становятся модными и… немодными. Очередная мода — DeepLearning с хитом сезона sequence learning on LSTM. И тут еще Google подогрел ситуацию с TensorFlow, хотя Torch и Theano ничем не хуже и давно всем известны.

    Понятно думаю, для чего применяется машинное обучение. Типичный пример: когда по причине сложности предметной области очень трудно аналитически сформировать набор правил для решения задачи — создается искусственный робот-математик, который тыкается «мордой» в данные до тех пор, пока не научится работать лучше, чем стандартные алгоритмы. Не нужно далеко ходить: половина алгоритмов из Natural Language Processing — машинное обучение, т.к. ну не описывается язык людей формально хорошо, особенно наш, русский.

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

    Функциональное программирование



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

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

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

    Haskell конечно умен, да, но, к сожалению, из разряда высшего космоса и недетерминированных арифмометров.

    Практика



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

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

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

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

    Что нам поможет в этом нелегком пути, коллеги? Конечно, хорошее настроение, позитивный коллектив, атмосфера творчества и умение как выкладываться на работе на полную катушку, так и качественно отдыхать. И помним, нужно быть фанатом кода, любить программную инженерию, жить ей — и тогда нам любые NP-hard и NP-very very hard задачки по плечу!

    P.S.



    А php7 и правда хорош! И без jit обошлось. В 1.5-2 раза быстрее стал и создает нагрузку в 2 раза меньше на железо. Вот и внезапный подарок — спасибо энтузиастам.

    Удачи всем! :-)
    • –12
    • 4.2k
    • 5
    1С-Битрикс
    77.83
    Company
    Share post

    Comments 5

      +8
      TLDR: Топик «про юмор» от 1С-Битрикс. Алгоритмы, машинное обучение, ФП — все это конечно нужно… Но не нам! PHP — наше все!
      И вправду смешно… немножко.
        +7
        Какой-то своеобразный юмор, борюсь с желанием положить под спойлер известную картинку с ничего не понявшим летчиком.
        Вот это — юмор, а тут статья похожа на самооправдание, мол, да не нужны программисту всякие заумные концепции, а то ведь на PHP надо жахать уже вот прямо сейчас. И Хаскель космосом обозвали, и по ФП прошлись.
        «Все, что я не понимаю — не нужно» — это не юмор, это грустно.
          +4
          > Чем мы занимаемся большую часть времени? Пишем код — прикладываем математику к реальности, крутим алгебру конструкциями языка и создаем новое и интересное.

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

            А в целом обожаю статьи из серии «все плохо». Все, действительно, плохо. Уважаю адско.
              +3
              Вопрос детерминированности поведения стохастических алгоритмов построения онтологических моделей в задаче полной категоризации, конечно, интересен, но, «свободная касса!», надо заказ принять и картошку фри из фритюрницы пора доставать.

              У кого какая работа, у того такие и задачи. Для кого-то np-полнота, для кого-то php. Каждому своё.

              Only users with full accounts can post comments. Log in, please.