April 13, 2016 at 12:39Humor in programming: P, NP and Turing machines
What do we do most of the time? We write the code - we apply mathematics to reality, we twist the algebra with language constructions and create a new and interesting one.
But for some reason we often forget that by the laws of the relations of numbers to each other and the algorithms studied, the world does not end and the reality is much more complex and multifaceted. This is especially noticeable in the face of fuzzy requirements, tight deadlines and a changing market.
We forget that while scientists once again made a noise around neural networks and try to learn them, we daily learn our internal recurrent neuron (brain) at speeds close to light - debugging a program or corny fixing bugs.
And sometimes people come up with things far divorced from reality - such as a non - deterministic Turing machineand the question is why? :-)
Any silicon general is an experienced programmer, knows well that it is never at first clear what they are going to code. And the smarter the developer, the more he sees ambiguities and muddy spots. And often there is more politics than engineering, especially from the management side - to do it yesterday, I don’t know what, but the client should be satisfied.
And the theoretical knowledge of algorithms and their complexity, problem classes, excellent, beloved, but ... "toy", although scientific - fade into the background. In the foreground - a premonition of the development of architecture, the choice of the necessary and reliable libraries, people, the atmosphere, iron.
In the first place - to be able to stop in time, not to get carried away with code and beauty. Stop and release as soon as possible until the market is ready!
Once upon a time you admired pictures like this onetheory of algorithms :
She was fascinated - a progressive science! Damn, having learned how to solve an NP-complete problem, it will be possible to reduce other difficult problems to it and find faster algorithms! Cool. And if “P = NP”, then you can find a polynomial algorithm for brute force and other space problems and cryptography will collapse to hell.
However, over time, everything is understood on an intuitive level and is expressed in simple words. Why were we loaded with complex terms, if it could be explained more simply? Who else is not in the topic, I remind you that tasks can be solved in polynomial time “P” on a regular Turing machine (remember polynomial, squares, cubes in total can be) and, sorry for “nonsense”, for polynomial time on a non-deterministic Turing machine"NP" :-) i.e. if you can simultaneously sort through all the options (and nobody knows how to do this yet, and quantum computers too).
We recall right away that the Turing machine is a crude old kind of arithmometer:
And someone can naively believe in the capabilities of quantum computers - what if they can solve NP problems better (although it is known that not everything is good there, as expected). But gradually it becomes both scary and funny from the classics. Tell the performance expert or just the hi-loader developer about the polynomial - yes, he is ready to commit a crime in one quadratic time in the code :-)
How can you really take seriously the ability to perform many tasks endlessly in parallel? Yes, MapReduce has moved a bit in this direction, there is Apache Storm, there is a stretch of Apache Spark - but they are very far from the idea of a non-deterministic Turing machine. This is clearly noticeable when these terabytes and algorithms do not work bluntly in a reasonable amount of time, taking the same K-means clustering on a million entities and the cluster will already help us a little.
When the search on a "non-existent parallel machine" does not help, the problem becomes NP-hard (this is an inaccurate definition, but intuitive). The funny thing is that, attention, the task of determining whether a program freezes or not is NP-hard .
The first time you find out about it, it’s no laughing matter. People, hear? Yes, a programmer solves such problems every day when he debugs the code! :-) Where did science go, how did it break away from reality.
Yes, it's fun too. With a bearded terver , logistic regression, Bayesian classifier, support vector machines more or less understood, learned, work well, and are not particularly difficult to implement. There are Markov models with algorithms in addition, but they are simple and understandable as underpants for twenty rubles. But with the neural networks, the detective story turned out ... Few people well understand how to properly train them in a reasonable time and how they then make decisions. And they regularly become fashionable and ... unfashionable . Another mod is DeepLearning with the hit of the season sequence learning on LSTM . And then Google warmed up the situation with TensorFlow , although Torch and Theano are no worse and have long been known to everyone.
I clearly understand what machine learning is used for. A typical example: when, due to the complexity of the subject area, it is very difficult to analytically form a set of rules for solving the problem, an artificial robot mathematician is created that pokes his face in the data until he learns to work better than standard algorithms. No need to go far: half of the algorithms from Natural Language Processing are machine learning, as Well, the language of people is not described formally well, especially ours, Russian.
Yes, recurrent neurons have recently made a breakthrough and have shown undeniably better results in recognizing speech, images, and a bit in NLP , for example, in machine translation. Yes, there is a hope that we will teach neural networks to choose the important attributes for training, as while looking at the unscientific medieval numerological hardcore that is going on at kaggle.com is impossible without tears. It’s sincerely a pity to waste time studying the methods of unscientific poking by hard competition.
Yes, that all worked out with him. This is one of the convenient designs - sometimes convenient, yes. But even Scala does not abolish the good old OOP practice and presents lambdas only as an addition.
The basis remains objects. Structuring his thoughts in essence and methods, hiding the implementation - the developer is able to reach victory, realize his plan. And when there are a lot of people, OOP helps you not step on your feet. If there were no tools for managing complexity and structuring, we would be confused in our own code and thoughts. Therefore, we breathe deeply.
And Straustrup - well done, was able to create a language both fast and applicable for large programs. And java is not bad. And no one can catch dynamic languages in flexibility so far.
Haskell certainly smart, yes, but, unfortunately, from the category of higher cosmos and non-deterministic arithmometers.
In general, it is clearly seen that in practice, a programmer almost daily has to solve hellish NP-hard tasks when debugging idle code, fixing bugs, specifying constantly changing requirements, refactoring and choosing an architecture and libraries.
And managers solve even greater complex algorithmic problems - creating a creative atmosphere in the team, buying cookies and motivating employees.
While scientists are looking for ways to effectively train recurrent neural networks for pattern recognition, the programmer pumps his more complex neuron (brain) every day at speeds close to the speed of light and does not notice it.
And the theoretical knowledge of languages, algorithms, operating systems - is broken up into harsh reality, where you need to know a lot from different areas, constantly weigh and evaluate risks and make the right decisions. And no one will ever give time to bring the task to perfection! Never.
What will help us in this difficult way, colleagues? Of course, a good mood, a positive team, an atmosphere of creativity and the ability both to give all the best to work and to have a good rest. And remember, you need to be a fan of code, love software engineering, live it - and then we can handle any NP-hard and NP-very very hard tasks!
And php7 is really good! And there were no jit . It became 1.5-2 times faster and creates a load of 2 times less on iron. Here is a surprise gift - thanks to the enthusiasts.
Good luck everyone! :-)
But for some reason we often forget that by the laws of the relations of numbers to each other and the algorithms studied, the world does not end and the reality is much more complex and multifaceted. This is especially noticeable in the face of fuzzy requirements, tight deadlines and a changing market.
We forget that while scientists once again made a noise around neural networks and try to learn them, we daily learn our internal recurrent neuron (brain) at speeds close to light - debugging a program or corny fixing bugs.
And sometimes people come up with things far divorced from reality - such as a non - deterministic Turing machineand the question is why? :-)
Will the theory help?
Any silicon general is an experienced programmer, knows well that it is never at first clear what they are going to code. And the smarter the developer, the more he sees ambiguities and muddy spots. And often there is more politics than engineering, especially from the management side - to do it yesterday, I don’t know what, but the client should be satisfied.
And the theoretical knowledge of algorithms and their complexity, problem classes, excellent, beloved, but ... "toy", although scientific - fade into the background. In the foreground - a premonition of the development of architecture, the choice of the necessary and reliable libraries, people, the atmosphere, iron.
In the first place - to be able to stop in time, not to get carried away with code and beauty. Stop and release as soon as possible until the market is ready!
Once upon a time you admired pictures like this onetheory of algorithms :
She was fascinated - a progressive science! Damn, having learned how to solve an NP-complete problem, it will be possible to reduce other difficult problems to it and find faster algorithms! Cool. And if “P = NP”, then you can find a polynomial algorithm for brute force and other space problems and cryptography will collapse to hell.
However, over time, everything is understood on an intuitive level and is expressed in simple words. Why were we loaded with complex terms, if it could be explained more simply? Who else is not in the topic, I remind you that tasks can be solved in polynomial time “P” on a regular Turing machine (remember polynomial, squares, cubes in total can be) and, sorry for “nonsense”, for polynomial time on a non-deterministic Turing machine"NP" :-) i.e. if you can simultaneously sort through all the options (and nobody knows how to do this yet, and quantum computers too).
We recall right away that the Turing machine is a crude old kind of arithmometer:
And someone can naively believe in the capabilities of quantum computers - what if they can solve NP problems better (although it is known that not everything is good there, as expected). But gradually it becomes both scary and funny from the classics. Tell the performance expert or just the hi-loader developer about the polynomial - yes, he is ready to commit a crime in one quadratic time in the code :-)
How can you really take seriously the ability to perform many tasks endlessly in parallel? Yes, MapReduce has moved a bit in this direction, there is Apache Storm, there is a stretch of Apache Spark - but they are very far from the idea of a non-deterministic Turing machine. This is clearly noticeable when these terabytes and algorithms do not work bluntly in a reasonable amount of time, taking the same K-means clustering on a million entities and the cluster will already help us a little.
NP-hard and looping
When the search on a "non-existent parallel machine" does not help, the problem becomes NP-hard (this is an inaccurate definition, but intuitive). The funny thing is that, attention, the task of determining whether a program freezes or not is NP-hard .
The first time you find out about it, it’s no laughing matter. People, hear? Yes, a programmer solves such problems every day when he debugs the code! :-) Where did science go, how did it break away from reality.
Machine learning
Yes, it's fun too. With a bearded terver , logistic regression, Bayesian classifier, support vector machines more or less understood, learned, work well, and are not particularly difficult to implement. There are Markov models with algorithms in addition, but they are simple and understandable as underpants for twenty rubles. But with the neural networks, the detective story turned out ... Few people well understand how to properly train them in a reasonable time and how they then make decisions. And they regularly become fashionable and ... unfashionable . Another mod is DeepLearning with the hit of the season sequence learning on LSTM . And then Google warmed up the situation with TensorFlow , although Torch and Theano are no worse and have long been known to everyone.
I clearly understand what machine learning is used for. A typical example: when, due to the complexity of the subject area, it is very difficult to analytically form a set of rules for solving the problem, an artificial robot mathematician is created that pokes his face in the data until he learns to work better than standard algorithms. No need to go far: half of the algorithms from Natural Language Processing are machine learning, as Well, the language of people is not described formally well, especially ours, Russian.
Yes, recurrent neurons have recently made a breakthrough and have shown undeniably better results in recognizing speech, images, and a bit in NLP , for example, in machine translation. Yes, there is a hope that we will teach neural networks to choose the important attributes for training, as while looking at the unscientific medieval numerological hardcore that is going on at kaggle.com is impossible without tears. It’s sincerely a pity to waste time studying the methods of unscientific poking by hard competition.
Functional programming
Yes, that all worked out with him. This is one of the convenient designs - sometimes convenient, yes. But even Scala does not abolish the good old OOP practice and presents lambdas only as an addition.
The basis remains objects. Structuring his thoughts in essence and methods, hiding the implementation - the developer is able to reach victory, realize his plan. And when there are a lot of people, OOP helps you not step on your feet. If there were no tools for managing complexity and structuring, we would be confused in our own code and thoughts. Therefore, we breathe deeply.
And Straustrup - well done, was able to create a language both fast and applicable for large programs. And java is not bad. And no one can catch dynamic languages in flexibility so far.
Haskell certainly smart, yes, but, unfortunately, from the category of higher cosmos and non-deterministic arithmometers.
Practice
In general, it is clearly seen that in practice, a programmer almost daily has to solve hellish NP-hard tasks when debugging idle code, fixing bugs, specifying constantly changing requirements, refactoring and choosing an architecture and libraries.
And managers solve even greater complex algorithmic problems - creating a creative atmosphere in the team, buying cookies and motivating employees.
While scientists are looking for ways to effectively train recurrent neural networks for pattern recognition, the programmer pumps his more complex neuron (brain) every day at speeds close to the speed of light and does not notice it.
And the theoretical knowledge of languages, algorithms, operating systems - is broken up into harsh reality, where you need to know a lot from different areas, constantly weigh and evaluate risks and make the right decisions. And no one will ever give time to bring the task to perfection! Never.
What will help us in this difficult way, colleagues? Of course, a good mood, a positive team, an atmosphere of creativity and the ability both to give all the best to work and to have a good rest. And remember, you need to be a fan of code, love software engineering, live it - and then we can handle any NP-hard and NP-very very hard tasks!
PS
And php7 is really good! And there were no jit . It became 1.5-2 times faster and creates a load of 2 times less on iron. Here is a surprise gift - thanks to the enthusiasts.
Good luck everyone! :-)