Pull to refresh
74.18

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

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

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

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

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



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


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

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

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

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

Она завораживала — прогрессивная наука! Черт, научившись решать 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 раза меньше на железо. Вот и внезапный подарок — спасибо энтузиастам.

Удачи всем! :-)
Tags:
Hubs:
-12
Comments 5
Comments Comments 5

Articles

Information

Website
www.bitrix24.ru
Registered
Founded
2012
Employees
201–500 employees
Location
Россия
Representative